Previous Up

3.11  いろいろな引数渡しの方式 — 値呼び・参照呼び・名前呼び・必要呼び

前節までの言語では，値呼び出しに基づいて関数呼び出しの際の引数渡しを実 現してきた．本節では，FORTRAN, Pascal などに見られる 参照呼出し(call-by-reference)と，遅延評価(lazy evaluation)を使った， Algol60 に見られる 名前呼出し(call-by-name)，Haskell などに見 られる，必要呼出し(call-by-need)といった引数渡しの方法をみてい く．

3.11.1  参照呼出し

前節で説明したように，値呼出しの下では，関数のパラメータに対する代入は 関数呼出し側に影響をおよぼすことはない．つまり，関数呼出しの前後で，あ る変数の内容が変わることがなく，呼出し側・関数側の干渉がない 7ことが保証されるため，プログラムの動作を考えるに当たって， 非常に助けになる．

しかし，一方で，関数に変数を渡し，内部で代入をしてもらい，その「代入さ れた結果」を呼出し側で利用したい場合もある．これは，関数呼出し時に，実引数 の格納場所をそのまま関数に渡すことで実現できる．このような 引数渡しの方法を参照呼出しという．関数への引数が，変数参照である場合， その格納場所 (denoted value) を渡し，他の種類の式である場合は， 値呼出しと同様に，新たに格納場所を確保し，その引数の値 (expressed value)を割り付けて渡す．

参照呼出しは，しばしば，複数の値を返す関数を模倣するために用いられる． ひとつの値を関数の通常の返り値とし，残りを代入を使って渡すのである．例 えば，Exercise 23のプログラムは，参照呼出しの下で 

(let 
  ((a 3)
   (b 4)
   (swap (lambda (x y)
            (let ((temp x))
              (let ((d (set x y)))
                (set y temp))))))
  (let ((d (swap a b)))
     (- a b)))
と書くことができる．これは値呼出しの下では -1 を，参照呼出しの下 ではswap 内の代入が呼出し側に及ぶため，a と b の内容 が入れ替わって，1となる．

参照呼出しの引数は，同じ場所を指す可能性がある． 次のプログラムで，引数 x，y は同じ場所を指すので， 実行結果は 4 になる． 

(let
  ((b 3)
   (p (lambda (x y)
        (let ((d (set x 4))) y))))
  (p b b))
このように，違う名前が同じものを指す現象をエイリアシング(aliasing)と呼ぶ．通常，ある変数の内容を更新して別の名前の変数の内容に 影響がでることは期待しないため，エイリアシングはプログラムの挙動を非常 に分かりにくくする．(もちろん，値呼出しであっても，参照が expressed value であるような言語ではエイリアシングが発生する．)

参照呼出しの実現は図15にあるように，実は簡単である． まず，値の定義は前と変わらず，denoted value は expressed value への参 照として定義される．インタプリタの変更点は，関数呼出しの引数を評価する 時に ref を作る部分のみである．eval_rands には，引数が変数であった 場合に，apply_env で得られた denoted value をそのまま使うようにして いる．また，let 式に関しては値呼出しを使うので，let 用の eval_let_rands を定義している．
core.ml:

let rec eval_exp env = function
   ...
  | Let (bs, e) ->
      ...
      let arg_vals = eval_let_rands env args in
      ...

and eval_rands env = function
   ...
  | Var id :: rest -> (apply_env id env) :: eval_rands env rest
   ...

and eval_let_rands env = function
    [] -> []
  | e :: rest -> ref (eval_exp env e) :: eval_let_rands env rest


Figure 15: 参照呼出し




Exercise 26  [難易度 1] 参照呼出しをインタプリタに実装し，上の swap の例をテストせよ． また，eval_let_rands を eval_rands で代用すると，どうなるだろうか．


Exercise 27  [難易度 2] Pascal などでは，関数を定義する際に，パラメータ毎に値呼出しを使うか 参照呼出しを使うかを指定することができる．この仕組みを，文法からデザインし 実装・テストせよ．


3.11.2  遅延評価と call-by-need, call-by-name

次に，参照呼出しとはかなり違う形態の引数渡しの方法についてみる． 関数定義において，本体中でパラメータのいくつかを使用しないことが ありえる．このとき，呼出し側で対応する実引数を評価するのは無駄である． 実引数の評価が止まらない場合には，問題ですらある．

mini Schemeのように，関数が第一級の値である場合には，無駄な引数を評価し ないために，パラメータ無しの関数として渡し，関数内部で使うときに初めて 関数適用を行って引数の評価を行うというプログラミングで，この問題を避け ることができる．このように，評価を遅らせるために用いられるパラメータ無 しの関数を thunk と呼び，thunk を構成・評価することを，それ ぞれ freezing, thawing と呼ぶ．例えば， 

(let ((p (lambda (x y) (* 2 x))))
   (p (+ 2 4) (fact 150)))
のようなプログラムを，機械的に実引数を freeze し，パラメータが使われて いるところで thaw するようにして，以下のように 

(let ((p (lambda (x y) (* 2 (x)))))
   (p (lambda () (+ 2 4)) (lambda () (fact 150))))
のように書き換えることができる．(ここでは fact は階乗を計算する プリミティブと考えよ．)これにより，結果が使われないが時間のかかる階乗 の計算をせずに，プログラムが実行される．

いくつかの言語では，引数の計算を，その計算結果が使われるまで(自動的に) 遅らせる遅延評価(lazy evaluation)の仕組みが備わっている．遅延 評価の仕組みは，パラメータが複数回現れたときの処理の違いによって2種類 に分けられる．もっとも単純なやり方は，引数が使われる度に，thunk を thaw してして値を求めるもので，名前呼出し(call-by-name) と呼ば れ，Algol60 などで使われた．しかし，代入などの副作用が無い場合，くりか えし計算するのは同じ値が得られるだけで無駄である．これを改良したのが， Haskell などで採用された 必要呼出し(call-by-need) という仕組み で，一度 thaw した thunk はその値を覚えておいて，二度目以降に使われる ときには，覚えておいた値を使うものである．このふたつの機構は副作用がな い限り，同じ実行結果になる．しかし，代入などを使うと，このふたつの違い を見ることができる．例えば，以下のプログラム 

(let 
  ((g (let ((count 0))
        (lambda ()
          (let ((d (set count (add1 count)))) 
            count))))
   (double (lambda (x) (+ x x))))
  (double (g)))
で，gは呼び出される度に，前回より1大きい値を返す．名前呼出しの下 では，g は，x の出現回数である2回呼び出されて，3 を 返す．一方，必要呼出しの下では，最初の x について g が呼び 出され 1 が値となる．しかし，次の x の出現では，呼出しが起 らず，前回と同じ1 に評価され，全体の値は 2 になる．

遅延評価言語は，副作用の無い場合，プログラムの挙動の推論を非常に単純な やり方でできるという利点がある．つまり，関数適用は，本体内のパラメータ を引数で「そのまま」置き換えることでモデル化できる．(値呼出しの場合， 引数の評価が止まらない場合もあるので，厳密にはこのような推論はできない．) また，データ構造と遅延評価を組み合わせると，無限の構造を持つデータなど も簡潔に表現することができる．一方，遅延評価はプログラムの制御の流れ・ 実行順序といったものをわかりにくくするため，「いつ」おこるかが重要であ る，副作用と組み合わせると，プログラムの挙動が著しく分かりにくくなる． 実際，遅延評価が採用されている多くの言語は，副作用を起こす機能がないも のが多い．

さて，ここでは名前呼出しを練習問題として，必要呼出しを実装していく． 変数には，thunk が束縛される場合もあるため，
Expressed Value = 整数 (…, −2, −1, 0, 1, 2, 3, …) + 関数値
Denoted Value = (Expressed Value + thunk) への参照
とする．core.ml の主要な変更点を図16に示す．まず， dnval は，pre_dnval への参照として定義されている．pre_dnval は， thunk もしくは，すでに thaw された expressed value である．thunk は本 質的にはパラメータのない関数閉包であり，本体と環境を保持している．

eval_exp は変数参照の部分が，大きな変更点である．まず，環境から 変数の束縛された denoted value を取り出す．もしも，その内容が thunk であった場合は，thunk の thawing を行う．しかも， 必要呼出しなので，一度評価した thunk の値で変数の内容を 更新する．

eval_rands は，関数呼出しの引数を処理する部分である．これも これ以上評価が進まない，整数リテラル・lambda 式の場合を除いて， thunk を生成して，引数の評価を遅らせている．整数リテラル・lambda式は そのまま値になるので，thunk を作らず最初から thaw されたものになる．
core.ml:

...
and pre_dnval =
    Thunk of exp * env
  | Thawed of exval
and dnval = pre_dnval ref
...

let rec eval_exp env = function
   ...
  | Var sym -> 
      let varref = apply_env sym env in
      (match !varref with
        Thunk (e, env') ->
          let v = eval_exp env' e in
          varref := Thawed v;
          v
      | Thawed v -> v)
   ...

and eval_rands env = function
   ...
  | ILit i :: rest -> ref (Thawed (IntV i)) :: eval_rands env rest
  | Lambda (ids, body) :: rest ->
      ref (Thawed (ProcV (ids, body, env))) :: eval_rands env rest
  | e :: rest -> ref (Thunk (e, env)) :: eval_rands env rest

   ...
and eval_let_rands env = function
    [] -> []
  | e :: rest -> 
     ref (Thawed (eval_exp env e)) :: eval_let_rands env rest


Figure 16: 必要呼出し




Exercise 28  [難易度 1] 他に必要な core.ml の変更を施して，必要呼出しインタプリタを 実装・テストせよ．


Exercise 29  [難易度 1] 必要呼出しインタプリタを改造し，名前呼出しの仕組みを実装・テストせよ．


Exercise 30  [難易度 2] 上で実装されたインタプリタは let に関しては，定義される値の遅 延評価が行われない．let を遅延評価が行われるように修正せよ． また，遅延評価を行う let と，遅延評価を行わない strictlet を導入し，プログラム上で使い分けられるよう改造せよ．


Previous Up