#<procedure>(define x 'a)
(list x x)
(a a)(let ((x 'b))
(list x x))
(b b)(let ((let 'let)) let)
let
Procedures and variable bindings are the fundamental building blocks of Scheme programs. This chapter describes the small set of syntactic form whose primary purpose is to create procedures and manipulate variable bindings. It begins with two most fundamental building blocks of Scheme programs: variable references and lambda expressions, and continues with descriptions of the basic local variable binding forms let and letrec, top-level and internal define, and set!.
Various other forms that bind or assign variables for which the binding or assignment is not the primary purpose (such as named let) are found in Chapter 5.
syntax: variable
returns: the value of variable
Any identifier appearing as an expression in a program 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. After syntactic extensions have been expanded (see Chapter 8), no keyword references remain, so all remaining identifier expressions are variable references.
list #<procedure>
(define x 'a)
(list x x) (a a)
(let ((x 'b))
(list x x)) (b b)
(let ((let 'let)) let) let
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 such a reference to appear within a part of a program that has not yet been evaluated. This permits mutually recursive procedures to be defined using top-level bindings.
i-am-not-defined error
(define f
(lambda (x)
(g x)))
(define g
(lambda (x)
(+ x x)))
(f 3) 6
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 of 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)
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.4, and a definition of the full let can be found on page 201.
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. More elaborate transformations that enforce this restriction and produce more efficient code are possible [23].
A definition of letrec performing this transformation is shown on page 199.
(letrec ((sum (lambda (x)
(if (zero? x)
0
(+ x (sum (- x 1)))))))
(sum 5)) 15
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)
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) ...)
(begin
(define-syntax var exp)
...))))
(let ()
(define plus
(lambda (x y)
(if (zero? x)
y
(plus (sub1 x) (add1 y)))))
(multi-define-syntax
(add1 (syntax-rules () ((_ e) (+ e 1))))
(sub1 (syntax-rules () ((_ e) (- e 1)))))
(plus 7 8)) 15
syntax: (set! var exp)
returns: unspecified
set! does not establish a new binding for var but rather alters the value of an existing binding. It first evaluates exp, then assigns var to the value of exp. Any subsequent reference to var within the scope of the altered binding evaluates to the new value.
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 implementing state changes.
(define flip-flop
(let ((state #f))
(lambda ()
(set! state (not state))
state)))
(flip-flop) #t
(flip-flop) #f
(flip-flop) #t
Assignments are also useful for caching values. The example below uses a technique called memoization, in which a procedure records the values associated with old input values so it need not recompute them, to implement a fast version of the otherwise exponential doubly-recursive definition of the Fibonacci function (see page 66).
(define memoize
(lambda (proc)
(let ((cache '()))
(lambda (x)
(cond
((assq x cache) => cdr)
(else (let ((ans (proc x)))
(set! cache (cons (cons x ans) cache))
ans)))))))
(define fibonacci
(memoize
(lambda (n)
(if (< n 2)
1
(+ (fibonacci (- n 1)) (fibonacci (- n 2)))))))
(fibonacci 100) 573147844013817084101
R. Kent Dybvig /
Copyright © 2003 The MIT Press. Electronically reproduced by permission.
Illustrations © 2003 Jean-Pierre Hébert
ISBN 0-262-54148-3 / LOC QA76.73.S34D93
to order this book / about this book