自作言語 oak その4 デリゲート((エン)クロージャ？)

進捗状況。パーサーはほとんど終わり、字句解析・構文解析フェーズはほとんど完成している。

意味解析について。Scope を設定し、Scope を生成する Symbol のメンバーを SymbolTable に格納したり、現在いる Scope から Symbol を同一 Module 内で探すことまではできるようになっている。import foo.bar; による他モジュールのインポート及び完全なシンボルルックアップは今の所まだできていない。

さて、関数(部分)適用とデリゲート(あるいはエンクロージャ？)について考えがまとまってきたのでひとまずここに挙げておく。まずはコード例から。

コード例1

let i:int;
func adder:int n:int = i + n;

func app5:int f:int->int = f 5;

i = 42;
writeln ( app5 adder );    // 47
i = 44;
writeln ( app5 adder );    // 49

i を後から変更したときにそれがデリゲートに効果を及ぼすようにするかしないかはまだあまり考えていないが、ここでは効果が及ぶものとして話を進める。

このコードがこのような実行結果になるには、adder が関数本体のコード位置以外にもコンテキストを保持しなければならない。つまり、数学的に言えば adder は自由変数 i を持っているため、その変数へのポインタも同時に持っている。この、コード位置のポインタとコンテキストのポインタの対がD言語で言うところの delegate、他言語で言うところのエンクロージャ(?)だ。

コード例2

let i = 5;
let pair = (2, 3);
func myf:int a:int b:int c:int =
    a*i + b*pair![0] + c*pair![1];

let j = 4;
let f = myf j;        // 部分適用
let g = myf 42 j;    // 部分適用

writeln ( f 6 7 );    // 4*5 + 6*2 + 7*3
i = 2;
j = 6;
pair = (7, 4);
writeln ( g 5 );    // 42*2 + 6*7 + 5*4

コンテキストはどういう形式で格納すれば良いか。関数の部分適用をサポートするため、それに対応できるような汎用性を持たせたい。

それを考える前に、まずは中間言語(あるいはアセンブリ)的に関数呼び出しがどのように行われるかを考える。

myf foo bar baz を実行する(計算する)には、

1. 今実行中のコード位置(呼び出し元位置)をスタックに積む
2. myf のコンテキストの各ポインタをスタックに積む
3. 引数を順番に積む
4. myf があるコード位置へジャンプする

を順番にやるだけである。4. を実行する時点でスタックに新しく積まれるものを順番に列挙する :

（ボトム）　｜　呼出元位置　｜　i へのポインタ　｜　pari へのポインタ　｜　foo　｜　bar　｜　baz　（トップ）

これを見ればわかる通り、myfoo を呼び出す際には常に5個スタックにモノが積まれる。この観察から、

f … myf のコード位置 + コンテキスト（ i へのポインタ, pair へのポインタ, j へのポインタ )
g … myf のコード位置 + コンテキスト（ i へのポインタ, pairs へのポインタ, 42, j へのポインタ )

という情報を持っていることがわかる。これに加えて、コンテキストのうち、どれを dereferencing, つまりポインタの指す値に置き換えるか、も同時に知る必要がある（※1）。これらを以てデリゲートの全情報となる。

g を呼ぶ際には、呼び出し元の位置を積み、コンテキストから抜き取った i へのポインタ, pairs へのポインタ, 42, j の値(ここ重要), を順番に積んで、myf へジャンプする。

※1 について。何を deref して何をしないのかを判別する方法として考えているのは今の所この二つ :

1. コンテキストの内容は全部ポインタ。コンテキストの0番目のエントリには非負整数 N が入っており、1番目からN番目までは deref せずポインタのまま、N+1 番目以降は deref する。
2. コンテキストの内容はポインタと値の混交。それぞれのエントリにはそれがポインタか否か判別するフラグがある。

1. がどういう仕組みか。それはコード例2の f, g が例となっているが、真のコンテキスト、すなわち最外の関数においてもなお自由変数である場合、言い換えれば関数の部分適用によって現れる自由変数ではない場合は、それは必ずポインタでスタックに積む必要がある。というのも、そのコンテキストを書き換えることがあるからだ。

コード例3

let i = 42;
func side_effect:int n:int m:int {
    // i は真のコンテキスト、n は side_effect に関数適用を一度だけしたときに現れる自由変数
    n = n+1;
    m = m+1;
    i = i+n+m;    // i を書き換える
    return i;
}

let f = side_effect 5;
let j = 691;
let g = side_effect j;

side_effect 2 4;
writeln i;    // 50
f 7;
writeln i;    // 64
g 771;
writeln i;    // 64 + 692 + 772
writeln j;    // 691

1. を採用した場合、コード例2 の g を呼ぶ際には、42 という定数へのポインタが必要になる。すなわち 42 をヒープ領域に確保しなければならず、そこが少しネックになる。
一方 2. を採用した場合は、T型とTへのポインタ型の両立(ポインタのサイズは8byte固定でもT型がメチャでかになるかもしれない)・及びフラグをどこに置くかが問題となる(こっちポインタの数だけビットを用意すれば良いのだが)。

最後に、コンテキストのメモリ安全性も問題である。

コード例4

func higher:int->int n:int m:int {
    let a = n + m;
    // λx:int . a*x を返す
    return \x:int (a*x);
}

このラムダ式のコンテキストの a へのポインタは、higher から制御が返ってくると宙ぶらりん状態になってしまう。そのため、このラムダ式を返値するときにはコンテキストの指す値を新しくヒープへ確保し、そこを指し直さないといけない。これが必要であるかどうかを静的にチェックしないといけない。