public
Last active

  • Download Gist
lazy-tails.scm
Scheme
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70
; 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.

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.