誰得UNIX: オレオレLisp処理系を実装してみた(3日目=最終日)

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

実装メモとしてはこれが最終日になりますが、感想などのまとめを次の記事としてのせるつもりです。

例によってコードは一番下に載せてます。

== 3日目 ==

car, cdr 等が正しく動かない件、lambda が動かない件は両方とも
1日置いたら解決した。

car, cdr, ... のほうの原因は内部でS式を扱ってる関数をユーザに見せる関数prm*()に
ラップするときのミス。
引数が一つのリストにまとめられてくるので、(まさしくapplyされる状態なので)
それを受け取る側の実装は
lptr prmcar(const lptr& args) { return car(car(args)); }
lptr prmcdr(const lptr& args) { return cdr(car(args)); }
しなきゃいかんのに
lptr prmcar(const lptr& args) { return car(args); }
lptr prmcdr(const lptr& args) { return cdr(args); }
としてた。(2日目はここのcar相当がprmcarという名前であり、それを
そのままシンボル"CAR"にも登録してた)
アホすぎる。

prmconsはちゃんと
lptr prmcons(const lptr& args) { return cons(car(args), cadr(args)); }
してて、たぶんもともとcons()が2引数なので注意深くやってたらしい。
nreverseとかも同様。

**

lambda が動かないほうは、apply の最後で body 部を sf_begin で評価すべきところ
eval を呼んでたのが原因だった。

しかしアホなバグで悩んだものだが、おかげで reader や printer が充実した
(デバッグの過程でいろいろ整理できた)ので良しとしよう。

続いてsf_define をさくっと実装。 MIT形式は非対応。道具は揃ってるので簡単。

**

そろそろ竹内関数も実装できそうなので実装してみる。
cond があればいいかと思ってたが、macroが書けるようになるのは先っぽいので
sf_if を実装。 Fixnum の演算用の関数もとりあえず実装してなんとか
tak 定義ができた。
で、実行したところ・・・

遅いw (tak 12 6 0) が終わらないどころか (tak 10 5 0) も 2秒ぐらい
かかる感じ。

プロファイルとってみたら C++ の dynamic_cast とstrcmp()っぽい内部関数が
かなりの割合を占めていた。なんでやー、と思って Effective C++ 引っ張りだして
眺めてたら
* dynamic_cast は遅いぞ。中で何回もクラス名を strcmp() で比較するからな！
* shared_ptr 使ってるなら派生クラスごとに shared_ptr を用意するか
基底クラスに派生クラスの全メソッドvirtual定義しとけやボケ
ってそのものズバリなのが書いてあって、見事にアンチパターンにはまってたｗ
Effective C++は偉大である。

直すか・・・いや、unionで即値と要GCオブジェクトをわけて再実装したほうが、
とかいろいろ別方向のモチベーションが高まってしまったが、
そもそも関数作るときにbodyを構成するS式はシンボルのまま解決してなかったり、
他にもいろいろ遅くなる原因はたくさんありそげでキリがないし、
とりあえずマクロ組めるところまでこのまま実装することにする。

**

ここらで Emacs の Scheme モードで動かしてみることにする。

何の工夫もなく普通に動いた。
コードは変更しまくるので自分自身を exec で OS プロセス的に再起動するような
"RESTART"コマンドを書く。

**

マクロを実装するまえにとりあえず QUASIQUOTE と UNQUOTE を充実させる。
が、'`(foo ,x) とかを評価すると
* '`(foo ,x)
=> (QUASIQUOTE FOO (UNQUOTE . X))
となってしまってダサいので、ちゃんと
`(foo ,x) と出して欲しい。

QUASIQUOTE や UNQUOTE のシンボル自体を printlptr で特別扱いしてしまうと、
本当に QUASIQUOTE などのシンボルとして出力したいときにできなくなってしまうので、
reader で読み込んだ時点で eval を呼んで Syntax オブジェクトとしてパースしたS式に
埋め込むことにした。ついでにQUOTEも同じ扱いにする。reader内で
evalを呼ぶのがやな感じなのでグローバル変数経由に後で変更するかも。

* '`(foo ,x)
=> `(FOO ,X)

うまく動くようだ。QUASIQUOTE, UNQUOTE のネスト対応チェックとか(必要性の
検討も含めて)真面目にやってないけどとりあえずよしとする。

UNQUOTEなどがちゃんと出力されるようになったので、
ついでに sf_lambda をシンボル "^" にも対応させて

* ((^ (^) `(,^ ',^)) '(^ (^) `(,^ ',^)))
=> ((^ (^) `(,^ ',^)) '(^ (^) `(,^ ',^)))

というQuineを書けるようになったｗ

reader を見てたら read_list で (foo . bar) を読んだときの考慮が
抜けてたのでなおした。

これによって lambda の引数で可変長引数を書いたら正しく動くようになった。

関数の define 時にいちいち lambda と書くのが面倒になったので
define を MIT 形式に対応させる。 Macro はまだない上に、それほど
難しい変換でもないので sf_define 内に実装する。
sf_define に渡ってくる引数の car が Cons だったら、
(define (<name> . <args>) . <body>)
のはずなので、分解して
(define <name> (lambda <args> . <body>))
に再構築、再度 eval に食わせることでこれまでの sf_define
が再帰的に呼びだされて正しく評価される。
特に苦労なく実装完了。

**

次はMacroを実装していく。
Macro のセマンティックから想像して、呼びだされたときにやることを整理してみると:
1 eval_syntax 経由でその時点に評価中のS式を渡される
2 自身が保持している変換器(lambda)にS式を食わせて処理する
3 結果がまたS式になっているはずなので、それをevalする。

変換器自体はdefine-macroを評価した時点の環境を持ってればいいはず。
変換器は入力されたS式に現れるシンボルを評価したりはせず、
単なるシンボルのリストとして扱い(つまりマクロ呼び出し時の
環境は不要)、結果としてできたS式をマクロ呼び出し時の環境下で
評価することになるはずだ。

ということで、Macro には変換器となる Proc (lambda)を1個持たせておけばよさげ。
Macor の eval_syntax は上の手順通りに実装。

define-macroの実体となる sf_define_macro は Macro インスタンスを作って THE_ENVIRONMENTに登録するラッパーとして実装。
(本来はDEFINE-MACRO呼び出し時の環境に登録すべきだろうか？)

最後にシンボル "DEFINE-MACRO" を sf_define_macro に対応させ、
実際に使えるようにする。

**

続いてマクロの動作確認。

* (define-macro (foo x y)
`(list ,x ,y))
=> #<Syntax FOO>
* (foo 1 2)
; #<Error: Undefined symbol: LIST>

list を定義してなかったｗ

* (define (list . x) x)
=> LIST
* (foo 1 2)
=> (1 2)

おｋ

これ以上複雑な(といってもletとかの)マクロを書くには色々材料が足りないので、
いくつか関数を追加してみる。

例えばシンプルなLETの定義は
(define-macro (let binds . body)
`((lambda ,(map car binds)
,@body)
,@(map cadr binds)))
になるので、mapと, mapのために(ユーザに見せる)apply が必要になる。
結果は:
=============================================================
* (define (list . x) x)
=> LIST
* (define-macro (let binds . body)
`((lambda ,(map car binds)
,@body)
,@(map cadr binds)))
=> #<Syntax LET>
* (let ((x 10)
(y 20))
(let ((x 12)
(a x)
(z (let ((a 7)
(b 11))
(* a b x y))))
(list a x y z)))
=> (10 12 20 15400)
=============================================================
できた。ついでに LET* も実装してみる。
=============================================================
* (define (null? x)
(eq x NIL))
=> NULL?
* (define (fold fn seed lst)
(if (null? lst)
seed
(fold fn (fn (car lst) seed) (cdr lst))))
=> FOLD
* (define-macro (let* binds . body)
(fold (lambda (bind body)
`(let (,bind) ,body))
`(begin ,@body)
(reverse binds)))
=> #<Syntax LET*>
* (let* ((x 10)
(y 20))
(let* ((x 12)
(a x)
(z (let* ((a 7)
(b 11))
(* a b x y))))
(list a x y z)))
=> (12 12 20 18480)
=============================================================
おｋぽい

さっきのletをlet*に置き換えただけだが、各束縛時に見える束縛がletのときと
かわるので評価値も変わる。
一応ほかのLisp処理系でも同じS式をevalしてみて
同じ答えになることを確認。

こういうのが一発で決まるとキモチいいね。

と、いうわけで、Lispのプリミティブな機能はある程度実装できた気がする。
# Fixnumの演算子とか全然だけど

マクロも実装できたし、上にレイヤを重ねていけばたいていのことはできる
であろうLispになった(性能は低いが)。

まだまだ処理系自身にバグがたくさんあって、効率も悪い実装だとわかってるけど、
自分で書いてみることで色々わかって勉強になったし、言語処理系を
書くってのは普通のアプリを書くのとはちょっと違った面白さがあることがわかって
満足したので、とりあえずここを区切りとする。

最終日のクラス構成は下記のとおり

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
class Macro : public Syntax

コードはこれ

誰得UNIX

2014年12月23日火曜日

オレオレLisp処理系を実装してみた(3日目=最終日)

0 件のコメント:

コメントを投稿