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.

Because hygiene. (I'll write a longer answer later, if someone doesn't beat me to it.) — C. K. Young, Mar 27 '14 at 18:07
@ChrisJester-Young I understand this is a bizarre example, likely with no useful application. However, I'm teaching a young student who is learning functional programming for the first time (coming from Java), and finds amusement from trying to break the language. I wasn't sure about an answer to this. — cryptic_star, Mar 27 '14 at 18:26
If you actually want to see the implementation of `let*` in Racket, you can look at https://github.com/plt/racket/blob/master/racket/collects/racket/private/qq-and-or.rkt#L8 It's not pretty code though, because it has to be written in low-level Racket. — Asumu Takikawa, Mar 27 '14 at 18:54
@AsumuTakikawa Wow. That's head-explodey in the way that trying to read psyntax's implementation is. :-D — C. K. Young, Mar 29 '14 at 17:44
I think the need to deal with multiple values also makes it much more complex than the single value case. Plus the code Asumu points to defines `let-values`, `let*-values` and `letrec-values` at the same time (lines 152-154). — Metaxal, Mar 29 '14 at 18:10
In order not to scare rookies: The implementation in qq-and-or.rkt is not the normal way of defining macros in Racket. qq-and-or.rkt is part of the bootstrapping process, so it needs to be written in a *very* restricted way. It is straightforward to implement `let*` using "normal" Racket. — soegaard, Mar 30 '14 at 14:03

score 5 · Answer 1 · answered Mar 27 '14 at 18:43

(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.

C. K. Young · Accepted Answer · 2014-03-29T18:08:11.540

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.

score 0 · Answer 3 · answered Mar 27 '14 at 22:56

The official definition of let* from R7RS:

(define-syntax let*
  (syntax-rules ()
    ((let* () body1 body2 ...)
     (begin body1 body2 ...))

    ((let* ((name1 val1) (name2 val2) ...)  body1 body2 ...)
     (let ((name1 val1))
       (let* ((name2 val2) ...)
         body1 body2 ...)))))

This shows the let* expands into nested let expressions. Your error arises because Scheme hygienic macros do not confuse the let binding when let* is defined with the let bound in your use of let*.

The question is "How is let* defined in Chez Scheme/Racket?"; I provide the exact definition of `let*` and get down voted. Nice. That. — GoZoner, Mar 28 '14 at 13:56

How is let* Defined in Chez Scheme/Racket?

3 Answers3