つい最近まで知りませんでした…
Schemeを使っている方には「letで末尾再帰するときのアレをEmacsでも使えるようにする」というので通じるとは思うのですが…
総和っぽいのを求める関数を定義してみましょう。
(defun sum-rec (n &optional sum)
(if (<= 0 n)
(sum-rec (1- n) (+ n (or sum 0)))
sum))
(sum-rec 100) ;=> 5050
アルゴリズムも使い方もめちゃ簡単なのですが、この実装には問題があります。
Lispに限らずよくあるプログラミング言語には、関数呼び出しの「深さ」と、その上限という概念があります。関数呼び出しをして、呼び出された関数から関数を呼ぶと深さは1追加され、その関数が実行終了すると深さは1減ります。
なぜこの呼び出しの深さという数が大事なのかというと、一般的なプログラムでは繰り返し関数を呼び出したときに制御を管理したりデバッグしやすくする情報を持っておくためにコールスタックというデータ構造を持っています。コンピュータのメモリは無限ではないので、関数呼び出しを深く深くしていくとコールスタックにメモリを食い潰されてしまいます。そうならないようにEmacsでも呼び出し回数のリミットが設けられています。
よくある普通のプログラミングでこの「深さ」の制限を意識することは少ないと思いますが、上のsum-rec関数のように関数から自分自身を呼び出すと途端にこの制限にぶつかりやすくなります。
この実装では(sum-rec 100)では問題ありませんが、(sum-rec 1000000)のように、数を増やすだけで実行時エラーが発生するようになります。
解決策は2つです。
- A. 再帰呼び出ししないようにループに書き直す
- B. 末尾呼び出し最適化(TCO, tail-call optimization)に期待する
Aはわかりやすいですね。
;; whileを使う場合
(defun sum-while (n)
(let ((sum 0))
(while (<= 0 n)
(setq sum (+ sum n))
(setq n (1- n)))
sum))
いいのですが、関数プログラミングが好きな我々の皆さんからは、明示的な状態の更新を伴うコードはエレガントではないとなじられます。
Bの末尾呼び出し最適化ですが、これはどの言語にもあるものではありません。Lisp一族の中でもSchemeというやつは末尾呼び出しされていればコールスタックを消費しないことが言語仕様で要求されている(なんでも再帰)ということですが、Emacs Lispにはそんなものはありませんでした。
12年ほど前、SICP(計算機プログラムの構造と解釈)という教科書で「SchemeもEmacs Lispも似たようなもんだろ」とたかをくくってEmacs Lispで課題を解き始めたら序盤で立ち塞がったのがレキシカルスコープと末尾再帰でした。
だが、今は違う！ Emacs Lispにもnamed-letが実装された！
;; named-letで書き換える
(defun sum-named-let (init)
(named-let loop ((n init) (sum 0))
(if (<= 0 n)
(loop (1- n) (+ n sum))
sum)))
これは (named-let loop ((var-1 初期値) (var-2 初期値)) ...) のような構造になっています。(loop (1- n) (+ n sum))のように自分自身を関数として呼び出している… ように見えますが、これは実際にはマクロでコールスタックを消費しないループに書き換えて実行されます。
気になる人は上記のコードをM-x pp-macroexpand-last-sexpなどで評価してどんなコードに展開されるか見てみたり、それを直接実行したりしてみてください。ここでは深く説明しません。
上記のような数学的な関数のようなものじゃなくてもnamed-letに展開することで明示的な変数の更新を避けることができます。
……まあ、展開されたコードを見た方ならおわかりの通り展開されたコードでは普通にwhileとかsetqが出てきます。
ただこれは、「愚直なコードを最初から自分で書く」か、「白鳥は水上では優雅に泳いでいるが、水面下では沈まないように必死に足をこいでいる」という話の通り人から見られる水上(Lispファイルのコード上)では優美さを保ち、「泥くさい処理はコンパイラの最適化に任せる」ということでもあります。
パフォーマンス
macOS上のGNU Emacs 30.1でチェックしてます。
This is GNU Emacs 30.1 (build 2, aarch64-apple-darwin24.3.0, NS
appkit-2575.40 Version 15.3.1 (Build 24D70)) of 2025-03-31
以下のコードを評価してみましょう。
(benchmark-progn
(sum-while 10000000))
(benchmark-progn
(sum-named-let 10000000))
;; バイトコンパイルしていない状態
Elapsed time: 0.693803s
50000005000000 (#o1327461042265500, #x2d7988896b40)
Elapsed time: 1.795464s
50000005000000 (#o1327461042265500, #x2d7988896b40)
;; バイトコンパイルした状態
Elapsed time: 0.084081s
50000005000000 (#o1327461042265500, #x2d7988896b40)
Elapsed time: 0.094937s
50000005000000 (#o1327461042265500, #x2d7988896b40)
;; ネイティブコンパイルした状態
Elapsed time: 0.070898s
50000005000000 (#o1327461042265500, #x2d7988896b40)
Elapsed time: 0.074567s
50000005000000 (#o1327461042265500, #x2d7988896b40)
常にwhileの方が高速だけどnamed-letも全然遅くないですね。素晴らしい。
あとこういうベンチマークあるあるなのですが、現実的なユースケースで10000000回ループするなんてことは皆無なので、実際には全然差は出ません。書きたいように書きましょう。
compat vs named-let
compatはEmacs Lispの最新機能を過去バージョンに可能な限りバックポートしてくれる神パッケージなのですが… 残念ながら本稿執筆時点でのcompat 30.1.0.0時点でのnamed-letのバックポートは壊れています。
Emacs 27以下をサポートするパッケージで使用するのはひとまず見送った方が無難でしょう。 バグレポート送ったらメンテナーが一瞬で直してくれました。壊れてるとかぼやいてないで、問題に気付いたらすぐ報告するのがいいですね。
別解: loopマクロ最強伝説
わたくしloopマクロが大好きなもんで…
(defun sum-loop (n)
(cl-loop for i downfrom n to 1
sum i))
(benchmark-progn
(sum-loop 10000000))
;; バイトコンパイルしていない状態
Elapsed time: 0.732781s
50000005000000 (#o1327461042265500, #x2d7988896b40)
;; バイトコンパイルした状態
Elapsed time: 0.083695s
50000005000000 (#o1327461042265500, #x2d7988896b40)
;; ネイティブコンパイルした状態
Elapsed time: 0.071482s
50000005000000 (#o1327461042265500, #x2d7988896b40)
cl-loopはループ処理に相当するものはなんでもできる万能マクロで、map/reduce/filter/sum/concat/find/allみたいな集合に対する操作はこれひとつで賄えます。それで短く書けて、パフォーマンスも出るならこんなに素晴らしいことはないですね。
TMTOWTDI！
追記: ルロワ師、弟子を諭す
老師ルロワが、弟子と共に道を歩んでいた。
対話のきっかけを得ようと、弟子が師に問うた。
「師よ。ループはすべて、末尾再帰関数に置き換えるべきものと聞き及びましたが、それはまことでございましょうか？」ルロワは弟子を哀れむように一瞥し、こう答えた。
「愚かな弟子よ。多くの末尾再帰関数など、ただ非効率なループにすぎぬ」それから数週間、弟子はその言葉を信じ、末尾再帰関数を明示的なループに書き換える作業に没頭した。そしてついに、その成果を師に見せ、お墨付きを求めんとした。
ルロワは、その弟子を棒で打ち据え、言った。
「いつになれば学ぶのだ。明示的なループなど、貧者の末尾再帰関数ではないか」
その瞬間、弟子は悟りを開いた。
(初出: eigenclass - Some functional programming and OCaml koans)
Discussion