EOPLの再帰関数の実装 - sumiiのブログ

SICPがset!を使っている(4.1.6節)ので当たり前?かもしれないのですが、EOPL（第二版）も再帰関数をややこしく実装している(3.6節)ことを知ってしまいました。いや、以前に輪講したので知っていたはずなのですが忘れていました…

EOPLでは再帰関数の名前が参照されるたびにクロージャを生成したり(Figure 3.9)、それを避けるために破壊的代入を使ってメモ化をしたり(Exercise 3.35)しているようです。が、そんなことをしなくても、クロージャの定義を拡張して、

letrec f(x) = eのように再帰関数が定義されたら、fが束縛されるクロージャに自分自身の名前fも格納

しておき、

関数適用時にふたたびfを自分自身のクロージャに束縛

すれば十分です。86ページ中ほどのクロージャ表現に合わせて書くと

(define-datatype procval procval?
  (closure
    (proc-name symbol?)
    (ids (list-of symbol?))
    (body expression?)
    (env environment?)))
(define apply-procval
  (lambda (proc args)
    (cases procval proc
      (closure (proc-name ids body env)
        (eval-expression body (extend-env (cons proc-name ids) (cons proc args)))))))

のような。無名関数（proc-exp）のproc-nameは適当につければOKです（参照されないので）。85ページ下のクロージャ表現や相互再帰の場合も考え方は同じです（Figure 3.9でいうと、各posごとのclosureをあらかじめ作っておくことができる）。