レキシカルスコープとダイナミックスコープ

1. レキシカルスコープとダイナミックスコープの違い

言語によって、変数のスコープに関する仕様が異なる。スコープには、レキシカルスコープとダイナミックスコープがある。採用しているスコープにより、変数の参照の仕方が違う。

レキシカルスコープでは、プログラムとして書かれた字句を解析すれば、変数のスコープを把握できる。実行時のことは考えなくて良い。これに対して、ダイナミックスコープでは、実行時における関数の呼び出され方により、参照できる変数が異なる。

用語の説明を見る前に、具体例を見た方が理解しやすい。

Scope (computer science) - Wikipedia の Lexical scoping and dynamic scoping によると、

… if function f invokes a separately-defined function g, then under lexical scoping, function g does not have access to f's local variables (since the text of g is not inside the text of f), while under dynamic scoping, function g does have access to f's local variables (since the invocation of g is inside the invocation of f).

（同上より、装飾は引用者による）

関数 f から関数 g を呼び出す場合を想定する。関数は、各々独立に定義されており、一方の関数がもう一方をネストしてないとする。

関数 f で定義されているローカル変数を、関数 g から、

1. レキシカルスコープでは、参照できない。
2. ダイナミックスコープでは、参照できる。

 

各言語が採用しているスコープ

言語によって、採用しているスコープが異なる。もしくは、両方使える。

Lexical scoping によると、

Lexical scoping is standard in all ALGOL-based languages such as Pascal, Modula2 and Ada as well as in modern functional languages such as ML and Haskell.

Dynamic scoping

Some languages, like Perl and Common Lisp, allow the programmer to choose static or dynamic scoping when defining or redefining a variable. Logo and Emacs lisp are examples of languages that use dynamic scoping.

多くの言語で、レキシカルスコープが採用されている。ダイナミックスコープを採用している言語として、Emacs Lisp がある。

 

レキシカルスコープの例

Scope (computer science) - Wikipedia に書かれていた例を、各言語で試してみる。

Python

x = 7
def g(): return x
def f(): 
    x = 9
    return g()
print f()           #=> 7

javascript

var x = 7;
function g(){ return x; }
function f(){ 
    var x = 9;
    return g();
}
f();                //=> 7

Haskell

x = 7
g = x
f = let x = 9 in g
main = print f      #=> 7

scheme

(define x 7)
(define g (lambda () x))
(define f
  (lambda ()
    (let ((x 1))
      (g))))
(f)   ;=> 7

関数 f が呼び出された後に、関数 g が呼び出されても、関数 g の中にある変数の参照先は変わらない。

レキシカルスコープの実行結果を見ると、「コレ普通じゃない？」と感じる。理由は、

Dynamic scoping によると、

dynamic scoping can be dangerous and few modern languages use it.

ダイナミックスコープは取り扱いが難しいので、モダンな言語でほとんど採用されていない。そのため、レキシカルスコープの考え方の方が馴染みがある。

 

ダイナミックスコープの例

続いて、ダイナミックスコープを採用している Emacs Lisp の例。

Emacs Lisp

(setq x 7)
(defun g () x)
(defun f ()
  (let ((x 9))
    (g))
(message "%d" (f))  ;=> 9

レキシカルスコープの言語に慣れていると、ダイナミックスコープの結果に違和感を感じる。

関数 f を呼び出した後、関数 f の中で関数 g が呼び出される。これにより、関数 g の中にある変数の参照先が変わってしまう。

もし、関数 f が呼び出されず、関数 g だけが実行されたら、

(setq x 7)
(defun g () x)
(message "%d" (g))  ;=> 7

関数の呼び出され方により、参照できる変数が変わる。実行時のことを考える必要なければならない。そのため、コード全体を見通すことが大変そう。 (+_+)

では、ダイナミックスコープにメリットはあるのだろうか？

Emacs Lisp - Wikipedia によると

Emacs Lispは、アプリケーション・プログラミングで使われる方言群であるSchemeやCommon Lispとは根本的に異なる。大きな違いの1つは、デフォルトで字句的スコープではなく動的スコープを使うことである。つまり、呼出し関数の局所変数は、ポインタや参照を渡さなくとも、呼び出された関数から参照できる。

関数から呼び出された側の関数は、自分のローカルにある変数の内容が、呼び出された文脈により変化する。

レキシカルスコープ的な視点で考えると、呼び出された側の関数は、呼び出した側の関数にネストされたかのように見える。

ところで、なぜ Emacs Lisp は、ダイナミックスコープを採用したのだろう？

Scope (computer science) - Wikipedia, the free encyclopedia によると、

Correct implementation of static scope in languages with first-class nested functions is not trivial, as it requires each function value to carry with it a record of the values of the variables that it depends on (the pair of the function and this environment is called a closure).

Dynamic scoping is fairly easy to implement. To find an identifier's value, the program could traverse the runtime stack, checking each activation record (each function's stack frame) for a value for the identifier.

レキシカルスコープより、ダイナミックスコープの方が実装が簡単とのこと。

Scope - GNU Emacs Lisp Reference Manual にも、同様のことが書かれている。

Emacs Lisp uses dynamic scoping because simple implementations of lexical scoping are slow. In addition, every Lisp system needs to offer dynamic scoping at least as an option; if lexical scoping is the norm, there must be a way to specify dynamic scoping instead for a particular variable. It might not be a bad thing for Emacs to offer both, but implementing it with dynamic scoping only was much easier.

 

2. レキシカルスコープとダイナミックスコープにおける変数の生存期間

書かれたテキストにより決まるレキシカルスコープ

Scope (computer science) - Wikipedia の Lexical scoping and dynamic scoping によると、

In lexical scoping (…), if a variable-name's scope is a certain function, then its scope is the program text of the function definition: within that text, the variable-name exists, and is bound to its variable, but outside that text, the variable-name does not exist.

レキシカルスコープでは、関数の中で定義されてる変数のスコープは、プログラムの字句によって決まる。関数の中に書かれている変数は、その関数が記述されている内側で存在するが、外側では存在しない。

 

実行時に決まるダイナミックスコープ

Scope (computer science) - Wikipedia の Lexical scoping and dynamic scoping によると、

By contrast, in dynamic scoping (or dynamic scope), if a variable-name's scope is a certain function, then its scope is the time-period during which the function is executing: while the function is running, the variable-name exists, and is bound to its variable, but after the function returns, the variable-name does not exist. （同上より）

ダイナミックスコープでは、関数の中で定義されてる変数のスコープは、その関数が実行されている期間と同じ。関数が実行されている間、変数は存在するが、関数の実行が終了すると変数は消える。

 

3. 実装から見る、名前の解決

実装の難しさ

レキシカルスコープとダイナミックスコープを実装する難しさについて、以下のように述べられている。

Lexical scoping

Correct implementation of static scope in languages with first-class nested functions is not trivial, as it requires each function value to carry with it a record of the values of the variables that it depends on (the pair of the function and this environment is called a closure).

レキシカルスコープを実装することが難しいのは、関数に対して、クロージャと呼ばれる、その関数が依存する変数（環境）を持って回る必要があるため。

Dynamic scoping

Dynamic scoping is fairly easy to implement. To find an identifier's value, the program could traverse the runtime stack, checking each activation record (each function's stack frame) for a value for the identifier. In practice, this is made more efficient via the use of an association list, which is a stack of name/value pairs. Pairs are pushed onto this stack whenever declarations are made, and popped whenever variables go out of scope.^[1]

ダイナミックスコープの実装が簡単なのは、実行中の関数に関する情報を持つスタックの中から、参照したい値を探すだけで済むため。

スタックとは、Call stack - Wikipedia によると、

Since the call stack is organized as a stack, the caller pushes the return address onto the stack, and the called subroutine, when it finishes, pops the return address off the call stack and transfers control to that address. If a called subroutine calls on to yet another subroutine, it will push another return address onto the call stack, and so on, with the information stacking up and unstacking as the program dictates.

サブルーチンを呼ぶときに、利用されるデータ構造。サブルーチンが呼び出されるとき、スタックにリターンアドレスが積まれ、呼び出されたサブルーチンが終了すると、リターンアドレスが取り出され、そのアドレスに制御が移される。

プログラムを実行するときの、メモリの利用のされ方と名称について、詳しくは、 Data segment - Wikipedia の Program memory を参照。

The computer program memory is organized into the following:

• Data Segment (Data + BSS + Heap)
• Stack
• Code segment

 

名前（識別子）の探し方

変数を参照するとき、レキシカルスコープとダイナミックスコープでは、以下の点が異なる。

Lexical scoping によると、

With lexical scope, a name always refers to its (more or less) local lexical environment. This is a property of the program text and is made independent of the runtime call stack by the language implementation. Because this matching only requires analysis of the static program text, this type of scoping is also called static scoping. …

Static scoping allows the programmer to reason about object references such as parameters, variables, constants, types, functions, etc. as simple name substitutions. This makes it much easier to make modular code and reason about it, since the local naming structure can be understood in isolation.

レキシカルスコープでは、「名前」が指し示す対象は、プログラムの字句を見れば分かる。実行時のことを考える必要ない。そのため、プログラムのテキストにおいて、参照しているものの名前を置き換えるだけで、何を指し示しているか把握できる。

Dynamic scoping によると、

With dynamic scope, each identifier has a global stack of bindings. Introducing a local variable with name x pushes a binding onto the global x stack (…), which is popped off when the control flow leaves the scope. Evaluating x in any context always yields the top binding. In other words, a global identifier refers to the identifier associated with the most recent environment. Note that this cannot be done at compile-time because the binding stack only exists at run-time, which is why this type of scoping is called dynamic scoping.

ダイナミックスコープでは、実行時に変数のような識別子があると、スタックに積まれる。その後、識別子が必要になったら、スタックに積まれている順に検索される。つまり、実行中の関数から、一番近い場所にある環境から、対象を見つけ出そうとする。

先ほどの例で考えると、

(setq x 7)
(defun g () x)
(defun f ()
  (let ((x 9))
    (g))
(message "%d" (f))  ;=> 9

1. 変数 x は 7 に束縛され、スタックに積まれる。
2. 関数 f の呼び出しにより、変数 x は 9 に束縛され、スタックに積まれる。
3. 関数 g が呼び出され、変数 x が参照される。このとき、直前にスタックに積んだ、中身が 9 の変数 x が取り出される。

これにより、結果が 9 となる。