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))
は,x1y(+ 2 2) の値(つまり 4) であると宣言した下で,式 (* (+ x y) v) を評価する,という意味である.

通常,宣言には,宣言が有効な場所・期間としての有効範囲・スコープ(scope) という概念が定まる.有効範囲をはずれたところで宣言を参照することは できない.上の let 式中で,宣言された変数 xyのスコープは (* (+ x y) v) である.一般に,mini Scheme3let 式は,
    (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_explet 式を扱う部分では, 最初に,束縛変数名,式を取りだし,各式を評価する. その値を使って,現在の環境を拡張し,本体式を評価している.

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