This is an interesting snippet. I came across this question because I was looking for a discussion of the exact differences between letrec and letrec* and how they varied between different versions of Scheme reports and different implementations of Schema. Experimenting with this fragment, I did some research and will talk about the results here.
If you mentally go through the execution of this fragment, you will need two questions:
Q1. In what order are the initialization clauses evaluated for x and y ?
Q2. All initialization parameters are first evaluated, and their results are cached, and then all assignments x and y are fulfilled? Or some of the tasks done before some of the initialization sentences were evaluated?
For letrec , Scheme reports say the answer to Q1 is "unspecified." Most implementations actually evaluate sentences in order from left to right; but you should not rely on this behavior.
The R6RS and R7RS schema represent the new letrec letrec* binding construct, which sets the evaluation order from left to right. It also differs in other ways from letrec , as we will see below.
Returning to letrec , the schema report returns, at least until R5RS seems to indicate that the answer to Q2 "evaluates all initialization sentences before doing any tasks." I say "it seems that I am pointing out" because the language does not so clearly indicate that it is required, as it could be. In fact, many implementations of the Scheme do not meet this requirement. And this is exactly what is responsible for the difference between the "alleged" and "observed" behavior in your fragment.
Go through your fragment with Q2 in mind. First, we set aside two “locations” (control cells) for the x and y bindings. Then we evaluate one of the initialization clauses. Let's say this is a sentence for x , although, as I said, with letrec it can be one. We keep continuing this assessment in cont . The result of this evaluation is 0. Now, depending on the answer to Q2, we immediately assign this result to x or cache it for later assignment. Then we evaluate another initialization clause. We save its continuation in cont , overwriting the previous one. The result of this evaluation is 0. Now all initialization sentences have been evaluated. Depending on the answer to Q2, we could at this moment assign the cached result 0 to x ; or assignment x may already have occurred. In any case, y is now assigned.
Then we begin to evaluate the main part of the expression (letrec (...) ...) (for the first time). cont stored in cont, so we return it to c , then clear cont and set! each of x and y to 1. Then we call the resulting continuation with a value of 0. This returns to the last initialization clause --- which we assumed as y . Then, the argument we supply to the continuation is used instead of (call-with-current-continuation (lambda (c) (set! cont c) 0)) and y will be assigned. Depending on the response to Q2, assigning 0 to x may or may not take place (again) at this point.
Then we begin to evaluate the main part of the expression (letrec (...) ...) (for the second time). Now cont is equal to #f, so we get (+ xy) . Which will be either (+ 1 0) or (+ 0 0) , depending on whether 0 was reassigned to x when calling the saved continuation.
You can trace this behavior by decorating your fragment with some display calls, for example, as follows:
(let ((cont #f)) (letrec ((x (begin (display (list 'xinit xy cont)) (call-with-current-continuation (lambda (c) (set! cont c) 0)))) (y (begin (display (list 'yinit xy cont)) (call-with-current-continuation (lambda (c) (set! cont c) 0))))) (display (list 'body xy cont)) (if cont (let ((c cont)) (set! cont #f) (set! x 1) (set! y 1) (c 'new)) (cons xy))))
I also replaced (+ xy) with (cons xy) and inferred a continuation with the argument 'new instead of 0 .
I ran this snippet in Racket 5.2 using a couple of different “language modes”, as well as in Chicken 4.7. Here are the results. Both implementations first evaluated the x init clause and the y clause, although, as I said, this behavior is unspecified.
Racket with #lang r5rs and #lang r6rs meets the specifications for Q2, and therefore we get the "expected" result of resetting 0 another variable when calling the continuation. (When experimenting with r6rs, I needed to wrap the final result in display to see what it would be.)
Here is the trace output:
(xinit #<undefined> #<undefined> #f) (yinit #<undefined> #<undefined> #<continuation>) (body 0 0 #<continuation>) (body 0 new #f) (0 . new)
A #lang racket with #lang racket and chicken do not match this. Instead, after calculating each initialization clause, it is assigned to the corresponding variable. Therefore, when a continuation is called, it only ends with the assignment of the value to the final value.
Here is the trace output with some comments added:
(xinit #<undefined> #<undefined> #f) (yinit 0 #<undefined> #<continuation>) ; note that x has already been assigned (body 0 0 #<continuation>) (body 1 new #f) ; so now x is not re-assigned (1 . new)
Now about what Scheme reports really require. Here is the relevant section from R5RS:
library syntax: (letrec <bindings> <body>)
Syntax: <Bindings> must be of the form ((<variable1 <init1>) ...), and <body> must be a sequence of one or more expressions. It is a mistake for <variable> to appear more than once in a list of related variables.
Semantics: variables <variables> s are tied to new locations containing undefined values, values <init> s are evaluated in the received environment (in some unspecified order), each <variable> is assigned to the result corresponding to <init>, <body> is evaluated in the received environment and the value (s) of the last expression in <body> is returned. Each a <variable> binding has a complete letrec expression as its scope, which allows for the definition of mutually recursive procedures.
(letrec ((even? (lambda (n) (if (zero? n) #t (odd? (- n 1))))) (odd? (lambda (n) (if (zero? n) #f (even? (- n 1)))))) (even? 88)) ===> #t
One limitation on letrec is very important: you must evaluate each <init> without assigning or referencing the value of any <variable>. If this restriction is violated, then this is an error. Constraint is necessary because the scheme passes arguments by value, not by name. In most cases, the general use of letrec, all <init> s are lambda expressions, and the constraint is done automatically.
The first sentence of the Semantics sections sounds as if all assignments are fulfilled after all initialization sentences have been evaluated; although, as I said earlier, this is not as obvious as it could be.
In R6RS and R7RS, the only significant changes to this part of the specification are the addition of a requirement that:
the continuation of each <init> should not be called more than once.
R6RS and R7RS also add another binding construct, though: letrec* . This differs from letrec two ways. First, it determines the evaluation order from left to right. Accordingly, the “limitation” mentioned above can be somewhat relaxed. Now you can refer to the values of variables that have already been assigned their initial values:
It should be possible to evaluate each <init> without assignment or by referencing the value of the corresponding variable <variable> or <& variable GT; any of the bindings that follow it in <bindings>.
The second difference concerns our Q2. With
letrec* specification now requires that assignments be executed after each initialization clause. Here is the first paragraph of “Semantics” from R7RS (project 6):
Semantics: <variable> s variables are tied to new locations, each <& variable GT; assigned in order from left to right the result of the evaluation is the corresponding <init>, <body> is evaluated as a result of the environment and the values of the last expression in <body> are returned. Despite the fact that evaluations and assignment order are from left to right, each <variable> binding has a full letrec * expression as its scope, which allows you to define mutually recursive procedures.
So, chicken and racket using #lang racket --- and many other implementations - actually implement their letrec as letrec* s.