Sketchy LISP |
Copyright (C) 2006,2007
Nils M Holm Buy a copy at Lulu.com |
An Introduction to Functional Programming in Scheme
| Previous Section | - Contents - Index - | Next Section |
Each point in an evaluation has a past and a future. The past is
gone and has condensed to a value. The future, which waits for its
past to complete, expects exactly that value. For instance, the
application of car in the following sample expression
waits for the completion of the application of reverse:
(car (reverse '(a b c)))
At the point where reverse returns, the past of the
evaluation has condensed to the value (c b a),
and the future can be expressed as a procedure application that awaits
that value:
(car _)
The underscore character represents the value that the future is waiting for.
Note that the procedure waiting for the past is always a single-argument procedure, even in expressions like
(+ (* 1 2 3) (* 2 3 4))
Although each * has three arguments and +
has two arguments, this expression can easily be broken up into a
past evaluating to one single value and a future expecting one single
argument at any point. The following sample reduction illustrates this:
(+ (* 1 2 3) (* 2 3 4)) -> (+ 6 (* 2 3 4)) ; (lambda (x) (+ x (* 2 3 4))) -> (+ 6 24) ; (lambda (x) (+ 6 x)) => 30
At the point where the first argument of + has
been evaluated (to 6), the future of the computation consists of a
procedure expecting that value in order to add it to
(* 2 3 4). The procedure that is forming
the future of the computation is constructed by replacing the
_, which marks the position where the past is expected
to complete, with a free variable:
(+ 6 _) becomes (+ 6 x)
and then performing the following transformation:
(+ x 6) becomes (lambda (x) (+ 6 x))
This transformation turns the expression into the body of a lambda function which binds the newly introduced free variable. Thereby the expression becomes a procedure.
In fact there were much more opportunities to split the above
example expression into a past and a future. Even the sub-expression
(+ 1 2 3) contains three points where
+ waits for a value:
(lambda (x) (+ x 2 3)) ; wait for 1 (lambda (x) (+ 1 x 3)) ; wait for 2 (lambda (x) (+ 1 2 x)) ; wait for 3
Each of the numeric arguments evaluates to itself. While it does
so, + waits for that part of the reduction to complete.
At each of these points, the process can be split into a past and
a future.
The future of a computation is also called its
continuation, and the
continuation of the current point in the process of an evaluation
is called the
current continuation.
For example, the current continuation of (f (g x))
at the point where (g x) returns is
(f _) or, after transforming it into a procedure:
(lambda (x) (f x))
Now imagine a procedure that captures the current continuation,
freezes it, and packages it for later use. Scheme has such a procedure and
it is called
call-with-current-continuation.
Because this name is a bit long, though, many Scheme implementation
abbreviate it to
call/cc. In
case your implementation has only the long variant, you can define
your own abbreviation using the definition:
(define call/cc call-with-current-continuation)
Call/cc is a single argument procedure expecting a
procedure of one argument. What it does is to capture the current
continuation and pass it to that procedure:
(call/cc f) -> (f #<continuation>)
where #<continuation> represents the captured
continuation.
To prepare the continuation for later use, call/cc
reifies
it, which is basically the same as the transformation
outlined above:
(f _) becomes (lambda (x) (f x))
So what you get is an ordinary procedure that constitutes the future
of a point in the evaluation of an expression. You can jump
to
that future by applying the reified continuation. When you decide to do
nothing with a captured continuation, nothing special happens.
Call/cc returns the return value of the procedure passed
to it:
(call/cc (lambda (k) 'foo)) => foo
When the captured continuation is applied to a value, this value
is returned by call/cc:
(call/cc (lambda (k) (k 'bar))) => bar
Of course, the application of k does have its own continuation. Because this is not obvious in the above example, here is a better one:
(f (call/cc (lambda (k) (g (k 'bar)))))
In this example, the continuation captured by call/cc
is (f _), and the continuation of (k 'bar)
is (g _).
Applying k melts the previously frozen continuation
which causes the problem that now there are two possible
futures for (k 'bar): (f _) and
(g _). So what Scheme does is to eradicate
the current future (g _) and establish
(f _) which is the future captured before:
(f (call/cc (lambda (k) (g (k 'bar))))) -> (f (g (#<continuation> 'bar))) -> (f 'bar)
The current continuation of (k 'bar)
is never reached and so g is never applied.
You could even do total nonsense in the future of the application
of a reified continuation - it would not matter as this example
illustrates:
(call/cc (lambda (k) (#f (k #t)))) => #t
The non-sensical application of #f is never reached.
The following sections will explain some things you can do with continuations.
The length procedure takes a proper
list as its
argument. Checking for an improper list takes linear time, because the
complete list has to be traversed before it can be recognized as an
improper one:
(define (checked-length x)
(letrec
((proper-list?
(lambda (x)
(cond ((null? x) #t)
((not (pair? x)) #f)
(else (proper-list? (cdr x))))))
(length
(lambda (x)
(cond ((null? x) 0)
(else (+ 1 (length (cdr x))))))))
(if (proper-list? x) (length x) #f)))
The checked-length procedure returns the length of a list or
#f in case an improper list is passed to it. To do so, it
has to traverse the list twice: once to check whether the last cdr part
of the list is () and another time to compute the length.
Of course, it would be nice if both of these tasks could be performed
in one loop. Unfortunately, this is not that simple:
(define (broken-length x)
(cond ((null? x) 0)
((not (pair? x)) #f)
(else (+ 1 (broken-length (cdr x))))))
While this procedure works fine for lists and correctly detects atomic arguments, its application to a dotted list has no normal form:
(broken-length '(a . b)) -> (+ 1 (broken-length 'b)) -> (+ 1 #f) => bottom
At this point, a continuation captured by call/cc could
avoid the application of + to #f.
The following version of checked-length uses call/cc
to implement a so-called
non-local exit:
(define (checked-length-nl x)
(call/cc (lambda (exit)
(letrec
((length
(lambda (x)
(cond ((null? x) 0)
((not (pair? x)) (exit #f))
(else (+ 1 (length (cdr x))))))))
(length x)))))
A non-local exit is a facility that bypasses the normal flow of
evaluation. The broken-length procedure uses a local exit
by just returning #f when an improper list is detected.
However, this value might be passed back to outer
instances
of broken-length which attempt to apply +
to this value. In the checked-length-nl procedure, the
exit continuation is used to exit from all
recursively called instances of the length procedure
at once. This is how it works:
The first thing that is applied inside of checked-length-nl
is call/cc. It captures the continuation of its own application
and passes it to its argument which binds the continuation to
exit. Inside of this context, length is defined
and applied to the list. When length detects an improper
list, it applies exit. This application discards the
current continuation of (exit #f) and establishes
the continuation saved at the beginning:
(checked-length-nl '(a . b)) ; the exit continuation is captured here -> (length (a . b)) -> (+ 1 (length b)) -> (+ 1 (exit #f)) => #f
You might wonder what the continuation captured by call/cc
in checked-length-nl looks like, because there does not seem
to be anything to do after the return of call/cc. In fact
there is something to to: checked-length-nl has to
return the value passed to the continuation. This operation can be
thought of as applying the
identity function
(lambda (x) x):
(+ 1 (length b)) -> (+ 1 (exit #f)) -> ((lambda (x) x) #f) => #f
Because adding an application of the identity function to any expression does not change the meaning of that expression, this is a useful tool for understanding continuations in expressions like this:
(call/cc (lambda (k) (#f (k 'foo))))
What does the continuation that is bound to k in this expression look like? Adding an application of the identity functions clarifies things:
((lambda (x) x) (call/cc (lambda (k) (#f (k 'foo)))))
The continuation is an application of identity:
((lambda (x) x) _)
What makes continuations special is that they are first class objects with indefinite extent. A first class object is an object that can be bound to variables, passed to procedures and returned by procedures. You can do this with all Scheme objects except for keywords. An object with indefinite extent exists as long as at least one variable refers to it (directly or indirectly through a list or vector). Only when the last reference to the object is broken, the object becomes garbage and is recycled. All Scheme objects have indefinite extent.
Because continuations are first class objects and have
indefinite extent, they can escape from the
dynamic context of
call/cc, as the following trivial example illustrates:
(call/cc (lambda (k) k)) => #<continuation>
The dynamic context of call/cc is the procedure
passed to it. When this procedure returns, the dynamic context of
call/cc vanishes. In the above example, the identity
function returns the continuation passed to it, so when the application
of call/cc returns, the continuation can be bound to a
symbol for later use. Even resuming the continuation at a later time
does not invalidate it. Because it captures the complete future
of a point in an evaluation, it can be applied any number of times,
which opens the door to a whole load of brain-twisting puzzles. Here
is a rather simple one:
(let ((x (call/cc (lambda (k)
(cons k 'foo)))))
(let ((k (car x))
(v (cdr x)))
(cond ((eq? v 'foo) (k (cons k 'bar)))
((eq? v 'bar) (k (cons k 'baz)))
(else v))))
The value x is bound to consists of a continuation and a symbol:
(#<continuation> . foo)
Because continuations are first class objects, they can be stored
in structures like lists or pairs. The second let
decomposes the structure, binding the continuation to k
and the symbol to v. The next action depends on the symbol.
Because it is foo when cond is entered,
the following body is evaluated:
(k (cons k 'bar))
And this is where the fun begins. The object that is passed to
the continuation is equal to the original structure only with
foo replaced by bar:
(#<continuation> . bar)
The continuation stays the same. But what does the captured
future look like in this example? It is the point where the
reduction of a value to be bound in let returns,
but the corresponding binding is not yet established. When k
is applied, the flow of the program kind of travels back in time
to the point where the value returned by call/cc is
bound to x. Instead of the originally specified value
(#<continuation> . foo)
call/cc this time returns
(#<continuation> . bar)
To let there is no difference to the first time
the value of x reduced. It binds the new value and
evaluates the cond expression in its body. The same
procedure is carried out again, this time replacing bar
with baz. The case that v is bound to
baz is not specified in cond, so it
falls through and the value of v is returned.
Let returns baz and the continuation
is finally recycled.
And now for the gory details that this section promised to
reveal. In fact call/cc is not hard to grasp. What
is hard to grasp are all the subtle little details
that the Scheme language encompasses. Call/cc
discloses some details that would pass unnoticed without its
existance. Whether this is a good thing or not is debatable.
The order of evaluation of arguments is undefined in Scheme. This means that the expressions passed to a procedure expecting multiple arguments can be evaluated in any order. You cannot tell which of the arguments a, b, and c in
(f a b c)
will be evaluated first, which second, and which last. Any combination is possible. As long as the sub-expressions a, b, and c do not have any side effects, the order of evaluation does not change the meaning of the application, so each Scheme implementation is free to choose the order of evaluation which is most efficient. If multiple sub-expressions have side effects, these side effects occur in some unspecific order:
(letrec
((print-and-return
(lambda (x) (display x)
x)))
(+ (print-and-return 2)
(print-and-return 3)
(print-and-return 4)))
=> 9
While this expression is guaranteed to evaluate to 9, it may
print any permutation of the values 1, 2, and 3. This is the reason
why begin cannot be expressed as a lambda function:
(lambda x (car (reverse x)))
would evaluate its arguments and return the normal form of the last one of them, but the order in which the arguments are evaluated would be undefined.
The following rather simple example exposes the order of sub-expression evaluation without using I/O:
(call/cc (lambda (k)
(#f (k 'left-to-right)
(k 'right-to-left))))
Because evaluating either of the both applications of k abandons the rest of the evaluation of this expression and returns the argument of k immediately, the expression will reduce to the argument of the k that is applied first. However, the result obtained from this expression does not really help. All it demonstrates is that the order of evaluation is left-ro-right or right-to-left in this particular situation. It does not consider the fact that an optimizing compiler still might re-order arguments of other applications in any way that may lead to more efficient code.
The following expression shows that
letrec
actually
does mutate bindings in order to create a recursive structure:
[Footnote: This test was posted to Usenet by Al Petrofsky on
2005-03-23 using Message-ID <87ll8effvu.fsf@petrofsky.org>.]
(letrec ((x (call/cc list)))
(if (pair? x)
((car x) (lambda () x))
(pair? (x))))
=> #f
As in an earlier example, x is bound to a structure (this time a list) containing a continuation. A list is a pair, so the continuation is applied to
(lambda () x)
Lambda freezes the outer context which includes the
current binding of x. The value of x is still a list
containing a continuation at this point. The binding is included in
the lexical environment of the resulting procedure. Lexical environments
of procedures cannot be changed by applicative programs like the above
one, so the value of x should not change.
The procedure is passed as an argument to the continuation
(car x). Evaluation continues at the point where
letrec binds its arguments. This time x
is bound to the procedure returned by (lambda () x).
A procedure is not a pair, so
(pair? (x))
is evaluated by cond and obviously
(x)
evaluates to a non-pair, or the whole expression would not evaluate
to #f. However, the value contained in the lexical environment
of (lambda () x) was a pair,
so that value must have changed at some point between the creation of the
procedure and the application of cond.
The only construct that was in between was letrec,
and what happened is this: When call/cc returns for
the second time, it evaluates to the procedure resulting from
(lambda () x)
This procedure contains a lexical environment in which x
is bound to (#<continuation>). However, x
is exactly the variable that is bound by letrec, so
it is a recursive reference. Because letrec fixes
recursive references, it changes the binding of x in
the procedure to the value that it binds to x, resulting
in the following recursive structure:
(lambda () x) where
x = (lambda () x) where
x = ...
To prove that this effect is really caused by letrec,
it is sufficient to replace letrec with let
and show that the effect does not occur in the resulting
program:
(let ((x (call/cc list)))
(if (pair? x)
((car x) (lambda () x))
(pair? (x))))
=> #t
Indeed this expression evaluates to #t, leaving
letrec as the only possible cause for the mutation of
the lexical environment.
| Previous Section | - Contents - Index - | Next Section |