Two arm spiral, warped in euclidean space.

Chapter 5. Control Operations

This chapter introduces the syntactic forms and procedures that serve as control structures for Scheme programs, The first section covers the most basic control structure, procedure application, and the remaining sections cover sequencing, conditional evaluation, recursion, continuations, delayed evaluation, multiple values, and evaluation of constructed programs.

Section 5.1. Procedure Application


syntax: (procedure exp ...)
returns: result of applying the value of procedure to the values of exp ...

Procedure application is the most basic Scheme control structure. Any structured form without a syntax keyword in the first position is a procedure application. The expressions procedure and exp ... are evaluated and the value of procedure is applied to the values of exp ....

The order in which the procedure and argument expressions are evaluated is unspecified. It may be left to right, right to left, or any other order. The evaluation is guaranteed to be sequential, however; whatever order is chosen, each expression is fully evaluated before evaluation of the next is started.

(+ 3 4) <graphic> 7

((if (odd? 3) + -) 6 2) <graphic> 8

((lambda (x) x) 5) <graphic> 5

(let ((f (lambda (x) (+ x x))))
  (f 8)) <graphic> 16


procedure: (apply procedure obj ... list)
returns: the result of applying procedure to obj ... and the elements of list

apply invokes procedure, passing the first obj as the first argument, the second obj as the second argument, and so on for each object in obj ..., and passing the elements of list in order as the remaining arguments. Thus, procedure is called with as many arguments as there are objs plus elements of list.

apply is useful when some or all of the arguments to be passed to a procedure are in a list, since it frees the programmer from explicitly destructuring the list.

(apply + '(4 5)) <graphic> 9

(apply min '(6 8 3 2 5)) <graphic> 2

(apply min  5 1 3 '(6 8 3 2 5)) <graphic> 1

(apply vector 'a 'b '(c d e)) <graphic> #5(a b c d e)

(define first
  (lambda (l)
    (apply (lambda (x . y) x)
             l)))
(define rest
  (lambda (l)
    (apply (lambda (x . y) y) l)))
(first '(a b c d)) <graphic> a
(rest '(a b c d)) <graphic> (b c d)

Section 5.2. Sequencing


syntax: (begin exp1 exp2 ...)
returns: the result of the last expression

The expressions exp1 exp2 ... are evaluated in sequence from left to right. begin is used to sequence assignments, input/output, or other operations that cause side effects.

(define x 3)
(begin
  (set! x (+ x 1))
  (+ x x)) <graphic> 8

A begin form may contain zero or more definitions in place of the expressions exp1 exp2 ..., in which case it is considered to be a definition and may appear only where definitions are valid.

(let ()
  (begin (define x 3) (define y 4))
  (+ x y)) <graphic> 7

This form of begin is primarily used by syntactic extensions that must expand into multiple definitions. (See page 91.)

The bodies of many syntactic forms, including lambda, let, let*, and letrec, as well as the result clauses of cond, case, and do, are treated as if they were inside an implicit begin; that is, the expressions making up the body or result clause are executed in sequence.

(define swap-pair!
  (lambda (x)
    (let ((temp (car x)))
      (set-car! x (cdr x))
      (set-cdr! x temp)
      x)))
(swap-pair! (cons 'a 'b)) <graphic> (b . a)

Section 5.3. Conditionals


syntax: (if test consequent alternative)
syntax: (if test consequent)
returns: the value of consequent or alternative depending on the value of test

test, consequent, and alternative are expressions. If no alternative is supplied and test evaluates to false, the result is unspecified.

(let ((l '(a b c)))
  (if (null? l)
      '()
      (cdr l))) <graphic> (b c)

(let ((l '()))
  (if (null? l)
      '()
      (cdr l))) <graphic> ()

(let ((abs
       (lambda (x)
         (if (< x 0)
             (- 0 x)
             x))))
  (abs -4)) <graphic> 4

(let ((x -4))
  (if (< x 0)
      (list 'minus (- 0 x))
      (list 'plus 4))) <graphic> (minus 4)


procedure: (not obj)
returns: #t if obj is false, #f otherwise

not is equivalent to (lambda (x) (if x #f #t)).

(not #f) <graphic> #t
(not #t) <graphic> #f
(not '()) <graphic> #f
(not (< 4 5)) <graphic> #f


syntax: (and exp ...)
returns: see explanation

and evaluates its subexpressions in sequence from left to right and stops immediately (without evaluating the remaining expressions) if any expression evaluates to false. The value of the last expression evaluated is returned. A syntax definition of and appears on page 60.

(let ((x 3))
  (and (> x 2) (< x 4))) <graphic> #t

(let ((x 5))
  (and (> x 2) (< x 4))) <graphic> #f

(and #f '(a b) '(c d)) <graphic> #f
(and '(a b) '(c d) '(e f)) <graphic> (e f)


syntax: (or exp ...)
returns: see explanation

or evaluates its subexpressions in sequence from left to right and stops immediately (without evaluating the remaining expressions) if any expression evaluates to a true value. The value of the last expression evaluated is returned. A syntax definition of or appears on page 61.

(let ((x 3))
  (or (< x 2) (> x 4))) <graphic> #f

(let ((x 5))
  (or (< x 2) (> x 4))) <graphic> #t

(or #f '(a b) '(c d)) <graphic> (a b)


syntax: (cond clause1 clause2 ...)
returns: see explanation

Each clause but the last must take one of the forms below.

(test)
(test exp1 exp2 ...)
(test => exp)

The last clause may be in any of the above forms or it may be an "else clause" of the form

(else exp1 exp2 ...)

Each test is evaluated in order until one evaluates to a true value or until all of the tests have been evaluated. If the first clause whose test evaluates to a true value is in the first form given above, the value of test is returned.

If the first clause whose test evaluates to a true value is in the second form given above, the expressions exp1 exp2... are evaluated in sequence and the value of the last expression is returned.

If the first clause whose test evaluates to a true value is in the third form given above, the expression exp is evaluated. The value should be a procedure of one argument, which is applied to the value of test. The result of this application is returned.

If none of the tests evaluates to a true value and an else clause is present, the expressions exp1 exp2 ... of the else clause are evaluated in sequence and the value of the last expression is returned.

If none of the tests evaluates to a true value and no else clause is present, the value is unspecified.

See page 196 for a syntax definition of cond.

(let ((x 0))
  (cond
    ((< x 0) (list 'minus (abs x)))
    ((> x 0) (list 'plus x))
    (else (list 'zero x)))) <graphic> (zero 0)

(define select
  (lambda (x)
    (cond
      ((not (symbol? x)))
      ((assq x '((a . 1) (b . 2) (c . 3)))
       => cdr)
      (else 0))))

(select 3) <graphic> #t
(select 'b) <graphic> 2
(select 'e) <graphic> 0


syntax: (case exp0 clause1 clause2 ...)
returns: see explanation

Each clause but the last must take the form

((key ...) exp1 exp2 ...)

where each key is a datum distinct from the other keys. The last clause may be in the above form or it may be an else clause of the form

(else exp1 exp2 ...)

exp0 is evaluated and the result is compared (using eqv?) against the keys of each clause in order. If a clause containing a matching key is found, the expressions exp1 exp2 ... are evaluated in sequence and the value of the last expression is returned.

If none of the clauses contains a matching key and an else clause is present, the expressions exp1 exp2 ... of the else clause are evaluated in sequence and the value of the last expression is returned.

If none of the clauses contains a matching key and no else clause is present, the value is unspecified.

See page 197 for a syntax definition of case

(let ((x 4) (y 5))
  (case (+ x y)
    ((1 3 5 7 9) 'odd)
    ((0 2 4 6 8) 'even)
    (else 'out-of-range))) <graphic> odd

Section 5.4. Recursion, Iteration, and Mapping


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

This form of let, called named let, is a general-purpose iteration and recursion construct. It is similar to the more common form of let (see Section 4.3) in the binding of the variables var ... to the values val ... within the body exp1 exp2 .... In addition, the variable name is bound within the body to a procedure that may be called to recur or iterate; the arguments to the procedure become the new values of the variables var ....

A named let expression of the form

(let name ((var val) ...)
  exp1 exp2 ...)

can be rewritten with letrec as follows.

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

A syntax definition of let that implements this transformation and handles unnamed let as well can be found on page 201.

The procedure divisors defined below uses named let to compute the nontrivial divisors of a nonnegative integer.

(define divisors
  (lambda (n)
    (let f ((i 2))
      (cond
        ((>= i n) '())
        ((integer? (/ n i))
         (cons i (f (+ i 1))))
        (else (f (+ i 1)))))))

(divisors 5) <graphic> ()
(divisors 32) <graphic> (2 4 8 16)

The version above is non-tail-recursive when a divisor is found and tail-recursive when a divisor is not found. The version below is fully tail-recursive. It builds up the list in reverse order, but this is easy to remedy, either by reversing the list on exit or by starting at n - 1 and counting down to 1.

(define divisors
  (lambda (n)
    (let f ((i 2) (ls '()))
      (cond
        ((>= i n) ls)
        ((integer? (/ n i))
         (f (+ i 1) (cons i ls)))
        (else (f (+ i 1) ls))))))


syntax: (do ((var val update) ...) (test res ...) exp ...)
returns: the value of the last res

do allows a common restricted form of iteration to be expressed succinctly. The variables var ... are bound initially to the values of val ... and are rebound on each subsequent iteration to the values of update .... The expressions test, update ..., exp ..., and res ... are all within the scope of the bindings established for var ....

On each step, the test expression test is evaluated. If the value of test is true, iteration ceases, the result expressions res ... are evaluated in sequence, and the value of the last expression is returned. If no result expressions are present, the value of the do expression is unspecified.

If the value of test is false, the expressions exp ... are evaluated in sequence, the expressions update ... are evaluated, new bindings for var ... to the values of update ... are created, and iteration continues.

The expressions exp ... are evaluated only for effect and are often omitted entirely. Any update expression may be omitted, in which case the effect is the same as if the update were simply the corresponding var.

Although looping constructs in most languages require that the loop iterands be updated via assignment, do requires the loop iterands val ... to be updated via rebinding. In fact, no side effects are involved in the evaluation of a do expression unless they are performed explicitly by its subexpressions.

See page 202 for a syntax definition of do.

The definitions of factorial and fibonacci below are straightforward translations of the tail-recursive named-let versions given in Section 3.2.

(define factorial
  (lambda (n)
    (do ((i n (- i 1)) (a 1 (* a i)))
        ((zero? i) a))))

(factorial 10) <graphic> 3628800

(define fibonacci
  (lambda (n)
    (if (= n 0)
        0
        (do ((i n (- i 1)) (a1 1 (+ a1 a2)) (a2 0 a1))
            ((= i 1) a1)))))

(fibonacci 6) <graphic> 8

The definition of divisors below is similar to the tail-recursive definition of divisors given with the description of named let above.

(define divisors
  (lambda (n)
    (do ((i 2 (+ i 1))
         (ls '()
             (if (integer? (/ n i))
                 (cons i ls)
                 ls)))
        ((>= i n) ls))))

The definition of scale-vector! below, which scales each element of a vector v by a constant k, demonstrates a nonempty do body.

(define scale-vector!
  (lambda (v k)
    (let ((n (vector-length v)))
      (do ((i 0 (+ i 1)))
          ((= i n))
        (vector-set! v i (* (vector-ref v i) k))))))

(define vec (vector 1 2 3 4 5))
(scale-vector! vec 2)
vec <graphic> #(2 4 6 8 10)


procedure: (map procedure list1 list2 ...)
returns: list of results

map applies procedure to corresponding elements of the lists list1 list2 ... and returns a list of the resulting values. The lists list1 list2 ... must be of the same length, and procedure must accept as many arguments as there are lists.

(map abs '(1 -2 3 -4 5 -6)) <graphic> (1 2 3 4 5 6)
(map (lambda (x y) (* x y))
     '(1 2 3 4)
     '(8 7 6 5)) <graphic> (8 14 18 20)

While the order in which the applications themselves occur is not specified, the order of the values in the output list is the same as that of the corresponding values in the input lists.

map might be defined as follows.

(define map
  (lambda (f ls . more)
    (if (null? more)
        (let map1 ((ls ls))
          (if (null? ls)
              '()
              (cons (f (car ls))
                    (map1 (cdr ls)))))
        (let map-more ((ls ls) (more more))
          (if (null? ls)
              '()
              (cons (apply f (car ls) (map car more))
                    (map-more (cdr ls)
                              (map cdr more))))))))

No error checking is done by this version of map; f is assumed to be a procedure and the other arguments are assumed to be proper lists of the same length. An interesting feature of this definition is that map uses itself to pull out the cars and cdrs of the list of input lists; this works because of the special treatment of the single-list case.


procedure: (for-each procedure list1 list2 ...)
returns: unspecified

for-each is similar to map except that for-each does not create and return a list of the resulting values, and for-each guarantees to perform the applications in sequence over the lists from left to right. for-each may be defined as follows.

(define for-each
  (lambda (f ls . more)
    (do ((ls ls (cdr ls)) (more more (map cdr more)))
        ((null? ls))
        (apply f (car ls) (map car more)))))

(let ((same-count 0))
  (for-each
    (lambda (x y)
      (if (= x y)
          (set! same-count (+ same-count 1))))
    '(1 2 3 4 5 6)
    '(2 3 3 4 7 6))
  same-count) <graphic> 3

Section 5.5. Continuations

Continuations in Scheme are procedures that represent the remainder of a computation from a given point in the continuation. They may be obtained with call-with-current-continuation, which can be abbreviated call/cc in many Scheme implementations.


procedure: (call-with-current-continuation procedure)
returns: the result of applying procedure to the current continuation

call-with-current-continuation is often abbreviated call/cc for the obvious reason that it requires fewer keystrokes to type. If the implementation you use does not have a binding for call/cc, you can define it or use the longer name in your code.

(define call/cc call-with-current-continuation)

call/cc obtains its continuation and passes it to procedure, which must accept one argument. The continuation itself is represented by a procedure of one argument. (In the context of multiple values, a continuation may actually accept zero or more than one argument; see Section 5.7.) Each time this procedure is applied to a value, it returns the value to the continuation of the call/cc application. That is, when the continuation procedure is given a value, it returns the value as the result of the application of call/cc.

If procedure returns normally when passed the continuation procedure, the value returned by call/cc is the value returned by procedure.

Continuations allow the implementation of nonlocal exits, backtracking [9,21], coroutines [11], and multitasking [6,24].

The example below illustrates the use of a continuation to perform a nonlocal exit from a loop.

(define member
  (lambda (x ls)
    (call/cc
      (lambda (break)
        (do ((ls ls (cdr ls)))
            ((null? ls) #f)
            (if (equal? x (car ls))
                (break ls)))))))

(member 'd '(a b c)) <graphic> #f
(member 'b '(a b c)) <graphic> (b c)

Additional examples are given in Sections 3.3 and 9.11.

The current continuation is typically represented internally as a stack of procedure activation records, and obtaining the continuation involves encapsulating the stack within a procedural object. Since an encapsulated stack has indefinite extent, some mechanism must be used to preserve the stack contents indefinitely. This can be done with surprising ease and efficiency and with no impact on programs that do not use continuations [12].


procedure: (dynamic-wind in body out)
returns: result of applying body

dynamic-wind offers "protection" from continuation invocation. It is useful for performing tasks that must be performed whenever control enters or leaves body, either normally or by continuation application.

The three arguments in, body, and out must be procedures of no arguments, i.e., thunks. Before applying body, and each time body is entered subsequently by the application of a continuation created within body, the in thunk is applied. Upon normal exit from body and each time body is exited by the application of a continuation created outside body, the out thunk is applied.

Thus, it is guaranteed that in is invoked at least once. In addition, if body ever returns, out is invoked at least once.

dynamic-wind appears in the Revised5 Report but not in the ANSI/IEEE standard.

The following example demonstrates the use of dynamic-wind to be sure that an input port is closed after processing, regardless of whether the processing completes normally.

(let ((p (open-input-file "input-file")))
  (dynamic-wind
    (lambda () #f)
    (lambda () (process p))
    (lambda () (close-input-port p))))

Common Lisp provides a similar facility (unwind-protect) for protection from nonlocal exits. This is often sufficient. unwind-protect provides only the equivalent to out, however, since Common Lisp does not support fully general continuations. Here is how unwind-protect might be specified with dynamic-wind.

(define-syntax unwind-protect
  (syntax-rules ()
    ((_ body cleanup ...)
     (dynamic-wind
       (lambda () #f)
       (lambda () body)
       (lambda () cleanup ...)))))

((call/cc
   (let ((x 'a))
     (lambda (k)
       (unwind-protect
         (k (lambda () x))
         (set! x 'b)))))) <graphic> b

Some Scheme implementations support a controlled form of assignment known as fluid binding, in which a variable takes on a temporary value during a given computation and reverts to the old value after the computation has completed. The syntactic form fluid-let defined below in terms of dynamic-wind permits the fluid binding of a single variable x to a value v within a sequence of expressions e1 e2 ....

(define-syntax fluid-let
  (syntax-rules ()
    ((_ ((x v)) e1 e2 ...)
     (let ((y v))
       (let ((swap (lambda () (let ((t x)) (set! x y) (set! y t)))))
         (dynamic-wind swap (lambda () e1 e2 ...) swap))))))

(Implementations that support fluid-let generally extend it to allow an indefinite number of (x v) pairs, as with let.)

If no continuations are invoked within the body of a fluid-let, the behavior is the same as if the variable were simply assigned the new value on entry and assigned the old value on return.

(let ((x 3))
  (+ (fluid-let ((x 5))
       x)
     x)) <graphic> 8

A fluid-bound variable also reverts to the old value if a continuation created outside of the fluid-let is invoked.

(let ((x 'a))
  (let ((f (lambda () x)))
    (cons (call/cc
            (lambda (k)
              (fluid-let ((x 'b))
                (k (f)))))
          (f)))) <graphic> (b . a)

If control has left a fluid-let body, either normally or by the invocation of a continuation, and control reenters the body by the invocation of a continuation, the temporary value of the fluid-bound variable is reinstated. Furthermore, any changes to the temporary value are maintained and reflected upon reentry.

(define reenter #f)
(define x 0)
(fluid-let ((x 1))
  (call/cc (lambda (k) (set! reenter k)))
  (set! x (+ x 1))
  x) <graphic> 2
<graphic> 0
(reenter '*) <graphic> 3
(reenter '*) <graphic> 4
<graphic> 0

An implementation of dynamic-wind is given below. In addition to defining dynamic-wind, the code redefines call/cc (call-with-current-continuation).

(define dynamic-wind #f)
(let ((winders '()))
  (define common-tail
    (lambda (x y)
      (let ((lx (length x)) (ly (length y)))
        (do ((x (if (> lx ly) (list-tail x (- lx ly)) x) (cdr x))
             (y (if (> ly lx) (list-tail y (- ly lx)) y) (cdr y)))
            ((eq? x y) x)))))
  (define do-wind
    (lambda (new)
      (let ((tail (common-tail new winders)))
        (let f ((l winders))
          (if (not (eq? l tail))
              (begin
                (set! winders (cdr l))
                ((cdar l))
                (f (cdr l)))))
        (let f ((l new))
          (if (not (eq? l tail))
              (begin
                (f (cdr l))
                ((caar l))
                (set! winders l)))))))
  (set! call/cc
    (let ((c call/cc))
      (lambda (f)
        (c (lambda (k)
             (f (let ((save winders))
                  (lambda (x)
                    (if (not (eq? save winders)) (do-wind save))
                    (k x)))))))))
  (set! call-with-current-continuation call/cc)
  (set! dynamic-wind
    (lambda (in body out)
      (in)
      (set! winders (cons (cons in out) winders))
      (let ((ans (body)))
        (set! winders (cdr winders))
        (out)
        ans))))

Together, dynamic-wind and call/cc manage a list of winders. A winder is a pair of in and out thunks established by a call to dynamic-wind. Whenever dynamic-wind is invoked, the in thunk is invoked, a new winder containing the in and out thunks is placed on the winders list, the body thunk is invoked, the winder is removed from the winders list, and the out thunk is invoked. This ordering ensures that the winder is on the winders list only when control has passed through in and not yet entered out. Whenever a continuation is obtained, the winders list is saved, and whenever the continuation is invoked, the saved winders list is reinstated. During reinstatement, the out thunk of each winder on the current winders list that is not also on the saved winders list is invoked, followed by the in thunk of each winder on the saved winders list that is not also on the current winders list. The winders list is updated incrementally, again to ensure that a winder is on the current winders list only if control has passed through its in thunk and not entered its out thunk.

The test (not (eq? save winders)) performed in call/cc is not strictly necessary but makes invoking a continuation less costly whenever the saved winders list is the same as the current winders list.

Section 5.6. Delayed Evaluation

The syntactic form delay and the procedure force may be used in combination to implement lazy evaluation. An expression subject to lazy evaluation is not evaluated until its value is required and once evaluated is never reevaluated. delay and force appear in the Revised5 Report but not in the ANSI/IEEE standard.


syntax: (delay exp)
returns: a promise

The first time the promise is forced (with force), it evaluates exp, "remembering" the resulting value. Thereafter, each time the promise is forced, it returns the remembered value instead of reevaluating exp. See the examples given for force below.


procedure: (force promise)
returns: result of forcing promise

delay may be defined as

(define-syntax delay
  (syntax-rules ()
    ((_ exp) (make-promise (lambda () exp)))))

where make-promise is defined as

(define make-promise
  (lambda (p)
    (let ((val #f) (set? #f))
      (lambda ()
        (if (not set?)
            (let ((x (p)))
              (if (not set?)
                  (begin (set! val x)
                         (set! set? #t)))))
        val))))

With this definition of delay, force simply invokes the promise to force evaluation or to retrieve the saved value.

(define force
  (lambda (promise)
    (promise)))

The second test of the variable set? in make-promise is necessary in the unlikely event that, as a result of applying p, the promise is recursively forced. Since a promise must always return the same value, the result of the first application of p to complete is returned.

delay and force are typically used only in the absence of side effects, e.g., assignments, so that the order of evaluation is unimportant.

The benefit of using delay and force is that some amount of computation might be avoided altogether if it is delayed until absolutely required. Delayed evaluation may be used to construct conceptually infinite lists, or streams. The example below shows how a stream abstraction may be built with delay and force. A stream is a promise that, when forced, returns a pair whose cdr is a stream.

(define stream-car
  (lambda (s)
    (car (force s))))

(define stream-cdr
  (lambda (s)
    (cdr (force s))))

(define counters
  (let next ((n 1))
    (delay (cons n (next (+ n 1))))))

(stream-car counters) <graphic> 1

(stream-car (stream-cdr counters)) <graphic> 2

(define stream-add
  (lambda (s1 s2)
    (delay (cons
             (+ (stream-car s1) (stream-car s2))
             (stream-add (stream-cdr s1) (stream-cdr s2))))))

(define even-counters
  (stream-add counters counters))

(stream-car even-counters) <graphic> 2

(stream-car (stream-cdr even-counters)) <graphic> 4

Section 5.7. Multiple Values

While all Scheme primitives and most user-defined procedures return exactly one value, some programming problems are best solved by returning something other than one value. For example, a procedure that partitions a list of values into two sublists needs to return two values. While it is possible for the producer of multiple values to package them into a data structure and for the consumer to extract them, it is often cleaner to use the built in multiple-values interface. This interface consists of two procedures: values and call-with-values. The former produces multiple values and the latter links procedures that produce multiple-value values with procedures that consume them. The multiple values interface appears in the Revised5 Report but not in the ANSI/IEEE standard.


procedure: (values obj ...)
returns: see discussion following

The procedure values accepts any number of arguments and simply passes (returns) the arguments to its continuation.

(values) <graphic>

(values 1) <graphic> 1

(values 1 2 3) <graphic> 1
                2
                3

(define head&tail
  (lambda (ls)
    (values (car ls) (cdr ls))))

(head&tail '(a b c)) <graphic> a
                      (b c)


procedure: (call-with-values producer consumer)
returns: see discussion following

producer and consumer must be procedures. call-with-values applies consumer to the values returned by invoking producer without arguments.

(call-with-values
  (lambda () (values 'bond 'james))
  (lambda (x y) (cons y x))) <graphic> (james . bond)

(call-with-values values list) <graphic> '()

In the second example, values itself serves as the producer. It receives no arguments and thus returns no values. list is thus applied to no arguments and so returns the empty list.

The procedure dxdy defined below computes the change in x and y coordinates for a pair of points whose coordinates are represented by (x . y) pairs.

(define dxdy
  (lambda (p1 p2)
    (values (- (car p2) (car p1))
            (- (cdr p2) (cdr p1)))))

(dxdy '(0 . 0) '(0 . 5)) <graphic> 0
                          5

dxdy can be used to compute the length and slope of a segment represented by two endpoints.

(define segment-length
  (lambda (p1 p2)
    (call-with-values
      (lambda () (dxdy p1 p2))
      (lambda (dx dy) (sqrt (+ (* dx dx) (* dy dy)))))))

(define segment-slope
  (lambda (p1 p2)
    (call-with-values
      (lambda () (dxdy p1 p2))
      (lambda (dx dy) (/ dy dx)))))

(segment-length '(1 . 4) '(4 . 8)) <graphic> 5
(segment-slope '(1 . 4) '(4 . 8)) <graphic> 4/3

We can of course combine these to form one procedure that returns two values.

(define describe-segment
  (lambda (p1 p2)
    (call-with-values
      (lambda () (dxdy p1 p2))
      (lambda (dx dy)
        (values
          (sqrt (+ (* dx dx) (* dy dy)))
          (/ dy dx))))))

(describe-segment '(1 . 4) '(4 . 8)) <graphic> 5
                                     <graphic> 4/3

The example below employs multiple values to divide a list nondestructively into two sublists of alternating elements.

(define split
  (lambda (ls)
    (if (or (null? ls) (null? (cdr ls)))
        (values ls '())
        (call-with-values
          (lambda () (split (cddr ls)))
          (lambda (odds evens)
            (values (cons (car ls) odds)
                    (cons (cadr ls) evens)))))))

(split '(a b c d e f)) <graphic> (a c e)
                        (b d f)

At each level of recursion, the procedure split returns two values: a list of the odd-numbered elements from the argument list and a list of the even-numbered elements.

The continuation of a call to values need not be one established by a call to call-with-values, nor must only values be used to return to a continuation established by call-with-values. In particular, (values v) and v are equivalent in all situations. For example:

(+ (values 2) 4) <graphic> 6

(if (values #t) 1 2) <graphic> 1

(call-with-values
  (lambda () 4)
  (lambda (x) x)) <graphic> 4

Similarly, values may be used to pass any number of values to a continuation that ignores the values, as in:

(begin (values 1 2 3) 4) <graphic> 4

Because a continuation may accept zero or more than one value, continuations obtained via call-with-current-continuation (call/cc) may accept zero or more than one argument.

(call-with-values
  (lambda ()
    (call/cc (lambda (k) (k 2 3))))
  (lambda (x y) (list x y))) <graphic> (2 3)

Many Scheme operators pass along multiple values. Most of these are "automatic," in the sense that nothing special must be done by the implementation to make this happen. The usual expansion of let into a direct lambda call automatically propagates multiple values produced by the body of the let. Other operators must be coded specially to pass along multiple values. For example, if the computation delayed by delay produces multiple values, all of the values must be retained so that force can return them. This is easily accomplished via call-with-values, apply, and values, as the following alternative definition of make-promise (see Section 5.6) demonstrates.

(define make-promise
  (lambda (p)
    (let ((vals #f) (set? #f))
      (lambda ()
        (if (not set?)
            (call-with-values p
              (lambda x
                (if (not set?)
                    (begin (set! vals x)
                           (set! set? #t))))))
        (apply values vals)))))

(define p (delay (values 1 2 3)))
(force p) <graphic> 1
           2
           3
(call-with-values (lambda () (force p)) +) <graphic> 6

Other operators that must be coded similarly to pass along multiple return values include call-with-input-file, call-with-output-file, with-input-from-file, with-output-to-file, and dynamic-wind.

The behavior is unspecified when a continuation expecting exactly one value receives zero values or more than one value. For example, the behavior of each of the following expressions is unspecified.

(if (values 1 2) 'x 'y)

(+ (values) 5)

Similarly, since there is no requirement to signal an error when the wrong number of arguments is passed to a procedure (although most implementations do so), the behavior of each of the following expressions is also unspecified.

(call-with-values
  (lambda () (values 2 3 4))
  (lambda (x y) x))

(call-with-values
  (lambda () (call/cc (lambda (k) (k 0))))
  (lambda (x y) x))

In the interests of catching possible coding errors and for consistency with the signaling of errors when procedures receive incorrect numbers of arguments, some implementations, including Chez Scheme, signal an error whenever an unexpected number of values is received. This includes the case where too few or too many are passed to the consumer of a call-with-values call and the case where zero or more than one value is passed to a single-value continuation, such as in the test part of an if expression. An implementation may, however, silently suppress additional values or supply defaults for missing values.

Programs that wish to force extra values to be ignored in particular contexts can do so easily by calling call-with-values explicitly. A syntactic form, which we might call first, can be defined to abstract the discarding of more than one value when only one is desired.

(define-syntax first
  (syntax-rules ()
    ((_ expr)
     (call-with-values
       (lambda () expr)
       (lambda (x . y) x)))))

(if (first (values #t #f)) 'a 'b) <graphic> a

Since producer is most often a lambda expression, it is often convenient to use a syntactic extension that suppresses the lambda expression in the interest of readability.

(define-syntax with-values
  (syntax-rules ()
    ((_ expr consumer)
     (call-with-values (lambda () expr) consumer))))

(with-values (values 1 2) list) <graphic> (1 2)
(with-values (split '(1 2 3 4))
  (lambda (odds evens)
    evens)) <graphic> (2 4)

If the consumer is also a lambda expression, the multiple-value variant of let defined below might be even more convenient.

(define-syntax let-values
  (syntax-rules ()
    ((_ ((fmls e0)) e1 e2 ...)
     (with-values e0
       (lambda fmls e1 e2 ...)))))

(let-values (((odds evens) (split '(1 2 3 4))))
  evens) <graphic> (2 4)

(let-values ((ls (values 'a 'b 'c)))
  ls) <graphic> (a b c)

This version of let-values is restricted to binding one set of variables to the values produced by one expression. A more general implementation of let-values that binds more than one set of variables to corresponding sets of values is given on page 200.

The definitions of values and call-with-values (and concomitant redefinition of call/cc) below demonstrate that the multiple return values interface can be implemented entirely in Scheme. No error checking can be done, however, for the case in which more than one value is returned to a single-value context such as the test part of an if expression.

(define call/cc call/cc)
(define values #f)
(define call-with-values #f)
(let ((magic (cons 'multiple 'values)))
  (define magic?
    (lambda (x)
      (and (pair? x) (eq? (car x) magic))))

  (set! call/cc
    (let ((primitive-call/cc call/cc))
      (lambda (p)
        (primitive-call/cc
          (lambda (k)
            (p (lambda args
                 (k (apply values args)))))))))

  (set! values
    (lambda args
      (if (and (not (null? args)) (null? (cdr args)))
          (car args)
          (cons magic args))))

  (set! call-with-values
    (lambda (producer consumer)
      (let ((x (producer)))
        (if (magic? x)
            (apply consumer (cdr x))
            (consumer x))))))

Multiple values can be implemented much more efficiently [1], but this code serves to illustrate the meanings of the operators and can be used to provide multiple values in implementations that do not support them.

Section 5.8. Eval

Scheme's eval procedure allows programmers to write programs that construct and evaluate other programs. This ability to do meta programming should not be overused but is extremely handy when needed.

eval and the environment specifiers appear in the Revised5 Report but not in the the ANSI/IEEE standard.


procedure: (eval obj env-spec)
returns: value of the Scheme form represented by obj

env-spec must be an environment specifier returned by interaction-environment, scheme-report-environment, or null-environment. eval treats obj as the representation of an expression. It evaluates the expression in the specified environment and returns its value.

(define cons 'not-cons)
(eval '(let ((x 3)) (cons x 4))
      (scheme-report-environment 5)) <graphic> (3 . 4)

(define lambda 'not-lambda)
(eval '(lambda (x) x) (null-environment)) <graphic> #<procedure>

(eval '(cons 3 4) (null-environment)) <graphic> error

An implementation may extend eval to support other environments. An implementation may also permit obj to be the representation of a definition, but eval must not allow the creation of new bindings in a null or scheme-report environment. The effect of assigning (through the use of eval) a variable bound in a scheme-report environment is unspecified; thus, the environment may be immutable.


procedure: (scheme-report-environment version)
procedure: (null-environment version)
returns: see below

version must be an exact integer. This integer specifies a revision of the Revised Report on Scheme, i.e., the Revisedv Report on Scheme for version v.

scheme-report-environment returns a specifier for an environment that is empty except for all bindings defined in the specified report that are either required or both optional and supported by the implementation. null-environment returns a specifier for an environment that is empty except for the bindings for all syntactic keywords defined in the specified report that are either required or both optional and supported by the implementation.

scheme-report-environment and null-environment must accept the value of version that corresponds to the most recent Revised Report that the implementation claims to support, starting with the Revised5 Report. They may also accept other values of version. An error is signaled if the implementation does not support the given version.


procedure: (interaction-environment)
returns: an environment specifier

interaction-environment returns an environment specifier that represents an environment containing implementation-dependent bindings. This environment is typically the one in which the implementation evaluates expressions dynamically typed by the user.

R. Kent Dybvig / The Scheme Programming Language, Third Edition
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

http://www.scheme.com