『関数型言語を実装する：チュートリアル』を読む

Simon L. Payton Jones, David R. Lester Implementing Functional Languages: a tutorial, 1991

本書は、遅延グラフ簡約を用いた非正格な関数型言語の実装を理解するための実践的なアプローチを提供します。 この本は、読者が自明ではないコンパイラを開発、修正、実験することで、関数型言語の実装を「生き生きと」させるための実践的な実験材料を提供することを目的としています。

この本にある実装は、元々 Miranda¹で書かれていましたが、現在、公開されているものは、Haskellで示されています²。 30年も前に出版されたものなので、説明されている実装は、最新の言語実装技術によるものではなく、現在では素朴にみえるものです。 しかし、基本的なアイデアは興味深く、実装としてもまとまっているので、入門をおえたプログラマ向けのHaskellプログラミングの教材として楽しいものになっています。 おまけに遅延評価を行う関数型言語系の実装が学べます。 他にも、現在では当たり前になり、標準的なライブラリとして提供されている（それゆえに、利用はするが、どのようなアイデアでデザインされているのかあまり知らない）プリティプリンタやパーザコンビネータのアイデアを楽しめます。

1. Core言語の抽象構文木、プリティプリンタ、パーザ
2. テンプレート具体化を利用した（仮想）マシン
3. G-machine（グラフ簡約マシン）
4. TIM（Three Instruction Machine）
5. 並列G-machine
6. λ リフティング