コンパイラ課題メモ

• 自分用。各回に出た課題とぱっと見の難易度とかをメモ。

単位取得要件

• コンパイラ演習分（第1回スライドより）
  • 共通課題を6回分クリア
  • コンパイラ係向け課題を1回分クリア
  • シミュレータ上でレイトレーサが完動
• プロセッサ実験分（第1回スライドより）
  • 無事に機材を返す。
  • （おぼえてない）

第1回

• 済
• 勝利条件：どれか1つ

  • MinCamlのSyntax.tやKNormal.tを出力するプログラムを実装。

    • 済
    • かんたん。

  • MinCamlを、パースエラーまたは型エラー時に問題となった行番号を出力するように改造。

    • OCamlのマニュアルでparserについて調べるとできた。

  • MinCamlが出力するアセンブリとソースを対応付けるように改造。

    • よくわからん。1個目をやればいいと思う。

第2回

• 済
• 勝利条件：すべて
  • スライドに載ってる式をK正規化してα変換。さらにA正規化。
    • 済
    • min-caml.top を使えば何も考えなくてよかった。
  • 共通部分式除去を実装。
    • 済
    • 何やるかをわかっていれば実装は軽いが勘違いしていて時間をだいぶ無駄にした。
  • インライン展開するときにα変換や回数制限がないと困る例をあげよ。
    • 済
    • let rec if-fun b t f = if b then t else f と if b then t else f の違い。

第3回

• 済
• 勝利条件：どれか2つ
  • 自分が書いた関数型言語のプログラムから自由変数を持つ関数を取り出し、自由変数がいらないように書き換えよ。
    • 済
    • 自由変数+引数を返す関数とかを捏造すれば一瞬では。
  • Lambda Lifting を実装せよ。
    • めんどくさそうな参考文献がヒントとして示されている。回避すべき。
  • スライドに載ってる関数をクロージャ変換したらどうなるかいくつかの問いに答えよ。
    • 済
    • closure.ml に実際に投げてもよいしスライドの資料をヒントに手計算してもよい。
    • min-caml.top 最強すぎわろあ。

第4回

• 済（メールを出せば）
• 勝利条件：どれか1つ
  • 自作CPUを含めて3つ以上のアーキテクチャについて関数呼び出し規約を比較して論じよ。
    • よその班の人に話を聞くなり、アセンブリ演習の時のPowerPCを使うなりすればいけそう。
  • Closure.progに対してタプル平坦化を実装せよ。
    • 済
    • クソ面倒だった。コンパイラ係でないなら1個目一択だと思う。もしやるなら最初にA正規化すると楽になるよ。
  • Closure.progに対して不要タプル定義除去を実装せよ。
    • まじめにやるとめんどくさそう。保守的かつ局所的なら楽かも。

第5回

• 勝利条件：どれか1つ（たぶん）
  • スライドに載ってる式にsave/restoreを挿入せよ。
    • スライド読めばできる系？
  • 簡単な再帰関数を自分でレジスタ割り当てせよ。
    • 例にならいとあるのでこれもスライド読めばできる系か？　今回はどっちもそれなりに楽そう。

第6回

• 勝利条件：どれか3つ
  • スライドに載ってるコードをコンパイルした際の末尾呼び出し最適化の有無による違いを述べよ。
    • コードは最大公約数を求めるもの。まあできそう。
  • スライドに載ってるコードをCPS変換せよ。
    • コードはアッカーマン関数。スライド見ながらならできる？

  • MinCamlにCPS変換を実装せよ。

    • Lispおじさんはここで引っかかってると言っていたような気がする。回避すべき？
      • manga architecture では関数呼び出しをハードウェアで補助しているのでこれすると遅くなりそう。
  • 種々の簡単な拡張を用いるMLプログラムを書き、それを既存のMLコンパイラがどうコンパイルするか調べよ。
    • ゴミみたいなプログラムを書いてocamloptに投げてアセンブリを読めばよさそう。

  • MinCamlをλ抽象・部分適用に対応させよ。

    • クロージャ作ればいいんですかね？　よーわからん。

第7回

• 済
• 勝利条件：どれか1つ
  • 既存の処理系を2つ選び、それぞれのparametric polymorphismについて説明せよ。
    • g++とocamloptでやればよさげ。

  • MinCamlを改造してオーバーロードされた演算子を1つ作れ。

    • 済

    • あれ、型推論情報を利用すればkNormal.mlとparser.mlyの改造だけで行けそう。MinCamlわかってればこっちのほうが軽いと思われる。

    • typing.ml の改造だけでいけた。

第8回

• 勝利条件：どれか1つ

  • MinCamlに、到達定義解析とそれを用いた最適化を実装せよ。

    • やばそう。なぜコンパイラ係向け課題でないのか。
  • スライドに載っている方法ではうまく最適化できないパターンを見つけよ的な。そしてそれの改善案を提案せよ。
    • さらにやばそう。この回は無理。

第9回

• 勝利条件：どれか1つ
  • 少なくとも2つの戦略によりリストスケジューリングを実装せよ。
    • やばそう。
  • min-rt.mlから大きめの関数を選んでレジスタ割り当てとスケジューリングをした結果を示せ。

    • MinCamlの出力を用いても良い、ということは元のコードとの対応関係を調べればいけるのか？　まあ他の回やったほうが良さそう。

第10回

• 勝利条件：どれか1つ
  • ループ変換を1つ実装せよ。
    • ここ最近のヤバ気なのに比べるとまし。
  • 既存の処理系の並列化技術に関する論文を読んで要約せよ。
    • 要約系課題って重いのかしら？　英語読むだけだったらいいなあ。

第11回

• 勝利条件：どれか1つ
  • JITコンパイルに関する論文を読んで要約せよ。
    • 要約系。
  • 何らかのバイトコードインタプリタに何らかのJITコンパイラを実装せよ。
    • CPU実験のシミュレータでもよいらしい。そういえばJITではなく全体をコンパイルした人が現れましたね。

第12回

• 済
• 勝利条件：どれか1つ（選択肢も1つ）

  • MinCamlの配列に配列長タグを付け加え、配列アクセスの前に境界検査をするようにせよ。

    • 済
    • タグの付け方によっては全体にわたって改造しなければならなさそうである。
    • そうではなかった。virtual.mlでアドレスの決定だけ触ればよい。配列長タグ付けは libmincaml.sの改造で。

コンパイラ係向け課題

• Closure.progに対する型検査を実装せよ。（第3回より）
  • コンパイラ係課題としては軽め？　新しいことにチャレンジせずに済む。ただし実装量はちょい重そう。
• Parametric polymorphismを実装せよ。（第7回より）
  • パーサ修正とexpansionゴリ押しで出来なくはなさそう。
  • 意外と資料が少ないのできついか？
• 関数間解析・エイリアス解析などの高度な解析とそれに基づく最適化を実装せよ。（第8回より）
  • ちょっとこれは……。
• グラフ彩色によるレジスタ割り当てを実装せよ。（第9回より）
  • xenophobiaが苦戦していると聞いて。
  • どのコンパイラ解説書にもだいたい載っている（タイガーブックは擬似コードまであった）のでワンチャン。
• 自作コンパイラに自動並列化を実装せよ。シミュレータ上で動作すればよい。（第10回より）
  • シミュレータを並列対応させるのがめんどくさそう。
• 自作CPUで動作するJVMサブセットを実装しそれにJITコンパイラをつけろ。（第11回より）
  • ジャバ。まずjavaがよくわからんので回避。
• 自作コンパイラにGarbage Collectionを実装せよ。（第12回より）
  • スライドによるとcopying GCが簡単らしいが。