50

GitHub - Wilfred/tco.el: Tail call optimisation in Emacs lisp

 6 years ago
source link: https://github.com/Wilfred/tco.el
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

README.md

tco.el

Tail call optimisation for Emacs lisp

Build Status

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)
(setq lexical-binding 't)

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


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK