# Proper Tail Calls for Common Lisp

## Rationale

Many people call Lisp a "functional programming language".
Yet, to truly support a functional programming style,
a language implementation must provide *proper tail calls*,
which isn't guaranteed by the Common Lisp Standard.
This package aims to bridge that gap.

## What Proper Tail Calls Are

Some people say
["tail call optimization"](https://wiki.c2.com/?TailCallOptimization) (TCO),
or "tail-call merging", or "tail-call elimination", or worse,
speak only of "tail recursion" inside a single function or
within a group of functions defined together.
However, *proper tail calls* are neither an "optimization" nor a specific
compiler implementation technique, and even less a technique restricted
to closed definitions.

*Proper tail calls* are a feature of a programming language's semantics,
wherein functions calling other functions in terminal position
do not cause a resource leak (and eventual exhaustion),
be it in stack space or heap space.

*Proper tail calls* work not just in "closed" settings,
for a function that calls itself, or
for a group of function defined together call each other, or
for functions that call other functions compiled as part of the same build.

*Proper tail calls* apply to calling functions defined in other modules,
where no recursion whatsoever is explicitly present, yet where it may happen
implicitly as part of future flows involving yet-unimagined
higher-order functions that may conditionally call other functions
pass to them as arguments,
that will be dynamically defined at the REPL by a programmer.

The future about how any existing functions will be used is unknown, yet
every function defined in the past is already guaranteed to be *safe-for-space*:
it will not leak any finite computing resource,
it will play nice with whatever functions defined in the future
may or may not lead to indefinite or merely long chains of tail calls
involving the past function.

## No guarantees from the Standard, but from Implementations

Now, the Common Lisp Standard does not mandate from conformant implementations
any provision about *proper tail calls*.
There is no standard way to guarantee that the programs that require it
will enjoy this important feature, or be able to detect that whether
the current evaluation environment does or doesn't support it.
And yet, the most prominent Common Lisp implementations seem to all provide
this feature to programs that know how to request it.

Therefore this trivial library aims at providing a portable way
for Common Lisp programmers to declare that their programs require
proper tail calls, without each of them having to figure out for
each past, present and future implementation what are the magic
incantations required to achieve this effect.

## Globally enabling proper tail calls

To proclaim at runtime (e.g. at the interactive REPL)
that from now on compilation should do proper tail calls,
call the following function:
```Lisp
(ptc:proclaim-proper-tail-calls)
```

To declaim that the current file should be compiled with proper tail calls,
invoke the following macro:
```Lisp
(ptc:declaim-proper-tail-calls)
```

Note that the latter is notionally equivalent to:
```Lisp
(eval-when (:compile-toplevel :execute) (proclaim-proper-tail-calls))
```

Note also that depending on your implementation,
these declaimations may or may not leak beyond the compilation of the current file.
Therefore, you must repeat it in every file that depends on the effect,
yet it might adversely affect other files if for whatever reason you ever
expect improper tail calls to happen.

There is currently no way to undo the effects
of these proclamations and declamations.

## Locally enabling tail calls

To ensure that some code definitions use proper tail calls,
you may wrap these definitions inside the following macro:
```Lisp
(ptc:with-proper-tail-calls ()
  ...definitions...)
```

To enable tail-calls in some lexical scope, insert the following
at any place where you could use a `(declare ...)` statement:
```Lisp
#.ptc:=declare-proper-tail-calls=
```

Thus a safe-for-space read-eval-print-loop would look like so:
```Lisp
(ptc:with-proper-tail-calls ()
  (defun perp ()
    (print (eval (read)))
    (perp)))
```

Or:
```Lisp
(defun perp ()
  #.ptc:=declare-proper-tail-calls=
  (print (eval (read)))
  (perp))
```

The reason we need a `#. interface` and cannot have a macro
expand into `(declare ...)` is that declaration processing happens
before the body of a function is macroexpanded, and
there is unhappily no such thing as a `declare`-macro
that would get expanded where a declaration is expected
(nor are there lambda-list-macros, or any such things, for the matter, etc.).
`ptc:with-proper-tail-calls` expands into a
`(locally ,ptc:=declare-proper-tail-calls= ...)`
statement that will hopefully achieve the desired effect.

Note that you should be careful not insert any further `(declare (optimize ...)`
declaration after that one that would undo the proper tail-call declaration.

## Supported implementations

Currenty, only SBCL and Clozure CL are supported for sure;
Allegro and LispWorks maybe.

 * SBCL: in SBCL, global settings do not leak to other files, and
   local settings do not otherwise interfere
   with `SPEED`, `SAFETY`, `DEBUG` settings.

 * Clozure CL: in CCL, global settings do leak to other files,
   but do not otherwise interfere with `SPEED`, `SAFETY`, `DEBUG` settings.
   Local settings do change the `DEBUG` quality to 2.

 * LispWorks: I have never really used it but another package similar
   to this one suggests to use `(DEBUG 0)`.
   https://github.com/rmoritz/trivial-tco/blob/master/src/trivial-tco.lisp

 * Allegro: I have never really used it but another package similar
   to this one suggests to use `(SPEED 3)`.
   https://github.com/rmoritz/trivial-tco/blob/master/src/trivial-tco.lisp

In otherwise unsupported implementations, we change the compilation quality settings
to `(SPEED 3) (DEBUG 1)` which in practice should achieve the desired effect,
but who knows?

## Special variables

In theory, it is possible to have proper tail calls
in presence of special variables
(a.k.a. dynamic scoping, a.k.a. "parameters" in Scheme,
a.k.a. the "reader" monad in Haskell, a.k.a. "scoped values" in Java):
```Lisp
(let ((*foo* ...) (*bar* ...)) ... (progv ...))
```

Indeed, when returning from the evaluation of such a series of such forms,
only the earliest restore value of each variable is needed, and sequences
of return frames that only restore special variable values can be merged.

Indeed, Chez Scheme and after it PLT Scheme and Guile do that correctly for
their "parameters" (as they call their equivalent of CL special variables), and
their "continuation marks" (which is their slightly more general mechanism).
Each parameter-restoring (delimited) continuation efficiently represents the
set of parameters that are to be restored (using persistent balanced trees?)
upon calling the continuation, and at run-time, a new continuation frame
is only created if that set is actually modified.

As far as I know, no Common Lisp implementation supports proper tail calls in
presence of special variable bindings, presumably because no one relies
on such proper tail-calls in current practice.

## Pointers

 * Why Object-Oriented Languages Need Tail Calls, by Guy Steele:
   https://web.archive.org/web/20110716163344/http://projectfortress.sun.com/Projects/Community/blog/ObjectOrientedTailRecursion
   Mirror for the deleted original at:
   http://projectfortress.sun.com/Projects/Community/blog/ObjectOrientedTailRecursion
   Another mirror by David Chase at:
   http://www.eighty-twenty.org/index.cgi/tech/oo-tail-calls-20111001.html
   Local copy in [ObjectOrientedTailRecursion.html](ObjectOrientedTailRecursion.html)

 * Tail Call Optimisation in Common Lisp Implementations
   http://0branch.com/notes/tco-cl.html

 * Another CL package promising "TCO":
   https://github.com/rmoritz/trivial-tco/blob/master/src/trivial-tco.lisp


Portably enable Proper Tail Calls in Common Lisp.

ptc

Upstream URL

Author

License

ptc

Version:

License:

Authors:

Dependencies:

Dependencies (0)

Dependents (1)