変数の有効範囲を表す用語に「スコープ (scope)」があります。この用語を使うと、厳密ではありませんが、変数の有効範囲は「レキシカルスコープ」と「ダイナミックスコープ」の 2 つに分けることができます。
伝統的な Lisp はダイナミックスコープですが、近代的なプログラミング言語、たとえば Common Lisp, Scheme, SML/NJ はレキシカルスコープを採用しています。
それでは、レキシカルスコープについて詳しく見てみましょう。変数 x を表示する関数 foo を定義します。
- val x = "global\n"; val x = "global\n" : string - fun foo() = print x; val foo = fn : unit -> unit - foo(); global val it = () : unit
関数 foo には局所変数 x を定義していないので、foo を実行した場合は大域変数の値を参照します。その結果 global が表示されます。それでは、foo1 という関数から foo を呼び出す場合を考えてみましょう。foo1 には let で局所変数 x を定義します。この場合、foo はどちらの値を表示するのでしょうか。実際に試してみましょう。
- fun foo1() = let val x = "local\n" in foo() end; val foo1 = fn : unit -> unit - foo1(); global val it = () : unit
大域変数の値 global を表示しました。このように、foo1 で定義した局所変数 x は、foo から参照することはできません。次の図を見てください。
┌────── SML/NJ system ──────┐
│ │
│ 大域変数 x ←────┐ │
│ │ │
│ ┌→┌─ 関数 foo ──────┐ │ │
│ │ │ ┌──────┼─┘ │
│ │ │ print x │ │
│ │ │ │ │
│ │ └────────────┘ │
│ │ ┌─ 関数 foo1 ─────┐ │
│ │ │ │ │
│ │ │ ┌─let : x ───┐ │ │
│ │ │ │ │ │ │
│ └─┼─┼─ foo() │ │ │
│ │ └────────┘ │ │
│ └────────────┘ │
│ │
└────────────────────┘
図 : レキシカルスコープ
上図では変数の有効範囲を枠で表しています。foo1 の let で定義した局所変数 x は、let の枠の中でのみ有効です。もしも、この枠で変数が見つからない場合は、ひとつ外側の枠を調べます。順番に外側の枠を調べていくと、最後には関数定義の枠に行き着きます。ここで変数（引数）が見つからない場合は大域変数を調べます。
関数 foo は関数定義の枠しかありません。そこに変数 x が定義されていないので、大域変数を調べることになるのです。このように、関数 foo から foo1 の枠と let の枠を超えて変数 x にアクセスすることはできないのです。これを「レキシカルスコープ (lexical scope)」といいます。レキシカルには文脈上いう意味があり、変数が定義されている構造の範囲内 (枠内) でないと、その変数にアクセスすることはできません。
ところが伝統的な Lisp の場合、foo1 で定義した変数 x は呼び出された関数 foo からアクセスすることができます。これを「ダイナミックスコープ (dynamic scope)」といいます。foo1 で定義された変数 x は、foo1 の実行が終了するまで存在し、foo1 から呼ばれた関数ならば、どこからでも参照することができます。もしも、foo1 をダイナミックスコープの処理系、たとえば Emacs Lisp で実行するならば、foo で表示される x の値は local になります。
それでは、匿名関数や局所的な関数の場合はどうでしょうか。次の例を見てください。
リスト : リストの要素を n 倍する fun mapcar(_, nil) = nil | mapcar(f, x::xs) = f x :: mapcar(f, xs) fun times_element(n, l) = mapcar(fn x => x * n, l)
匿名関数の引数は x だけですから、変数 n は大域変数を参照するように思われるかもしれません。ところが、変数 n は関数 times_element の引数 n を参照するのです。これを図に示すと、次のようになります。
┌────── SML/NJ system ─────┐
│ │
│ ┌─ times_element : n, l ─┐ │
│ │ ↑ │ │
│ │ └─┐ │ │
│ │ ┌── fn : x ──┐│ │ │
│ │ │ ↑ ││ │ │
│ │ │ ┌──┘ ││ │ │
│ │ │ x * n ││ │ │
│ │ │ └───┼┘ │ │
│ │ └────────┘ │ │
│ └─────────────┘ │
│ │
└───────────────────┘
図 : 匿名関数内の変数
ポイントは、匿名関数が times_element 内で定義されているところです。変数 n は関数の引数として定義されていて、その有効範囲は関数の終わりまでです。匿名関数はその範囲内に定義されているため、変数 n にアクセスすることができるのです。つまり、関数内で定義された匿名関数は、そのとき有効な局所変数にアクセスすることができるのです。
これは let で定義された局所的な関数も同じです。times_element は次のように書き換えることができます。
リスト : リストの要素を n 倍する
fun times_element(n, l) =
let
fun timesN x = x * n
in
mapcar(timesN, l)
end
関数 timesN は times_element 内で定義されているので、timesN から times_element の引数 n を参照することができます。
簡単な例題として、クイックソートを高階関数に改良してみましょう。データを比較する関数を渡すことで、クイックソートを多相型関数にすることができます。次のリストを見てください。
リスト : クイックソート
fun quicksort(_, nil) = nil
| quicksort(f, x::xs) =
let
(* リストの分割 *)
fun partition(_, nil, a, b) = (a, b)
| partition(z, y::ys, a, b) =
if f(y, z) then partition(z, ys, y::a, b)
else partition(z, ys, a, y::b)
val (m, n) = partition(x, xs, nil, nil)
in
quicksort(f, m) @ (x :: quicksort(f, n))
end
quicksort の第 1 引数 f がデータを比較する関数、第 2 引数がリストです。リストを分割する関数 partition は quicksort 内で定義しているので、quicksort の引数 f を参照することができます。わざわざ関数 f を partition に渡す必要はありません。なお、partition は末尾再帰でプログラムしています。ご注意ください。
それでは、実行例を示します。
val quicksort = fn : ('a * 'a -> bool) * 'a list -> 'a list
- quicksort(op <, [5,9,1,8,2,7,3,6,4]);
val it = [1,2,3,4,5,6,7,8,9] : int list
- quicksort(op >, [5,9,1,8,2,7,3,6,4]);
val it = [9,8,7,6,5,4,3,2,1] : int list
- quicksort(op <, ["c", "a", "d", "e", "b"]);
val it = ["a","b","c","d","e"] : string list
関数型をみると quicksort は多相型関数として定義されていることがわかります。比較関数を渡すことで、データを昇順でも降順でもソートすることができます。