why define-syntax of or in scheme need consider three conditions？

Question

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?

Mesnalty

Answer 1

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.

Mudra

I think you are right, but when I run "even?" with a larger number(run almost 10 minute) in chez scheme, I can not see memory occupation become more. The chez scheme only occupy 20M memory. – Mesnalty

I have a suspicion that the optimizer in Chez Scheme saves the day in this example. Try the example on a simpler Scheme implementation. – Mudra

You are right! When I run it in Racket, the procedure immediately run out of my memory! Think you for your explanation! – Mesnalty

Answer 2

It will works too

(define-syntax foo
  (syntax-rules ()
  ((_) #f)
  ((_ e) e)
  ((_ e1 e2 ...)
   (let ((t e1))
     (if t t (foo e2 ...))))))

Dative

Yes, in actually, the code you show me is the definition of "or" in r6rs, it is same as the correct definition which I give. But I want to know what is the defferent of the incorrect one and correct one? – Mesnalty