Three arm spiral.

Chapter 4. Variable Binding

This chapter describes the small set of syntactic forms whose primary purpose is to bind or to assign variables. Other forms that bind or assign variables for which the binding or assignment is not the primary purpose (such as do) are found in later chapters, especially in Chapter 5. This chapter begins with variable references and the lambda syntactic form. All variable binding operations in Scheme are derived from lambda, except top-level occurrences of define, which establishes top-level bindings.

Section 4.1. Variable References

syntax: variable
returns: the value of variable

Any unquoted identifier appearing in an expression is a keyword or variable reference. It is a keyword reference if a lexical or top-level keyword binding for the identifier is visible; otherwise, it is a variable reference. It is an error to evaluate a top-level variable reference before the variable is defined at top-level, but it is not an error for a variable reference to appear within an expression that has not yet been evaluated.

list  #<procedure>
(define x 'a)
(list x x)  (a a)
(let ((x 'b))
  (list x x))  (b b)
(let ((let 'let)) let)  let

(define f
  (lambda (x)
    (g x)))
(define g
  (lambda (x)
    (+ x x)))
(f 3)  6

Section 4.2. Lambda

syntax: (lambda formals exp1 exp2 ...)
returns: a procedure

The lambda syntactic form is used to create procedures. Any operation that creates a procedure or establishes local variable bindings is ultimately defined in terms of lambda.

The variables in formals are the formal parameters of the procedure, and the sequence of expressions exp1 exp2 ... is its body.

The body may begin with a sequence of definitions, in which case the established bindings are local to the procedure. If definitions are present, the body is replaced by a letrec expression formed from the definitions and the remaining expressions. Consult Section 3.5 or Section 4.4 for more details. The remainder of this discussion on lambda assumes that this transformation has taken place, if necessary, so that the body is a sequence of expressions without definitions.

When the procedure is created, the bindings of all variables occurring free within the body, excluding the formal parameters, are retained with the procedure. Subsequently, whenever the procedure is applied to a sequence of actual parameters, the formal parameters are bound to the actual parameters, the retained bindings are restored, and the body is evaluated.

Upon application, the formal parameters defined by formals are bound to the actual parameters as follows.

When the body is evaluated, the expressions exp1 exp2 ... are evaluated in sequence. The value of the last expression is the value of the procedure.

Procedures do not have a printed representation in the usual sense. Scheme systems print procedures in different ways; this book uses the notation #<procedure>.

(lambda (x) (+ x 3))  #<procedure>
((lambda (x) (+ x 3)) 7)  10
((lambda (x y) (* x (+ x y))) 7 13)  140
((lambda (f x) (f x x)) + 11)  22
((lambda () (+ 3 4)))  7

((lambda (x . y) (list x y))
 28 37)  (28 (37))
((lambda (x . y) (list x y))
 28 37 47 28)  (28 (37 47 28))
((lambda (x y . z) (list x y z))
 1 2 3 4)  (1 2 (3 4))
((lambda x x) 7 13)  (7 13)

Section 4.3. Local Binding

syntax: (let ((var val) ...) exp1 exp2 ...)
returns: the value of the final expression

let establishes local variable bindings. Each variable var is bound to the value of the corresponding expression val. The body of the let, in which the variables are bound, is the sequence of expressions exp1 exp2 ....

The forms let, let*, and letrec (let* and letrec are described after let) are similar but serve slightly different purposes. With let, in contrast with let* and letrec, the expressions val ... are all outside the scope of the variables var .... Also, in contrast with let*, no ordering is implied for the evaluation of the expressions val .... They may be evaluated from left to right, from right to left, or in any other order at the discretion of the implementation. Use let whenever the values are independent of the variables and the order of evaluation is unimportant.

The body of a let expression may begin with a sequence of definitions, which establish bindings local to the body of the let. See Section 3.5 or Section 4.4.

The following definition of let shows the typical derivation of let from lambda.

(define-syntax let
  (syntax-rules ()
    ((_ ((x v) ...) e1 e2 ...)
     ((lambda (x ...) e1 e2 ...) v ...))))

(let ((x (* 3.0 3.0)) (y (* 4.0 4.0)))
  (sqrt (+ x y)))  5.0

(let ((x 'a) (y '(b c)))
  (cons x y))  (a b c)

(let ((x 0) (y 1))
  (let ((x y) (y x))
    (list x y)))  (1 0)

Another form of let, named let, is described in Section 5.5.

syntax: (let* ((var val) ...) exp1 exp2 ...)
returns: the value of the final expression

let* is similar to let except that the expressions val ... are evaluated in sequence from left to right, and each of these expressions is within the scope of the variables to the left. Use let* when there is a linear dependency among the values or when the order of evaluation is important.

Any let* expression may be converted to a set of nested let expressions. The following definition of let* demonstrates the typical transformation.

(define-syntax let*
  (syntax-rules ()
    ((_ () e1 e2 ...)
     (let () e1 e2 ...))
    ((_ ((x1 v1) (x2 v2) ...) e1 e2 ...)
     (let ((x1 v1))
       (let* ((x2 v2) ...) e1 e2 ...)))))

(let* ((x (* 5.0 5.0))
       (y (- x (* 4.0 4.0))))
  (sqrt y))  3.0

(let ((x 0) (y 1))
  (let* ((x y) (y x))
    (list x y)))  (1 1)

syntax: (letrec ((var val) ...) exp1 exp2 ...)
returns: the value of the final expression

letrec is similar to let and let*, except that all of the expressions val ... are within the scope of all of the variables var .... letrec allows the definition of mutually recursive procedures.

The order of evaluation of the expressions val ... is unspecified, so it is an error to reference any of the variables bound by the letrec expression before all of the values have been computed. (Occurrence of a variable within a lambda expression does not count as a reference, unless the resulting procedure is applied before all of the values have been computed.)

Choose letrec over let or let* when there is a circular dependency among the variables and their values and when the order of evaluation is unimportant.

A letrec expression of the form

(letrec ((var val) ...) body)

may be expressed in terms of let and set! as

(let ((var #f) ...)
  (let ((temp val) ...)
    (set! var temp) ...
    (let () body)))

where temp ... are unique variables, one for each (var val) pair. The outer let expression establishes the variable bindings. The initial value given each variable is unimportant, so any value suffices in place of #f. The bindings are established first so that the values may contain occurrences of the variables, i.e., so that the values are computed within the scope of the variables. The middle let evaluates the values and binds them to the temporary variables, and the set! expressions assign each variable to the corresponding value. The inner let is present in case body contains internal definitions.

This transformation does not enforce the restriction that the values must not directly reference one of the variables.

A definition of letrec performing this transformation is shown on page 176.

(letrec ((sum (lambda (x)
                (if (zero? x)
                    (+ x (sum (- x 1)))))))
  (sum 5))  15

Section 4.4. Variable Definitions

syntax: (define var exp)
syntax: (define (var0 var1 ...) exp1 exp2 ...)
syntax: (define (var0 . varr) exp1 exp2 ...)
syntax: (define (var0 var1 var2 ... . varr) exp1 exp2 ...)
returns: unspecified

In the first form, define creates a new binding of var to the value of exp. The remaining are shorthand forms for binding variables to procedures; they are identical to the following definition in terms of lambda:

(define var
  (lambda formals
    exp1 exp2 ...))

where formals is (var1 ...), varr, or (var1 var2 ... . varr) for the second, third, and fourth define formats.

Definitions often appear at "top level," i.e., outside the scope of any lambda or any form derived from lambda, such as let, let*, or letrec. A variable bound at top level is visible within any expression typed at the keyboard or loaded from a file, except where shadowed by a local binding.

Definitions may also appear at the front of a lambda body or body of any form derived from lambda. These internal definitions must precede the expressions in the body. Any lambda expression whose body begins with definitions may be transformed into an equivalent lambda expression without such definitions, by rewriting the body as a letrec expression. That is, a lambda expression of the form

(lambda formals
  (define var val) ...
  exp1 exp2 ...)

may be expressed in the equivalent form below.

(lambda formals
  (letrec ((var val) ...)
    exp1 exp2 ...))

Although this shows the transformation for the first and simpler form of definition, either form may appear within a lambda body.

Syntax definitions may appear along with variable definitions wherever variable definitions may appear; see Chapter 8.

(define x 3)

(define f
  (lambda (x y)
    (* (+ x y) 2)))
(f 5 4)  18

(define (sum-of-squares x y)
  (+ (* x x) (* y y)))
(sum-of-squares 3 4)  25

(define f
  (lambda (x)
    (+ x 1)))
(let ((x 2))
  (define f
    (lambda (y)
      (+ y x)))
  (f 3))  5
(f 3)  4

A set of definitions may be grouped by enclosing them in a begin form. Definitions grouped in this manner may appear wherever ordinary variable and syntax definitions may appear. They are treated as if written separately, i.e., without the enclosing begin form. This feature allows syntactic extensions to expand into groups of definitions.

(define-syntax multi-define-syntax
  (syntax-rules ()
    ((_ (var exp) ...)
       (define-syntax var exp)
(let ()
  (define plus
    (lambda (x y)
        (if (zero? x)
            (plus (sub1 x) (add1 y)))))
    (add1 (syntax-rules () ((_ e) (+ e 1))))
    (sub1 (syntax-rules () ((_ e) (- e 1)))))
  (plus 7 8))  15

Section 4.5. Assignment

syntax: (set! var exp)
returns: unspecified

set! assigns a new value to an existing variable. The value of the variable var is changed to the value of exp. Any subsequent reference to var evaluates to the new value.

This form is different from the forms described earlier in this chapter because it does not establish a new binding for var but rather changes the value of an existing binding. It is an error to assign a top-level variable that has not yet been defined, although many implementations do not enforce this restriction.

Assignments are not employed as frequently in Scheme as in most traditional languages, but they are useful for updating the state of a system and in creating recursive structures (as with letrec).

(let ((x 3) (y 4))
  (set! x 5)
  (+ x y))  9

(define f
  (lambda (x y)
    (cons x y)))
(f 'a 'b)  (a . b)
(set! f
  (lambda (x y)
    (cons y x)))
(f 'a 'b)  (b . a)

R. Kent Dybvig
The Scheme Programming Language, Second Edition
© 1996. Electronically reproduced by permission of Prentice Hall, Upper Saddle River, New Jersey.
Illustrations © 1997 Jean-Pierre Hébert
to order this book
about this book