Implenting simultaneous bindings

Question

I'm writing a Lisp (code at GitHub) and I want to implement local bindings. Currently I have two syntaxes:

(let <var> <val> <expr>)

for binding a single variable or function, and

(with (<var1> <val1> ... <varN> <valN>) <expr>)

to bind multiple values at once.

At present, the bindings are evaluated sequentially, and each new function binding retains a copy of the environment it was defined in, so <var2> can refer to <var1> but not vice-versa.

I would like to modify the code so that when binding multiple values at once you effectively have simultaneous binding. For example, I would like to be able to write (this is a trivial example, but it should illustrate the idea):

(define (h y)
  (with ((f x) (if (eq? x 0) #t (g (- x 1)))
         (g x) (if (eq? x 0) #f (f (- x 1))))
  (f y))

At the moment this code doesn't run - g closes over f, but not the other way around.

Is there a canonical way to implement simultaneous binding in Lisp?

Answer 1

In SICP there's a section on internal definitions which covers this subject. In particular, the exercises 4.16, 4.18, 4.19 tell you how to implement different strategies for achieving simultaneous definitions.

The syntax is a bit different, but the idea in the book boils down to transforming this code:

(lambda <vars>
  (define u <e1>)
  (define v <e2>)
  <e3>)

Into this code:

(lambda <vars>
  (let ((u '*unassigned*)
        (v '*unassigned*))
    (set! u <e1>)
    (set! v <e2>)
    <e3>))

The same idea applies to your with special form. Take a look at the linked book for more implementation details.