はじめに
先日この記事『Pythonのリスト内包表記はチューリング完全だから純LISPだって実装できる』でLispを実装しました。わりとよくできていて、実行してみるとそこそこそれっぽく動き、ぽちぽち遊ぶのにはうってつけの日です。
でもこいつ、ほんとのところなにができるんだろう。数値型は実装していないので、そのままでは電卓にすらなりません。
なので、どれくらいのことができるのか、リスト処理に入門していろいろ遊んでみました。
前提条件
この記事では拙作のLisp処理系LISCを使います。いわゆる純LISP程度の能力があるものであれば何でも構いませんが、ここでは流れ上LISCを使います。
用意するもの
- python3系の処理系
- 折れぬ心
インタプリタの起動方法
これでいけます:
$ python3 <(curl -sL https://raw.githubusercontent.com/t-sin/lisc/master/lisc.py)
ただ、謎い挙動の原因を調査するためにprint()を仕込みたい場合は、リポジトリをクローンしてlisc_ref.pyにデバッグ文を仕込むのがよいと思います。
LISCの注意点
エラーは値
エラーは__hoge__形式の値として返ってきます。なので、プログラムの奥深くでエラーが起こったとき、そのまま外のコードで値として処理されるので、折れぬ心を以って対処してください。Good luck!
コンスセルはない
コンスセルがないので、Common Lispでいう(hoge . fuga)のようなものはつくれません。consの挙動はClojureのそれと同じ動きをするので、その点注意してください。
リストをつくる
まずはリストをつくってみましょう。まずは、長さ0のリストをつくってみましょう。
> ()
nil
おお、できた。Lispでは空のリストはnilとも書かれますから、実行結果がnilと印字されました。
ではリストの中に要素を入れてみましょう。
> (cons (quote a) nil)
(a)
consというのは、リストをつくる関数です。consは2引数の関数で、一つめに値、二つめにリストをとって、二つめのリストの先頭に一つめの値を入れたリストをつくって返します。また、(quote なになに)というのは「なになには変数じゃないから読みにいってエラーになるなよ（絶対だぞ！）」という意味のオペレータです。
これさえ知っていれば、複雑なリストをつくることもできます。
> (cons (cons (quote a) (cons (quote b) nil)) (cons (cons (quote c) nil) (cons (quote d) nil)))
((a b) (c) d)
こんな感じで。
リストを走査する
でも、ただリストをつくれたからといって、たとえばmap的な操作を手でやっていてはたまりません。そういう仕事は機械に奪われるべきであって、われわれはもっと抽象的なことに思考力を割くべきです。なので、リストを走査してみましょう。
ここにはfor文なんて便利なものはありません。代わりといってはなんですがlambdaというもっと抽象的なものがあります。こいつをつかって再帰的にリストを走査することにします。
たとえば、リストの中の要素をリストに入れたものを返す関数はこんなかんじです:
> (define wrap
(lambda (lis)
(if (eq lis nil)
nil
(cons (cons (car lis) nil) (wrap (cdr lis))))))
[lambda ['lis'] <fn 140072224567080>]
> (wrap (quote (a b c d e f)))
((a) (b) (c) (d) (e) (f))
これはLispではよく知られたリストの走査のやりかたです。carはリストの先頭要素を返す関数で、cdrはリストの先頭を除いた残りをリストで返す関数です。これらを組み合わせて、(先頭 その ほか の リスト)というようなリストを先頭と(その ほか の リスト)に分けて、またさらに残りのリストに分けて、……というふうにしてcdrが空になるまで繰り返します。
これをすこし捻ってやると、リストを逆順にすることだってできるんですよ！
> (define reverse
(lambda (lis reversed)
(if (eq lis nil)
reversed
(reverse (cdr lis) (cons (car lis) reversed)))))
[lambda ['lis', 'reversed'] <fn 140466985038712>]
> (reverse (quote (a b c d e f)) nil)
(f e d c b a)
このコードのキモは、関数を呼んだ時点でわかっている逆順の値を、つぎの再帰の引数にしているところです。ある時点のreverse呼び出しの時点で、そこまでの順番を逆にしたリストは簡単につくれるはずです。一番目（上ではa）のときは、単にaをリストに入れればよくて（最初の逆順リスト）、二番目以降は一つ前の逆順リストの頭に今の値（たとえばbとか）を入れてやればいいだけだからです。で、最後にそれを返したいなら、後ろまで引数で伝えてあげよう、という寸法です。
ね、簡単でしょう？
リストを連想配列としてつかう
もうちょっと複雑なことをやってみましょう。ここまでは配列としてリストを扱ってみました。今度はリストをつかってkey-valueな構造、連想配列（辞書、ハッシュテーブル、マップ）を表現してみます。
連想配列 as a リスト
まず、形式を決めましょう。Lispの世界では、リストで連想配列を表現する方法としてよく用いられる2種類の構造があります。
- 連想リスト (association list, alist)
- 属性リスト (property list, plist)
連想リストは、keyとvalueをリストとして保持し、keyとvalueのペアをさリストで保持する形式です。一方、属性リストはkeyとvalueを交互に並べたリストで表現されます。連想リストはkeyとvalueのペアを単純な再帰で舐めることが容易です。属性リストはぱっと見がすっきりしています（カッコが少ないので）。好みの分かれるとろだと思いますが、ここではコードで扱いやすい連想リストを採用することにします。
値を取得する関数assoc
まず、すでに連想リストがここにあるとして、そこから値を取り出すことを考えてみましょう。たとえば、こんな連想リストがあるとします:
> (define alis (quote ((key1 value1) (key2 value2))))
((key1 value1) (key2 value2))
この中からkey1に対応する値value1を取ってくる関数assoc
> (assoc (quote key1) alis)
(key1 value1)
を定義してみます。assocがvalueではなく見つかったkey-valueのペアを返すのは──Lispの慣例的な動きなのですが──値がないときと値がnilのときととを区別するためです。
> (define assoc
(lambda (key lis)
(if (eq lis nil)
nil
(if (eq (car (car lis)) key)
(car lis)
(assoc key (cdr lis))))))
[lambda ['key', 'lis'] <fn 140466985038848>]
> (assoc (quote key1) alis)
(key1 value1)
処理の概要としては、
- リストが空だったら
nil(値見つからず) - そうでない場合
- リスト先頭要素の
carがkeyと一致したら、先頭要素 (値発見！) - そうでない場合
- リストの
cdrについて同じことをやる (探索続行)
- リストの
- リスト先頭要素の
という流れになります。
値を更新する関数update
keyに対応する値を取得ことができるようになりましたが、値の追加はどうしたらよいでしょう？ ここではとりあえずキーに対応する値を更新した別なリストをつくって返す関数updateをつくることを考えます。
使用感はこんな感じでしょう:
> alis
((key1 value1) (key2 value2))
> (update alis (quote hoge) (quote fuga))
((key1 value1) (key2 value2) (hoge fuga))
更新作業には二つのケースが考えられます。すなわち
- 連想配列にkeyが既に存在するとき
- →既存のペアの値を新しいものにしたペアをつくる
- 連想配列にkeyが存在しないとき
- →新規にkey-valueのペアをつくる
の二つです。この点に留意すると、コードは以下のようになります:
> (define update
(lambda (alis key value)
(if (eq alis nil)
(cons (cons key (cons value nil)) nil)
(if (eq (car (car alis)) key)
(cons (cons key (cons value nil)) (cdr alis))
(cons (car alis) (update (cdr alis) key value))))))
[lambda ['alis', 'key', 'value'] <fn 140466985040888>]
> (update alis (quote hoge) (quote fuga))
((key1 value1) (key2 value2) (hoge fuga))
> (update alis (quote key1) (quote fuga))
((key1 fuga) (key2 value2))
更新後の値を取っておきたければ、defineでシンボルを束縛しておきましょう。
こんな感じで、連想配列を検索・作成・更新できるようになりました！ リストのちからってすげー。
リストをプログラムとして見なす
先の記事で、Pythonのリスト内包表記は、他のPythonの機能を組み合わせることでたいていのことを表現できてしまうという意味で、「リスト内包表記はチューリング完全」だと言いました。
ところでいままで使ってきたこの言語、チューリング完全なんですかね？？ そこそこなんでもできそうだけど、Lispのくせしてこいつにはevalがありません。そんなのって意味あるんですか？？
LISCを意味のあるLispにするために、リストをプログラムと見なして、与えられた計算手順を実行するものをつくってみようと思います。つまり、リストを引数にとって、実行結果を返す関数evalです！
では、やっていきましょう。
evalの要件
evalをつくるにあたって考えなければならないことがらを並べてみます:
-
atom,cons,car,cdr,eqの関数 -
if,quote,lambda,defineの特殊形式 - 関数オブジェクトと関数呼び出し
- 環境 (environment): 変数名と値のテーブル
- 各関数呼び出しの際に、実引数に束縛された名前テーブルをつくる必要あり
こんなところでしょうか。
関数オブジェクトはLISCの関数オブジェクトをほぼそのまま使うことにします。また、環境、つまり変数と値の表ですが、これには先ほどつくった連想リストの関数が使えそうです。
環境を整える
まずは変数名-値テーブルである環境まわりをつくっていきます。環境は、ただのkey-valueなデータではなく、階層構造を持つ必要があります。なぜなら、関数の引数のスコープを表現する必要があるからです。たとえば、以下のような場合、fn中にあるvはその関数スコープの中では定義されていないため、その上のグローバルな環境へと辿って値を見にいかなければならないからです。
> (define v (quote value))
> (define fn (lambda (a) (cons a (cons v nil))))
> (fn (quote hoge))
(hoge value)
というわけで簡単に、環境とは以下のような構造のリストとしましょう:
(親の環境 ((変数名1 値1) (変数名2 値2) ...))
グローバルな環境には親がいませんから（グローバルな環境で変数が見つからなかったら、変数は未束縛にする）、グローバル環境の親はnilとします。ではグローバル環境を定義しましょう。
(define *env* (quote (nil nil)))
これだけ！
環境(まわり)をよく見る
ではまず、evalのユーティリティとして、環境から値を探索するコードを書きましょう。やることはそんなにむずかしくありません。手順を分解して考えると
- 環境の連想リスト部分に名前が見つからなかったら、
nil - そうでない場合
- 環境の連想リスト部分に名前が見つかったら返す
- そうでない場合
- 親の環境 (
car部分)に対して再帰的に探索を実行
- 親の環境 (
と、こうなります。ここまでassocのしくみがわかっていれば、それはきっとこんなふうに実装できるでしょう:
(define lookup
(lambda (name env)
((lambda (pair)
(if (eq pair nil)
(if (eq (car env) nil)
(quote :unbound:)
(lookup name (car env)))
(car (cdr pair))))
(assoc name (car (cdr env))))))
地味にトリッキーなことをしています。((lambda (pair) ...) (assoc ...))の部分です。無名関数は値として返したりするだけでなく、その場で呼ぶこともできます。かつ、関数呼び出しによって、実引数の値が新しい環境の中で束縛を持ちます。これらを利用してassocの結果を一時変数pairに束縛したのです。そうしない場合、assocを二回呼ばなければならないことに注意です。
Lispにはletという局所変数宣言をするための式がありますが、これはlambdaの糖衣構文として定義される処理系もあります。
実は let は lambda 式を使って次のように表されます。
--- 『Scheme 入門 6. 局所変数』
lookupを実際につかってみると、このような感じになります。
> (lookup (quote key)
(quote (nil ((k v) (key value)))))
value
> (_lookup (quote gkey)
(quote ((nil ((gkey gval))) ((k v) (key value)))))
gval
ぼくにはよさげにみえる。
環境に手を加える
変数を探せたなら、こんどは更新したいです。そんな関数setvを用意しましょう。こちらは、assocの結果によって*env*をどのように更新するかが変わります。
(define setv
(lambda (name value)
((lambda (pair)
(if (eq pair nil)
(define *env* (cons nil (cons (cons (cons name (cons value nil)) (car (cdr *env*))) nil)))
(define *env* (cons nil (cons (update (car (cdr *env*)) name value) nil)))))
(assoc name (car (cdr *env*))))))
環境は構造が複雑なのでcons地獄になっていますが、キアイと共に読めばなにをやっているかはわかるはずです。
consをぼくの手の上に
ところで、基本関数のうちconsを定義して、グローバル環境に入れておきましょう。関数の格納方法を決めるという意味でも、eval本体を実装する前にいちど考えておきたいことがらです。
関数の実体はLISCの関数オブジェクトにするとはいえ、LISCの関数オブジェクトについての判定関数は用意されていません。そこで、ここでは次のようなものをevalが扱う関数オブジェクトとします:
- 3要素のリスト
- 1番目:
:lambda:というシンボル - 2番目: 仮引数 (呼び出し時に環境をつくるのに利用する)
- 3番目: 関数本体
- 引数は環境
- 内部では
lookup関数を利用して実引数の値を得る
- 1番目:
どうでしょう。つまり、たとえばこんな感じのものです。
(:lambda: (a b) [lambda ['ne'] <fn 140256455415464>])
このようなものをsetvをつかってグローバル環境に設定していきます。ここではconsの実装のみを示します:
(setv (quote cons)
(cons (quote :lambda:)
(cons (quote (a b))
(cons (lambda (ne) (cons (lookup (quote a) ne) (lookup (quote b) ne)))
nil))))
呼び出されたら束縛する
eval本体にいく前に、実引数の式を環境の値に基づいて評価し、仮引数の名前で新たな束縛をつくるbind関数を用意しておきましょう。評価が必要なのでevalに依存し、またbindがなければ評価が実行できないため、evalとbindは相互に依存する形になりますが、まず先に定義します。
ひとつの再帰で二つのリストを同時に辿っていくので、注意して考えてください。基本的には、二つのリストをcdrで辿りながら、実引数のほうはevalで評価し、仮引数と併せて束縛をつくって環境に加える、という作業を行います。
(define bind
(lambda (fn-args act-args env)
(if (eq fn-args nil)
nil
(if (eq act-args nil)
(quote :too-few-args:)
(cons (cons (car fn-args) (cons (_eval (car act-args) env) nil))
(bind (cdr fn-args) (cdr act-args) env))))))
ここではめんど つかれ 簡単のために、仮引数・実引数の数を正しくチェックしていません。それは読者への課題とする。
超循環評価器eval
ここでやっとevalです。
_evalは、quoteされたリストと環境を受け取ります。この環境がグローバルだったらeval、ローカルな環境だったら_evalで明示的に環境を指定する、という感じです。
実装の仕方は、与えられた式の種類をifで分岐して、都度必要なことをしていくのが基本です。たとえば、シンボルであれば、nilだったらnilを返し、tならt、それ以外なら現在の環境をlookupして見つかったものを返す、といったように。
注意したいのは、lambdaとdefineと関数呼び出しの部分です。これまでのパーツがあるので組み立てること自体はあまり苦労しませんが、トランボリン式にいろんな関数を呼び出していくため、デバッグが非常にしにくい点です。「ここで式は評価しておくべきか」などについて注意を払いながら実装しましょう。
evalの全貌を示します。ここまでで変数や関数の扱われかたを決めておいたため、evalのコードを読むのにはあまり苦労をしないはずです。
(define _eval
(lambda (form env)
(if (atom form)
(if (eq form nil)
nil
(if (eq form t)
form
(lookup form env)))
(if (eq (cdr form) nil)
nil
(if (eq (car form) (quote if))
(if (_eval (car (cdr form)) env)
(_eval (car (cdr (cdr form))) env)
(_eval (car (cdr (cdr (cdr form)))) env))
(if (eq (car form) (quote quote))
(car (cdr form))
(if (eq (car form) (quote lambda))
(cons (quote :lambda:)
(cons (car (cdr form))
(cons (lambda (ne) (_eval (car (cdr (cdr form))) ne)) nil)))
(if (eq (car form) (quote define))
(setv (car (cdr form)) (_eval (car (cdr (cdr form))) env))
((lambda (fn)
(if (eq fn (quote :unbound:))
(quote :undefined-op:)
((car (cdr (cdr fn))) (cons env (cons (bind (car (cdr fn)) (cdr form) env) nil)))))
(lookup (car form) env))))))))))
(define eval
(lambda (form) (_eval form *env*)))
実行するとこうなります:
> (eval (quote (cons (quote a) (cons (quote b) nil)))))
(a b)
> (eval (quote (define fn (lambda (a) (cons a nil)))))
...
> (eval (quote (fn (quote hoge))))
(hoge)
リスト処理ってすごいなー。リスト処理ってチューリング完全なんだなー。なるほどなー。
完成品
ここまでに述べたことを実装したのがこちらのコードです。
名前や実装が若干ちがうけど、読み替えてください。
おわりに
Lisp実装したのにevalがないっていうのはその出自としてどうなんだ、うーん、と悩んでいたらevalが生えてきました。なにこれ！
つかれ