SICP: Could or be defined in lisp as a syntax conversion 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 the value is not true.

The way I want to approach it is to convert, for example (or bc) to

(if aa (if bb (if cc false))) 

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

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

and this, in turn, can be implemented through lambda, as in exercise 4.6. Now the problem is the definition of syma, symb, and symc; if, for example, the expression b contains a reference to the syma variable, then let will destroy the binding. So we must have that syma is not a character in b or c.

Now we are trapped; the only way I can see from this hole is to have characters that cannot be in any expression passed to eval. (This includes characters that could be conveyed by other syntax conversions).

However, since I do not have direct access to the environment in the expression, I am not sure if there is a reasonable way to create such characters; I think Common Lisp has a gensym function for this purpose (which would mean a sticking state in the metacircular interpreter that would jeopardize any simultaneous use).

Am I missing something? Is there a way to implement or without using gensym? I know that Scheme has its own gigabit macrosystem, but I have not watched how it works, and I'm not sure if this worked out under it.

Answer 1

I think what you can do here is to convert to a syntax extension where evaluating the various forms is not nested. You can do this, for example, by wrapping each form as a lambda function, and then the approach you use is fine. For example, you can do something like

 (or abc) 

in

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

(In fact, evaluating calls to lambda functions is still nested in if and let s, but the definition of lambda functions is in such a place that calling them in nested if and let does not cause difficulties with captured bindings.) This does not concern the issue of how you get the variables l1 - l3 and v1 - v3 , but that doesn’t mean they don't matter much, none of them are objects for lambda function bodies, so you don’t have to worry about whether they appear in the body or not . In fact, you can use the same variable for all results:

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

At this point, you are really just doing a circular scan of a more general form, for example:

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

and decomposition (or abc) is just

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

This approach is also used in the answer to Why (apply and '(1 2 3)) does not work (and 1 2 3) works in R5RS? . And none of this required GENSYM ing!

Answer 2

SICP provides you with two ways to implement or. One that treats them as special forms that are trivial and one as derived expressions. I'm not sure if they really thought you would see this as a problem, but can you do this by implementing gensym or changing the variable? and how you make derived variables as follows:

 ;; 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, make-var creates a new list every time it is called, even with the same argument. Since it has id , since the first element is variable? will identify it as a variable. Since this is a list, will it only match the lookup variable with eq? if it is the same list, therefore several nested or → combination tmp-vars will be considered as different using lookup-variable-value , since (eq? (list) (list)) => #f and special variables in lists, they will never obscure the character in the code.

This is influenced by eiod , written by Al-Petrofsky, who similarly implements syntactic rules. If you do not look at other implementations as spoilers, you should let it read.