tco.el
Tail call optimisation for Emacs lisp
tco.el provides tail-call optimisation for functions in elisp that call themselves in tail-position. Mutually recursive functions are unchanged.
It works by replacing each self-call with a thunk, and wrapping the
function body in a loop that repeatedly evaluates the thunk. Roughly
speaking, a function foo:
(defun-tco foo (...)
(...)
(foo (...)))Is rewritten as follows:
(defun foo (...)
(flet (foo-thunk (...)
(...)
(lambda () (foo-thunk (...))))
(let ((result (apply foo-thunk (...))))
(while (functionp result)
(setq result (funcall result)))
result)))Example
;; -*- lexical-binding: t -*-
(require 'tco)
(defun-tco sum (n &optional accum)
(setq accum (or accum 0))
(if (zerop n)
accum
(sum (1- n) (+ accum n))))
;; Without TCO, values greater than `max-lisp-eval-depth' (usually
;; 600) would cause stack overflow here:
(sum 700)Known issues
Due to a bug in cl-letf in Emacs 24.3.1, this package will not work on Emacs 24.3.1.
Other Projects
recur also offers TCO for self-tail recursion.
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent