How is let* Defined in Chez Scheme/Racket?

Question

How is let* defined in Chez Scheme/Racket? In particular, why does this first example evaluate to 6...

(let* ((let +) (a (let 2 4)))
    a)

...when my understanding from exercise 3.1.3 is that let* can be expanded to nested let (or even nested let*) statements, but expanding the above example as one would expect the interpreter to do results in an error?

(let ((let +))
    (let (a (let 2 4))
        a))

Is the implementation different than in the exercise? I would expect that first example to also result in an error due to the new definition of let.

Answer 1

(let* ([let +] [a (let 2 4)]) a)

becomes

(LET ([let +]) (LET ([a (let 2 4)]) a))

where LET refers to the let "macro" at the place where let* is defined (as Chris wrote: "hygiene").

When this is evaluated, LET will bind the value of + to let. The the value of (let 2 4) is computed, and this is 6 (due to the binding of let). Then 6 is bound to a. Finally the body is evaluated, and since a is bound to 6, the result is 6.

Answer 2

Let's assume this definition of let* (I'm trying to make this as simple as possible, so it's not as "industrial-strength" as Racket's that Asumu Takikawa linked to):

(define-syntax let*
  (syntax-rules ()
    ;; base case
    ((_ () body ...)
     (let ()
       body ...))

    ;; recursive case
    ((_ (binding next ...) body ...)
     (let (binding)
       (let* (next ...)
         body ...)))))

Scheme has a concept called hygiene, which says that any free identifiers (i.e., identifiers that are not defined within the macro) in a macro will be bound to its value as of the macro's definition. In the case of the above let* macro, the free identifiers are let and let*, since they're not bound elsewhere (as binding, next, and body are) in the macro.

That means that within that macro, let and let* will have the values that were there at the time of the macro's definition, and user code (that surround the use of the macro) will not have an effect on the values of let and let* that are used.

One way to implement this hygiene is via renaming. So, with renaming, the above macro could be renamed as follows:

(define-syntax let*
  ;; bind g1 to current let, g2 to current let*
  (syntax-rules ()
    ((_ () g3 ...)
     (g1 ()
       g3 ...))
    ((_ (g4 g5 ...) g6 ...)
     (g1 (g4)
       (g2 (g5 ...)
         g6 ...)))))

Here, the g1 through g6 are generated temporary symbols, usually known as "gensyms" (after the Lisp function gensym, which creates such things). Notice that, because of the renaming, user code cannot affect the definition of let and let* within the macro, and also the macro's binding of binding, next, and body do not affect any user code that may use such identifiers within the body of the let*.

Footnote (in case your student wants a more in-depth treatment of this): For many Scheme implementations, gensyms are uninterned (they are not entered into the symbol pool, unlike ordinary symbols, which are all interned). Then, even if the user happens to correctly "guess" the identifiers generated by the renaming procedure (e.g., even if they happen to use g1, g2, etc. in the example above), they won't actually collide with the identifiers that the macro actually uses.

However, standard Scheme does not talk about uninterned symbols, and in the context of standard Scheme, all symbols are interned, and thus it's perfectly valid for a Scheme implementation to use interned symbols exclusively, even for gensyms. In such cases, it is possible to create ways to break hygiene by colliding with the renamed symbols.