341 : 10 Jan 2002 : Intro to Scheme

Evaluation in Scheme

Scheme is expression-oriented---it encourages a style in which programmers think about computing the values of expressions, rather than executing a series statements. In Scheme, all expressions are atoms (numbers, strings, etc.) or lists (parenthesis-surrounded sequences of whitespace-separated expressions).

The heart of expression evaluation in Scheme is extraordinarily simple:

1. Is the expression an atom? If so, return the value of the atom.
2. Is the expression a list? If so:
   1. Is the first element of the list a special form? If so, do the rule for the special form.
   2. Otherwise, evaluate the first element of the list, and apply its (as a function) to the rest of the list.

Hence, consider the following expressions (note that comments in Scheme begin with a semicolon and extend to the end of the line:

  4        ; The literal number four

  +        ; The symbol +.  This symbol is "bound" to the addition
           ; function, so this evaluates to the addition function.

  (+ 1 2 3) ; A list containing +, 1, 2, and 3.  + is not a special form,
            ; so we evaluate it.  This returns the addition function, so
            ; (+ 1 2 3) evaluates to the number 6.

  (define x 5)     ; A list containing define, x, and 5.  define is a
                   ; special form: it binds values to symbols.  Hence,
                   ; this statement binds the result of evaluating 5
                   ; to the symbol x.

  x                ; The symbol x.  This symbol was "bound" to the value
                   ; 5 by the above define, so this evaluates to 5.

  (define y (+ 7 8))  ; A list containing define, y, and the list
                      ; containing +, 7, and 8.  As before, we evaluate
                      ; (+ 7 8), yielding 15.  Hence, this binds 15 to y.


  ; How do you think the following expressions are evaluated?
  ; Do you they are legal?

  (+ x y)

  (+ x y (1 2))

  (define + 5)

  (- + +)

  (- + (define z 9))