I'm reading the scheme programming language, in chapter 3, the book use define-syntax to define or and and procedure, and it says the following definition of or is incorrect:
(define-syntax or ; incorrect!
(syntax-rules ()
[(_) #f]
[(_ e1 e2 ...)
(let ([t e1])
(if t t (or e2 ...)))]))
And the correct definition is:
(define-syntax or
(syntax-rules ()
[(_) #f]
[(_ e) e]
[(_ e1 e2 e3 ...)
(let ([t e1])
(if t t (or e2 e3 ...)))]))
Why the correct definition need three conditions? I run many tests, the two definitions produce the same results. How can tell me why the first definition is wrong?
Let's consider the hint from the book.
First we define our own version of or
:
(define-syntax my-or ; incorrect!
(syntax-rules ()
[(_) #f]
[(_ e1 e2 ...)
(let ([t e1])
(if t t (my-or e2 ...)))]))
Then we look at the expression in the hint.
(letrec ([even?
(lambda (x)
(my-or (= x 0)
(odd? (- x 1))))]
[odd?
(lambda (x)
(and (not (= x 0))
(even? (- x 1))))])
(list (even? 20) (odd? 20)))
Let's look at the expansion (I edited the full expansion a little):
(letrec ([even? (lambda (x)
(let ([t (= x 0)])
(if t t (let ([t (odd? (- x 1))])
(if t t #f)))))]
[odd? (lambda (x) (if (not (= x 0)) (even? (- x 1)) #f))])
(list (even? 20) (odd? 20)))
The problem here is that the call to odd?
in (let ([t (odd? (- x 1))]) ...)
is not in tail position. For each loop the let
expression will allocate a new variable (on the stack or elsewhere) an eventually we have a memory problem.
In short: The semantics of or
is that in (or e1 ... en)
the last expression en
is in tail position. If we use the simple version of the my-or
macro, then
(my-or e1)
expands into
(let ([t e1])
(if t t #f))]))
and the expression e1
is not in tail position in the output.