5-3. 再帰関数の処理

再帰呼び出し(recursive call)を行う関数の処理をインタープリタに追加する。

OCaml では、たとえば、階乗を計算するプログラムは以下のように定義できる。

  let rec factorial x =
     if x = 0 then 1 else x * (factorial (x - 1))
  in factorial 5

ここで let factorial ではなく、再帰を表す rec というキーワードをつけて、 let rec factorial となっている。

再帰関数を実装するには、いくつかの方法がある。

方法1. 再帰しない関数(前回までに実装したもの)とは別に、再帰関数を表すデータ構造を導入し、再帰関数のための処理を別途記述する。
この方法は実装が簡単であるため、ここで採用する。詳細は後述する。
方法2. 再帰しない関数の処理をそのまま使えるように、環境の表現においてループ構造を導入する。ループ構造というのは、たとえば、
```
   x = 1::(2::x)
```
を満たす x のことである。この x は、OCaml では,
```
  let rec x = 1:: (2 :: x) ;;
```
とすると定義できる．絵を描くと、環状にぐるっとまわって元にもどる構造であり， x そのものを印刷しようとすると，[1; 2; 1; 2; ...] という無限長のリストとなる． (なお，OCamlを通常のモードで実行しているときは，サイズが大きなデータは，途中で印刷を打ち切ってくれるので，無限に印刷することはない．)
再帰関数は、「factorial という関数の中で、factorial を使う」というように、概念的にループ構造をもっているので、このような構造を使って環境を表すと再帰関数を実装することができる。具体的な実装としては，let rec のかわりに，参照型(ref型)をうまく使って実装できる．本実験では、参照型などの「汚ない」機能は使わないことにしているので、この方法は採用しないが、この方法の方が、上記の1つ目の方法より効率よく実装できる(ことが多い)。
方法3. 処理系では再帰関数に対応せず、再帰しない関数だけを使って再帰関数を表現する、というテクニックを、ユーザ(プログラマ)に使ってもらう。
ラムダ計算の授業などを受講している人は、「ラムダ式だけを使って再帰関数を定義する方法」として習ったことがあるだろう。知らない人は、「Yコンビネータ」というキーワードで検索すると良い。ただし、この方法は、ユーザに負担をかける(ユーザがラムダ計算の理論をよく知っていなければいけない)という事のほか、効率が非常に悪くなる可能性が高い、という欠点がある。

ここでは、第1の方法に基づいて、再帰関数の実装を行い、他の方法は発展課題とする。第1の方法では、再帰しない関数のほかに、再帰関数というデータが必要になるので、値の型を拡張する。

type value = 
  | IntVal  of int        
  | BoolVal of bool       
  | ListVal of value list 
  | FunVal  of string * exp * ((string * value) list)
  | RecFunVal  of string * string * exp * ((string * value) list)

ここで FunVal は再帰しない関数の値で、RecFunValが追加部分である。 let rec f x = e1 in e2 という形の式で再帰関数 f が導入された場合、その値を RecFunVal("f", "x", e1, env) という形で保持するためのものである。ここで env は FunVal のときと同様、この let rec式を評価するときの環境である。

次に、let rec の処理をeval4 に追加する。新しいインタープリタを eval6 と呼ぶ。

let rec eval6 e env =
  ...
  match e with
  ...
  | LetRec(f,x,e1,e2) ->
      let env1 = ext env f (RecFunVal (f, x, e1, env))
      in eval6 e2 env1
  ...

この定義は、それほど難しくないだろう。 let rec f x = e1 in e2 という式をeval6 にかけると、 RecFunVal(f,x,e1,env) という再帰関数値を生成し、 f=RecFunVal(f,x,e1,env) という束縛を現在の環境 envに追加して、 e2を評価する、というものである。

次に、関数適用により再帰関数を使う部分の処理を記述する。これは、 App(e1,e2) に対する処理の変更(e1 が再帰関数値だったときの処理の追加)となる。

  ...
  | App(e1,e2) ->
      let funpart = (eval6 e1 env) in
      let arg = (eval6 e2 env) in
        begin
         match funpart with
         | FunVal(x,body,env1) ->
            let env2 = (ext env1 x arg) in
            eval6 body env2
         | RecFunVal(f,x,body,env1) ->
            let env2 = (ext (ext env1 f funpart) x arg) in
            eval6 body env2
         | _ -> failwith "wrong value in App"
        end

ここで RecFunVal の部分を追加した。App(e1,e2) の計算においては、 e1 を評価した結果を funpartとするとき、funpart が再帰しない関数 FunVal であるか、再帰関数 RecFunVal かで場合分けしている。前者と後者の処理は非常に似ているが、違いが一点だけあり、後者では、f=funpartという束縛を環境に追加しているのである。これは何故かといえば、再帰関数の本体 body を評価するときは、 f への再帰呼び出しが含まれているかもしれないので、 f=funpart という束縛を環境の中にいれなければいけないのである。一方、前者では、再帰しない関数であるので、 bodyを計算している最中に f=funpartという束縛はあってはいけない。 (body の中で fを呼びだしているところがあれば、その f はもっと外側で束縛されているはずである。)

このように、再帰関数の処理は(言葉で書くと長いが)処理の上では非常に単純に記述できた。

[2024/11/06 追加] 上記の実装について，昨日まで掲載していたもの(以下のコード)にはバグがあるという指摘があり，修正した．

(誤りを含む実装)
         | RecFunVal(f,x,body,env1) ->
            let env2 = (ext (ext env1 x arg) f funpart) in
            eval6 body env2

正しい実装との差は，環境の拡張において，f の束縛をしてからx を束縛する(正しい実装)か，逆に，xの束縛をしてから fを束縛する(誤った実装)かである．両者に差が出るのは，以下のプログラムのように関数名と引数名に同じ名前を使った場合である．

  let rec f f = f in f 7 ;;

「誤った実装」が，どういう意味で間違いかを解析した人は下記の発展課題の解答としてほしい(必須課題ではない)．この誤りを指摘してくれた受講生の尾釜君に感謝する．

課題 5-3.

再帰関数の動きを見るため、以下のテストプログラムを空の環境のもとで評価し、その実行過程を考えてみよ。

  let rec f x = x in 0
  let rec f x = x in f 0
  let rec f x = if x = 0 then 1 else 2 + f (x + (- 1)) in f 0
  let rec f x = if x = 0 then 1 else x * f (x + (- 1)) in f 3
  let rec f x = if x = 0 then 1 else x * f (x + (- 1)) in f 5

上記以外の再帰関数を定義し、eval6 を使って実行せよ。 (たとえば、課題1 で作成した fibや gcd を定義してみよ。)
[必須ではない課題] 上記の実装では、再帰呼び出しが起こるごとに、環境の拡張 (ext関数の呼びだし)を行っており、効率がやや悪い。これを改善することは可能だろうか？ (アイディアを述べればよく、実装しなくてもよい。)
[必須ではない課題] 上記の第1の方法の「誤った実装」について、正しい実装との差異が生じるプログラム例を与えた上で、両者の差異がなぜ生じるか説明せよ。
[必須ではない課題] 上記の第2、第3の方法の概要を後述の項目で述べるので、それのいずれかを実装せよ。

補足: 第2の方法(バックパッチ)

第2の方法は、環状のデータ構造を必要とする。それをref型を使って実装する。 ref型については、この実験では極力使わないようにしてきたが、以下の簡単な例題を見れば使い方はわかるであろう。

  let x = ref 100 in
    x := !x + 10;
    x := !x * 20;
    !x

(ref 100) という式は、メモリ領域(特にヒープ領域)からメモリを1つもらってきて、その初期値を 100 とする。上記の let式で x に代入されるのは「100」という値ではなく、「100が格納されているメモリ領域」あるいは、「100が格納されているメモリ領域への参照(ポインタ)」である。 C言語と違って、OCaml では、参照(ポインタ)に1を足したり引いたりすることはできない。参照(ポインタ)の値を取り出すには「!」の記号をつける。また、値を更新するには「:=」の記号を使う。なお、上記の ref 100 という式や x という変数は int ref という型を持つ。これを「参照型」と言う。

このようにして、C言語や Java言語と同じように、「変数に値を格納し、それを更新する」というプログラミング・スタイルが OCamlでも可能となる。 (なお、C言語の変数と OCamlの参照は、若干違う。上記の ref 100 で生成された参照は、 let x = ... のスコープを抜けた後も生き残り、将来、どこからも使われなくなった後に、「ごみ集め」によって消える。) さて、第2の方法の実装である。まず、第1の方法で使った RecFunVal は、 string, string, exp, env の4つのデータを集めたものであったが、今回は環境のところを環状のデータ構造にしたいので、そこを参照型に変更する。

type value = 
  | IntVal  of int    
  ...
  | RecFunVal of string * string * exp * env ref
and
  env = (string * value) list

インタープリタ eval6 のうち、変更すべき箇所は、LetRec の処理と Apply の処理の2か所だけである。 (以下では、変更後のeval6をeval6bとする。) まず、LetRecの処理は、以下の通りである。

最初は、どのような環境を RecFunValの引数にいれればよいか決まらないので、とりあえず、空の環境を作って、そこへの参照をいれておく。これを eerefという名前とする。(これはダミーであり、すぐに違う環境を代入する。)
次に、第1の方法と同様に、現在の環境 env に、再帰関数とその値である再帰クロージャの対を追加したものを作成する。第1の方法では、(ext env f (RecFunVal (f, x, e1, env)) であったが、第2の方法では、(ext env f (RecFunVal (f, x, e1, eeref)) となる。作成された環境を env1 と呼ぶ。
その環境ができたあとに、eeref のところを env1 で書きかえる。
再帰関数の本体を、env1 のもとで実行する。

以上をまとめると、以下の実装となる。

  | LetRec(f,x,e1,e2) ->
      let eeref = ref (emptyenv ()) in
      let env1 = ext env f (RecFunVal (f, x, e1, eeref))
      in 
        begin
          eeref := env1;
          eval6b e2 env1
        end

次に、この再帰クロージャを使うところを修正する。クロージャを使うのは関数適用の場合のみであり、App のケースの処理を修正する。修正点は、第1の方法では、RecFunValの第4引数が環境だったものが、第2の方法では、「環境への参照」に変わったのでその分を直す。そして、第1の方法では、App を処理するごとに、環境に新たに再帰関数とその値を追加しないといけなかったが、今回は、その処理は不要である。 (環境の中で、環状の構造があるので、いわば無限回、再帰関数の定義を使うことができる。) 実装は以下の通り。

      | App(e1,e2) ->
  let funpart = (eval6b e1 env) in
  let arg = (eval6b e2 env) in
    begin
      match funpart with
        | FunVal(x,body,env1) ->
            eval6b body (ext env1 x arg)
        | RecFunVal(f,x,body,env1ref) ->
            let env2 = (ext (! env1ref) x arg) in
              eval6b body env2
        | _ -> failwith "wrong value"
    end

以上で、第2の方法の実装は終わりである。

第2の方法は、参照型を使うという代償は払ったが、第1の方法と比べて、再帰呼び出しごとに環境を拡張しなくて済むという点で、実行速度の向上が期待できる。

参考: 第3の方法(Yコンビネータ)

第3の方法は、言語処理系には一切手を加えず、プログラマ側の負担で再帰関数を実現するものである。一般論は、ラムダ計算の参考書・授業で学習してもらうこととして、ここでは、例で説明する。

以下のものは通常のfact 関数(階乗を計算する関数)をOCamlで記述したものである。

  let rec fact x = if x = 0 then 1 else x * (f (x-1)) in fact 10

これを、以下のように変形すると、

  let fact = fun f -> fun x -> if x = 0 then 1 else x * ((f f) (x-1))
  in (fact fact) 10

この関数は、再帰呼び出しを使わずに実装される。後者のプログラムは OCaml では型がつかないが、miniOCaml言語は(ここまでの範囲では) 型をチェックしていないので、上記の手法で再帰関数を実現できる。

なお、この方法は高階関数を使う等をしているので、効率は上記2つの方法より悪い(ことが多い)。

トップ, 前へ, 次へ.

亀山幸義