なんちゃってMathematicaを作る - その10

先日Mathematicaの計算の基本である「評価」が、式に対して「書き換え規則」を適用して書き換えた結果を出力するものであるということを確認した。この「評価」というのはMathematica固有のアイデアではなく、LISPという古いシステムがもとになっている。今日はこのLISPの評価メカニズムを概観する。

8.1  LISP評価エンジン

これまでなんどか書いてきたけど、実は、Mathematica本体の評価エンジン（入力された内容を解釈して結果を計算する）部分は基本的にLISPと同じ思想で作られている。LISPの評価エンジンは非常に小さなコードで、インタプリタ動作が可能になる優れたものである。

僕は入社して数年経った頃、仕事でインタプリタを実装した。それはある測定機用のソフトウェアで、計算量が（当時としては）多く、パラメータの数も多く、測定機として稼働し始めてからも仕様変更というか、あれが欲しいこれがないとダメ、でいじり続けることになってしまっていた。そこで、あるきっかけからソフトウェアを全部書き直して、プログラマブルなものにしよう、と思った。

HPのワークステーションを使って、HP-UX上に当時使い慣れていたVAX/VMSのDCL（シェルコマンドのようなもの）に似せたシンタクスのインタプリタを作り、コマンド列として測定手順を表現するようにした。インタプリタは完成したけど肝心の計算部分の作り込みが全然不十分でバグが多く、結局古いソフトウェアのほうにもう一度手を入れて使うことになった。ようするにインタプリタを作る方が面白くなってしまって、本来の目的からははずれたものを作ってしまった、と言う具合。若気の至りということで勘弁してくれい。

そのインタプリタは僕専用の数値計算環境としてしばらく生き残った。式をそのまま入れればいいし、変数の定義もできて、math.hにある数値関数の値は評価できた。あまり扱いは良くなかったけど配列も使えた。

そのインタプリタがLISPの評価エンジンでできていた。入力ラインを字句解析して、評価エンジンで評価して結果を出力する、というようなものだった。シンタクスのもとにしたDCLは文法としては非常に簡単なものだったので構文解析は楽だった。当時はlex、yaccなんて知らなかった（もちろん使っていたHP-UXの/usr/bin/ディレクトリにはちゃんとあったはずだけど）ので全部手動で実装した。

まあ、昔話はいいとして、LISPの評価エンジンを簡単に見てみるが、そのまえにLISPではデータのプログラムもリストというもので表現される。リストはS式（Symbolic Expression）ともいう。LISPで有効な表現はリストだけである。リストとは入出力の場面では

(a b c d)

などというような括弧に囲まれてスペースで分離された要素の連続である。内部的には図-2のようなものである。

図にある箱がふたつつながった□□みたいなやつをconsセルという。これはふたつのポインタの組である。前のポインタをcar（ふつう「カー」と読まれる）、後ろをcdr（「クダー」と読まれる）という（変な名前だけど、これには歴史的な理由があるらしい。僕はよく知らない）。リストはcdrポインタを辿ってnilで終わるconsセルの鎖である。consセルはようするに左右の葉の区別があるバイナリツリーである。

例えば

(a (b c) d)

は内部的には図-3であることはちょっと考えればわかる。

このようにLISPでは入出力の表現で括弧を使うことで、内部表現をそのまま表していることがわかる。

LISPではデータ構造はこの入れ子になったリストで表現される。また、プログラムもこのリストで表現される。LISPプログラムとは例えばこのようなものである。

(car '(a b c d))

これを実行（評価）すると

a

が返る（後ろのリストの頭に「'」がついているのはquoteという関数の省略形。その後ろをプログラムとして評価しない、という意味。LISPの書き方を説明したいわけではないので気にしないで欲しい）。LISPではリストのcar部が関数の名前、cdr部がその引数であるとみなして関数を実行する。LISPではそれを「評価する」という。先の例ではcarと言う関数は引数のcar部を取り出して返すということを行う。

LISPではプログラムとデータが同じ形式なのでたとえばさっきのプログラムをデータとして扱うことができる。

(cdr '(car '(a b c d)))

この例ではさっきのプログラムの引数を取り出す、というプログラムになる。プログラムそのものがデータとして扱われている、と言うことができる。

このため自己改変プログラムが簡単にできて、おもしろいこともいっぱいあるけど、バグがあったときの解決が極端に難しくなるので、多用されることはない。