Create a gist now

Instantly share code, notes, and snippets.

; 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.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment