ラムダ計算から Grass へのコンパイラ作ったったｗWWｗｗｗｗWWｗｗ - Object.create(null) の続きです.
経緯
ラムダ計算から Grass への変換ができたのは良かったものの, 生成コードはそのままでは無駄が多く, 例えば Brainfuck インタプリタの場合, 生成されたコードは 20000 文字を超えてしまいました.
これがあまりに長かったので, なんとか手作業でソースの無駄を省いたり, スタック順序を考えて並び替えたり, インライン展開したり, と繰り返して 16000 文字程度までは縮めたのですが, 冷静に考えると, この件についてはコードゴルフがしたいわけでもなく, 単に無駄の多いコードが生成されるのが気に食わなかっただけだったので, 特に並び替えについてコンピューター (というか乱数) に丸投げして適当に最適化してもらうことにしました.
もしタイトルで速度面の最適化を期待されていた方がいたら申し訳ないのですが (いるのか?), この最適化は速度面ではなく, コードの長さについてです. (Grass はスタックベースなので, コードが短いほうが速度も多少速くなるはずですが……)
何をしたのか
全探索はおそらく不可能な上, 良いアルゴリズムを考えられなかったので, モンテカルロ法で適当に良さそうな並べ替えを探索しました.
簡単にいえば ボゴソートより効率の悪いアルゴリズムを考える回 - Object.create(null) の逆です.
項の入れ替えに対してコスト (出力コードの長さ) を割り当てて, それが小さくなる方向を好むように交換を繰り返すというアルゴリズムです. ただしボゴソートの時とは違い,
- 項の間に依存関係がある
- 関数適用は副作用がある可能性がある
- 最後の項は Grass の言語仕様上入れ替えてはいけない
などのせいで交換できない場合があるので, そこはきちんと対応してやる必要があります.
本当は副作用があるかどうかタグ付けしたりしたほうが良さそうですが, なんだか面倒だったのでやっていません.
結果など
Brainfuck インタプリタは (ソースを多少弄ったもので) 11218文字 まで縮みました (これは適当な試行回数で試しただけなので, もちろん同じソースでもっと縮まる可能性はあります).
ちなみにちょっと前に lambda lifting の処理に無駄があったのを修正したのですが, このときに高速化と引き換えに, 出力コードが長くなってしまうものが出てきました. こいつを今回のアルゴリズムで最適化するとどうなったかというと, なんと修正前のコードよりも長いままでした. なかなか難しいですね.
Try it!
みんなもっと草を生やそう! github.com
