Scheme in Short (Finished!)

[Guest]

Wow!

The amount of effort you put into your posts is amazing; I know I certainly appreciate it.

In all honesty, I don't know if I'll ever have any use for Scheme (I have read about it briefly -- and learnt some of it in 'How To Design Programs'), but I will certainly be bookmarking this post should I ever desire to know more about it.

Kudos, sir.
-Guest

[Schol-R-LEA]

It occurs to me that it would be useful to add an actual example of a small Scheme program. This example is one I've posted before, but I thought it would be appropriate here as well. I will probably use the hexdump example in future tutorials, as a conveninet comarison tool. The code is admittedly non-optimal, and really needs more comments than it has, but it should be clear enough. (EDIT: I've simplified the code a little, which should help.)

Code: Select all

(define (dump-file filename width height)
  ;; read in a file and print a dump of it.
  
  ; display a number's ASCII value
  (define (display-char-value x)
    (display (char-value (modulo x 256))))
  
  ; display a character's hex value
  (define (display-hex-value x)
    (let ((hexval (number->string (modulo x 256) 16))) 
      (if (> 2 (string-length hexval))
          (display #\0))
      (display hexval)
      (display #\space)))
  
  ;; display a line of character values
  (define (display-line-values dump)
    (for-each display-char-value dump))
  
  ;; display a line of hex values
  (define (display-line-dump dump)
    (for-each display-hex-value dump))
  
  ;; display a line of hex values followed by 
  ;; a line of character values
  (define (display-line dump width)
    (let* ((size (length dump))
           (diff (- width size)))
      (display-line-dump dump)
      (if (> diff 0)
          (do ((count diff (- count 1)))
            ((<= count 0))
            (display #\space)
            (display #\space)
            (display #\space)
            ))
      (display #\space)
      (display #\:)
      (display #\space)
      (display-line-values dump)
      (newline)
      diff))          
  
  ;; read in a line of data
  (define (read-dump-line src width)
    (let read-data ((count width))
      (if (or (>= 0 count)
              (eof-object? (peek-char src))) 
          '()
          (append (list (char->integer (read-char src))) 
                  (read-data (- count 1))))))
  
  ;; main function
  (if (and (string? filename)
           (> width 0)
           (> height 0))
      (let ((src (open-input-file filename)))
        (if (null? src)
            #f
            (let write-dump ((count height))
              (display-line (read-dump-line src width) width)
              (if (or (<= count 0) 
                      (eof-object? (peek-char src)))
                  (begin
                    (close-input-port src)
                    #t)
                  (write-dump (- count 1))))))
      #f))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; some support functions (usually in a separate file)
(define (hex->char x y)
  ;; converts a character to a hex value
  (integer->char 
   (string->number (string x y) 16)))

(define (char-symbolic? c)
  ;; returns #t if the character is a symbol, #f otherwise )
  (if (not (member c '(#\` #\~ #\! #\@ #\# #\$ #\% #\^ #\& #\* #\( #\)
                        #\- #\_ #\+ #\= #\\ #\| 
                        #\[ #\{ #\] #\} #\; #\: #\' #\" 
                        #\, #\< #\. #\> #\? #\/))) 
      #f
      #t))

(define (char-printable? c)
  ;; returns #t if a character is printable, #f otherwise
  (or (char-alphabetic? c)
      (char-numeric? c)
      (char-symbolic? c)))

(define (char-value x)
  ;; takes a character and returns its integer value
  ;; returns a period if given an invalid value
  (let ((c (integer->char x)))
    (cond ((not (integer? x)) #\.)
          ((char-printable? c) c)
          (else #\.))))

[Schol-R-LEA]

Not to beat a dead horse, but I've attached a new version of the hexdump program. It is now much better commented, and considerably more efficient, than the earlier version. It should be easier to read, as well, as most of it is now considerably simpler. If I ever get around to rewriting the tutorial, this program will probably be the primary example in it. It has ben tested succesfully under Dr Scheeme, Petite Chez Scheme, Bigloo Scheme, and SCM (with one minor modification for the last one); it ran under MIT Scheme but with an odd discrepancy which I'm looking into now. HTH.

[attachment deleted by admin]

[mystran]

Could you give some ideas about the implementation of a compiler/interpreter too?

[Schol-R-LEA]

Could you give some ideas about the implementation of a compiler/interpreter too?

[me=Schol-R-LEA]temporizes umtil on opportunity to do arises[/me]

[chris]

Would you be able to tell me how to get input from the user?

I tryed

Code: Select all

(var (read))

but I don't think that's right. Things are quite odd in Scheme coming from C and Python .

[Schol-R-LEA]

You seem to have the right idea, but you need to use an assignment function - either a (define) or a (let) to define the variable, or a (set!) to change it.

In most cases, you would use the (read) to initialize the variable as part of a (let) block.

Code: Select all

(define (greet)
  (display "Hello! What is your name? ")
  (let ((name (read)))
    (display "Nice to meet you, ")
    (display name)
    name))

You can also use (define), but only at the top level or at the beginning of a function, not in the body of a function. It would be fairly unusual to do that in any case.

Code: Select all

(define password (read))

You would only use (set!) if you are changing a variable that has already been defined. While it can be done with local variables, it is usually avoided; mutators are generally used only with persistent global state.

Code: Select all

(define location null)  ; no default location

(define (get-location!)
  (display "Enter your current location: ")
  (let ((new-location (read)))
    (display "You entered \"")
    (display new-location)
    (display "\". Is that correct? (y/n)? ")
    (if (equal? 'y (read))
        (begin 
          (set! location new-location)
          (display "Location now set to \"")
          (display location)
          (display "\"."))
        (display "Location unchanged."))))

Now you may notice something if you run these: (read) only reads in the first word you type in, and apparently converts it to lower case. Well, what is actually happening is that read is designed to read in an atom, not a string per se; it tries to interpret the stream in Scheme terms. So, if you enter a number, it reads it as a numeric literal; if you enter a character literal (e.g., #\a) it will read it as a char; and if you enclose the values in parens, it reads it as a list. However, if you try to enter a string without enclosing it with double quotes, it interprets the fist value as a symbol and ignores the rest; While this can have advantages, it makes it a pain to work with string data. While Dr Scheme has functions such as (read-line) and (read-string), they are non-standard. Fortunately, it is easy to write a string reading function using (read-char):

Code: Select all

(define (read-str . port)
  (define (read-str-from port)
    (let accumulate-string ((next-char (read-char port)))
      (if (or (eof-object? next-char)
              (equal? next-char #\newline))
          ""
          (string-append (string next-char) (accumulate-string (read-char port))))))
  
  (if (null? port)
      (read-str-from (current-input-port))
      (read-str-from port)))

You can use this to re-write the first function as:

Code: Select all

(define (greet-string)
  (display "Hello! What is your name? ")
  (let ((name (read-str)))
    (display "Nice to meet you, ")
    (display name)
    name))

... which will work more or less correctly now.

I hope I haven't confused things too much

[chris]

Well I made a small program, but my guess is that it's horribly written.

Code: Select all

(define (calc)
  (display "Enter first number: ")
  (let ((num1 (read)))
    (display "Enter second number: ")
    (let ((num2 (read)))
    (display "Enter operation: ")
    (if (equal? '+ (read))
        (display (+ num1 num2))))))

I'm still confused because I don't need to perform something after the (let ((num1 (read)))

[Schol-R-LEA]

Actually, if you check your parens and indentation, you'll see that the code after that line is in the scope of that (let). DrScheme's prettyprint tool (menu item Scheme:Reindent All; this will correct the indentation fo anything in the edit window, but it does not affect the interpreter window) indents it as so:

Code: Select all

(define (calc)
  (display "Enter first number: ")
  (let ((num1 (read)))
    (display "Enter second number: ")
    (let ((num2 (read)))
      (display "Enter operation: ")
      (if (equal? '+ (read))
          (display (+ num1 num2))))))

Which Scheme interpreter are you using? Like most things, each has it's advantages and disadvantages; I like DrScheme's environment, for example, but if I were going to produce a stand-alone executable I would rather use Bigloo or Stalin.

[chris]

I'm using DrScheme on OS X. Btw, is the way I wrote that function correct or would there be a more obvious way to write it?

[Schol-R-LEA]

What you have here seems reasonable to me. There are always other ways to write a program; this one seems about as simple and effective as is possible. It depends also on what you want to do with it, I suppose. Stylistically, it's not bad.

You might want to add is some error checking on the numbers (using the [tt](number?)[/tt] predicate), though. One of the downsided of dynamic typing is that you often have to do type checking at run time. Something like

Code: Select all

 (let ((foo (read)))
    (if (number? foo)
        ; ... your code 
        
        ; the 'else' clause
        (error "Not a valid number.")

On a similar note, you might want to add a error message to that last if clause, in case it isn't a plus sign.

[chris]

It didn't have error checking because it was just some code I used to figure out how to use (read) properly . Thanks for the new code though . Btw, how different is Scheme when compared to Common Lisp? Are there any other popular dialiects?

[kris]

I remember, that MIT has its course on LISP online somewere as a split up vidio. Maybe someone remembers the URL, I don't have it in my bookmarks anymore.

[mystran]

Reading stuff can be actually done in a few ways. The number one cause of confusion is that "read" is a primitive to read a single lisp form (or s-expression) which is a single string (with double quotes), a list, number, character literal (like #\a or #\newline) or whatever the interactive top-level accepts as one thing. So typing into top-level

Code: Select all

> (begin
  (display "What's your name? ")
  (if (symbol? (read))
     (display "That's a symbol!\n")))
What's your name? Mystran
That's a symbol!
> 

Notice that you can write a top-level loop as:

Code: Select all

(defun my-read-eval-print-loop ()
  (print (eval (read)))
  (my-read-eval-print-loop))

So "read" is not simply a reader, put a whole parser. The reason stuff is converted to lower-case is that symbols are (in most implementations) printed as lower-case, why they are truly case-insensitive.

Code: Select all

> (read)
'foobar
(quote foobar)
>

Yup, it's a parser

If you want to read a whole line into a string, you can use "readline":

Code: Select all

> (begin (read-char) (read-line))
foo bar duh
"foo bar duh"
> 

The reasons for the extra (read-char) is simply that MzScheme at least seems to think that I want to start reading the line before the evaluation-triggering first newline, so I have to eat-that first. If you run stuff from a file or something, you can ignore this problem. It's just because the newline after parsed form is not part of the parsed form.

Code: Select all

> (display "foo\n")(display "bar\n")
foo
> bar
>

So it gives a prompt even if there already is more stuff..

Ok, this might be confusing, but play around with the above, and you should get it quite fast.

There are other ways to read stuff, and if you absolutely can't do what you need to do with the built-ins, you can always parse stuff yourself using "read-char" and "peek-char" which return the next character in the input-stream, while "read-char" also removes it from the stream and "peek-char" does not.

There are also "format" functions around, which pretty much act like printf/scanf but unfortunately they aren't part of R5RS, so one needs to get those as extra libraries.

I'd also like to point to two books in the net, Teach yourself Scheme in Fixnum Days which is intended as a scheme tutorial for folks that already know how to program, and Structure and Interpretation of Computer Programs which starts from programming basics, using Scheme, and continues through evaluation models to interpretation, compilation, including stuff like basics of garbage-collection. SICP is definitely a book that everyone should read, if they want to learn basics of programming language implementation.

Both books are completely available in the above URLs.

[chris]

Thanks alot mystran!