連鎖性言語を作る7

スタックエフェクトはForthではコメントだがFactorではコンパイル時にチェックされる記述になっている。コンパイルはワードの定義時ではなく実行時にされる。らしい。
例えば、

 : aaa ( x -- x ) drop ;

などと定義すると、これを呼び出すときに「effect-error f ( x -- ) ( x -- x )」と言う感じにエフェクトエラーが出る。( x -- )じゃねーのかよ、と言っているわけだな。あと、ifワードに渡すQuatationで使うスタック数が食い違っているとこれもエラーになる。こちらはスタックエフェクトは書かないので増減だけチェックされるらしい。増減だけチェックなので、

: aaa ( x x x -- x x ) [ drop dup ] [ ] if ;

は実行できたりして、前のスタックを書き換える/書き換えないの違いは気にしないっぽい。ちなみにこの例のスタックエフェクトは、ifに食わせるboolが1つ、dropされるオブジェクトが1つ、dupのネタに使われるオブジェクトが1つで入力は計3つとなる。出力はdupされて2つになったオブジェクトだ。つまりFactorのスタックエフェクトはスタックを書き換えるか否かに関わらず、参照するものを書く必要がある。後ろ側はスタック構造の特性上いくら使って捨てても無視でよい。ところでスタックエフェクトに書く文字は何でもよくて、同じだったら同じオブジェクトを表すというわけでもなく、数だけが重要である。見た感じわかりやすいように例えばswapは( x y -- y x )としたりするけども、これも別に( x x -- aa bb )でも間違いではない。

ということで、スタックエフェクトについて考えたことをメモ。

Factorはスタックエフェクトを単なるコメントではなく、実際のコードの動作と照らし合わせて食い違っていたらエラーを出力してくれる。これはこれで非常に便利なのだが、このような機能を作ろうとしたら実際どのような処理が必要になるだろう。
ま、とりあえずコメントとして飛ばすんじゃなくてきちんとパースしてワード定義に持たせる必要がある。問題はそこではなく、実際のスタック増減や、参照するスタックの位置をどうにかして知る必要がある、というところだ。
ワード定義の中にはスタックに積むコードがもちろんあるだろうが、それだけではなく、他のワードの呼び出しや、Quotationの呼び出しなどが混ざる。つまり処理の途中で他の処理が入り込むため、全てのワードにスタックエフェクトを付けて、1つ1つ追いかけながらスタックの状態を確定させていくような処理となる。ある瞬間、今のスタックトップはどこで、前方どこまで参照したのかを判断していって、最後まで行ったところでそのワードのスタックエフェクトが決まる。
この情報はスタックエフェクトチェックにももちろん使えるが、思うにその後の最適化などにも有効に使える、気がする。このへんの処理は興味深いのでそのうちやってみようと思っている。