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>を 参照することが許される.

例えば,以下のプログラムは,階乗を計算する関数 factletrec を用いて宣言し,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.mlylexer.mll を除く,プログラムの変 更点である.eval_expLetrec を処理する部分は,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.mlylexer.mll を 完成させ,mini Scheme5 インタプリタを作成し,テストせよ.ただの再帰的関数 だけでなく,相互再帰的な関数もテストすることが望ましい.

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


Previous Up Next