Sketchy LISP

An Introduction to Functional Programming in Scheme

1.7 Different Ways of Binding Symbols

In the previous section, two facilities for binding symbols locally were mentioned, but there is a third one, so Scheme has in fact three variants of let:

let let* letrec

This section explains the differences between these constructs. Let is the most straight-forward one of them. As outlined before, it is basically equal to a procedure application:

(let ((x 3)) (* x x))

is just another way of writing:

((lambda (x) (* x x)) 3)

Procedure applications are typically divided into the procedure part (which is bound to a name) and the arguments to which the procedure is applied:

(define square
  (lambda (x) (* x x)))
(square 3) => 9
(square 5) => 25
(square 7) => 49

Let, on the other hand, is mainly used to name parts of more complex expressions in order to increase efficiency and/or readabiliy. For instance, the following procedure searches an environment of the form that is used in let:

(define (value-of sym env)
  (cond ((null? env) #f)
    ((eq? sym (car (car env))) (car env))
    (else (value-of sym (cdr env)))))

When the search for the symbol sym in the environment env is successful, it returns the binding of the given symbol and otherwise it returns #f to signal failure:

(value-of 'b '((a 1) (b 2) (c 3))) => (b 2)
(value-of 'x '((a 1) (b 2) (c 3))) => #f

If you wanted to write a procedure that evaluates to the value of a symbol if the symbol is in env and to the symbol itself otherwise, you would have to call value-of twice:

(define (substitute sym env)
  (if (value-of sym env)
      (value-of sym env)
      sym))

The second application of value-of can be saved by using let:

(define (substitute sym env)
  (let ((val (value-of sym env)))
    (if val (cadr val) sym)))

Instead of evaluating (value-of sym env) twice in case of a match, this version of substitute binds the result returned by value-of to val and uses the variable in the place of the application of value-of. This version is both more readable, because val is easier to read than (value-of sym env), and more efficient, because value-of is only called once, no matter whether the given symbol exists in the environment or not.

BTW: in a real Scheme program, you would use the built-in assoc procedure rather than coding value-of yourself. Assoc has the same cost as value-of, though, so the above example remains valid.

Here is another application for let which demonstrates how to simplify an expression. Given the coordinates of two points on a grid, the distance between the points is to be calculated. Using Pythagoras' theorem, the distance is computed by:

square-root ( distance-on-x-axis² + distance-on-y-axis² )

If the coordinates of one point are (x,y) and the coordinates of the other point are (x2,y2), the distance on the x-axis is |x2-x| and the distance on the y-axis is |y2-y|, where |x| denotes the absolute value of x. So the procedure to compute the distance in Scheme looks like this:

(lambda (x y x2 y2)
  (sqrt (+ (* (abs (- y2 y))
              (abs (- y2 y)))
           (* (abs (- x2 x))
              (abs (- x2 x))))))

Although indentation even makes the formula readable, it can be simplified by extracting the distances on the individual axes using let:

(define (distance-between-points x y x2 y2)
  (let ((dx (abs (- x2 x)))
        (dy (abs (- y2 y))))
    (sqrt (+ (* dx dx)
             (* dy dy)))))

In applications of Scheme procedures, the order of evaluation is unspecified. This means that in a procedure application like

(+ (* 1 2) (* 3 4) (* 5 6))

the arguments (* 1 2), (* 3 4), and (* 5 6) may be evaluated in any order before they are passed to +. Because let is equivalent to the application of a (lambda) function, the same is valid for let:

(let ((a (* 1 2))
      (b (* 3 4))
      (c (* 5 6)))
  (+ a b c))

When creating local contexts using let, it is important that the definitions of the local values be independent (which they are in the above example). No value specified in the environment of a let may refer to a variable defined in the same let. This is because let first evaluates all values in its environment and then binds the values to symbols. The above expression would first evaluate (* 1 2), (* 3 4), and (* 5 6) in some unspecific order and only after evaluating all of these expressions, it would bind a to 2, b to 12, and c to 30. Dependencies between definitions of the same let will lead to undesired results:

(let ((a 5)
      (b (+ 1 a))
      (c (+ 1 b)))
  c)
=> bottom

Because a is bound to 5 after the evaluation of all values of the environment, a is not bound at all when evaluating (+ 1 a). The same is valid for the b in the value of c. The desired effect can be achieved, though, by nesting let:

(let ((a 5))
  (let ((b (+ 1 a)))
    (let ((c (+ 1 b)))
      c)))
=> 7

In this example, the value to be bound to b is computed inside of the context in which a is bound to 5, and c is bound inside of the context in which b is bound to 6. Because nesting applications of let may look a bit cumbersome, Scheme provides a binding construct which evaluates and binds values in sequence:

(let* ((a 5)
       (b (+ 1 a))
       (c (+ 1 b)))
  c)
=> 7

The star in let* indicates that the construct does something sequentially. Let* evaluates the first value and binds it to a symbol, thereby creating a new context. In this context it evaluates the second value and binds it to a symbol, creating yet another context, and so on. The expression forming the value of a symbol may refer to all variables created before it in the same let*. The following expressions are equivalent:

(let ((v1 a1))      =  (let* ((v1 a1)
  (let ((v2 a2))              (v2 a2)
   ...                         ...
    (let ((vn an))            (vn an))
      body)))            body)

1.7.1 Binding Recursive Procedures

In the code so far letrec was used to bind procedures and let was used to bind all other values. However, this is not really the difference between these two binding constructs. Letrec can be used to bind values, too:

(letrec ((a 17)
         (b 4))
  (+ a b))
=> 21

and let can be used to bind trivial procedures:

(let ((square (lambda (x) (* x x))))
  (square 7))
=> 49

The order of evaluation of the values of letrec is unspecified, just as the order of evaluation in let. So what is the difference between let and letrec? A minor hint was already given in a sentence above: let can only be used to bind trivial procedures. In this case trivial means not using recursion, and this is exactly what letrec is for: binding recursive procedures. In case you wonder why let cannot be used for this, take a look at the following expression:

(let ((down
        (lambda (x)
          (if (zero? x)
              0
              (down (- x 1))))))
  (down 5))
=> bottom

When you try this example, your Scheme system will complain about down being unbound. How can this be?

First the value to be assigned to down is evaluated. This involves the application of lambda which returns a closure. And this is exactly the problem. Lambda closes over down before down is bound to the procedure. In the resulting closure, down is unbound, and when the closure is applied to a non-zero value, an error occurs. (When the closure is applied to zero, no recursion takes place and 0 is returned, just as expected.)

What letrec does after binding values to symbols in the same way as let does is to fix recursive references. It even fixes indirect recursive references which are created by mutually recursive expressions like these:

(letrec
  ((even-p
     (lambda (x)
       (if (zero? x) #t (odd-p (- x 1)))))
   (odd-p
     (lambda (x)
       (if (zero? x) #f (even-p (- x 1))))))
  (cons (even-p 5) (odd-p 5)))
=> (#f . #t)

To fix recursive bindings, letrec needs a construct that is not purely functional, because it changes the value of a variable. This construct is the set! pseudo function. The trailing ! in the name set! indicates that it does something that requires special attention. Constructs ending with ! are used with care in Scheme.

Set! changes the value associated with a variable:

(define foo 0)
foo => 0
(set! foo 1)
foo => 1

It differs from define in two ways:

• define introduces a new variable, which set! does not;
• set! can be used anywhere, define only in specific contexts.

Standard Scheme requires a variable to be defined before you can set! it, but some Scheme environments do not enforce this rule.

How does set! help letrec define recursive procedures? Like let*, letrec can be re-written to let (and set!):

(letrec ((down
           (lambda (x)
             (if (zero? x) 0 (down (- x 1))))))
  (down 5))

becomes

(let ((down #f))
  (let ((t0 (lambda (x)
              (if (zero? x) 0 (down (- x 1))))))
    (set! down t0)
    (down 5)))

The outer let binds the variable down to something unimportant. The only purpose of this definition is to introduce the procedure name before the inner let is entered. In the inner let, lambda closes over the binding of down to an unimportant value and then let binds the resulting procedure to the temporary variable t0. In the body of the inner let, the binding of down to #f is still visible. Set! changes its value to the procedure bound to t0. This mutation also affects the value that lambda closed over, because the scope of the outer let is still in effect. The resulting structure is recursive:

down = (lambda (x)
         (if (zero? x) 0 (down (- x 1))))

In general, letrec can be transformed to let in the following way:

(letrec ((v1 p1)  =  (let ((v1 #f) ... (vn #f))
         ...           (let ((t1 p1)
         (vn pn))            ...
  body)                      (tn pn))
                         (set! v1 t1)
                         ...
                         (set! vn tn)
                         body))

Set! and letrec are the only Scheme constructs discussed in this book which can create cyclic structures. If you think that you can create a recursive structure in a purely applicative subset of Scheme without using constructs like letrec or set!, I really would like to see how it works (but do not try too hard, it may turn out to be impossible).