inline展開 - Scheme VM を書く

scheme

inline 展開を軽く実装してみたが難所が多そう。ベースの仕組みは難しくない。手続き呼び出し部分を手続き本体に置き換えるだけ。
手続き定義 (define hoge (lambda ...)) を見つけたら hoge => (lambda ...) の対応を env に保存しておく。その際に手続きを flatten してからコードサイズを求め、閾値を超えていたら env に保存しない。巨大なコードを inline 展開するのを防ぐためである。
次に (hoge a b c) という手続き呼び出しを見つけたら hoge の body と置き換え仮引数を実引数に置き換える。

  • [OK]小さなパターンから最適化が有効なことを試す
  • [OK]実引数の置き換えが大雑把過ぎる
    • その前に alpha-reduction のテスト
    • できた
  • [OK]inline化のあと再び inline 化する
  • 副作用がある場合がまだ分かっていない
  • pretty printer を書く
  • 再帰的な場合どうするか
    • 今は inline 回数制限しているけど。本当は self-recursive? 判定をしたほうが良い。どうやる？


inline 展開されようとする手続きに副作用がある場合はどうすれば良いのだろう。一つ簡単な方法としては let 展開するというのがある。ただ自分の処理系では let も手続き呼び出しのどちらの場合も closure の call に変換されるの最適化の意味がなくなってしまう。
そうなると絶対に副作用がない手続きの組み合わせは、副作用がないという方式かな？
あとダメダメな案としては、手続き名の末尾に ! がついていたら inline 展開しないとか。
処理系において、let と ((lambda ) ...) がまったく同一なのが良くない気がするな。自由変数を持っていない let ならもっと低いコストで実現できたりしないだろうか。
Gauche の場合 pass2/head-lref あたりで inline 可能か調べているみたい。

追記

問題は見えてきた。 ((lambda (a) ...) 実引数) ならぬ本当の軽量 let があれば良い。
lambda lifting 調べるか。