Schemeでdefineを使わずに超循環評価器を実装してみた
なぜか実装例が見つからなかったので…．リファレンス実装を御存知の方がおられましたら教えていただけないでしょうか（冒頭から懇願）．Common Lisp版でもいいですよ？（ぶしつけ）
超循環評価器とラムダ式
LISPでLISP評価器を定義する超循環評価器は原初LISP処理系からの伝統で，むしろ本来はその理論と考察が目的のひとつだったのが，その評価器がマシン語で実装されてしまったことから，プログラミング言語としてのLISPが始まったと言われています．
原初LISP処理系のラムダ式はダイナミックスコープであり，それゆえ，ラムダ式の引数に別のラムダ式を束縛することで，ラムダ式のみで再帰関数を定義することが容易でした．このため，このラムダ式（とcond，quote，car，cdr，cons，eq，atom）でLISP評価器を自己定義でき，万能チューリングマシンと等価と扱われる（チューリング完全）ことがあります．ただ，このラムダ式は，元となった理論であるラムダ計算の，そして，現在のプログラミング言語で主流の，レキシカルスコープのラムダ式とは異なる仕組みです．
その後のCommon Lispによる評価器やSchemeによるレキシカルスコープの評価器は，Common LispのdefunやSchemeのdefineを用いて実装されており，レキシカルスコープの局所環境ではなく，大域環境で名前定義し呼び出し可能とすることで再帰等が実現されています．型なしラムダ計算はチューリング完全であることが証明されており，わざわざラムダ式のみで超循環評価器を実装するまでもないという話はあります．ですが，たとえば単純型付きラムダ計算は意図的にチューリング完全ではなく，型付きを採用しているHaskellやStandard ML，OCamlなどの純関数型言語では，むしろ大域環境定義を併用して再帰を実現しています．
このため，『本当にレキシカルスコープのラムダ式だけで超循環評価器が実装できるの？』という素朴な疑問が湧き出たことから，実現に必要な記述方法を整理した上で，実際にSchemeで超循環評価器を実装してみた次第です．前置き長いよ．
ラムダ式による無名相互再帰
ラムダ式による再帰は，自己再帰であれば不動点コンビネータを用いて実現可能です．ですが，判断分岐やapplyによるラムダ式適用などの処理を行うには，evalとの相互再帰が必要になります．ラムダ式による相互再帰（無名相互再帰）は，mapやapplyで実装されたY*コンビネータを用いる方法が知られていますが，最小構成を想定する今回の超循環評価器で別途mapを定義するのは煩雑です．レキシカルスコープのラムダ式において，リスト結合などのユーティリティ関数の定義を様々な箇所で使用するための方法も欲しいところです．
そこで，まず上位ラムダ式で束縛した名前をお互いの引数とすることで相互再帰や関数呼び出しを実現する例を示したいと思います．次は，Schemeのdefineによる相互再帰定義で実装した，リスト内のアトム数を求める処理の記述例です（元は『森の中の木の葉を数える』アルゴリズムとして有名なものです）．
> (define (atoms lst)
(if (pair? lst) (atoms-p lst) 1))
WARNING: reference to undefined variable: atoms-p
> (define (atoms-p p)
(if (null? p) 0 (+ (atoms (car p)) (atoms-p (cdr p)))))
> (atoms '((a a) (a (a a) ((a) a (a) a)) a))
10
>
これを，上記の考え方に基づいて書き直したのが，次の無名相互再帰および関数呼び出しの記述例です．
> ((lambda (atoms atoms-p)
(atoms '((a a) (a (a a) ((a) a (a) a)) a) atoms atoms-p))
(lambda (lst atoms atoms-p)
(if (pair? lst) (atoms-p lst atoms atoms-p) 1))
(lambda (p atoms atoms-p)
(if (null? p) 0 (+ (atoms (car p) atoms atoms-p)
(atoms-p (cdr p) atoms atoms-p)))))
10
>
めんどくさいですね（本音）．普段のコーディングではまず使用しないなと感じると共に，大域環境のありがたみが身に沁みます．このことは，Excelベータ版で導入されたラムダ式にも言えることで，再帰をラムダ式のみで実装するよりも名前管理で定義する方がはるかに…記事の趣旨からズレましたのでここまでにします（ぐだぐだ）．
ラムダ式による超循環評価器の実装
前節を踏まえて作成したLISP評価器を，下記GitHubリポジトリにて公開しています．バグとかありましたらお知らせ下さい．あと，もっとエレガントな記述方法がありましたら…（冒頭からの続き）．
補足その1
ラムダ式の自己再帰については，Yコンビネータを擬似遅延評価で利用できるようにしたZコンビネータではなく，Uコンビネータを用いています．これは，不動点コンビネータ単体によるラムダ式の再帰駆動ではなく，不動点コンビネータの再帰呼び出し部分が再帰される関数定義本体に組み込まれているような形となっています（Zコンビネータをβ展開したラムダ式）．自己再帰のラムダ式ごとに記述する必要があるコンビネータであるためあまり知られていませんが，（カリー化されていない）複数の引数にも対応できることと，自己再帰関数単位で記述できることから，大域定義を想定しない今回のような事例に合っている表現方法かと思います．次のようなラムダ式のみワンライナー一発実行とか（またズレた）．
> (((lambda (u) (u u)) (lambda (u) (lambda (n a b) (if (< n 0) '() (cons a ((u u) (- n 1) b (+ a b))))))) 21 0 1)
(0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946)
補足その2
リポジトリには，超循環評価器の記述例であるmce.scmに加え，mce.scmからコピペで作成したmcemce.scmも置いてあります．いやあ，これこそ超循環評価器，そして，チューリング完全．
補足その3
リポジトリに，JavaScriptのラムダ式で作り直した記述例mcescm-js.jsを追加しました．要は移植なのですが，S式入出力部は作っておらず，次の例のように，JavaScriptの配列構文でLISPコードを表現するスタイルとしています．その関係で，リスト表現は内部的にもコンスセル構造ではありません．で，このJavaScriptの配列構文によるLISPコード表現で超循環評価器mce.scmを書き直したmcemcescm-js.jsも置いてあります．…さすがにやりすぎたかな．いやでも，ここまでやらないと超循環評価器とは言えないしなあ．カンマとシングルクォートの挿入がめんどうでした（月並な感想）．
JavsScript関係の実装については，別テーマ（他サイト記事参照）のためのリポジトリに移動させました．
mcescm-js.jsとmcemcescm-js.jsは，JavaScript実装のmcelisp-json-node.jsとJS
ON記述（ハッタリ半分）としてのmcelisp.jsonに分かれました．
補足その4
mce.scmを実行できるSchemeコードのeval-mce.scmを追加しました．mce.scmとの違いは，超循環評価器としての基本構文・関数にこだわらず，assqやmapなどを多用してコンパクトにまとめていることです．ただし，リポジトリ（この記事）の趣旨に沿って，defineだけは用いていません．30行もないのでここにベタ投下しますが，今後の修正等はリポジトリの方のみとなるかもしれません．
;;;;
;;;; Evaluator written in Scheme, without define, to run mce.scm
;;;;
;;;; This code is licensed under CC0.
;;;; https://creativecommons.org/publicdomain/zero/1.0/
;;;;
(display
(((lambda (U) (U U))
(lambda (U)
(lambda (S E)
(cond ((pair? S)
(let ((T (car S)) (V (cdr S)))
(cond ((eq? T 'quote) (car V))
((eq? T 'lambda) (append S `(,E)))
((eq? T 'cond)
(((lambda (M) (M M))
(lambda (M)
(lambda (P E)
(cond ((null? P) '())
(((U U) (caar P) E) ((U U) (cadar P) E))
(else ((M M) (cdr P) E)))))) V E))
(else
(let ((F ((U U) T E))
(A (map (lambda (X) ((U U) X E)) V)))
(cond ((pair? F)
((U U) (caddr F)
(append (map cons (cadr F) A) (cadddr F))))
((eq? F 'car) (caar A))
((eq? F 'cdr) (cdar A))
((eq? F 'cons) (cons (car A) (cadr A)))
((eq? F 'eq?) (eq? (car A) (cadr A)))
((eq? F 'pair?) (pair? (car A)))))))))
(else (cond ((memq S '(car cdr cons eq? pair? else)) S)
(else (cdr (assq S E)))))))))
(call-with-input-file "mce.scm" read) '())) (newline)
備考
更新履歴
- 2021-07-21：
eval-mce.scmに関する補足説明の追加 - 2021-07-21：JavaScript関係の別リポジトリへの移行について修正
- 2021-07-18：JavaScript版超循環評価器に関する補足説明の追加
- 2021-07-16：初版公開，
mcemce.scmに関する補足説明の追加
Discussion