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!

Answer 2

In SICP you are given two ways of implementing or. One that handles them as special forms which is trivial and one as derived expressions. I'm unsure if they actually thought you would see this as a problem, but you can do it by implementing gensym or altering variable? and how you make derived variables like this:

;; a unique tag to identify special variables
(define id (vector 'id))

;; a way to make such variable
(define (make-var x)
  (list id x))

;; redefine variable? to handle macro-variables
(define (variable? exp) 
  (or (symbol? exp)
      (tagged-list? exp id)))


;; makes combinations so that you don't evaluate
;; every part twice in case of side effects (set!)
(define (or->combination terms)
  (if (null? terms)
      'false
      (let ((tmp (make-var 'tmp)))
        (list (make-lambda (list tmp)
                           (list (make-if tmp 
                                    tmp 
                                    (or->combination (cdr terms)))))
              (car terms)))))


;; My original version
;; This might not be good since it uses backquotes not introduced 
;; until chapter 5 and uses features from exercise 4.6
;; Though, might be easier to read for some so I'll leave it.
(define (or->combination terms)
  (if (null? terms)
      'false
      (let ((tmp (make-var 'tmp)))
        `(let ((,tmp ,(car terms)))
           (if ,tmp
               ,tmp
               ,(or->combination (cdr terms)))))))

How it works is that make-var creates a new list every time it is called, even with the same argument. Since it has id as it's first element variable? will identify it as a variable. Since it's a list it will only match in variable lookup with eq? if it is the same list, so several nested or->combination tmp-vars will all be seen as different by lookup-variable-value since (eq? (list) (list)) => #f and special variables being lists they will never shadow any symbol in code.

This is influenced by eiod, by Al Petrofsky, which implements syntax-rules in a similar manner. Unless you look at others implementations as spoilers you should give it a read.