bryan garza
Exploring Racket Forms: define and letrec 2016-03-11

Table of contents

A couple weeks ago I was trying to understand why expressions like this were valid:

(define (future-bound)
  (define (f) (+ x 1))
  (define x 5)
  (f))

Why can you define the x after its usage in f? I initially thought that define desugared into nested let's or perhaps let*, like this:

(let ([f (+ x 1)])
  (let ([x 5])
    f))

(let* ([f (+ x 1)]
       [x 5])
  f)

But neither made sense, since we still have the same problem of x being bound after f is bound. It turns out that define desugars into letrec:

(letrec ([f (λ () (+ x 1))]
         [x 5])
  (f))

This works because letrec initializes the bindings for each of the symbols, to something akin to undefined. After that, all bindings are initialized to their values at once. This allows bindings to reference others before those bindings' definitions exist. The value of x in f is only looked up once f is evaluated. We're referencing symbols statically, but the lookup is dynamic. That means anything any symbols referencing symbols that come after have to be wrapped in a lambda; if you try to look up too early, it won't work.

; Trying to reference a value immediately
(letrec ([six (+ x 1)]
         [x 5])
  #t)

Result:

Error: struct:exn:fail:contract:variable

x: undefined;
 cannot use before initialization

You can see this fails at the point that we try to look up x during the binding of six. Now using a lambda (and with let since it behaves in the same way and this example only binds one symbol anyways):

; loophole?
(let ([f (λ () (+ x 1))])
  f)

Here, x isn't bound anywhere, but f can still be bound and returned! But if we actually try to evaluate f, we'll run into problems.

; => Error: struct:exn:fail:contract
(let ([f (λ () (+ x 1))])
  (f))