オレオレLisp処理系を実装してみた(2日目)

Lisp処理系の実装メモ2日目です。(1日目、3日目)

例によって最後にその日の最後の時点くらいのコードを載せますが、
結構がっつり書き換えたりしてるんで、あんまりメモ内の記述と整合性がないかもしれません。あくまで参考ということで。




== 2日目 ==

evalにむけて少し関数を書いてたけど eval より reader のほうが先か、ということでreaderを実装する。

最初カッコの対応つけるのに、カッコのネストレベルを
渡すようなインターフェースにしてたんだけど、
printer同様'('を読んだらread_list()に飛んでそいつは
reader()を呼ぶ、という感じで再帰的な感じで書くと、スッキリできた。
再帰的に作ってやればread_list()が同一レベルのカッコの対応に責任を持つことが
できるので、 そもそもネストのレベルなんて見なくてもread_list()でEOFか
reader()本体で')'を読んだ時点カッコ対応 の不備を検出できる。
read自体はread_list(), read_string(), read_symbol()とかへのディスパッチャ
のみって感じ。

どうでもいいけど相互再帰ってハノイの塔みたいなある種の再帰関数を書くときの
不思議な感覚はあんましないね。パーツとしてはそれぞれ完成してる、あるいは
別物に見えるからかな。

しかしLispのパーサは書いてみると非常に簡単だった
他のパーサを真面目に書いたことないけど、何種類もの予約語とそれに
対応する何種類もの構文の正しさを検証するとか考えただけでめんどくさそう。
一方Lispは(パーサにとっての)構文はシンボルかリストのみだからなー。
しかも意味論的構文は基本的にapplyで、例外的な特殊形式があるとは言え、そのへんはevalが計らってくれるわけだからreaderはほんと何もしなくていい。
抽象度の高いプログラミング言語の中では他に類を見ないほど簡単なんじゃ無かろうか。
よく「Lispを実装するのは簡単」というのはパーサの難易度が低いことに起因してる
のかも。

**

reader の次は eval を書く。

evalのインターフェースは
lptr eval(const lptr& expr, const lptr& env);
exprはS式、つまりリスト(ConsかTHE_NIL)かアトム(Symbol, String, Fixnumのどれか)
が入ってくる。envのほうはもちろんEnv, applyをまだ実装してないので
今のところTHE_ENVIRONMENTしか入ってこない。

中身はとりあえずisAtomでアトムかCons or Listじゃないことを判定できるようにして、
アトムの場合はシンボルが指すオブジェクトを探して返す。

ここに来て、 reader で String, Fixnum を読んだときは Symbol としてではなく
直接それぞれのクラスを生成してreaderの結果で返すS式に埋め込んでやるほうが
良さそうだなと気づく。なので一旦readerをそのように改造し、evalのほうは結局
アトムの場合でかつシンボルの場合はそれが指すオブジェクトを探して返し、
シンボルじゃなければそのまま返すようにした。

途中でFixnumとかにはスーパークラスとしてSelfEvaluateみたいなクラスが
必要かなと思って書いてみたが、SelfEvaluateをevalするときに自分を返す以外
することが何もないので結局アトムでシンボルでなければ自身として評価される、
という理解でよさそう。

**

evalの続き。

さて、exprがアトムじゃなければ関数か特殊形式なので、
オペレータ＋オペランドなS式とみなして処理すればよさげ。

オペレータが関数か特殊形式でオペランドの評価順序が変わるので
たぶんまずオペレータ位置にあるS式だけ eval し、その後その評価結果が
関数か特殊形式かで分岐させてみる。

特殊形式は Syntax クラスとし、それを親として持つ SpecialForm クラスで
組み込みの特殊形式を表す。もうひとつのサブクラスとしてMacroを作るつもりだけど
今は置いとく。
一方、関数のほうは Proc クラスとして、それを親として持つ PrimitiveProc と
CompoundProc を作る。Syntax と Proc は名前の他はそれぞれ eval_syntax, apply という
純仮想関数を持たせてサブクラスで実装を強制させる。
Syntax は virtual lptr eval_syntax(lptr& args, lptr& env) = 0;
Proc は virtual lptr apply(lptr& values) = 0;
て感じ。

関数のほうのapplyに env がなくなっていいのか自身ないけど、
apply に渡すオペランドは先に全部 eval した結果として渡すので
現時点の環境はいらないはず。
CompoundProcは評価時に環境が必要になるけど、それは関数の
オブジェクト生成時の環境と、引数から作る新しい環境のはずなので問題ないはず
evalから環境を渡して使っちゃうと、レキシカルスコープにならず、
ダイナミックスコープになっちゃう気がするし。

結局オペレータが Syntax の場合はすぐにその eval_syntax() に渡す。
関数の場合、S式のcdrにあるS式を1個ずつ個別に評価してリストにして返す関数
eval_apply_values()に渡し、その結果を関数の apply() に渡してやる。
これで
「特殊形式は引数の eval の順序が不定なので個別の場合で評価する」
「関数は引数を全部評価してからオペレータをapplyする」
という動きになるはず。

各特殊形式やeval_apply_values()では eval を呼ぶことになるので(相互再帰)、
コードの実行パスとしては相当複雑なはずだが、evalのコード自体はかなり
シンプルになっている。readerと似てるな。
というか再帰が持つ抽象化力がすごいってことか。

とりあえずPrimitiveProcのインスタンスとしてFixnum同士を足し算する
prm_add_fixnum のみ定義しとく。
あとはS式操作用の cons, car, cdr, nreverse とかも
function<lptr(lptr& args)> なインターフェースになるよう
prmcons, prmcar, prmcdr などを定義しておく。

register_primitive_proc(std::string, function<lptr(lptr& args)>) という
組み込み関数登録用の関数を作って
シンボル"+"とか"CAR"の実体が各prm関数を指すよう THE_ENVIRONMENT に登録
できるようにし、 main() の初期に登録処理を書く。

あとシンボルらしきトークンをreaderで読み込んだときに、全部大文字化して
シンボルを生成するようにした。

特殊形式は一個も登録してないのだが、これで (+ 1 1) は動くはずなので
REPLを実装して動かしてみる。

(+ 1 1)
2

動いた!
すんなりいって嬉しい ( ´∀｀)

次は "CONS"(prmcons) や "CAR"(prmcar), "CDR"(prmcdr) の動きを見る。
動かないｗ
prmcons は想定通りだが prmcar, prmcons がちゃんと動かない。

 * (cons 1 2)
=> (1 . 2)
 * (car (cons 1 2))
=> (1 . 2)
 * (cdr (cons 1 2))
=> NIL

とりあえず apply するときにリストが1個余計にくるんでいるみたいだ。
もしかしたら cons がおかしいのかもと思って大急ぎで
特殊形式 quote を実装してreaderで読んだS式をわたして見るがやっぱり変。
よくわからんので逃避的に ' を読んだら次のS式<next>を読んで (quote <next>) に
変換する処理を reader に実装したりした。
('はREADが読んだ直後(quote ...)に変換するっていろんなとこで読んだ気がするので)

ここで nreverse を組み込み関数として登録した REVERSE! の動きがおかしいことに
気づく。

 * (reverse! '(1 2 3 4))
=> ((1 2 3 4))

eval_apply_values()で呼んでる nreverse がアカンのかと思って
reverseを実装してそれと交換してみたりしたんだけどダメ。

prm* の書き方が悪いのかとも思うが prmcons はちゃんと動いてるし
意味がわからん。

進まないので T のクラスになる True やインスタンスの THE_T を作ったりした。
さらにこのバグはほっといてquote以外の特殊形式を実装する。

プリミティブな特殊形式は function<lptr(lptr&, lptr&)>というシグニチャで実装し、
SpecialFormクラスにもたせるだけ。
register_primitive_proc() と同様、register_specialform() という
インスタンス生成 && THE_ENVIRONMENT 登録用関数を作ってmain開始直後に
シンボルと結びつける。

とりあえず初期から適当に実装してるのが begin, cond, lambda あたり。
begin と cond は、最初に実装してたバージョンほぼそのままで正しく動いた。

lambda は CompoundProc をインスタンス化するだけだけど、 CompoundProc の
構造とその apply には PrimitiveProc と違って少し工夫がいる。
合成関数というかlambdaの適用で何をするのか、を整理してみると
1. 関数定義時の環境を外側の環境フレームとして新しい環境を作る
2. 関数の仮引数(lambda式の第1引数)リストのシンボルを環境に登録する
3. 関数の実引数(applyの引数で渡されたもの)をそれぞれ2のシンボルにセットする
4. lambda の body 部を今作った新しい環境でeval する。
となる。というわけで、lambda のインスタンスである CompoundProcには
* インスタンス作成時の環境フレーム
* 仮引数リスト
* ボディ
を保持しとけば良さそうだ。

apply も上の4ステップを素直に実装に落として完成。


 * ((lambda (x) (+ x x)) 5)
=> #<Error: Cannot Evaluate: 10>

lambda自身は動いているようだがおかしい。
リストになってるぽくてprmcarの問題と同じニオイがする。

prmcarとあわせていろいろ試してみたがわからず。

疲れたので以上で2日目は終わり
クラス構成は以下。

class LObj
class True : virtual public LObj
class TrueInstance : public True
class Error : public True
class List : virtual public LObj
class Nil : public List
class Cons : public True, public List
class String : public True
class Fixnum : public True
class Symbol : public True
class Env : public True
class Proc : public True
class PrimitiveProc : public Proc
class CompoundProc : public Proc
class Syntax : public True
class SpecialForm : public Syntax

コードは以下の通り。次の日のメモはこちら