研究してました

Haskell Study

今日は主にプログラミングばかりやっておりました。 Haskell でいうところの where 節内に書かれた関数を外で使えるようにするために、引数を補ってやりましょうみたいな話。今までは外側の関数の引数を全部内側の引数に加えるという力技でなんとかしてたんだけど、出力されるソースが半端なく長くなってしまったのでそれを改善しようというのが動機。最低限必要な引数だけを補うようにした。
関数が相互再帰したり、引数を省略したりしなかったりできるのでややめんどくさくて、かつ、"変化がなくなるまで計算を続ける"みたいな処理に関しての経験がほとんどなかったもんだから、やたらと時間がかかってしまった。

以下、未来の自分のためへのメモ。今回考えたアルゴリズムの話。

  • まず準備。
    • 入力ソースを走査して、関数の依存関係を取得
    • 関数ごとに走査して、引数にない変数を補う
    • 関数ごとに、引数の名前を入れたデータベースを作る
  • ループに入る
    • 関数の依存関係と引数データベースを使って必要な引数を新しく求め、データベースを更新
    • 更新をしながら登録された関数を回る
    • なんの更新もなく登録された関数を一巡したらおしまい
  • 出力
    • 作ったデータベースを使って入力ソースを整形
    • その他、細かい処理

今のところはα変換とかはやってないので、もし同じ名前の関数があれば普通にぶつかってしまうでしょう。