戻る


M.I.T. AI Lab.
AI Memo 199
June 1970

The Function of FUNCTION in LISP or Why the FUNARG Problem Should be Called the Environment Problem

Joel Mose

原文


概要

多くの強力なプログラミング言語に共通するある問題が、 関数の自由変数にどんな値を割り当てるかを決めなければいけない場合に 発生する。 この問題を解くための異なる実装アプローチを考察する。 議論は、LISPの実装に集中し、 なぜ現在のたいていのLISPシステムが オリジナルのLISP1.5システムほど一般的でないのかを指摘する。 可能な限りALGOL風の用語での議論を試みたので、 LISPになじみのない読者も困難なくこの文章を読めるに違いない。


多くのプログラマは、 スタックを使って再帰関数の引数と局所変数の値を管理する事を 良く知っている (訳注1)。

具体的にするため、 スタックの端へのポインタを入れるインデックスレジスタがあると想定して、 それをスタックポインタと呼ぼう。 変数の値やスタック中の他の情報は、 スタックポインタの値に小さな値を加えたり減らしたり (どちらなのかはマシンの実装による)でアクセスできる。 スタックは、関数に入った時に下向きに大きくなっていくと想定しておく。 なので、図1はスタックポインタの、 関数fに入る直前、 引数x局所変数aとして関数fに入った直後、 fが値を返した直後、を示している。

すでに注意したように、 スタックの仕組みを使えば引数や局所変数の値は容易に得られる。 「自由」変数を提供したい場合には、状況はもっと複雑になる。 変数が関数で自由に使用されているというのは、 変数がその関数内で引数でも局所変数でもない場合である。 例えば、

  define f(x) =
  begin;
     if a>0 then return x
     else return -x;
  end;

で与えられる関数fで、変数aは自由に使用されている。 もちろんこの関数が意味をなすためには、 関数fを呼び出している関数・ブロック、 あるいは関数fを呼んでいる関数gを呼んでいる関数・ブロック等々、 で変数aが束縛されていなければ (つまり、自由でなくなっていなければ)ならない (訳注2)。

自由変数を使うというのは、非常に強力な計算上の概念である。 多くの場合、関数に引数を追加する事で自由変数の使用を避けられるが、 これはかなり煩わしくなりえるし、 手続き呼出しでたくさんのパラメータの保存が要るので非効率になる。 関数の中の自由変数をその値で置き換えるという考えの方も、例えば 自由な変数の出現と自由でない変数の出現を区別しないといけなくなるので、 非効率である。 さらにどちらの方法でも、 自由変数の値を変更して望んだ作用を達成する、という事ができなくなる。

ある関数が自由変数を使用したり自由変数を使う関数を呼んだりする場合、 その関数の値は引数だけからは完全には決まらない。 なぜなら自由変数の値にも依存するかもしれないから。 したがって計算を特定するためには、 関数と引数に加えて、 自由変数の値を決定するための環境を特定しなければならない (注1)。 スタックは、環境を管理するひとつの方法である。 この文章の目標は、環境を管理するのに、 なぜ多大な配慮が必要かを明らかにする事である。 それを行なうためにいくつかの状況を示していく。 そこでは計算を続けるのに必要な環境を適切に保つのが、 だんだん複雑になっていく。

たぶん、自由変数が現れる最も単純な状況は、 ブロック構造のプログラムである。 ある(ALGOLでの意味での)ブロックを想定する。 そのブロックは、一つ以上の局所的ブロックを含み、 その各ブロックも局所的ブロックを持っているかも知れない。 内側のブロックで自由に現れている変数には容易にアクセス・変更できる。 なぜなら、 その自由変数の値をスタックのどこに保存するのかを コンパイラは知っているから。 だから下のプログラム断片における自由変数aは、 束縛された場所の字面の上での近くで使用されていて容易にアクセスできる。

       ---------- begin local a;
       |             a = 2;
   'a' |      ---    begin local x;
  bound|      |         x = f(2) + a;
       |   'a'|         :
       |  free|         :
       |      ---    end;
       ---------- end;

しかし自由変数が再帰関数の内側で使われる状況を考えると、 たとえ字面上では関数呼出しの近くで変数が束縛されていても、 スタックのどこに値が保存されているかを知るのは難しくなる。

       --- define g(x) =
       |   begin;
   'a' |      :
  free |      a
       |      :
       |      g
       |      :
       --- end;
       --- begin local a,b;
   'a' |      a = 5;
  bound|      b = g(2);
       --- end;

上のような場合を扱うために、 自由変数の値を(したがって計算の環境も)管理するいくつかのやり方がある。 どのテクニックを使っても、いくらかの時間増加を伴う。 一つのアプローチでは、自由変数の値へのアクセスは容易だが その変数を局所的に持つブロックに入る時と出る時のコストが増える。 このアプローチはLISPの最近の実装で好まれている。 これを「浅いアクセス(shallow access)」アプローチと呼ぼう。

別のアプローチでは、 自由変数を束縛しているブロックに入るのと出るのは簡単だが、 自由変数のアクセスの方が高くつく。 このアプローチは、 LISPの古典的な「連想リスト(alist)」による実装で使われている。 いくつかのAlgolシステムは似たアプローチを選んでいる。 これを「深いアクセス(deep access)」アプローチと呼ぼう。 どちらのアプローチでも、自由変数の値のアクセスも変更もできる。 片方でのアクセス時間は、近似的には他方の変更時間と同じになる (訳注3)。

まず「浅いアクセス」アプローチを考えよう。 「浅いアクセス」は、 自由変数の値が一回のメモリフェッチで得られる事を意味する。 自由変数の現在値が スタック内の決めるのが面倒な位置に保存されるかもしれないので、 現在値のための特別なセルが使われる。 多くの最近のLISP実装では、 この特別な値セルはアトムの属性として保存され、 ひとつの自由変数に対して唯一である。 特別セルの適切な値を管理するためには、 その変数を引数や局所変数とする関数やブロックに入る毎に 余分な仕事をしないといけない。 通常、関数やブロックに入る時、 特別セルにある古い値はスタックに保存され、 スタックにあるその値がどこから来たか知るのに充分な情報が加えられる。 その関数やブロックから出る時は、 スタックに保存された値を特別セルに忘れず保存しないといけない。

「深いアクセス」アプローチでは、 自由変数の最も新しい値を得るのにスタックの上方への探索を強いられる。 もし自由変数がスタックの非常に上の方で束縛されていると、 探索が非常に深く遅くなり得る。 しかしこのアプローチは、余計な特別な値セルを必要としないという利点がある。 その上このアプローチでは、 「浅いアクセス」アプローチよりも はるかに楽で柔軟に自由変数を使えるようになる事を後ほど見る。

先ほど指摘したように、 LISPの「連想リスト」による実装は「深いアクセス」アプローチの一例である。 「連想リスト」には、 それまでの全ての束縛変数の値を変数名と一緒にしたもの へのポインタが含まれている。 変数の名前はペアの左側、変数の値はペアの右側に現れる。 だから下図で最初に出会う変数は「a」で、その値は5である。

いくつかのAlgolの実装では、与えられたブロックの全ての変数は、 線形なスタックのひと続きの場所に束縛される。 さらに、スタック内にポインタを持ち、 あるブロックに対して局所的な値も もっと外側のブロックに対して局所的な値も得られるようにしている。 だから、もし自由変数の値の探索をしないといけないなら、 このポインタを使って自由変数が束縛されているブロックまでたどり着く事で、 あるブロックに対して局所的な値も外側のブロックに対して局所的な値も得られる。

「深いアクセス」の本当の利点は、 関数をある関数やブロックから別の関数やブロックに渡す事を考えた時に判る。 始めに関数が下向きに渡される、つまり別の関数の引数として使われる、 という簡単な場合を考える。 難しい方、関数が計算結果として返される場合、は後から考える。 ALGOL60やALGOL68では関数を返すのが許されていないので、 難しい方は起きない事を注意しておく。

関数の評価は、引数に依存するだけでなく、 その関数とその関数のサブルーチンで使われるどの自由変数にも意味を与える環境 にも依存する事を思い起こそう。 関数引数(FUNARGと略される)に関して気づかないといけない重要な点は、 この場合には二つの異なる環境を含んでいる事である。 第一の環境は、実際にFUNARGが引数として束縛された環境である (訳注4)。 これを束縛環境(binding environment)と呼ぼう。 第二の環境は、実際にFUNARGが関数として活動する場所である。 これを活動環境(activation environment)と呼ぼう。

束縛環境と活動環境は一般には異なり得るので、 関数引数を評価するのにどちらの環境を使うか決める事は、 瑣末でない問題である。 次の例を考える。

  define f(x) =
     begin;
        if a = 0 then return x
        else return -x;
     end;
  
  define g(x,fun) =
     begin local a;
        a = 0;
     return x + fun(x);         activation environment
  end;
  
  begin local a, b;
     a = 1;
     b = g(3,f);                binding environment
  end;

束縛環境ではa=1、活動環境ではa=0なのを注意しておく。 もし束縛環境を使ってf(x)を評価すると、値は-3であり、 活動環境を使ってf(x)を評価すると、値は3である。 だから、どちらの環境を使うかを決めるのが重要なの事ははっきりしている。

実装の観点からは、 関数引数に対してどちらの環境を与えたいかは明白である。 活動環境の方だ。 「浅いアクセス」実装では自由変数の値がその時点で正しくセットされている、 「深いアクセス」の場合では自由変数の値が近くになる、 というのがその理由である。 残念ながら、プログラマは普通、 自由変数には束縛環境で保持されている値を持たせたい。

システムが関数引数のために束縛環境を復元するのに何が必要か、 を考えよう。 スタックまたは「連想リスト」のどこに束縛環境が存在しているかを、 環境への何らかのポインタによって知る必要があるだろう。 そういうポインタを提供する事が、LISPでのFUNCTIONの機能である。 つまり、束縛環境で評価したい関数引数fを渡す時、 QUOTE(f)の代りにFUNCTION(f)を使う。 FUNCTIONはその引数fの評価を防ぎ、これはQUOTEと同じである。 FUNCTIONの結果値は、 関数fへの参照だけでなく束縛環境へのポインタも含むような構造になる。 FUNARGが活動する時、 そのポインタを使って環境を適切な位置に復元できる。 スタック実装での「深いアクセス」の場合、 復元の過程にはそれほどコストはかからない。 スタックの現在の位置から束縛環境へのポインタを作って、 束縛環境の値とは異なっている活動環境の値を飛び越せるからである(図2を参照)。

「連想リスト」実装では、この過程はもっと簡単になる。 なぜなら、 保存したポインタが現在の「連想リスト」になり、 自由変数の値は束縛環境を持った「連想リスト」から得れば済むので。

「浅いアクセス」の場合、事情はもっと複雑になる。 スタックをさかのぼって自由変数を以前の束縛にする事で、 特殊値セルを復元しないといけない。 それが完全に束縛環境に戻るまで行なわれる。

関数引数が評価された後は、環境を活動環境に復元しないといけない (そうする必要がある事には、もちろん疑問は無いだろう)。 「深いアクセス」の場合、スタックは自動的に現在の環境に戻る。 「浅いアクセス」の場合、回復の過程を繰り返さないといけないが、 今度は束縛環境から活動環境へと下向きに行なわれる。

関数引数のためにこのように環境を変更するというのは、 これ以上の複雑さは許容できないという 「浅いアクセス」派にとって充分な実装上の困難 を引き起こすように思える。 実際には「浅いアクセス」のLISPシステムのいくつかの実装者は、 私が述べたように実装し、 適切な環境を管理するのに関係した全ての問題を解決したと考えている (Bobrow,et al[1]を見よ)。 しかしながら、もっと悪い場合がまだある事をすでに指摘していた。 関数がなんらかの計算結果として返る場合である。

この場合は「浅いアクセス」アプローチでは難しく、 それは、リターンがなされた時のスタックの部分は普通捨てられるからである。 スタックの捨てられた部分が占めていた領域は、後の計算で使用されるが、 束縛環境を保存しておくつもりなら、 リターンがなされた時のスタックの部分は捨てられない。

下の例で束縛環境の値を捨てたらどうなるかを考えよう。

  define f(x) =
  begin;
     if a = 0 then return x
     else return -x;
  end;
  
  define g(x) =
  begin local a;
     a = 2;
     return f;               binding environment
  end;
  
  begin local a, b, h;
     a = 0;
     h = g(2);
     b = h(3);               activation environment
  end;

上の例で、aの値はgの中で束縛の所では2で、 活動の所では0である。 もしgを呼んで作られる環境を捨てたら、 aに対する2という値は全く失われてしまう。 スタックは捨てないようにして束縛環境へのポインタを保存すると、 大量のゴミがfの呼出しで作られるのが判る。

したがって、束縛環境で活動する関数を返す時は、 束縛環境を保存してそこに戻れるようにしないといけない。 しかし、どのように束縛環境を復元するのか。 本質的には関数が返された所に達する地点まで スタックを上に戻さないといけない。 しかしそれだけでは充分でなく、 束縛が作られ関数からの戻りが始まった地点に達するまで、 保存した環境を下に戻らないといけない(図3を参照)。

関数からの戻り時にスタックを捨てない事により、 分岐した環境が作られる事が判る。 スタックを捨てずに複数の関数を戻すのを許すと、 作られる環境はツリーになる。 疑問は、今度は、 始めは線形のスタックだったものからツリー構造をどのように作るか になる。 もしもスタック内に上向きポインタと下向きポインタの両方を許せば、 ツリーが得られる。 だから、上向きポインタによる「深いアクセス」実装者は、 下向きポインタの導入だけが必要で、問題は解決される (注2)。 「連想リスト」による「深いアクセス」実装者は、 いつでもツリーが得られる(たぶん実装者の多くはその重要性に気づいていない)。 だからこの場合に、さらなる問題には出会わない。 だが「浅いアクセス」実装者に災いあれ。 束縛環境は管理しないといけないし、そこから変数の値を間違って得てもいけない。 また、束縛環境に達するまでスタックをまず上に戻し それから下に戻さないといけない。 最後に、返された関数から出る時に、この過程を逆向きに行なわなければならない。 この場合の「環境問題」を解決しようとした「浅いアクセス」のLISP実装を知らない (注3) (訳注5)。

ここまでの要点は、こうである。

  1. 関数定義内の自由変数により、 その関数を評価できるための環境を持つ事が要求される。
  2. 関数を引数にすると、 その関数を評価するのに 束縛環境と活動環境のどちらを選ぶかという問題が生じる。
  3. (評価する時に自由変数の値が要るような)関数を戻り値とする時、 束縛環境を保存し、スタック(実際にはツリー)を作る必要がある。

いくらかの言語設計者は、 すべての関数は束縛環境を無視して評価される、 という望ましくない決定をしている。 LISPでは、 関数をFUNCTIONで束縛するかQUOTEで束縛するかで、 ユーザが束縛環境か活動環境かを選べるようにしている。 LISPでのFUNCTIONとQUOTEの違いについては、 次のように考えるのが有用な比喩になる。 QUOTEは多孔的または開放的に関数をおおっていて、 自由変数は現在の環境へと脱出できる。 FUNCTIONは閉鎖的または非多孔的に関数をおおっている (このことから、Landinはクロージャ(閉包)という用語を使っている)。 だから、「開」ラムダ式と「閉」ラムダ式と呼ぶ (LISPの関数は通例ラムダ式である)。 経験では、 多くのLISPプログラマは閉ラムダ式を返す事はまれで、 そのため完全な環境問題に出会う事もまれである。 今のところ、 自由変数のアクセス・変更時に常に効率を悪くせずに 完全な環境問題を解決する方法は無いようだ。 ある場合には「浅いアクセス」を、 別の場合には「深いアクセス」を提供するシステム を設計するのも複雑な仕事である (注4)。 そういう実装上の困難が残っている限りは、 設計者が環境問題の不完全な解決だけを提供するだけなのも正当化される。

歴史的展望と謝辞

計算機科学の多くの論文は 誰か他の人がすでに知っていた事を執筆者がいかに学んだのかを記述している、 とかつてPeter Landinは言った。 この文章も例外ではない。 私が環境の問題に興味を持ったのは、 Landin(彼はこの問題を深く理解していた)が1966-67年にMITにいた時に始まった。 そしてLISP[2]の「閉」ラムダ式を評価した結果のFUNARGリストと、 ISWIMのラムダクロージャ[3,4]との対応に気づいた。 Joseph Weizenbaumは、Landinの仕事に非常に興味を持ち、 ISWIMのサブセットを彼のSLIP-OPLシステムに基づき実装した。 結果として生じるスタックのツリー構造は私には目の覚めるようなものだったが、 その時Weizenbaumは 一般的な場合に必要な逆向きポインタの実装で困難にぶつかっていた。 判り良い実装で作られる循環的なSLIPの構造のゴミ集めができない、 というのが困難の理由だった。 それが動機となり、 結局Weizenbaumは古典的なガーベージコレクションをSLIPに導入した[5]。

この文章の最初のバージョンは、 多くのLISP実装者がこの問題を理解していないか気にしていないという事実に 私が怒りを感じるようになっていた1967年に書かれた。 その後Weizenbaum教授が、 この問題とそれに対する彼の実装での解決の非常に面白い解説を書いた[6]。 この文章の現行のバージョンで実装面が強調されているのは、 多くをWeizenbaumの解説に負っている。

またMITのRobert Fenichel教授とCarl Hewitt教授との有益な議論にも感謝したい。


文献

  1. Daniel G. Bobrow and Daniel L. Murphy, "Structure of a LISP System Using Two-level Strorage", CACM, vol.10, no.3, March 1967, pp. 155-159. (特にp.158の脚注)
  2. J. McCarty et al., LISP 1.5 Programmer's Manual, MIT Press, 1965. (特にpp.70-71)
  3. P.J. Landin "The Next 700 Programming Languages", CACM, vol.9, no.3, March 1966, pp.157-165.
  4. P.J. Landin "A λ-Calculus Approach" in Advances in Programming and Non-Numerical Computation, pegamon Press, 1966, pp.77-141.
  5. J. Weizenbaum, "Recovery of Reentrant List Structures in SLIP", CACM, vol.12, no.7, July 1969, pp.370-372.
  6. J. Weizenbaum, "The FUNARG Problem Expained", unpublished memorandum, MIT, 1968.

[注1] もちろん、外部ソースからの入力も計算結果に影響し得る。 入力値もまた環境の一部だと見なしておこう。

[注2] 残念ながらこの実装では、 スタックの捨てられる部分の再利用に困難がある。 環境を管理するのに要求される記憶域の量を最小にする解法は、 スタックをやめて「連想リスト」に近い構造を使う事である(図4参照)。

この構造は、 隣接してない線形の配列を上向きや下向きのポインタで繋げて出来ていて、 部分構造へのポインタがあるかどうかをチェックすることで 自動的にゴミ集めができる。

[注3] FUNARG問題は誤ってそう名付けられている事を、 ここではっきりさせるべきだろう。 関数引数を扱えるだけでは困難は完全には解決されないのだから。 関数を返す場合、 あるいは本質的には同じ問題だが 関数を値として自由変数に代入する場合も扱われるべきだ。 こういう理由で「環境問題(Environment Problem)」という用語の方を好む (訳注6)。

[注4] いくらかのLISPシステムは、 インタプリットされる関数に「深いアクセス」を使い、 コンパイルされる関数には「浅いアクセス」を使う。 もしコンパイルされる関数中の自由変数がCOMMONに宣言されると、 値は「連想リスト」に保存される。 このやり方で環境問題を解決できるが、 インタプリタと自由変数への「深いアクセス」が非常に遅いという代価がかかる。


訳注

[訳注1] ここでわざわざ「再帰関数」と言ってるのは、 昔の言語には、 引数とか局所変数の領域を スタックでなくあらかじめ決めた位置に割り当てていて 再帰ができないものがあったからだと思う。

[訳注2] プログラムはALGOL風に書いてあるけど、 この文章ではすべて動的スコープで考えている。 字句スコープの場合は、 関数fの定義を字面の上で囲んでいる関数・ブロックで 変数aが束縛されている必要がある。

[訳注3] 「浅いアクセス」「深いアクセス」よりも、 「浅い束縛(shallow binding)」「深い束縛(deep binding)」 という言い方が一般的かもしれない。

[訳注4] これは動的スコープの場合の話で、 字句スコープの場合では、 束縛された環境ではなく関数が作られた時の環境になる。

[訳注5] 浅い束縛による扱いについては、 Henry G. Baker, Jr. 「Shallow Binding in Lisp 1.5」(1978) を参照。

[訳注6] 関数を引数として渡す方は下向きFUNARG、 関数を戻す方は上向きFUNARG、 と呼ばれたりもする。


戻る