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

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

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

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

この本の構成

• 1. Core言語の抽象構文木、プリティプリンタ、パーザ
• 2. テンプレート具体化を利用した（仮想）マシン
  • 2.3 Mark1 最小のテンプレート具体化グラフ簡約器
  • 2.4 Mark2 let(rec)式
  • 2.5 Mark3 更新の追加
  • 2.6 Mark4 算術演算の追加
  • 2.7 Mark5 構造を持つデータ
    • 2.7.2 条件式
    • 2.7.3 対
    • 2.7.4 リスト
    • 2.7.5 リストの印字
  • 2.8 別実装
    • 2.8.1 プリミティブの別実装（Mark5a）
    • 2.8.2 ダンプの別実装（Mark5b）ステップ実行機能も追加済み
    • 2.8.4 データ値の別実装（Mark5c）
  • 2.9 GC
    • 2.9.1 マーク・スキャン GC（Mark5mgc）
    • 2.9.2 間接参照の除去
    • 2.9.3 反転ポインタ
    • 2.9.4 2-スペースGC（コピーGC）
• 3. G-machine（グラフ簡約マシン）
  • 3.1 G-machine 入門
    • 3.1.1 例
    • 3.1.2 さらに最適化
  • 3.2 雛形を構築するためのコード列
    • 3.2.1 算術式の後置評価
    • 3.2.2 後置コードでグラフを構成する
    • 3.2.3 具体化の後に何が起きるか
  • 3.3 Mark 1: 最小限の G-machine
    • 3.3.1 全体構造
    • 3.3.2 データ構造
    • 3.3.3 評価器
    • 3.3.4 プログラムのコンパイル
    • 3.3.5 結果の印字
    • 3.3.6 Mark 1 G-machine の改良
  • 3.4 Mark 2: Lazy化
    • 3.4.1 データ構造
    • 3.4.2 評価器
    • 3.4.3 コンパイラ
  • 3.5 Mark 3: let(rec) 式
    • 3.5.1 局所的に束縛される変数
    • 3.5.2 データ構造
    • 3.5.3 評価器
    • 3.5.4 コンパイラ
  • 3.6 Mark 4: プリミティブの追加
    • 3.6.1 データ構造
    • 3.6.2 状態の印字
    • 3.6.3 新しい命令の状態遷移
    • 3.6.4 コンパイラ
  • 3.7 Mark 5: 算術演算処理をよりよくするために
    • 3.7.1 課題
    • 3.7.2 解決
  • 3.8 Mark 6: データ構造の追加
    • 3.8.1 概観
    • 3.8.2 データ構造
    • 3.8.3 結果の表示
    • 3.8.4 命令セット
    • 3.8.5 コンパイラ
    • 3.8.6 比較演算で新しい論理値表現を使う
    • 3.8.7 受け入れ言語の拡張
  • 3.9 Mark 7: さらなる改良
    • 3.9.1 V-スタックを使った階乗計算の実行
    • 3.9.2 データ構造
    • 3.9.3 インストラクションセット
    • 3.9.4 コンパイラ
  • 3.10 結論
• 4. TIM（Three Instruction Machine）
  • 4.1 背景： TIMの動作
    • 4.1.1 平坦化
    • 4.1.2 タプリング
    • 4.1.3 無脊椎
    • 4.1.4 例
    • 4.1.5 状態遷移規則による機械の定義
    • 4.1.6 コンパイル
    • 4.1.7 更新
  • 4.2 Mark 1: 最小TIM
    • 4.2.1 全体構成
    • 4.2.2 データ型定義
    • 4.2.3 プログラムのコンパイル
    • 4.2.4 評価器
    • 4.2.5 結果の印字
    • 4.2.6 ガベージコレクション
  • 4.3 Mark 2: 算術演算の追加
    • 4.3.1 概要: 算術演算の動作
    • 4.3.2 単純な算術演算の実装追加
    • 4.3.3 算術演算用コンパイル図式
  • 4.4 Mark 3: let(rec) 式
    • 4.4.1 let 式
    • 4.4.2 letrec 式
    • 4.4.3 フレームスロットの再利用
    • 4.4.4 ガベージコレクション
  • 4.5 Mark 4: 更新
    • 4.5.1 基本的な技法
    • 4.5.2 PushMarker命令のコンパイル
    • 4.5.3 更新機構の実装
    • 4.5.4 間接参照の更新に伴う問題
    • 4.5.5 共有let(rec)-束縛変数の更新
    • 4.5.6 間接参照鎖の除去
    • 4.5.7 部分適用の更新
  • 4.6 Mark 5: 構造を持つデータ
    • 4.6.1 汎用的アプローチ
    • 4.6.2 構造を持つデータに対する遷移規則とコンパイル図式
    • 4.6.3 トライアウト
    • 4.6.4 リストの印字
    • 4.6.5 構造をもつデータ構造の直接使用
  • 4.7 Mark 6: CAFとコードストア
    • 4.7.1 CAFの実装
    • 4.7.2 より正確なコードストアのモデル
  • 4.8 まとめ
• 5. 並列G-machine
• 6. λ リフティング

コードについて

この main ブランチのコードは ghc-9.2.0 で導入された言語拡張 'OverloadedRecordDot' を使用しています。

起動

プロジェクトルートにおいて、コマンド stack exec -- ti5b prog/prog17.ifl で雛形具体化機械 ti5b にサンプルプログラム prog17.ifl ロードして起動すると、

% stack exec -- ti5b prog/prog17.ifl
   0) Heap [  40: NAP #21 #1
              39: NPrim print
              ...
              途中略
              ...
      Stack [  40: NAp   21    1 (NSupercomb main) ]
      Depth 1
      Dump []
      Output []
      no description


|

のように初期状態（の一部）が表示された状態で停止する。

• Enterキー（空文字列の入力）で、次の状態に遷移
• Cキー、Enterキーの順で押下（文字列Cの入力）で、最後の状態まで遷移
• 数字入力で、指定したかずぶんだけ状態が遷移

Footnotes

1. Miranda は Research Software Ltd. の登録商標です。 ↩

2. 地の文の説明は、Miranda を前提としています。 ↩