Schemeでlambda/quote/if/eq?/procedure?のみで超循環評価器を実装してみた
『Schemeでdefineを使わずに超循環評価器を実装してみた』の続きです．自己満という名のポエム最高潮．あ，でも，もっとエレガントな実装がありましたらぜひ紹介して下さい差し替えますんで（誤用の方の他力本願）．
超循環評価器とcons/car/cdr
前記事の目的は『純LISPとかで示されている超循環評価器ってダイナミックスコープのラムダ式だよね，レキシカルスコープのラムダ式はできるの？』というのが発端で，相互再帰や自己再帰でなんとか実装できることを示しました．
ところで，この純LISPの解説やScheme系のプログラミング教科書などでは，基本関数であるcar cdr consも，他のプリミティブであるところのラムダ式（クロージャ）でたとえば次のように実装でき，必ずしも基本とは言えない旨が述べられています．
> (define (CONS x y) (lambda (m) (m x y)))
> (define (CAR z) (z (lambda (p q) p)))
> (define (CDR z) (z (lambda (p q) q)))
> (define a (CONS 10 20))
> (CAR a)
10
> (CDR a)
20
> (define s (CONS 10 (CONS 20 (quote ()))))
> (CAR s)
10
> (CAR (CDR s))
20
> (CDR (CDR s))
()
ただ，上記の方法は，評価器におけるプログラムコードの処理の基礎ともなっているリスト処理（list processing）を直接的に扱うことができないことなどから，最初から基本関数として組み込まれているのが普通であるとも述べられています．実際のところ，下記の通り，構築したコンスセル/リスト構造を直接確認できないのはとても不便です．
> (define (CONS x y) (lambda (m) (m x y)))
> (CONS 10 20)
#<procedure #f>
> (CONS 10 (CONS 20 (quote ())))
#<procedure #f>
現実問題として，cons car cdr相当を評価器内でラムダ式による実装で置き換えるのは難しくなく，むしろ，処理対象であるプログラムコードもラムダ式による実装で置き換える方がはるかに困難です．
たとえばサンプルコードとして，次の連想リスト処理を考えます．評価器がcons car cdrを基本関数としてもたないことを想定し，このサンプルコードでも自らラムダ式でcons car cdr相当を定義し利用しています．これ自体は，標準のScheme処理系で動きます．
((lambda (ASSQ CONS CAR CDR C3)
(CDR (ASSQ (quote B)
(C3 (CONS (quote A) (quote X))
(CONS (quote B) (quote Y))
(CONS (quote C) (quote Z)) CONS)
CAR CDR CONS)))
((lambda (U) (U U))
(lambda (U)
(lambda (K V CAR CDR CONS)
(if (eq? V (quote ())) (quote ())
(if (eq? K (CAR (CAR V))) (CAR V)
((U U) K (CDR V) CAR CDR CONS))))))
(lambda (X Y) (lambda (F) (F X Y)))
(lambda (C) (C (lambda (X Y) X)))
(lambda (C) (C (lambda (X Y) Y)))
(lambda (A B C CONS) (CONS A (CONS B (CONS C (quote ()))))))
;;;; => Y
ですが，このプログラムコードはS式表現であり，評価器がラムダ式によるcons car cdr相当しかない場合，そのラムダ式による実装で処理できるプログラムコードにする必要があります．評価器で実装されるcons相当が（区別のため）CSという関数であるとすると，上記のサンプルコードはCSを用いて次のように生成することとなります．
(CS (CS (quote lambda) (CS (CS (quote ASSQ) (CS (quote CONS) (CS (quote CAR) (CS (quote CDR) (CS (quote C3) (quote ())))))) (CS (CS (quote CDR) (CS (CS (quote ASSQ) (CS (CS (quote quote) (CS (quote B) (quote ()))) (CS (CS (quote C3) (CS (CS (quote CONS) (CS (CS (quote quote) (CS (quote A) (quote ()))) (CS (CS (quote quote) (CS (quote X) (quote ()))) (quote ())))) (CS (CS (quote CONS) (CS (CS (quote quote) (CS (quote B) (quote ()))) (CS (CS (quote quote) (CS (quote Y) (quote ()))) (quote ())))) (CS (CS (quote CONS) (CS (CS (quote quote) (CS (quote C) (quote ()))) (CS (CS (quote quote) (CS (quote Z) (quote ()))) (quote ())))) (CS (quote CONS) (quote ())))))) (CS (quote CAR) (CS (quote CDR) (CS (quote CONS) (quote ()))))))) (quote ()))) (quote ())))) (CS (CS (CS (quote lambda) (CS (CS (quote U) (quote ())) (CS (CS (quote U) (CS (quote U) (quote ()))) (quote ())))) (CS (CS (quote lambda) (CS (CS (quote U) (quote ())) (CS (CS (quote lambda) (CS (CS (quote K) (CS (quote V) (CS (quote CAR) (CS (quote CDR) (CS (quote CONS) (quote ())))))) (CS (CS (quote if) (CS (CS (quote eq?) (CS (quote V) (CS (CS (quote quote) (CS (quote ()) (quote ()))) (quote ())))) (CS (CS (quote quote) (CS (quote ()) (quote ()))) (CS (CS (quote if) (CS (CS (quote eq?) (CS (quote K) (CS (CS (quote CAR) (CS (CS (quote CAR) (CS (quote V) (quote ()))) (quote ()))) (quote ())))) (CS (CS (quote CAR) (CS (quote V) (quote ()))) (CS (CS (CS (quote U) (CS (quote U) (quote ()))) (CS (quote K) (CS (CS (quote CDR) (CS (quote V) (quote ()))) (CS (quote CAR) (CS (quote CDR) (CS (quote CONS) (quote ()))))))) (quote ()))))) (quote ()))))) (quote ())))) (quote ())))) (quote ()))) (CS (CS (quote lambda) (CS (CS (quote X) (CS (quote Y) (quote ()))) (CS (CS (quote lambda) (CS (CS (quote F) (quote ())) (CS (CS (quote F) (CS (quote X) (CS (quote Y) (quote ())))) (quote ())))) (quote ())))) (CS (CS (quote lambda) (CS (CS (quote C) (quote ())) (CS (CS (quote C) (CS (CS (quote lambda) (CS (CS (quote X) (CS (quote Y) (quote ()))) (CS (quote X) (quote ())))) (quote ()))) (quote ())))) (CS (CS (quote lambda) (CS (CS (quote C) (quote ())) (CS (CS (quote C) (CS (CS (quote lambda) (CS (CS (quote X) (CS (quote Y) (quote ()))) (CS (quote Y) (quote ())))) (quote ()))) (quote ())))) (CS (CS (quote lambda) (CS (CS (quote A) (CS (quote B) (CS (quote C) (CS (quote CONS) (quote ()))))) (CS (CS (quote CONS) (CS (quote A) (CS (CS (quote CONS) (CS (quote B) (CS (CS (quote CONS) (CS (quote C) (CS (CS (quote quote) (CS (quote ()) (quote ()))) (quote ())))) (quote ())))) (quote ())))) (quote ())))) (quote ())))))))
はい，とてつもなく面倒ですね．なお，上記は手作業で記述したものではもちろんなく，次のようにして自動生成したものです．
> (define (S2C-T s)
(cond ((eq? s (quote ())) `(quote ()))
((pair? s) `(CS ,(S2C-T (car s)) ,(S2C-T (cdr s))))
(else `(quote ,s))))
> (S2C-T '((lambda (X) X) (quote A)))
(CS (CS (quote lambda) (CS (CS (quote X) (quote ())) (CS (quote X) (quote ())))) (CS (CS (quote quote) (CS (quote A) (quote ()))) (quote ())))
とはいえそれでもやってみようというのがこの記事です．結果として，5つの基本構文・関数で実装できました．満足満足←．
ラムダ式による超循環評価器の実装
前節を踏まえて作成（修正）したLISP評価器mce2.scmを，下記GitHubリポジトリにて公開しています．なお，前記事の基本関数には，コンスセル構造かアトムかを判定するpair?（純LISPの説明などでは，アトムか否かを判定するatom相当）がありましたが，今回はcons相当がラムダ式（クロージャ）を生成するため，pair?ではなくprocedure?に置き換える必要があります．また，apply相当を中心に条件分岐が多岐に渡ることがほとんどなくなったため，条件分岐構文として，評価器実装が若干煩雑になるcondではなくifに置き換えています．バグ報告orコメント大歓迎．
$ chibi-scheme < mce2.scm
> Y
> $
次は，上記mce2.scmをサンプルコードごと自動変換してmce2.scmの評価器に読み込ませているmce2mce2.scmです．これぞ超循環評価器．なお，mce2.scmの例と区別するためサンプルコードを微妙に変更しており，上記とは処理結果が異なります．
$ chibi-scheme < mce2mce2.scm
> Z
> $
備考
記事に関する補足
- ところで，超循環評価器実装が実用面で役立つとすれば，その最小プリミティブさえ用意すればOKという意味で，LISP評価器の他のプログラミング言語への移植がしやすくなることなのですが，各言語でレキシカルスコープのラムダ式をプリミティブとして用意するよりも，構造体や配列などで
cons,car,cdrを用意する方がはるかにはるかに楽なのは言うまでもなく． - しかも（今回のコンスセル構造実装がなければ）実装用プリミティブ構文としてのラムダ式は基本的な関数定義・適用さえできればよく，レキシカルスコープでなくても高階関数としての機能がなくても良いという．だからこそ，C言語でもPOSIXシェルのスクリプトでも実装可能なのだけれども．
更新履歴
- 2021-08-02：初版公開
Discussion