RSS Feed

Lisp Project of the Day

trivial-tco

You can support this project by donating at:

Donate using PatreonDonate using Liberapay

trivial-tcolanguage

Documentation😀
Docstrings🥺
Tests 😀
Examples😀
RepositoryActivity🥺
CI 😀

This library could be considered as a portability layer for tail call optimization.

When I first found it, I decided it implements a TCO for implementations which do not support it by doing a trampolining trick like this. But I was wrong.

It does ensure the proper declaration is used on implementations which support a proper TCO and signals warning or error on others.

Here is an example on SBCL, which supports TCO only if speed declared to be greater or equal to debug:

POFTHEDAY> (declaim (optimize (debug 3) (speed 1))

POFTHEDAY> (labels ((sum-aux (acc x)
                        (if (zerop x)
                            acc
                            (sum-aux (+ acc x) (- x 1))))
                      (sum (n)
                        (sum-aux 0 n)))
               (sum 1000000))
Control stack guard page temporarily disabled: proceed with caution
; Debugger entered on #<SB-KERNEL::CONTROL-STACK-EXHAUSTED {1004F12E73}>
[1] POFTHEDAY> 
; Evaluation aborted on #<SB-KERNEL::CONTROL-STACK-EXHAUSTED {1004F12E73}>

POFTHEDAY> (tco:with-tail-call-optimization ()
             (labels ((sum-aux (acc x)
                        (if (zerop x)
                            acc
                            (sum-aux (+ acc x) (- x 1))))
                      (sum (n)
                        (sum-aux 0 n)))
               (sum 1000000)))
500000500000 (39 bits, #x746A5A2920)

This macro gets expanded into:

(let ()
  (declare (optimize (speed 3)))
  (labels ((sum-aux (acc x)
             (if (zerop x)
                 acc
                 (sum-aux (+ acc x) (- x 1))))
           (sum (n)
             (sum-aux 0 n)))
    (sum 1000000)))

That is it. Use this library, if you want to employ a tail call and want to ensure they a properly optimized by your Lisp implementation.

Maybe this article by Marc Simpson will be interesting for you. It investigates which Common Lisp implementations have a proper TCO implementation.


Brought to you by 40Ants under Creative Commons License