日々の流転

λ. “The worker/wrapper transformation” by Andy Gill and Graham Hutton

• 公式版
• 著者版

を読んだ。

GHCでお馴染みの worker-wrapper transformation についての論文。 私は worker-wrapper transformation というと非ボックス化(unboxing)のための手法という認識だったが、この論文では再帰する際の型を変更する変換として一般化して形式化しており、それを適用するための前提条件と、以下のような幾つかの例を紹介している。

1. リストのreverseの素朴な再帰的定義から蓄積変数を利用する定義への変換
2. 階乗を計算する関数の非ボックス化
3. フィボナッチ数列を計算する関数のメモ化
4. 例外を持つ言語の評価機のタグレス化

非ボックス化以外の例を worker-wrapper transfomration として形式化できるだなんて、考えたことがなかったので、驚いた。 ただ、それらはコンパイラが自動的に行うのは難しく、むしろ人間が使うための推論規則ではあるのだけれど。