Racket seems fairly good at "lambda lifting", if that is the correct term. To demonstrate with adding the numbers from 1 to n: version 0 should pretty obviously be compiled into a loop; versions 1 and 2 are less obvious. In 64-bit "racket", versions 1 and 2 seem to take twice as long as the loop in version 0, but that's still much better than allocating lambdas; in 32-bit, the "twice as long" difference is smothered by the cost of allocating/GCing bignums. The last version is actually written in Arc, and 25x slower in arc3.1; though in 32-bit, the cost of handling bignums makes arc3.1 only 2x slower. The results of the 64-bit version seem to demonstrate that Racket successfully avoided allocating closures at runtime in all cases.
(define (sum0 n)
(let loop ((n n) (tt 0))
(if (zero? n)
tt
(loop (- n 1) (+ n tt)))))
(define sum1
(λ (n)
((λ (f n tt)
(if (zero? n)
tt
(f f (- n 1) (+ n tt))))
(λ (f n tt)
(if (zero? n)
tt
(f f (- n 1) (+ n tt))))
n
0)))
(define sum2
(λ (n)
((λ (f) (f f n 0))
(λ (f n tt)
(if (zero? n)
tt
(f f (- n 1) (+ n tt)))))))
(= sum3
(fn (n)
((fn (f n tt)
(if (is n 0)
tt
(f f (- n 1) (+ n tt))))
(fn (f n tt)
(if (is n 0)
tt
(f f (- n 1) (+ n tt))))
n
0)))
;Paste this command in, but copy the above to clipboard before running:
arc> (let xs (readall:pbpaste) (map [eval (list '$ _)] butlast.xs) (eval last.xs)
(each x '(sum0 sum1 sum2 _sum3) (repeat 2 (time:eval `(($ ,x) 10000000)))))
;64-bit racket v5.2.0.3: no mallocing beyond initial compilation
time: 41 cpu: 41 gc: 0 mem: 25720
time: 40 cpu: 41 gc: 0 mem: 6096
time: 80 cpu: 80 gc: 0 mem: 7576
time: 80 cpu: 80 gc: 0 mem: 6136
time: 81 cpu: 80 gc: 0 mem: 7576
time: 80 cpu: 80 gc: 0 mem: 6096
time: 1026 cpu: 1027 gc: 0 mem: 7408
time: 1018 cpu: 1019 gc: 0 mem: 6112
;32-bit racket v5.1.3.10: runtime is dominated by consing bignums
time: 894 cpu: 892 gc: 24 mem: 1478560
time: 872 cpu: 872 gc: 16 mem: 1236500
time: 841 cpu: 841 gc: 15 mem: 1238156
time: 844 cpu: 843 gc: 17 mem: 1236476
time: 839 cpu: 839 gc: 15 mem: 1237300
time: 838 cpu: 837 gc: 15 mem: -15541124
time: 1857 cpu: 1857 gc: 18 mem: 1237784
time: 1864 cpu: 1864 gc: 17 mem: 1236436
