I have been told that the following expression is intended to evaluate to 0, but that many implementations of Scheme evaluate it as 1:
(let ((cont #f))
(letrec ((x (call-with-current-continuation (lambda (c) (set! cont c) 0)))
(y (call-with-current-continuation (lambda (c) (set! cont c) 0))))
(if cont
(let ((c cont))
(set! cont #f)
(set! x 1)
(set! y 1)
(c 0))
(+ x y))))
I must admit that I cannot tell where even to start with this. I understand the basics of continuations and call/cc
, but can I get a detailed explanation of this expression?
This is an interesting fragment. I came across this question because I was searching for discussions of the exact differences between
letrec
andletrec*
, and how these varied between different versions of the Scheme reports, and different Scheme implementations. While experimenting with this fragment, I did some research and will report the results here.If you mentally walk through the execution of this fragment, two questions should be salient to you:
Q1. In what order are the initialization clauses for
x
andy
evaluated?Q2. Are all the initialization clauses evaluated first, and their results cached, and then all the assignments to
x
andy
performed afterwards? Or are some of the assignments made before some of the initialization clauses have been evaluated?For
letrec
, the Scheme reports say that the answer to Q1 is "unspecified." Most implementations will in fact evaluate the clauses in left-to-right order; but you shouldn't rely on that behavior.Scheme R6RS and R7RS introduce a new binding construction
letrec*
that does specify left-to-right evaluation order. It also differs in some other ways fromletrec
, as we'll see below.Returning to
letrec
, the Scheme reports going back at least as far as R5RS seem to specify that the answer to Q2 is "evaluate all the initialization clauses before making any of the assignments." I say "seem to specify" because the language isn't as explicit about this being required as it might be. As a matter of fact, many Scheme implementations don't conform to this requirement. And this is what's responsible for the difference between the "intended" and "observed" behavior wrt your fragment.Let's walk through your fragment, with Q2 in mind. First we set aside two "locations" (reference cells) for
x
andy
to be bound to. Then we evaluate one of the initialization clauses. Let's say it's the clause forx
, though as I said, withletrec
it could be either one. We save the continuation of this evaluation intocont
. The result of this evaluation is 0. Now, depending on the answer to Q2, we either assign that result immediately tox
or we cache it to make the assignment later. Next we evaluate the other initialization clause. We save its continuation intocont
, overwriting the previous one. The result of this evaluation is 0. Now all of the initialization clauses have been evaluated. Depending on the answer to Q2, we might at this point assign the cached result 0 tox
; or the assignment tox
may have already occurred. In either case, the assignment toy
takes place now.Then we begin evaluating the main body of the
(letrec (...) ...)
expression (for the first time). There is a continuation stored incont
, so we retrieve it intoc
, then clearcont
andset!
each ofx
andy
to 1. Then we invoke the retrieved continuation with the value 0. This goes back to the last-evaluated initialization clause---which we've assumed to bey
's. The argument we supply to the continuation is then used in place of the(call-with-current-continuation (lambda (c) (set! cont c) 0))
, and will be assigned toy
. Depending on the answer to Q2, the assignment of 0 tox
may or may not take place (again) at this point.Then we begin evaluating the main body of the
(letrec (...) ...)
expression (for the second time). Nowcont
is #f, so we get(+ x y)
. Which will be either(+ 1 0)
or(+ 0 0)
, depending on whether 0 was re-assigned tox
when we invoked the saved continuation.You can trace this behavior by decorating your fragment with some
display
calls, for example like this:I also replaced
(+ x y)
with(cons x y)
, and invoked the continuation with the argument'new
instead of0
.I ran that fragment in Racket 5.2 using a couple of different "language modes", and also in Chicken 4.7. Here are the results. Both implementations evaluated the
x
init clause first and they
clause second, though as I said this behavior is unspecified.Racket with
#lang r5rs
and#lang r6rs
conforms to the spec for Q2, and so we get the "intended" result of re-assigning0
to the other variable when the continuation is invoked. (When experimenting with r6rs, I needed to wrap the final result in adisplay
to see what it would be.)Here is the trace output:
Racket with
#lang racket
and Chicken don't conform to that. Instead, after each initialization clause is evaluated, it gets assigned to the corresponding variable. So when the continuation is invoked, it only ends up re-assigning a value to the final value.Here is the trace output, with some added comments:
Now, as to what the Scheme reports really do require. Here is the relevant section from R5RS:
The first sentence of the "Semantics" sections sounds like it requires all the assignments to happen after all the initialization clauses have been evaluated; though, as I said earlier, this isn't as explicit as it might be.
In R6RS and R7RS, the only substantial changes to this part of the specification is the addition of a requirement that:
R6RS and R7RS also add another binding construction, though:
letrec*
. This differs fromletrec
in two ways. First, it does specify a left-to-right evaluation order. Correlatively, the "restriction" noted above can be relaxed somewhat. It's now okay to reference the values of variables that have already been assigned their initial values:The second difference is with respect to our Q2. With
letrec*
, the specification now requires that the assignments take place after each initialization clause is evaluated. Here is the first paragraph of the "Semantics" from R7RS (draft 6):So Chicken, and Racket using
#lang racket
---and many other implementations---seem in fact to implement theirletrec
s asletrec*
s.