第28回『Implementing functional languages: a tutorial』勉強会

Simon L. Payton Jones, David R. Lester Implementing Functional Languages: a tutorial, 1991 を読みながら非正格関数型言語の処理系を書きます。

p172「4.3.3 Compilation schemes for arithmetic」 の実装から進めます。以前の蒸し返しも歓迎。 途中参加で手元にここまでのコードが無いからと尻込みしている人は https://github.com/nobsun/ifl-tut を clone するという手もあります。

オンライン開催

Google Meet によるオンラインでの開催になります。

登録いただいた参加者の方には URL など参加のための情報を前日までに通知いたします。 当日まで connpass からの連絡に気をつけるようにしておいてください。

すすめ方

この本のほとんどが、コードとその説明、それに練習問題も不足している実装を行うコードを書くというものです。 コードを書いて、動作を確認し、議論しながら楽しみましょう。

持ち物

• 『Implementing functional languages: a tutorial』
• Haskellのプログラミング環境を作ったPCを用意しておいてください

参考書について

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

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

[^1]: Miranda は Research Software Ltd. の登録商標です。

[^2]: 地の文の説明は、Miranda を前提としています。

この本の構成

1章で提示されたCore言語を4つの異なるVMの機械語にするコンパイラとそれぞれの機械語の解釈系を書きます。 6章は、λリフティングの技法に関する解説です。

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