SICP: Can or be defined in lisp as a syntactic transformation without gensym?

Question

I am trying to solve the last part of question 4.4 of the Structure and Interpretation of computer programming; the task is to implement or as a syntactic transformation. Only elementary syntactic forms are defined; quote, if, begin, cond, define, apply and lambda.

(or a b ... c) is equal to the first true value or false if no value is true.

The way I want to approach it is to transform for example (or a b c) into

(if a a (if b b (if c c false)))

the problem with this is that a, b, and c would be evaluated twice, which could give incorrect results if any of them had side-effects. So I want something like a let

(let ((syma a)) 
     (if syma syma (let ((symb b)) 
                        (if symb symb (let ((symc c))
                                           (if (symc symc false)) )) )) )

and this in turn could be implemented via lambda as in Exercise 4.6. The problem now is determining symbols syma, symb and symc; if for example the expression b contains a reference to the variable syma, then the let will destroy the binding. Thus we must have that syma is a symbol not in b or c.

Now we hit a snag; the only way I can see out of this hole is to have symbols that cannot have been in any expression passed to eval. (This includes symbols that might have been passed in by other syntactic transformations).

However because I don't have direct access to the environment at the expression I'm not sure if there is any reasonable way of producing such symbols; I think Common Lisp has the function gensym for this purpose (which would mean sticking state in the metacircular interpreter, endangering any concurrent use).

Am I missing something? Is there a way to implement or without using gensym? I know that Scheme has it's own hygenic macro system, but I haven't grokked how it works and I'm not sure whether it's got a gensym underneath.

Answer 1

I think what you might want to do here is to transform to a syntactic expansion where the evaluation of the various forms aren't nested. You could do this, e.g., by wrapping each form as a lambda function and then the approach that you're using is fine. E.g., you can do turn something like

(or a b c)

into

(let ((l1 (lambda () a))
      (l2 (lambda () b))
      (l3 (lambda () c)))
  (let ((v1 (l1)))
    (if v1 v1
      (let ((v2 (l2)))
        (if v2 v2
          (let ((v3 (l3)))
            (if v3 v3
              false)))))))

(Actually, the evaluation of the lambda function calls are still nested in the ifs and lets, but the definition of the lambda functions are in a location such that calling them in the nested ifs and lets doesn't cause any difficulty with captured bindings.) This doesn't address the issue of how you get the variables l1–l3 and v1–v3, but that doesn't matter so much, none of them are in scope for the bodies of the lambda functions, so you don't need to worry about whether they appear in the body or not. In fact, you can use the same variable for all the results:

(let ((l1 (lambda () a))
      (l2 (lambda () b))
      (l3 (lambda () c)))
  (let ((v (l1)))
    (if v v
      (let ((v (l2)))
        (if v v
          (let ((v (l3)))
            (if v v
              false)))))))

At this point, you're really just doing loop unrolling of a more general form like:

(define (functional-or . functions)
  (if (null? functions)
      false
      (let ((v ((first functions))))
        (if v v
            (functional-or (rest functions))))))

and the expansion of (or a b c) is simply

(functional-or (lambda () a) (lambda () b) (lambda () c))

This approach is also used in an answer to Why (apply and '(1 2 3)) doesn't work while (and 1 2 3) works in R5RS?. And none of this required any GENSYMing!