Aziz,
(and any other compiler wizards in the audience)
Here's 'list-recursion' from yesterday:
(define (list-recursion f g h)
(define (rec fun lst)
(let loop ((lst lst))
(if (null? lst)
(f lst)
(let ((hd (car lst))
(tl (cdr lst)))
(let ((val (fun hd)))
(if val
(g loop val hd tl)
(h loop val hd tl)))))))
rec)
Here's a version of 'count' with an implementation based on the above:
(define (zero x) 0)
(define add-1-recur
(lambda (loop vl hd tl)
(+ 1 (loop tl))))
(define recur
(lambda (loop vl hd tl)
(loop tl)))
(define (count fun lst)
(let loop ((lst lst))
(if (null? lst)
(zero lst)
(let ((hd (car lst))
(tl (cdr lst)))
(let ((val (fun hd)))
(if val
(add-1-recur loop val hd tl)
(recur loop val hd tl)))))))
With this version, there's a one-time up-front cost of 8 bytes:
(time (count odd? '()))
> running stats for (count odd? '()):
no collections
0 ms elapsed cpu time, including 0 ms collecting
0 ms elapsed real time, including 0 ms collecting
8 bytes allocated
Demonstrating that it stays at 8 bytes:
> (time (count odd? '(1 2 3 4 5 6)))
running stats for (count odd? '(1 2 3 4 5 6)):
no collections
0 ms elapsed cpu time, including 0 ms collecting
0 ms elapsed real time, including 0 ms collecting
8 bytes allocated
3
>
Now, consider the same definition of count, with the 'add-1-recur' and
'recur' control flow combinators inlined:
(define (zero x) 0)
(define (count fun lst)
(let loop ((lst lst))
(if (null? lst)
(zero lst)
(let ((hd (car lst))
(tl (cdr lst)))
(let ((val (fun hd)))
(if val
(+ 1 (loop tl))
(loop tl)))))))
Zero allocation:
> (time (count odd? '()))
running stats for (count odd? '()):
no collections
0 ms elapsed cpu time, including 0 ms collecting
0 ms elapsed real time, including 0 ms collecting
0 bytes allocated
0
> (time (count odd? '(1 2 3 4 5 6)))
running stats for (count odd? '(1 2 3 4 5 6)):
no collections
0 ms elapsed cpu time, including 0 ms collecting
0 ms elapsed real time, including 0 ms collecting
0 bytes allocated
In principle, can a compiler be smart enough to perform the inlines so
as to achive the zero-allocation behaviour? Or is there something about
the design of the combinator itself which prevents this?
Ed
