Quickdocs

Q

ptc

2023-10-21

Proper Tail Calls for CL

Upstream URL

gitlab.common-lisp.net/frideau/ptc

Author

Francois-Rene Rideau

License

MIT
README
Provided Systems

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" (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:

(ptc:proclaim-proper-tail-calls)

To declaim that the current file should be compiled with proper tail calls, invoke the following macro:

(ptc:declaim-proper-tail-calls)

Note that the latter is notionally equivalent to:

(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:

(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:

#.ptc:=declare-proper-tail-calls=

Thus a safe-for-space read-eval-print-loop would look like so:

(ptc:with-proper-tail-calls ()
  (defun perp ()
    (print (eval (read)))
    (perp)))

Or:

(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.

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):

(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

Dependencies (0)

    Dependents (1)

    • scribble
    • GitHub
    • Quicklisp