Previous Up Next

3.9  mini Scheme6 — 変数への代入の導入

次に，変数への代入のための構文 set 式を，以下の文法で導入する．
<式> ::= …
  | (set <識別子> <式>)
set 式は <識別子> の変数に <式> の値を 「代入」する．set 式自体の値は 0 と定義する．

さて，「代入」とはなんだろうか？代入について考える前に，束縛の意味をも う一度吟味してみよう．プログラミング言語(や論理)における束縛とは，何か(こ こでは denoted value)に名前をつけるための仕組みであり，一旦束縛関係が 発生したら，通常その関係は束縛の有効範囲内で不変である．set のような代入を導入した言語においても，その原則は保たれるとしたほうが， 様々な言語を統一的に捉えることができる．束縛関係が不変だとした場合， setは，以下のようなものとして考える． まず，変数は式の値そのものにではなく，「値を格納している場所(メモリア ドレス)」に束縛されると考える．この変数と「場所」の束縛関係はこの変数 の有効範囲内で不変である．そして，set 式は変数が束縛されたアドレ スの示す「内容」を<式>の値に変更するものである，と考える．この ように考えることによって束縛の概念に手をつけずに代入を扱うことができる． 以上の議論を expressed value, denoted value の定義に反映させると，
Expressed Value = 整数 (…, −2, −1, 0, 1, 2, 3, …) + 関数値
Denoted Value = (整数 + 関数値) への参照(アドレス)
のようになる．

このようにした言語では，プログラム中の変数参照は二種類の意味を持つこと になる．例えば 

(set x (add1 x))
という式において，最初の x の出現の示すものは，変数の denoted value，すなわち束縛されているアドレスであり，ふたつめの出現の示すもの は，束縛されているアドレスの「内容」(expressed value)である．このよう に，代入のある言語では，変数に「二種類の値」が関連づけられていると考え， アドレスとしての値を左辺値(L-value)，その内容としての値を 右辺値(R-value) と呼ぶことがある．これらの名前は，C 言語の x=x+1; といった代入文で，左辺の x はアドレスであり，右辺の x は その内容を示すことに由来する．これに対し，Objective Caml の参照型は，これら の概念をきっちりと分けており，x が int ref 型とすると，x と書い た場合は常にその「左辺値」を示し，x の「右辺値」を参照する際には常に !x と明示的に書かなければならない．

代入は，プログラムの別の個所でなにかを共有するために用いることができる． 以下のプログラムは，inc，get という関数で，counter を共有している． 

(let ((counter 0))
   (let ((get (lambda () counter))
         (inc (lambda () 
                 (let ((d (set counter (add1 counter)))) 0))))
     (let ((d (inc)))
        (let ((d (inc)))
          (get)))))
d はダミーの変数で，let とともに用いて式の実行の順序付けを している．counter の内容を1増やす関数 inc を2回呼んで， counter の内容を get で得ており，全体の評価結果は 2 になる．このふたつの関数は，値をパラメータとしてやり取りするのではなく， 変数の状態を変更することで行っている．また，counter を関数に プライベートなものとして宣言することで，隠れた状態を実現できる． 

(let ((inc_and_get 
         (let ((counter 0))
            (lambda () 
              (let ((d (set counter (add1 counter))))
                counter)))))
   (+ (inc_and_get) (inc_and_get)))
2回の inc_and_get の呼出しは，呼出し時点の内部状態 (counterの値によって)それぞれ違う値を返している．

mini Scheme6 では，関数呼び出し毎に，各パラメータのために，実引数を格納す るためのアドレスを新たに用意する．このような仕組みを，値呼び出 し(call-by-value) と呼ぶ6．値呼び出しの下では，関数のパラメータに対する代入は関数の外 側では観察できない．例えば， 

(let ((x 100))
  (let ((p (lambda (x) 
          (let ((d (set x (add1 x)))) x))))
    (+ (p x) (p x))))
の値は 202 である．つまり，p の呼び出し毎に，新しいアドレスが 実引数のために割り当てられ，そこに set で代入されても，p の 外側の x には影響をおよぼさないのである．

さて，プログラムの主な変更点を図14に示す．まず， dnval 型の定義を見るとわかるように．参照を表現するものとして ref 型を用いる．変更後の apply_env は dnval を返すので，変数参照の Var を処理するときには，! オペレータを使って，中身のexval を取り 出す必要がある．代入文 Assign の処理は，代入される式の値と，変数の denoted value を計算し，Objective Caml の代入 := を使って更新している． eval_rands 関数は，引数を評価した後，それを新しく割り当てた参照値に 格納している．プリミティブの引数では，この操作は必要なく，引数式の expressed value をそのまま渡せばよいので，以前の eval_rands の定義を eval_prim_rands として使っている．
syntax.ml:

type exp = 
   ...
  | Assign of id * exp


core.ml:

type exval = ...
and dnval = exval ref
...

let extend_env_rec syms procs env =
  let vec = Array.make (List.length syms) (ref (IntV 0)) in
  ...
  iteri
    (fun i (ids, body) -> vec.(i) <- ref (ProcV (ids, body, newenv)))
    procs;

let rec eval_exp env = function
   ...
  | Var sym -> !(apply_env sym env)
  | Prim (p, es) -> 
      let args = eval_prim_rands env es in
      ...
   ...
  | Assign (id, exp) ->
      let arg = eval_exp env exp in
      let idref = apply_env id env in
      begin idref := arg; IntV 0 end

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

and eval_prim_rands env = function
    [] -> []
  | e :: rest -> eval_exp env e :: eval_prim_rands env rest


Figure 14: 変数への代入




Exercise 21  [難易度 1] 図に示した syntax.ml にしたがって，parser.mly と lexer.mll を 完成させ，mini Scheme6 インタプリタを作成し，テストせよ．


Exercise 22  [難易度 1] 式を順番に評価するための begin 式を導入したインタプリタを作成せよ．
<プログラム> ::= <式>
<式> ::= …
  | (begin <式1> … <式n>)
begin式は，<式1>から順に評価し，<式n> の値を全体の式の値とする．これを用いて，(let を使って評価順序を つけているような)テキストの例を書き直し，インタプリタでテストせよ．


Exercise 23  [難易度 2] 言語に代入を導入するもうひとつの方法は，Objective Caml に見られるように，「値の 格納場所」を expressed value として導入し，代入だけでなく，格納場所 の作成・値の取りだしも明示的な操作として導入する方法である．(引数を 初期値とした)値の格納場所を作成する ref，引数として与えられた 場所の内容を取り出す deref，第1引数として与えられた場所に，第2 引数の値を代入する setrefをプリミティブとして導入せよ．値の定 義は以下に与える．
Expressed Value = 整数 (…, −2, −1, 0, 1, 2, 3, …) + 関数値
         + Expressed Value への参照
Denoted Value = Expressed Value
そして，以下のプログラムをテストせよ． 

(let
  ((g (let ((count (ref 0)))
        (lambda ()
          (let ((d (setref count (add1 (deref count)))))
            (deref count))))))
  (+ (g) (g)))


Previous Up Next