How not to de­fine log­i­cal OR in terms of IF in Scheme

Created: Tue Nov 27 15:39:11 CET 2018

Last mod­i­fied: Sat Feb 2 06:00:02 CET 2019


Might be use­ful when do­ing ex­er­cise 3.2.6 of TSPL3.

With the in­cor­rect de­f­i­n­i­tion of or be­low,

(define-syntax or
  (syntax-rules ()
    ((_) 'a)
    ;((_ e1) e1)
    ((_ e1 e2 ...)
     (let ((t e1))
       (if t t (or e2 ...))))))

the fol­low­ing de­f­i­n­i­tion of f would not be tail-re­cur­sive. I made (or) to re­turn 'a in­stead of #f, this is to pre­vent any optimization of the in­ter­preter.

(let f ((x 1))
  (if (zero? x)
      #t
      (or (f (- x 1))))

Here is the trace for (f 5) as shown by chez-scheme:

|(f 5)
| (f 4)
| |(f 3)
| | (f 2)
| | |(f 1)
| | | (f 0)
| | | #t
| | |#t
| | #t
| |#t
| #t
|#t

This is be­cause our call to f oc­cured in the list of de­f­i­n­i­tion of a let-block. Tail Call Optimization is not pos­si­ble there.

By un­com­ment­ing the sec­ond pat­tern/tem­plate pair in our de­f­i­n­i­tion of or, we get the fol­low­ing trace:

|(f 5)
|(f 4)
|(f 3)
|(f 2)
|(f 1)
|(f 0)
|#t

Showing that f is now tail-re­cur­sive.

Were we to re­de­fine f as be­low,

(let f ((x 1))
  (if (zero? x)
      #t
      (or (f (- x 1)) #t)))

that it would not be tail-re­cur­sive any­more be­cause our re­cur­sive call is no longer the last ac­tual ar­gu­ment of or and is not eval­u­ated as the al­ter­na­tive of an if in tail-call po­si­tion.

source code