--- Copyright 1994 Paul R. Wilson You may use these notes freely for noncommercial purposes, as long as this notice is preserved in all copies. --- LET and LETREC Letrec is a special form that is very similar to LET, with one minor difference that's useful in some situations. When a normal LET is evaluated, the initial value expressions for the variable bindings are evaluated BEFORE the variables are bound, and the evaluation occurs in the OUTER environment (i.e., not inside the LET's new environment). Then the variables are bound and the body expressions are executed in the new environment. With letrec, on the other hand, the variables are bound FIRST, then the initial value expressions are evaluated in the NEW environment, like the body expressions. Suppose you want to define a couple of local procedures, foo and bar, which need to call each other. (They might be mutually recursive procedures that implement a search, for example.) If you try to use a let this way: (let ((foo (lambda (x) ... (bar ...) ...)) (bar (lambda (x) ... (foo ...) ...))) ...) it won't work. The problem is that the lambda expressions are evaluated in the environment outside the let, before foo and bar are bound. So the lambda expressions will not refer to this foo and bar, but to whatever bindings of foo and bar exist in the outer environment. The same problem can occur with just one variable, if we want a local procedure that calls itself (let ((foo (lambda (x) ... (foo ...) ... ))) ... (foo) ...) What appears to be a recursive call isn't---it's a call to whatever foo evaluates to in the outside environment. To fix these, we just replace LET with LETREC. One tricky thing about letrec---it's not defined what order the evaluations take place, so don't write any code where the initial values depend on the OTHER initial values, e.g., (let ((foo (lambda (x) ... (bar) ...)) ; OK (bar foo) ; NOT OK ...) Here, the initial value of foo is required to initialize bar, which means that things will blow up if the value of bar is computed before the value of foo. Note, however, that the use of bar in the lambda expression is fine, because it depends on the binding of bar, but not the value in that binding---the value of bar is not required by the closure until the closure is actually called. Now that you've seen how it's typically used, you can probably understand why it's called LETREC---it's let for defining RECursive stuff. --- LET* Another sometimes-handy variant of LET is LET*, which binds several variables, but one at a time in the obvious order. So, for example, if you want to write have a local variable a, and then a local variable b that depends on a but not vice versa, you can use LET* like this (let ((a (foo quux)) (b (baz (+ quux a)))) ...) LET* is equivalent to a series of nested LETs, binding one variable each. The above example is equivalent to (let ((a (foo quux))) (let ((b (baz (+ quux a)))) ...)) Note that if we were talking about procedure variables, procedure b would be able to call procedure a by name, but not vice versa. A reference to b in the initial value expression of a will refer to whatever b refers to in the outer environment. --- USING CLOSURES TO IMPLEMENT RECORDS (Warning: this is just a demonstration of how you can do lots of hip things with closures. In most implementations, it's not nearly as fast to implement cons cells with closures as it is to use built-in cons cells. The real points are (1) that it is a nice example to reinforce your understanding of closures and environments, and (2) it demonstrates the deep similarities between procedural abstraction and data abstraction.) Suppose we had a language with no normal record-defining facilities, and no built-in record types---e.g., no cons cells---but we wanted to build them anyway. Let's use cons cells (pairs) as the example. We can build a reasonable (but not perfect) approximation of cons cells using closures if we want to. Recall that when we call a procedure and pass it arguments, it creates bindings to hold the argument values. (Arguments are bound as local variables. So we can write a procedure cons that takes two arguments, and capture its local binding environment and use it as a record. The only thing that can capture an environment is a closure. We will use the closure to capture the environment, and also to implement the operations on it. So to create a cons cell, we'll create both a new environment and a new closure to operate on that environment. We'll keep a pointer to the closure and think of it as a cons cell. The problem here is that the closure is just one procedure, but cons cells support several operations. We need a way of making that one procedure do each of the things a cons cell is capable of doing (i.e., storing a value in the car field, storing a value in the cdr field, fetching the car value, or fetching the cdr value). To make one procedure do several jobs, we'll write it so that it takes a special argument telling it which job we want it to do, and then dispatch on that argument to do the appropriate action. We use a symbol as the argument, and we pick the symbol with the name of the operation, but that's just to make things simple and readable. (define (cons car-val cdr-val) (lambda (operation argument) (cond ((eq? operation 'car) car-val) ((eq? operation 'cdr) cdr-value) ((eq? operation 'set-car! (set! car-value argument)) ((eq? operation 'set-cdr! (set! cdr-value argument)) ((eq? operation 'pair?) #t)))) OK, now we're set, except that our cons cells don't look like normal cons cells. Instead of saying (set-car! foo 10), we have to say things like (foo 'set-car! 10). (The way things are written above, that's especially awkward for car and cdr, because they only look at the "operation" argument, not the "argument" argument; you still have to pass in some value, which will be ignored, e.g., (foo 'car #f) or (foo 'car 'ignore-this). We can make this prettier by defining our own procedures car, cdr, set-car! and set-cdr!: (define (car x) (x 'car 'ignore-this)) (define (cdr x) (x 'cdr 'ignore-this)) (define (set-car! x value) (x 'set-car! value)) (define (set-cdr! x value) (x 'set-cdr! value)) Now we have a fairly passable approximation of cons cells, with one problem: when we ask something if it's a pair, we call it as a procedure. This is the wrong thing to do if it's NOT a procedure, or if it is a normal procedure and not one we're using as a cons cell. We can fix the former problem by defining our pair? procedure to check first to see if something is a procedure: (define (pair? x) (and (procedure? x) (x 'pair? 'ignore-me))) The other problem doesn't go away, however---we have to avoid using our "cons cells" in any context where we would have to discriminate between them and normal procedures. --- USING LETREC TO IMPLEMENT A MODULE Suppose we want to implement a procedure foo that has some private state variables and hidden helper procedures. Suppose, to make this tricky, that we want the helper procedures to be able to access each other and the private state, but we don't want the state or helpers to be visible to any procedure other than foo. We can do something like this: (define foo (letrec ((helper1 (lambda (x) ... private-var ... ... (helper2)...) (helper1 (lambda (x) ... (helper1)... ... private-var...) (private-var 22)) (lambda (x) ... (helper1 private-var)... ... private-var ... (helper2 ...) ...))) Notice that we used the normal variable definition syntax here, not the procedure definition syntax, so the letrec is executed just once, when we define the variable var (and compute its initial value). The letrec will create bindings for the variables helper1, helper2, and private-var. Then the initial value expressions will be evaluated in that environment. (Remember, for a LETREC we bind first, and evaluate initial value expressions inside the NEW environement.) That way, the closures created by the lambda expressions can see the bindings of their own and each others' names---they can call each other and see private-var. Once we've created this pleasant environment where the helpers can help each other and see the private data, we create the procedure that we'll call foo. The lambda expression creates a closure in the new environment and returns it. Since that's the last expression in the letrec, it's also returned as the value of the letrec and used as the initial value for the variable foo. Now we have a function foo that is visible in the outside world, and which has access to the special environment where the helpers are bound. It's a module, which exports some functionality (the function foo) and hides the rest. --- EXPORTING MULTIPLE FUNCTIONS FROM A MODULE Suppose that we wanted to do the above trick, but we want to have more than one function (say, two) that is visible to the outside, while having a bunch of others that are hidden. One way to do it would be to return a list of closures (whichever ones you want to export) as the value of the letrec, and then tear this list apart and assign the results into different publicly visible variables. Another way would be to return from the letrec a procedure that you can ask for pointers to other procedures. --- LET CAN BE IMPLEMENTED IN TERMS OF LAMBDA AND CALLING A let evaluates expressions to get initial values of variables, binds the variables and initializes them, and then evaluates the body expressiosn in the new environment. The same effect can be achieved by using a combination of LAMBDA and PROCEDURE CALLING. A lambda creates a procedure that will bind arguments and execute its body in that environment. By combining this with a procedure call expression, we can ensure that the initial values are computed and passed to the procedure. (let ((var1 init1) (var2 init2) ... (varn initn)) ) is translated into ((lambda (var1 var2 ... varn) ) init1 init2 ... initn) This is a procedure call expression whose first subexpression happens to be a lambda expression. The lambda expression will result in a procedure whose execution is equivalent to most of a LET---it will bind variables and execute a body. What's left out is that we need to evaluate the expressions for the initial values of the variables into the bindings. To do that, we just embed the lambda expression in a combination, and let the normal mechanism for procedure calls do the evaluation for us. (This depends on Scheme's ability to accept any kind of expression in the function position of a procedure call---we're putting an "anonymous" lambda there instead of the name of a procedure.) The initial value expressions of the let become the argument expressions to the procedure call. So what we're saying here is 1. evaluate the first subexpression (executing the lambda) to get a procedure value (a closure) back 2. evaluate the second subexpression (evaluating the variable bar) 3. apply the result of the 1st subexpression to the results of the remaining subexpressions, i.e., call the closure created by the lambda, passing it the value of bar as its argument. The first thing the closure will do when it is called is bind the argument variable foo and initialize it with the value it was passed (in this case, the value of bar). This is equivalent to binding the variable in the original let. Then it will evaluate the expressions in the body of the lambda, which is equivalent to executing the expressions in the body of the original let. --- LET, LAMBDA, and COMPILER ORGANIZATION Some compilers actually implement LET this way. The main part of the compiler doesn't understand LETs at all, but it's very good at compiling procedure calls and lambda expressions. An initial phase of the compiler recognizes LETs and transforms them straightforwardly into combinations with lambdas, as we did above. Then the main part of the compiler goes to work compiling what's left. The same strategy can be used for LETREC, LET*, named LET, DO, and so on, with an initial pass translating these constructs into the simpler language that the main compiler understands. This translation may be done by a macro facility, and these special forms may be written as simple macros. We will discuss macros later... don't worry if this isn't crystal clear right now. The important idea is that you have a compiler that's organized as two very different parts: one that does simple translations from a variety of user-friendly constructs into a simple but powerful base language, and another that is very good at optimizing complicated expressions in that powerful base languauge. (An advantage to this is that you can write a single general-purpose optimizer for the base language, and let people devise new high-level constructs that map onto the base langauge via macros.) --- On the other hand, don't assume that systems are implemented this way. If I ask you whether a LET creates a closure, the answer is NO, because at the language level, all LET does is create an environment and evaluate some subexpressions. Even if a particular implementation happens to create a closure and call it, that's not a NECESSARY, LANGUAGE-LEVEL feature of LET. It's a low-level fact about a particular implementation of LET. For our purposes, when we talk about environment and closure creation, we are talking about Scheme-level stuff, due to things like LETs and LAMBDAs in the program, unless we specify otherwise. It's irrelevant that a particular implementation might create more closure objects and/or environment frames (because of the above kind of implementation strategy) or fewer (because compiler optimizations take them out). --- IMPLEMENTING LOOPS WITH LETREC and LAMBDA We've said before that we don't need a looping construct to get iteration in Scheme---we can just use recursion instead, and if our recursive procedures never need to return, they don't use up an unbounded amount of stack space. Suppose we want a loop sort of like a while loop in Pascal (while ) We can get by without it, if we're willing to write something like this instead: (letrec ((loop (lambda () (if (begin (loop))))) (loop)) The guts of this solution is the lambda expression. It's just a procedure that will test the loop condition, and if it's true, evaluate the body expressions and then do a tail-call to itself to iterate. The letrec around the lambda expression is just there to give the looping procedure a name that it can see, so that it can call itself; we also use the body of the letrec to get the looping started by calling the looping procedure the first time. We can do the same thing to get a FOR loop which binds a variable. (for ( ) ) might become (letrec ((loop (lambda () (if (=< ) (begin (loop (+ i 1))))))) Notice that when the iterating procedure tail calls itself, it computes the next value of the iteration variable and passes that as an argument to the call. The next iteration will re-bind the variable and give it that value. This is the usual way iteration variables work in Scheme---at each iteration, the iteration variable is bound to a fresh location and initialized. As with LET, some compilers actually implement things loops this way. WHILE or FOR might just be a macro that expands to a letrec like this, and the compiler is smart enough to deal with letrec and lambdas and get good code---in effect, it optimizes the letrec and lambda away again, and gets machine code that looks like a plain old loop. (This might seem silly, but if you write one good optimizer you have the freedom to come up with a bunch of different macros that implement different control constructs, and you don't have to rewrite the main compiler to understand them.) NAMED LET Named LET is a general and flexible iteration construct that is really just syntactic sugar for a letrec and a lambda. (It looks like a LET, but it's usually used as a LOOP.) (let (( ) ( ) ... ( )) ) is equivalent to (letrec (( (lambda ( ... ) ) ( ... )) So, for example, if we wanted to write a for-like loop as a named let, (for (i 1 10) (display i)) could be written instead as (let loop ((i 1)) (if (=< i 10) (begin (display i) (loop (+ i 1))))) That's a little easier to write than an explicit letrec and lambda, but it's still a little awkward compared to using a while or for loop. Named LETs are very powerful, however: * Unlike most languages' for loops, the iteration variables can be any kind of value you want, not just numbers. At each iteration (tail call), yo might cons something onto a list, or pop something off of one. Or you might have two iteration variables, one that's being popped from and another that's being pushed onto... or whatever you want. * The fact that you have to name the loop comes in handy if you have nested loops and you want to be able to bail out of an iteration of the inner loop into the outer one, e.g., (let outer ((i 1)) ... (let inner ((j 1)) ... (if (things-going-normally?) (...) (outer (+ i 1)) ; bail out of this iteration of inner loop, ... ; going directly to start of outer loop * Even the body of a single non-nested loop can contain more than one point where the loop is iterated, and at each point it may use a different technique to compute the next value of the iteration variable(s). You're allowed to call the procedure that iterates a loop from anywhere the name is visible. (You're even allowed to save a pointer to the loop procedure and call it after the loop has exited.) * The variable bindings created at each iteration can be captured by lambda expressions. If the loop body contains a lambda expresion, a closure is created that captures the current bindings. If that closure is called later, it will operate on those bindings, even if the loop has iterated and new bindings have been created. You can use this to capture a state of a search, for example, and call that routine and have it still be able to operate on that old state. (WARNING: notice that closures capture bindings, but don't save the VALUES in those bindings. If somebody assigns to one of those bindings later, that change will be visible when to the closure that "captured the state" of the search---it didn't really capture the state, just the environment.)