Created: Tue Nov 27 15:39:11 CET 2018
Last modiﬁed: Sat Feb 2 06:00:02 CET 2019
Might be useful when doing exercise 3.2.6 of TSPL3.
With the incorrect definition of
(define-syntax or (syntax-rules () ((_) 'a) ;((_ e1) e1) ((_ e1 e2 ...) (let ((t e1)) (if t t (or e2 ...))))))
the following definition of
f would not be tail-recursive. I made
(or) to return
'a instead of
#f, this is to prevent any
optimization of the interpreter.
(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 because our call to
f occured in the list of definition of a
let-block. Tail Call Optimization is not possible there.
By uncommenting the second pattern/template pair in our definition
or, we get the following trace:
|(f 5) |(f 4) |(f 3) |(f 2) |(f 1) |(f 0) |#t
f is now tail-recursive.
Were we to redeﬁne
f as below,
(let f ((x 1)) (if (zero? x) #t (or (f (- x 1)) #t)))
that it would not be tail-recursive anymore because our recursive call
is no longer the last actual argument of
or and is not evaluated as
the alternative of an
if in tail-call position.