lazy-tails.scm

; Trying to figure out tail call optimisation for normal-order Scheme

(define (fact x)
  (begin
    (define (rec y acc)
      (cond ((= y 0) acc)
            (else (rec (- y 1) (* y acc)))))
    (rec x 1)))

(fact 4)

; Applicative mode stack:

;.  (fact)
;.  (begin)
;.  .  (define)
;.  (rec)
;.  (cond)
;.  .  (=)
;.  (rec)
;.  .  (-)
;.  .  (*)
;.  (cond)
;.  .  (=)
;.  (rec)
;.  .  (-)
;.  .  (*)
;.  (cond)
;.  .  (=)
;.  (rec)
;.  .  (-)
;.  .  (*)
;.  (cond)
;.  .  (=)
;.  (rec)
;.  .  (-)
;.  .  (*)
;.  (cond)
;.  .  (=)

; Normal order stack:

;.  (fact)
;.  (begin)
;.  .  (define)
;.  (rec)
;.  (cond)
;.  .  (=)
;.  (rec)
;.  (cond)
;.  .  (=)
;.  .  .  (-)
;.  (rec)
;.  (cond)
;.  .  (=)
;.  .  .  (-)
;.  (rec)
;.  (cond)
;.  .  (=)
;.  .  .  (-)
;.  (rec)
;.  (cond)
;.  .  (=)
;.  .  .  (-)
;.  .  (*)
;.  .  .  (*)
;.  .  .  .  (*)
;.  .  .  .  .  (*)

; The final phase blows up the stack eventually.