2013年5月11日土曜日

[Ruby][Scheme] Micro Schemeの実装(6) letrec式の評価

letrec式を評価できるようにし、再帰呼び出しが可能になった。
https://github.com/takeisa/uschemer/tree/v0.06

let式での再帰呼び出し

階乗を求めるコードの例
(let ((fact
      (lambda (x) (if (= x 0)
                      1
                      (* x (fact (- x 1))))))) ← ◆このfactは参照できない
  (fact 5))           

外側のletで自分自身を変数に束縛しても、lambda式を評価してクロージャを生成した時の環境と、クロージャの仮引数と引数の束縛を使って、クロージャ本体を評価するため、クロージャ本体からは、その変数で自分自身を参照できない。

letrec式での再帰呼び出し

(letrec ((fact
         (lambda (x) (if (= x 0)
                         1
                         (* x (fact (- x 1))))))) ← ◆このfactを参照可にする
  (fact 5))           

factを参照できるようにするために、letrecは次のように評価する。
(1)letrecの束縛定義に従い、変数と、lambda式を評価した結果のクロージャの束縛を作成する。
(2)環境にその束縛を追加する。
(3)(1)のクロージャそれぞれの環境に(1)で作成した束縛を追加する。
(4)letrec本体を評価する。

書籍(http://tatsu-zine.com/books/scheme-in-ruby)の実装とは違うが、
この方式だと何か問題があるのかな?

実行結果

10の階乗

(letrec ((fact
         (lambda (x)
                 (if (= x 0)
                     1
                     (* x (fact (- x 1)))))))
  (fact 10))
 #=> 3628800

100の階乗

(letrec ((fact
         (lambda (x)
                 (if (= x 0)
                     1
                     (* x (fact (- x 1)))))))
  (fact 100))
 #=> 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

再帰呼び出しで、正しく計算できた。
少しずつ出来ることが増えてきて、なかなか楽しい。