自作言語 oak その5 (symbol lookup/access)

自作言語 oak の関門の一つであるシンボルルックアップとシンボルアクセスが95%実装できた。

シンボルルックアップ : 現在いるスコープから、識別子を検索する。検索の仕方は次の通り。

1. 現在いるスコープから、スコープをうなぎのぼりし、識別子がそのスコープ内で宣言されているか探す。つまり最内のシンボルを見つける。
2. もし見つからなかったら、現在いるスコープからインポートされているモジュールをすべて集め、各モジュールについて現在いるスコープからそのモジュールのその識別子にアクセス(後述)する。この過程で複数見つかることもある。

シンボルアクセス : 現在いるスコープから、シンボルのメンバーにアクセスする。当然 private, package, public, protected といったプロテクションレベルも考慮しなければならない。うち、protected については class がまだできていないのでやりようがなく、未実装。また、package(pkgname) も未実装。これが残りの 5%。

この他にも import public MyModule による循環参照を避けることも考える必要があったが、無限ループに陥ることなく正しく実装できた(はず)。

備忘録として、Scope と ScopeSymbol は互いにリンクを持っており、ScopeSymbol.enclosing : Scope で上と繋がれる。

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

自作言語 oak その3 

func f:var int x:var int y:var int = x + y;
var a = 3;
let g = f a;
a = 5;
writeln ( g 7 )    // 10? 12?

このようなコードを考える。最後に表示されるのは 10 になるか 12 になるか？

個人的には、このコードのように単純に書いた場合は 10 を表示したい(→しない可能性大、oak その4参照)。つまり、a の値を g に記録しておくことにする。

もちろん、12 と表示されるようにもしたいので、それについての新しい構文(キーワード)を考えたいのだが。今の所D言語と同じlazyを導入しておけば良さそうとしか考えていない。

自作言語 oak その2

型とメタプログラミングについて。 var の仕様について。

let a: var (int, int) = (3, 5)
a = (4, 6)    // pass
a!!0 = 4; a!!1 = 6    // error

let b: var [int] = [4, 6, 8, 10]
b = [3, 5, 7, 9]    // pass
b !! 0 = 3    // error

これを見れば大体わかると思う。

だが、var を再帰的に適用したいときがある。三次元配列の全てを自由にいじれる型は、

var [ var [ var [ var int ] ] ]

という型を持つが、これは書くのが大変である。そこで、mut という、型に対して型を返すメタ関数を、

mut int = var int
mut a -> b = var ( a -> b )
mut [a] = var [ mut a ]
mut *a = var ( *(mut a) )
mut (a0, ..., an) = var (mut a0, ..., mut an)

とすれば便利だ。しかし、これを言語仕様として定めずに、言語内でこの mut というメタ関数を書けるようにしたら面白くなるだろう。D言語のテンプレートに近いものを感じる。

自作言語 oak その1

自作言語作るぞ作るぞ詐欺を始めてはや数年、やっとこさ自作言語に取り掛かり始めた。今はパーサーを手書きしている。
最初は yacc だの bison だのといったLALRパーサ生成器でやろうかと思ったけど、最近の言語はLL文法が流行っているらしく、再帰下降パーサーを手書きすることにした。構文は関数型言語っぽくしたいと思っている。だが、言語仕様も関数型言語のようにするかは決まっていない。

構文の雰囲気はこんな感じ:

let x:int = 100, y:string = "a string";
//x = 200 : error
var a = 20;    // same as 'let a: var int = 20;'
a = 30    // ok

func:int factorial n:int (n>=0) = 
    n * factorial (n-1) when n > 0 else
    1;

func:[b] map f:a->b xs:[a] =
    (map f (xs!!(0, $-1))) ~ [f (xs!!($-1))] when xs.length > 0 else
    [];

proc show_factorial n:int {
    n |> factorial |> writeln;    // pipe-line operator
    // same as:
    //writeln@factorial n;    // @ : function composition
}

今一番悩んでいるのは型システムで、特に関数の純粋さについて。func は純粋な関数、proc は非純粋な関数ということにしたいのだが、たとえば型 a -> b にどうやってその情報を付与するかを考えている。pure a -> b とするのもちょっとなあ・・・というか。


当然実装はD言語でだよな。 https://github.com/marx-saul/oak