CODEWITHSUNDEEP
functional-programmingschemelispracket
myy1966
myy1966

Reputation: 83

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

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?

Upvotes: 8

Views: 336

Answers (2)

soegaard
soegaard

Reputation: 31145

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.

Upvotes: 10

Hurry Blob
Hurry Blob

Reputation: 140

It will works too

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

Upvotes: -2

Related Questions