Previous Up Next
3.7 mini Scheme5 --- 再帰的関数定義の導入

多くのプログラミング言語では，変数を宣言するときに，その定義にその変数 自身を参照するという，再帰的定義(recursive definition)が許され ている．mini Scheme5 では，このような再帰的定義の機能を導入する．ただし， 多くの言語と同様，単純化のため再帰的定義の対象を関数に限定3する．

まず，再帰的定義のための構文 letrec 式を，以下の文法で導入する．
<式> ::= …
  | (letrec (<再帰関数定義リスト>) <本体式>)
<再帰関数定義リスト> ::= (<識別子1> (lambda (<識別子11> … <識別子1n1>) <式1>))
    … (<識別子m> (lambda (<識別子m1> … <識別子mnm>) <式m>))
letrec 式は，<識別子1>，...，<識別子 n>という名前の相互再帰的関数を示す変数を宣言し，その下で <本体式> を評価する．let 式と違い，各変数が束縛される 対象は lambda 式でなければならない．また，各変数の有効範囲は， <本体式>および，全てのlambda 式であるため，各lambda式の 本体で，<識別子1>，...，<識別子n>を 参照することが許される．

例えば，以下のプログラムは，階乗を計算する関数 fact を letrec を用いて宣言し，5! を計算するものである． 

(letrec
  ((fact 
     (lambda (n) 
       (if (= n 0) 1 
           (* n (fact (sub1 n)))))))
  (fact v))
この構文の基本的なセマンティクスは let 式と似ていて，環境を宣言 にしたがって拡張したもとで本体式を評価するものである．ただし，環境を拡 張する際に，再帰的な定義を処理する工夫が必要になる．各変数の有効範囲は， 宣言される関数式を含むため，それらの関数の閉包を作るときの環境は，本体を 評価するときの環境と同じもの，つまり，これから得られるはずの拡 張された環境でなくてはならない．これを扱うために，ここでの実装は，Objective Caml の配列の更新機能を利用する．
syntax.ml:

type exp = 
   ...
  | Letrec of (id * (id list * exp)) list * exp


core.ml:

let extend_env_rec syms procs env =
  (* assumes List.length syms = List.length procs *)
  let vec = Array.make (List.length syms) (IntV 0) in
  let newenv = ExtendEnv (syms, vec, env) in
  let rec iter f i = function
      [] -> ()
    | x :: ls -> f i x; iter f (i + 1) ls in
  let iteri f = iter f 0 in
  iteri
    (fun i (ids, body) -> vec.(i) <- ProcV (ids, body, newenv))
    procs;
  newenv
  
let rec eval_exp env = function
   ...
  | Letrec (procdefs, body) ->
      let (ids, procs) = List.split procdefs in
      let newenv = extend_env_rec ids procs env in
      eval_exp newenv body

Figure 13: 再帰的関数定義

図13が，parser.mly，lexer.mll を除く，プログラムの変 更点である．eval_exp の Letrec を処理する部分は，Let の処理とほ とんど同じである．環境に関する新しい操作 extend_env_rec が重要な部分 である．extend_env_rec は，同時に宣言される変数名・関数(パラメータリ ストと本体式の組)・環境を受け取る．最初に宣言される vec は， 後で関数閉包が格納される配列で，初期値として，ダミーの整数値を いれている．newenv は，vec と宣言される変数名で拡張した 新しい環境である．次は 
(int -> 'a -> unit) -> 'a list -> unit
型を持つ補助関数 iteri の宣言で， 
iteri f [a0; a1; ... an]
は 
f 0 a0; f 1 a1; ...; f n an
を実行する．これを使って， newenv を，関数閉包を束縛するように更新している． 関数閉包は，拡張された環境 newenv を使って作られていることに注意． 最終的には，更新された環境を返している．
Exercise 15  [必修課題] 図に示した syntax.ml にしたがって，parser.mly と lexer.mll を 完成させ，mini Scheme5 インタプリタを作成し，テストせよ．ただの再帰的関数 だけでなく，相互再帰的な関数もテストすることが望ましい．

Exercise 16  [難易度 3] letrec を使って定義されるものは，lambda 式に限られていたが， この制限をどの程度緩められるか議論し，インタプリタを改造せよ．

Previous Up Next