静的スコープと動的スコープ・浅いアクセスと深いアクセス

目的

静的スコープと動的スコープ・深いアクセスと浅いアクセスについて、現代的でまとまった解説が検索では見つからないようなので書いてみる。

余談1: スコープとエクステント

プログラミング言語において「スコープ」(可視範囲)と同様程度に習得すべき概念に「エクステント」(生存期間・寿命)がある。エクステントも重要だが、この文章では必要最低限を除いて触れない。

グローバル(スコープ)とローカル(スコープ)

この文章を読むための前提として、スコープについてグローバルとかローカルといったものについては既に理解しているものとする。モジュールあるいは関数などを「またいで」可視なものがグローバル、モジュール内だけや関数内だけといった「狭められた範囲だけ」に可視なものがローカル、といった程度の理解で良い(どうせ厳密にはそれぞれの言語and・or実装により異なる)。

静的スコープと動的スコープ

手続き(関数)がファーストクラス(第一級)オブジェクト*1であるようなプログラミング言語では、名前へのアクセスを持った手続きオブジェクトを作り、それを手続きの実引数として渡したり、手続きの返戻値として戻したりすることができる。そのようにした時その中にある、名前へのアクセスがどのように決まるか、というのが、静的スコープと動的スコープである。以下、具体例で説明する。

静的スコープ

JavaScriptPythonPerlによる、同等のプログラムによるサンプルを示す。


# 実行例
$ perl static_sample.pl
a: 5
a: 5
b: 5

retxやretyの返している値が、fxy2とfxy2aで呼出しの途中で別のxやyが挟まっても、retxやretyの定義された場所からローカルにxやyといった名前を参照したものであることに注目してほしい。このように、手続きオブジェクトのようなものを引張りまわしたとしても、ソースコード上で元々静的に確定できる範囲のものが見えるというスコープ規則が「静的スコープ」である。「レキシカルスコープ」(レキシカル=字面上の)とも言う。また、スコープが静的に(レキシカルに)「閉じられる」ことから、静的スコープの手続きオブジェクトをクロージャと言う。
(先頭に b: と付いている出力は後の説明のための伏線であり、ここでは気にしなくてよい)
ここで挙げた言語以外でも、現代のプログラミング言語で手続きがファーストクラスであるような言語ではたいがいが静的スコープであり(例外はTclなどごく少数)、このようなスコープは当然のように思うかもしれない。しかし前述のようにTclあるいは昔のLispや、現在広く使われているものとしてはEmacsLispなど(ただし先日、静的スコープが入った)のように、そうでないスコープの言語and・or実装もある。

動的スコープ

ポピュラーな言語では、Perlでlocalというキーワードを使った変数が動的スコープになる。静的スコープの例と同様のプログラムが、localによる動的スコープによって結果が違ってくるPerlによる例を示す。

# 実行例
$ perl dynamic_sample.pl
a: 5
a: 112
b: 5

use strictでは修飾されない動的スコープの変数は禁止されるためパッケージを作っている。「実行時の呼出しの途中に挟まっているxとyの値」が、結果に影響していることがわかるだろう。
ここで、グローバルと同じでは? と思うかもしれないが、同じではない。グローバルであればfxy2aを抜けた後でも元に戻らない。例を示す。先頭に b: と記した出力が異なる。

# 実行例
$ perl global_sample.pl
a: 5
a: 112
b: 112

以上のように、呼出されたコンテキスト中にある名前が参照されるというスコープが、動的スコープである。
(「動的スコープ」という表現が定着しているが、正確には「indefiniteスコープ」と「動的エクステント」の組合せである、という指摘がある(CLtL2eの "3. Scope and Extent" http://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node43.html )。ここでindefiniteというのは、Schemeの仕様ではinfiniteと言っているもの(一般に「無限」と訳されている)と同様だが、CLではそのように表現する。CLtL(及び同2e)の訳書ではindefiniteは「無限」と訳されている。ISLISP(JIS X 3012)では "indefinite extent" を「無制限の存在期間」としている)

余談2: C言語の「static」

C言語では "static" というキーワードに、文脈によって全く違う意味を持たせており、きわめて宜しくない。まず、C言語には関数ポインタはあっても関数そのものはファーストクラスではないため、基本的にはここで説明したような静的スコープは無い(拡張が提案されたことはあるし、GCCには実装されたりもしていた。C++では拡張されている)。
C言語のstaticは、トップレベル(関数の外)にある場合、修飾対象の名前のスコープが、デフォルトではモジュール(ファイル)外にもエクスポートされるのに対し、staticを付けるとモジュール内のみに制限する、という意味がある。
関数の中で変数にstaticを付けた場合は、修飾された変数のスコープはローカルでデフォルトと変わらないがエクステントがプログラムの起動から終了までに変化、すなわち静的に(関数の呼出しと脱出にともなって生成・消滅する、という動的エクステントから)変化する。意味的には、前者ではなく後者が "static" という表現にマッチしていると言えば言えるかもしれない。

余談3: PHP

PHPの公式なドキュメントにおいて、Another important feature of variable scoping is the static variable.のようにキーワード static がスコープに関連するものと読めなくもない表現があるが( http://php.net/manual/en/language.variables.scope.php#language.variables.scope.static )この「PHPのstatic」は、説明を読めば明らかだが、C言語で後者として説明した、スコープではなく、エクステントを動的ではなくするキーワードである。まぁ、いつものパターンをさらにまたもう1つ見掛けたにすぎないわけだが、PHPには最近クロージャも追加されたので、プログラマ諸氏の混乱がせめて増大しないよう願うばかりである。

深いアクセスと浅いアクセス

「深いアクセス」は「深い束縛」、「浅いアクセス」は「浅い束縛」とも言うが、基本的に言語の意味(仕様)ではなく実装について議論したいので、意味の議論で使うこともある「束縛」という言葉は避ける。
古い文献などでは、前半で説明したようなスコープの話とチャンポンになっていることがあるが(実際、仕様を実現しているのは実装であるわけだけども)、現代的にはこの「深い」「浅い」の用語と議論は、意味ではなくもっぱら実装を指している。
まず、ここで議論するプログラミング言語処理系はインタプリタを前提とし、特に変数名の解決を事前に(ソースコード読取り・内部表現構築)済ませるのではなく、実行時に行うものとする。コンパイラなどの技法については他を見ること(スタックフレーム、特に静的スコープを実現するための静的リンク*2は『エキスパートCプログラミング』の p. 157 に簡単な、『最新コンパイラ構成技法』(タイガーブック)の p. 122~124 に詳細な解説がある。実装の一例は "Lexical Closures for C++"(1988) が詳しい。他の技法としてはディスプレイやDe Bruijn インデックスなど)。
プログラミング言語処理系などにおいて、プログラムの実行時に「名前 → 値」の情報を提供するものを環境と呼ぶ。名前空間(関数やブロック)の字句上のネストや呼出しのネストに対応して、単方向リンクリストないしはスタックのようなデータ構造ベースのシンボルテーブルによって環境を保持し、ネストの外側の名前にはそれを辿ってアクセスする、という手法が「深いアクセス」である。
それに対し、Ο(1) なハッシュテーブルのようなデータ構造をひとつだけ持ち、常にそれに「今見えている名前だけ」を保持するようにする手法が「浅いアクセス」である。以下、前半で使ったサンプルを例としてそれぞれを詳解する。

深いアクセス

まず、構文を仮想の言語に単純化して、サンプルを示す。

def fxy2(x, y) {
  def retx() { x }
  def rety() { y }
  fxy2a(retx, rety, 45, 67)
  print(retx() + rety())
}

def fxy2a(f, g, x, y) {
  addfun(f, g)
}

def addfun(f, g) {
  print(f() + g())
}

fxy2(2, 3)

ここで、まず説明が単純な、深いアクセスによる動的スコープの実現方法から説明する。
手続きaddfunの実行中、環境は次の図のようになっている(一例。LispLispを簡単に実装する場合などはリストのリストにすることが多いだろう)。

それぞれのテーブルは、それぞれの手続き呼出しの最初に作られ、呼出しから抜ける時に破棄される。xやyという名前を「深いほうに」探していった時に、「動的なスコープによる」45や67が先に見つかる、ということがわかるだろう。
次に、静的スコープの実現方法を説明する。静的スコープでは、手続きは自身の内容だけではなく、定義された時点の環境の情報も持たなければならない。名前を解決するための情報が内部にあって、外部に依存しない(閉じている)ことから、クロージャ(閉包、特に「関数閉包」)と呼ばれている。
静的スコープを深いアクセスで実装した一例における、addfunの実行中のデータ構造を図にすると次のようになる。右側に描いたそれぞれのクロージャがそれぞれの定義されている環境へのポインタを持っているのが重要で、それぞれのクロージャの中の手続きを実行(評価)する際は、まずこのポインタをたどった先のフレームを「今の」環境とする。各フレーム内にはリターンアドレスは無く、環境とは別のフレームが必要である。

以上のように、典型的な実装法であれば、深いアクセスで静的スコープを実装するのも動的スコープを実装するのも、あまり大きな違いは無い。(なお、見ればわかる通り、ここで示したような典型的実装法ではデータ構造にループが発生するので、データ構造のコピーや、GCを参照カウントで行いたい場合など、注意が必要である)

浅いアクセス

浅いアクセスは、実行中のプログラムにおいて、、現在見えている(スコープにある)名前を全て、ハッシュテーブルのような一発でアクセスできる1個のシンボルテーブルに保持する方法である(簡単な実装などでは連想リスト等を使うこともあるだろうが)。近年のLightweight Language等では組込みの連想配列(辞書構造)を使えば良いだろうし、Lispならシンボルを使う手もある。
深いアクセスの場合と同じ例で、やはり動的スコープの場合から説明する。深いアクセスとは異なり実行状況を表現するデータ構造が直接作られるわけではないため、実行が進行する順に説明する。
まず fxy2(2, 3) を実行しようとする時点でのシンボルテーブルは次のようになっている(実際には手続きの値は何らかの内部表現であろう)。

{
  addfun → func (f, g) { print(f() + g()) }
  fxy2 → func (x, y) { def retx() {...... }
  fxy2a → func (f, g, x, y) { addfun(f, g) }
}

これが、fxy2の3行目の fxy2a(retx, rety, 45, 67) を実行しようとする時点では次のようになる。

{
  addfun → func (f, g) { print(f() + g()) }
  fxy2 → func (x, y) { def retx() {...... }
  fxy2a → func (f, g, x, y) { addfun(f, g) }
  retx → func () { x }
  rety → func () { y }
  x → 2
  y → 3
}

さらに fxy2aの中では、

{
  addfun → func (f, g) { print(f() + g()) }
  f → func () { x }
  fxy2 → func (x, y) { def retx() {...... }
  fxy2a → func (f, g, x, y) { addfun(f, g) }
  g → func () { y }
  retx → func () { x }
  rety → func () { y }
  x → 45; x → 2
  y → 67; y → 3
}

となる。xとyは、既に存在している要素を一時的に上書きし、あとで回復できる特殊なハッシュテーブルを使っていることにする。手続き呼出しが深くなる方に追ってみたが、抜ける側は、シンボルテーブルからその手続き内で上書きした要素を回復し、その手続き内で追加した要素を削除すればよい。
このように、浅いアクセスにおいても、単純に「手続きに入りながら追加、出るとき復旧」というようになるのが、動的スコープの実装ということになる(保存・復帰すべき名前は、実行前に解析して決定してしまうか、スタックなどを併用する必要があるかもしれない)。
これに対し、浅いアクセスで静的スコープを実装するには、手続き内から他の手続きを呼び出す際にもスコープから抜ける名前について何か(スタックなど)に保存し、そこから戻ってきた時だけでなく、ネストして定義されている手続きが他から呼ばれた時にも保存したものを復帰させる必要がある。
やはり同じサンプルを例にすると(再掲)、

def fxy2(x, y) {
  def retx() { x }
  def rety() { y }
  fxy2a(retx, rety, 45, 67)
  print(retx() + rety())
}

def fxy2a(f, g, x, y) {
  addfun(f, g)
}

def addfun(f, g) {
  print(f() + g())
}

fxy2(2, 3)

fxy2からfxy2aを呼ぶ時にxとyは(静的スコープの)スコープから外れるので、スタックフレームなどに保存して、シンボルテーブルから外す必要がある。そのスタックフレームはretxやretyのクロージャから指されている必要があり、fxy2 → fxy2a → addfunと呼出しが進んで、addfunの中でfとgとしてretxおよびretyを呼ぶ時に、元の(2と3という値を保持している)xとyをシンボルテーブルに加える必要がある。抜けてゆく時には、全てを以上の逆順に戻してゆく。

おわりに

静的スコープと動的スコープ・深いアクセスと浅いアクセスについてまとめた。実装の際には、特に静的スコープにおけるindefiniteエクステントのことも考える必要があり、ストリクトにLIFO(FILO)なスタックではなく、リストによるスタック(フレームが他からも参照されている場合はGCされず消滅しない)などを使う必要がある、といった話もあるが(いわゆる「FUNARG問題」の一部)、ここでは省略する。

付記1・Lisp

以上ではプログラミング言語を限定しない議論に努めたつもりだが、この節では特にLispに限定して浅いアクセスについて議論する。Lispでは伝統的に、いわゆる「同図像性」により、プログラム自身もまたLispデータで表されている。そのデータ構造中で、変数はシンボルオブジェクトで表されているのだから、やはり伝統的なLispのシンボルオブジェクトのようにその中にデータを参照できるスロットがあれば、そこに変数値を保存するようにすることで、効率よいインタプリタが実現できる。Lispではこれが浅いアクセスの一番のキモなのかもしれない。

*1:この「オブジェクト」は、オブジェクト指向のそれではなく、もっと広いプログラミング言語一般における値を指す意

*2:「動的リンクライブラリ」などの「動的リンク」の逆の「静的リンク」とは全く無関係なので注意