tco　20160810.1712(in MELPA)
tail-call optimisation for Emacs lisp

概要

tco.el は、関数の末尾再帰を行うパッケージです。
末尾再帰というのは、関数呼び出しの自分自身を最後に再帰呼び出しする再帰パターンです。
関数型言語では定番の手法で、Schemeでは実装仕様で末尾再帰を要求してくる言語です。

それをループに置き換えることで末尾再帰の最適化が行えます。
最適化を行えばstack overflowを防げます。
defunの末尾再帰バージョンともいえる defun-tco マクロを使います。
これがあればSchemerら関数型言語ガチ勢もEmacs Lispを楽しめますね！！！

;; -*- lexical-binding: t -*-
(require 'tco)
(setq lexical-binding t)

;;; 1〜nの総和 (Σ(k=1..n) k)
(defun-tco sum (n &optional accum)
  "末尾再帰バージョン"
  (setq accum (or accum 0))
  (if (zerop n)
      accum
    (sum (1- n) (+ accum n))))
(defun sum0 (m &optional accum)
  "末尾再帰しないバージョン"
  (setq accum (or accum 0))
  (if (zerop m)
      accum
    (sum0 (1- m) (+ accum m))))

これをバイトコンパイルして計測したところ…

(sum 10)                                ; => 55
(sum0 10)                               ; => 55

(benchmark-run 1000 (sum 500))          ; => (1.208836634 7 0.7694204509994051)
(benchmark-run 1000 (sum0 500))         ; => (1.2184165589999998 7 0.7778593409998393)

速度は変わっていません。

大きな数を指定するとstack overflowになってしまいます。

(setq max-lisp-eval-depth 600)
(sum 300)                               ; => 45150
(sum0 300)                              ; => error
;; (error "Lisp nesting exceeds `max-lisp-eval-depth'")

追記:sum0がsumを呼ぶというドジを踏んでしまい変なことを書いてしまいました。
申し訳ありませんでした。御指摘感謝です。

インストール

パッケージシステムを初めて使う人は
以下の設定を ~/.emacs.d/init.el の
先頭に加えてください。

(package-initialize)
(setq package-archives
      '(("gnu" . "http://elpa.gnu.org/packages/")
        ("melpa" . "http://melpa.org/packages/")
        ("org" . "http://orgmode.org/elpa/")))

初めてtcoを使う方は
以下のコマンドを実行します。

M-x package-install tco

アップグレードする方は、
以下のコマンドでアップグレードしてください。
そのためにはpackage-utilsパッケージが必要です。

M-x package-install package-utils (初めてアップグレードする場合のみ)
M-x package-utils-upgrade-by-name tco


本日もお読みいただき、ありがとうございました。参考になれば嬉しいです。