1 of 8

Haskell で

　Haskell 処理系

　　かいてます (575)

2021-05-30 プログラミング言語処理系が好きな人の集まり　第１回ミートアップ

​

海野　秀之（うんの　ひでゆき）

@unnohideyuki

2 of 8

Bunny

A Haskell compiler for Android

  • Haskell で書かれた Haskell コンパイラ
  • ターゲットは Android
    • オブジェクトコードは Java プログラム
    • 別途 Java で記述したランタイムライブラリと結合
    • Android SDK を用いて Android アプリを作成
  • 簡単な （Andorid API 使わない）テストプログラムは�開発マシン上で実行可能（Java プログラムなので）

3 of 8

コンパイラの構造（処理パイプライン）

https://uhideyuki.sakura.ne.jp/studs/index.cgi/ja/HaskellInHaskell

2016 年時点からこの図の構造はかわってないです

4 of 8

これまでやったこと（とてもながい。盆栽？）

  • 2014 ~ 2015: Tiger Book の前半: Haskell で Tiger コンパイラをつくる
  • 2015: Bunny 作成開始、Lexer 書き始め、�並行して Typing Haskell in Haskell を勉強（ほぼノートに書き写しつつ読む）
  • 2016/5月 STG のことを勉強していたのがこのへん�型推論器は Typing Haskell in Haskell みれば作れたとして、その先が�よくわからない。型推論 → （Core を用いてなにかやる）→ STG なので�ターゲットを知りたい
  • 2016/7月 辞書渡し形式についての論文をいくつか探してきてよむ
  • 2016/12月 最初の目標だったクイックソートが動くように
  • （停滞というか放置というか…）
  • 2020/12月 Android 上で簡単なプログラムが動くようになった

modern

compiler

implementation

in ML

(通称 Tiger Book)

5 of 8

Tiger コンパイラとの比較

Tiger コンパイラの処理フェーズ

  • 字句解析
  • 構文解析
  • 意味解析（型チェック）
  • 翻訳
  • 正準化
  • 命令選択
  • 制御フロー／データフロー解析
  • レジスタ割付け
  • コード生成
  • アセンブラ／リンカ

Bunny の処理フェーズ

  • 字句解析
  • 構文解析
  • 結合性解決
  • リネーム（α変換など）
  • 意味解析（型推論１）
  • 脱糖／パターンマッチ変換
  • 辞書渡し形式（型推論２）
  • STG 変換
  • クロージャ変換
  • コード生成
  • Java コンパイラ

言語は単純だが、マシン語出力に必要な

メモリ・レジスタ配置の処理が多い

Haskell が高水準言語なので

意味解析と中間言語間の翻訳段数が多い

今回は Java を吐くことにしておいて良かった…

6 of 8

JVM ターゲットの限界？（Dalvik でも同じはず）

  • 現状は、まず動くものにしたいこともあって、STG（中間言語）のインタプリタのようなものをランタイムライブラリと用意して実行している（めちゃくちゃ非効率）
  • GHC では、STG → C-- → ターゲットのマシン語 となっているが、これは真似できない
    • 理由１： 難しくて、まだ、よくわかってない
    • 理由２： C-- の関数呼び出しは全て末尾呼び出しらしいが、 JVM/Dalvik 上では不可でしょ？
  • JVM / Dalvik の仕様的に、末尾呼び出しは不可能ですよね？（私の理解）
    • 大域ジャンプがない（Goto はあるが、分岐先は同一メソッド内に限定）
    • そもそも、メソッドをまたがるようなアドレス空間が定義されない
  • 関数型言語の実行基盤としては厳しめなんだろうか？
  • 再帰呼び出しをループに変換するような最適化が必要となる？

※ Version 2 以降で気にします（いまはまず Version 1 を目指さねば）

7 of 8

Version 1 / 2 へのロードマップ

Version 0.9.x

  • バグ修正および不足機能の追加
  • 性能向上は基本的にしない
  • Semantic Versioning 導入
  • Issue Tracking とレポジトリ運用方針を決める（まともにしたい）

Version 1.0.0 (2021 年 5 月予定（未達））

  • Haskell 2010 仕様を満たす
  • FFI サポート、Java ライブラリを�利用可能とする
  • ターミナルエミュレータを改良

Version 2

  • 高速化�（STG実行方式の変更を含む）

定めてみたものの…

（めちゃくちゃ停滞中）

Version 1 に向けた大物（主観）

  • deriving 構文のサポート
  • ライブラリの import サポート�(いまでも Prelude.hs だけは import）
  • レコード構文
  • 例外
  • FFI

※ Haskell 処理系としてのコアは作成済みだが、実用的言語に�必要とされる様々なものが未だたくさん未実装。あとバグも多い。

8 of 8

ミートアップで話したかったこと

  • 進捗させる工夫について（みなさんどうしていますか？）
    • 小さな問題への分解、進捗のマネージメント�（これで少しは進んだ： https://uhideyuki.sakura.ne.jp/studs/index.cgi/ja/bunny_notes）
    • モチベ維持の仕掛け（ゲーミフィケーション的スコア？　芝生？）
    • 発表機会をつくる（私はアドベントカレンダーが唯一のドライバーでした）�→ このミートアップを励みにしたい！（重要）
  • いくつか話した悩み・不明点について教えてもらえたりしたらいいなぁ
    • Issue Tracker とか CI とか（ぜんぜん知らない）
    • JVM (/Dalvik) 上での関数型言語実装に関する情報

…など