Schemeの実装におけるスタックフレーム(Draft)

まず、C等の手続き型言語におけるスタックフレームの使い方を復習しておきましょう。次のように、関数Aが関数Bと関数Cを呼び出しているものとします。

    int A(int a, ...) { int b, c; B(b); C(c); }
    int B(int b) { int b1; /* other calculation */ }
    int C(int c) { int c1; /* other calculation */ }

関数Aが呼ばれた直後のスタックには、保存された呼び出し元のレジスタ、戻りアドレス、そしてAの引数 (a等) とローカル変数 (b, c) 等が積まれます。スタックポインタ(SP)はスタックの再下端を指し、またフレームポインタ(FP) がローカル変数にアクセスしやすい位置にセットされます (図1a)。この例では、n番目の引数はFP+nでアクセスでき、m番目のローカル変数はFP-mでアクセスできます。なお、コンパイラには一般に(alloca等、動的にスタック領域を確保する手段を使わない限り)ローカル変数の数が分かっているので、FPを使わずにSPのみでローカル変数や引数にアクセスする処理系もありました。

関数Aから関数Bを呼び出すと、その時点でセーブすべきレジスタ、FP、SP、戻りアドレスおよび引数がスタックに積まれ、FPとSPが修正されます(図1b)。関数Bから復帰すると、関数Bのスタックフレームは削除されます (図1c)。関数Cが呼ばれた時にも同じことが行われます (図1d)。

図1. C言語におけるスタックフレームの配置の例。FP=frame pointer, SP=stack pointer.

さて、Schemeの場合はどうなるでしょうか。次のような例を考えます。上の例と同じように、関数Aの中で関数Bと関数Cを順に呼び出しています。さらに、関数Aの中で関数Dを作成し、それを関数Cに渡して、関数Cの中で呼び出しています。

    (define (A a1 a2)
      (let ((a3 (+ a1 a2)))
        (define (D e1) (+ a3 e1))
        (B arguments)
        (C D)))
    (define (B arg)
       some-calculation)
    (define (C func)
       some-calculation
       (func args))

関数Aが呼ばれた時点のスタックフレームは図2aのようになっています。引数やローカル変数へのアクセスはC言語と同じようにFP経由で行われますが、 dynamic linkとstatic linkという余分な情報が積まれています。 dynamic linkは自分を呼び出した関数のスタックフレームを、static linkは自分を定義した関数のスタックフレームを指しますが、どう使われるかはおいおい見てゆきましょう。

関数Aから関数Bを呼び出します。C言語との違いは、呼び出した側のFPの値が呼び出された側のdynamic linkに保持されることです(図2b)。

関数Bから復帰すると、FPの値はdynamic linkの値を元にして回復されます。しかし、スタックフレーム自体は原則として回収されません。すなわち、SPの値はそのままに留まります (図2c)。え、それじゃメモリが足りなくなるんじゃないかって? それは後で説明します。

関数Aが関数Cを呼び出すと、そのスタックフレームは関数Bのスタックフレームの下方に作られます (図2d)。dynamic linkはやはり呼び出した関数のフレームを指しています。

関数Cがfunc (実態は関数A内で定義された関数D) を呼び出すと、そのスタックフレームが関数Cのスタックフレームの下に作られます。関数Dは、自分を作成した関数Aのスタックフレームの値を覚えていて、static link が関数Aのフレームを指すようにします。このリンクにより、関数Dは自分の引数やローカル変数に加えて、関数Aの引数やローカル変数にアクセスすることができるわけです (図2e)。

Stack frame usage of Scheme
図2. Schemeにおけるスタックフレームの配置の例。FP=frame pointer, SP=stack pointer.

さて、この説明を聞いただけではC言語プログラマは納得いかないでしょう。だって関数を呼べば呼ぶ程スタックは膨れるばかりですから。でも良いのです。メモリが足りなくなったらガベージコレクタが走って、使ってないスタックフレームを回収し、パックしてくれますから。

さらに現実の実装では、スタックフレームを保存しておく必要があるのは、自分の内側で関数を作成し、その関数が自分の引数やローカル変数を参照している場合のみです (このように、作成した関数から参照される変数を "closed variable" と呼んだりします)。上記の例で、関数BやCの内部で関数を作成していないのなら、それらのスタックフレームは関数から戻る際にC言語の場合と同じように削除して構いません。内部で関数を作成しているかどうかはコンパイル時に分かるので、コンパイラは必要な場合にのみスタックを保存するコードを生成するように出来ます。

ガベージコレクタのコストを除けば、Schemeでもローカル変数のアクセスおよび関数呼び出し／復帰処理はC言語と同等の速度で行い得る (但し、closed variable についてはポインタ参照が入りますが) ということがおわかり頂けたでしょうか。但し、現存するScheme処理系の多くはベースにC言語を用いており、このような特殊なスタック操作が実装しにくくなっています。どの変数がcloseされるかはコンパイル時にわかりますから、コンパイラがclosed variable だけを抜きだしてヒープ領域に格納する、というふうに実装しているものが多い様です。

以降はちょっとした余談。

関数Dは関数Aの環境(引数やローカル変数)をCloseするという意味で、Closure と呼ばれます。関数Aのスタックフレームを直接参照していることに注目してください。もし関数Dが関数Aの変数a3等を変更すれば、その変更は関数Aのスタックフレームに影響を及ぼします。次の例では、関数make-incr/decrの中で二つの関数が作成され、その両者が変数xをcloseしています。

    (define incr #f)
    (define decr #f)

    (define (make-incr/decr)
      (let ((x 0))
        (set! incr (lambda () (set! x (+ x 1)) x))
        (set! decr (lambda () (set! x (- x 1)) x))))

すると、次のように、二つの関数が外からは見えない変数を介して影響を及ぼし合うようになります。

    (make-incr/decr) → undefined
    (incr)  → 1
    (incr)  → 2
    (decr)  → 1
    (decr)  → 0