ゆにふぃやー

と、いうわけで、なんか、100行ぐらいのコードを書いては捨て、書いては捨てを3回くらい繰り返してるうちに、いつのまにかネタストックはどうでもよくなってしまったので、ILogScriptについて考える。
ILogScriptは僕の中でネタ切れした時のクッションの役割を担っているのだ！！（意味不明）

http://d.hatena.ne.jp/w_o/20050728#p4
うーん。明日書くって書いたのがいつのはなしだ…実に、構想一時間、放置三カ月のネタ。

どうしたらいいかわからなくて放置してた、ILogScriptの型チェックライブラリなんだけど、Prologもどき、というか、unificationみたいなのをうまくやればいいんじゃないか、っていう話。

まず、

// add_float:: (float,float) -> float 
// add_int:: (int,int) -> int
// float_to_int:: (float) -> int

function fun(x,y,z) =
	return add_int( x, float_to_int( add_float(y,z) ) );

こんな関数があったとしよう。
これの型は、

fun:: (int,float,float)->int

になるはず。
それで、だ。型推論したいわけなんだけど、なんと、Prolog（のようなもの）は型推論エンジンに使えるのである。（多分）

上の関数funの定義を

add_int( [int,int] ,int).
add_float( [float,float], float ).
float_to_int( [float], int ).


fun( [X,Y,Z], Ret ) :- 
	add_float( [Y,Z] , Tmp1 ),
	float_to_int( [Tmp1], Tmp2 ),
	add_int( [X,Tmp2], Ret ).

こういうふうなPrologに変換するとしよう。上の関数定義プログラムは構文木に変換してしまえば、下のPrologプログラムに変換するのはそんなに難しくない。スタックマシンのコードを生成するのと同じぐらいの労力でできる。多分。
すると、あとは、これをPrologインタプリタに突っこんでやるだけで、

?- fun( [X,Y,Z], Ret ).

X = int
Y = float
Z = float
Ret = int 

Yes

正しく、型推論された結果が出てくるのだ。

function swap(x,y) = 
    let v = *x in
       *x = *y
       *y = v

こーんな関数を考えたとしても、

deref( pointer_to(T), T ).

swap( [X,Y], Ret ) :-
	ref( Y, Tmp ),
	V = Tmp,
	deref( X ) = deref( Y ),
	deref( Y, Tmp1 ),
	Tmp1 = V.

こういうPrologを考えて（これも構文木から簡単に生成できるはず）実行したとすると、

?- swap( [X,Y], _ ).

X = pointer_to(_G227)
Y = pointer_to(_G227) 

Yes

XとYは汎用な型へのポインタ型っていうのを推論できるのだ。

と、いうわけで、コンパイラから呼べる、Prologみたいな単一化をしてくれる「なんか」があれば、型推論ライブラリとして使えそうだ。と、思ったのが、三カ月前。
だがしかし、その「なんか」がどういうインターフェースにしたらいいかわからんので、一歩も進まないままなのであった。

とりあえず、考えたのが、

var unifier = gen_unifier();
...
unifier.run();

こんなふうに実行できるunifierオブジェクトを作れるようにすると考えて、

function unmatch() { error("type unmatch in " + lineno + ".\n"); }
unifier.add_call( ..., unmatch );
unifier.add_unify( var1, var2, unmatch );

そのunifierにはなんか節のようなものを追加していける。ここで、この節が失敗したときのハンドラを指定できるようにしとく。

function type_determine(node,val) {
	node.type = val;  // このノードの型を決定
}

var type_var = unifier.make_var( "name", type_determine, obj );

こんな感じで、unifier内の変数を作れる。ここで、この変数の値が決定したときのハンドラと、そのハンドラに渡す引数を指定できるようにしとく。

と、いったところ。
で、推論処理の実体をunifer.runの中に閉じこめておけば中身は全部Cで書けるから遅くはならないはず。メモリ割り当てがちょっと多いかもしれん。そこらへんはやってみないとわかんない。

あと、タグ付けした引数とかが無いと、レコード型の推論がアレ。タグ引数はPrologにもあるのかしら。Prologはあんまりわからんので、もうちょっとそこらへんを調べておく、こと。
あと、根本的な問題として、単一化のアルゴリズムがわかんない。そこらへんも調べること。