読者です 読者をやめる 読者になる 読者になる

やろーじだい

ブログです

「つくって学ぶプログラミング言語 - Ruby による Scheme 処理系の実装 」を途中まで読んだ

きちんと Lispインタプリタの実装したことがなかったのでここを参考にしながら 2 ヶ月程前に Common Lisp で 3 章 (再帰) まで実装していた。いつ再開するかわからないので今日の記事で宣言した通りとりあえずまとめておく。
 自分のプログラムはここで公開しているが、自作のライブラリ と CL21 を使っているので導入しなければ動かない。
 Ruby を使っても良かったのだが、ただ写すだけになってしまいそうだったのと、

本書で出てくるプログラムをコピー&ペーストしていけば、実行できるようになっています。動作することを確認するくらいには役立つでしょう。ただし、本当に理解したいのであれば、なるべく自分で プログラミングしてみてください。それもプログラムを見て理解した後は、そのプログラムを見ずに。 どこが理解できないでるかが明確になるかと思います。
はじめに P-ii

ということから、別な言語を使った方がこれを実践しやすいと思ったため。

第1章 プログラムと評価

1章終了段階でのコードは ここ で確認できる。
 この本では Ruby で配列として扱えるという理由で [:+, 1, 2] というような構文を採用していたので自分は (:+ 1 2) という様にした。関数と変数は共にシンボルとして扱うようにした。また命名規則に関しても基本的に Common Lisp でよく見る形式にした。例えば述語は Ruby の場合 immediate_val? となるものを immediate-val-p のようにハイフン区切りで p を付けるといった様に。
 環境は

(defparameter *primitive-fun-env*
  #H(:+ '(:prim +)
     :- '(:prim -)
     :* '(:prim *)))

のように Hash-tabel を利用した。

第2章 関数適用の評価

eval_let の実装にあたって

(defun let-to-parameters-args-body (exp)
  `(,(map #'first (second exp))
    ,(map #'second (second exp))
    ,(third exp)))

(defun eval-let (exp env)
  (destructuring-bind (parameters args body) (let-to-parameters-args-body exp)
    (let ((new-exp (append `((:lambda ,parameters ,body)) args)))
      (_eval new-exp env))))

というようにバッククオート構文を使用しているのだが、

(defun let-to-parameters-args-body (exp)
  (list (map #'first (second exp))
        (map #'second (second exp))
        (third exp)))

の方が読みやすい気がした。
 let? のような関数の実装が雑で不安だったので

(defun letp (exp)
  (and
   (eq :let (first exp))
   (listp (second exp))
   (third exp)))

のようにした。
 ここを読むと、クロージャとは何なのかが明確になるので、その辺りが曖昧な人は読む価値があると思った。

第3章 再帰

再帰関数の実装に興味があったのでこの章は楽しかった。実装にあたって苦労したのだが、最も苦労した理由がテストのミスであり辛かった。テストのミスというのはどうすれば防ぐことができるのだろう。
 ここでは Ruby に慣れていなかったのと、環境を用意せずに読んでいた (実際に実行して試さなかった) ため eval_retrec など少し読むのに苦労した。もう少し関数を分けて処理に名前を付けて欲しいと思った。
 またここまでで唯一の破壊的処理を行う set_extend_env! が実装されているが、何故ここで副作用を使うようにしたのかの説明が無かった。単純に考えれば環境 (Hash-tabel) の更新なので Copy を作るのは重い処理だからかと思ったが、 extend_env では Hash.new を使って新しい環境を作成しているのだが違いは何なのだろう。

追記:

 このツイートへのリプライで破壊的更新をしている理由について教えて頂いた。
 コピーをするとクロージャの持つ環境が更新できず :dummy にアクセスしてしまうので、ここでは破壊的処理を行って更新しなければならなかった (extend_env では既に環境内にある closure の持つ環境を変更することができない)。