Previous Up Next
3.5 mini Scheme3 --- 局所定義の導入

ここまで，mini Scheme中で参照できる変数は core.ml 中の global_env であらかじめ定められた変数に限られていた．mini Scheme3では変数宣言の機能を 導入する．

3.5.1 変数宣言と有効範囲

ここで導入する変数宣言のための構文は let 式と呼ばれ，宣言のみを 独立して導入できるものではなく，宣言と，その宣言の下で評価される式が対 になるものである．例えば，以下の mini Scheme3 プログラム 

(let ((x 1) (y (+ 2 2)))
  (* (+ x y) v))
は，x は 1，y は (+ 2 2) の値(つまり 4) であると宣言した下で，式 (* (+ x y) v) を評価する，という意味である．

通常，宣言には，宣言が有効な場所・期間としての有効範囲・スコープ(scope) という概念が定まる．有効範囲をはずれたところで宣言を参照することは できない．上の let 式中で，宣言された変数 x， yのスコープは (* (+ x y) v) である．一般に，mini Scheme3 の let 式は，
    (let ((<識別子1> <式1>)
              ⋮
         (<識別子n> <式n>))
       <本体式>)
といった形をしているが(形式的な定義は後で示す)，<識別子 i>の変数の有効範囲は <本体式>になる(<式i> を含まないことに注意)．また，有効範囲中でのその変数の出現は，束 縛されている(bound)といい，変数自身を束縛変数(bound variable)である，という．上の例で，(* (+ x y) v) 中のx は束縛変数である．このように，プログラムの文面のみから宣言の有効範囲や 束縛の関係が決定されるとき，宣言が静的有効範囲(static scope, lexical scope)を持つといったり，変数が静的束縛(static binding)されるといったりする．これに対し，実行時まで有効範囲がわから ないような場合，宣言が動的有効範囲(dynamic scope)を持つといい， 変数が 動的束縛(dynamic binding) されるという．また，ある式に 着目したときに，束縛されていない変数を自由変数(free variable) と呼ぶ．

また，多くのプログラミング言語と同様に，mini Schemeでは，ある変数の有効 範囲の中に，同じ名前の変数が宣言された場合，内側の宣言の有効範囲では， 外側の宣言を参照できない．このような場合，内側の有効範囲では，外側の宣 言のシャドウイング(shadowing)が発生しているという．例えば， 

(let ((x 2) (y 3))
  (let ((x (+ x y)))
    (* x y)))
において，最初の x の宣言の有効範囲は，内側の let 式全体で あるが，内側にも x が宣言されているので，(* x y) 中の x は内側の宣言に束縛される．また (+ x y) の x は外側 の宣言に束縛されるので，この式の値は，15 である．実は，最初の例でも x の宣言は，大域環境に束縛されている x のシャドウイングが 発生しているといえる．

3.5.2 let 式の導入

mini Scheme3 の構文は，以下のように与えられる．
<式> ::= …
  | (let (<束縛リスト>) <本体>)
<束縛リスト> ::= (<識別子1> <式1>) … (<識別子n> <式n>)

expressed value, denoted value ともに以前と同じ，つまり， let による束縛の対象は，式の値である．プログラムの変更点を 図9に示す．eval_exp の let 式を扱う部分では， 最初に，束縛変数名，式を取りだし，各式を評価する． その値を使って，現在の環境を拡張し，本体式を評価している．
syntax.ml:

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


parser.mly:

%token LET

Exp :
   ...
  | LPAREN LET LPAREN Bindings RPAREN Exp RPAREN { Let ($4, $6) }

...
Bindings:
 /* empty */ { [] }
  | LPAREN ID Exp RPAREN Bindings { ($2, $3) :: $5 }


lexer.mll:

let reservedWords = [
   ...
  ("let", Parser.LET);
]


core.ml:

let rec eval_exp env = function
   ...
  | Let (bs, e) ->
      let ids, args = List.split bs in
      let arg_vals = eval_rands env args in
      eval_exp (extend_env ids arg_vals env) e

Figure 9: 局所定義


Exercise 8  [必修課題] mini Scheme3 インタプリタを作成し，テストせよ．

Exercise 9  [難易度 1] ここで導入した let 式は，変数を「同時に」宣言するもので， 宣言されている変数をその宣言内で参照することはできなかった． 以下の文法
<式> ::= …
  | (letseq (<束縛リスト>) <本体>)
<束縛リスト> ::= (<識別子1> <式1>) … (<識別子n> <式n>)
で定義される letseq 式は，変数を「順番に」宣言する ものである．つまり，<識別子i>の有効範囲は， <式i+1>，...，<式n> と <式> である． 例えば以下のプログラム 


(letseq ((x 4) (y (+ x 3)))
   (* x y))
の実行結果は 52 ではなく 28 である．letseq 式をイン タプリタに実装・テストせよ．

Previous Up Next