PPLサマースクール

お越しくださった皆様、本当に有難うございました。現在新幹線車内。またしても多くの方とはお話もできなくてすみません…

追記：ブログやprivate communicationで聞かれた質問の答えを追加していこうかと。

図14のclosure変換で、L_x(y1,...,ym)(z1,...,zn) = e1'のe1'において、xがfreeになってしまっていないか？

実はL_xのxはe1'の中のxをbindします。で、図20のレジスタ割り当てにおいて、xにはR_0 (MinCamlの関数呼び出し規約により、自分自身のclosureのアドレス)が割り当てられます。ad hocなのはわかっているんですが、実装としてはこれがもっとも単純だったので…

gcdのコンパイル結果にnopがあったのはなぜ？

SPARCでは、ブランチ命令やcall命令の直後にdelay slotがあって、ジャンプの前に一つ先の命令まで実行されます。本当はアセンブリ生成などを改良して意味のある命令を入れたほうが良いのですが、MinCamlではサボっていて、単にnopで埋めています。

Closure変換よりλ Liftingのほうがわかりやすいのでは？

λ Liftingといった場合にどのアルゴリズムを想定すればよいのか、（自分が無知で）はっきりとはわからなかったのですが、たとえばJohnsson 1985だと、λ Liftingした後も部分適用が残ることがあるので、その部分適用をどうするか考えなければならず、ネイティブコードだとやはりclosureのようなものが要るのではないか、と思いました（スタックマシンのバイトコード等ならば良いのかもしれませんが）。あと、主観の問題になってしまいますが、たとえばJohnsson 1985の3節のアルゴリズム（特に3のaとb）と、min-caml.pdfの図14〜16を比べて、前者が後者より特にわかりやすいかというと、そうでもないと思いました。わかりにくかったとしたら、私の説明が下手だったせいかと…。すみません。

Haskellのコンパイラについては（日本では）だれに聞けば良いのか？

う、特に「コンパイラについて」と言われると僕はちょっとすぐには思いつきませんが、やはり武市研の先生方でしょうか…？　他に詳しそうな方がいらしたら教えてください（他力本願）。

（英語の）参考図書は資料の最後に挙げた本などもありますが。

もちろん、単純に遅延評価を実装するだけなら、OCamlで（組み込みのlazyや、関数以外の値のlet recを使わずに）書くと

type 'a thunk = NotYetEvaluated of (unit -> 'a) | AlreadyEvaluated of 'a
type 'a my_lazy = 'a thunk ref

のように思って

let delay f = ref (NotYetEvaluated f)
let force x =
  match !x with
  | NotYetEvaluated f ->
      let v = f () in
      x := AlreadyEvaluated v;
      v
  | AlreadyEvaluated v -> v

や

type 'a lazy_list = Nil | Cons of 'a * 'a lazy_list my_lazy
let ones =
  let rec f () = Cons(1, delay f) in
  f ()
let rec take n = function
  | Cons(head, tail) when n > 0 ->
      head :: take (n - 1) (force tail)
  | _ -> []

のような感じにすれば良いのかもしれませんが、strictness analysis（いずれ絶対にforceされるthunkは、最初からstrictにevaluateする）やlinearity analysis（一回しかforceされないthunkは、:=によるupdateを省略する）など、最適化等もいろいろとあるので…

余談：「strictな言語で、関数だけ再帰定義できるのはなぜ？」という質問をどこかで見かけた気がするのですが探しても見つからない…。関数の本体（fun x -> eのe）は、その関数が適用されるまで評価されないという意味で「遅延評価」されるから、と私は理解しています。同じ話かもしれませんが、effect systemやcomputational lambda-calculusなどでも、→の上にはlatent effectがついている（ないし→の右がmonadになっている）し。