Arantium Maestum

プログラミング、囲碁、読書の話題

OCaml

A正規化されたIRをCPSに変換する

A正規化について非常に参考にさせてもらっているMatt Mightのブログ記事で A later transformation to continuation-passing style (like that in Appel's book) is also simplified if transforming from A-Normal Form. とあるので、これまでのA正規化され…

CEK抽象機械をCESK抽象機械に拡張する

前回のCEK抽象機械を拡張して、ミュータブルな状態のある言語も自然に実行できるようにする。 CESK抽象機械 CEK抽象機械はControl(実行する式)、Environment(変数環境)、Kontinuation(継続)の三つの要素を持つ。 CESK抽象機械はそこにStore(格納)を…

A正規化されたIRをCEK抽象機械で実行

前回で定義した言語とそのA正規化されたIRをインタプリタで実行したい。 というわけでまたしてもMatt Mightのブログを参考にする: matt.might.net こちらのブログはCESKマシンの話だが、今のところ破壊的変更を言語機能として実装してないので、まずはCESK…

関数のある言語のA正規化

前回の言語に関数定義・適用を追加する。 単一引数の関数 まずは変更を簡単にするために「単一引数の関数」を実装する。 関数自体の式であるFnと関数適用のCallをASTに追加: type t = ... | Fn of string * t | Call of t * t α変換は関数式に関しては(仮…

条件分岐のある言語のA正規化

前回に続いてA正規化の話。前回のミニマルな言語にブール型とifによる条件分岐を加える。実は条件分岐の正しいA正規化に関しては曖昧性があるようなので、後半はその話。 言語拡張 ASTに以下を追加: type t = ... | Bool of bool ... | Lt of t * t ... | I…

ミニマルなA正規化コードサンプル解説

言語処理系の実装の手法として「A正規化」というものがある。 元のソースプログラムを変換して最適化や機械語へのコンパイルなどがやりやすい形にする、処理系IRの選択肢一つである。CPS(継続渡しスタイル)のIRと非常に似ている。 The Essence of Compilin…

OCamlでmliいつ書くの問題

mliとは? OCamlのプログラムは基本的にいくつものモジュールに分割されて書かれる。そして「あるファイルに記述されたOCamlコード」は独立した一つのモジュールとなる(中に複数のサブモジュールが定義されていることはあり得る)。 ただし、Cの.hと.cファ…

OCamlでLLVM JITを試した

自作言語熱が高まっていて、バックエンドをLLVMでやりたいと思っている。 OCamlでLLVMというとLLVMプロジェクト公式のKaleidoscope言語をOCamlで実装するチュートリアルが有名、なのだが、10年近く前に壊れたAPIを使っていたりと実際に使えるものではなく、…

参考になるMenhir製パーサ その3(500行以上編)

前々回、前回に続いて500行以上の本格的なMenhirパーサの例。 C11パーサ A simple, possibly correct LR parser for C11という論文のもとになった、Menhirを使ってなるべく正確な(過去のC11基準コンパイラがパースに失敗するプログラムもパースできる)C11…

参考になるMenhir製パーサ その2(500行未満編)

前回に続いて、今回は少し大きめの「教材ではない」パーサの例を挙げる。 GraphQL github.com GraphQLのクエリをパースするコード。OCamlでGraphQLサーバを作るライブラリの一部。クエリ言語であって本格的なプログラミング言語ではないので、ある程度簡単(…

参考になるMenhir製パーサ その1(チュートリアル・サンプル編)

最近またぼちぼちMenhirでパーサを書いている。 けっこう仕様が大きめの自作言語用で、とりあえず書いてみたら案の定というか、見事にメチャクチャになって討ち死にした。なので一旦そのパーサ制作から離れてMenhir(とLRパーサ全般)について勉強し直してい…

OCamlのlambda IRをいじる(代数的データ型)

代数型データ型とそれに対するパターンマッチのlambda IRへのコンパイルを見ていく タグのみ直和型 まずは簡単なタグのみ直和型を見てみる: type t = A | B | C let () = let x = C in match x with | A -> print_int 1 | B -> print_int 2 | C -> print_in…

OCamlのlambda IRをいじる(レコード)

レコード型を定義して使うコードがどのようにlambda IRにコンパイルされるかを見ていく。 定義して使う 簡単なレコード型を定義した上でa.xなどとアクセスして使ってみる: type t = { x : int; y : string } let () = let a = {x=1; y="hello"} in print_en…

OCamlのlambda IRをいじる(リスト)

リストとパターンマッチ、Listモジュール使用のコンパイルを見ていく。 簡単なパターンマッチ 簡単なリストを作り、リストのコンストラクタ2つに対しての素直なパターンマッチをする: let () = let xs = [1;2] in match xs with | [] -> print_endline "he…

OCamlのlambda IRをいじる(タプル)

タプルとそれに対するパターンマッチがどうlambda IRにコンパイルされるかを見ていく。 fst/snd まずは非常に簡単なタプルと、その値をfst/sndでアクセスするコード: let () = let x = (1,2) in print_int @@ (fst x) + (snd x) -dlambdaでコンパイル: (se…

OCamlのlambda IRをいじる(再帰関数)

再帰関数のことを忘れていた! というわけで幕間的な記事。 Factorial 再帰で階乗なコード: let () = let rec f x = if x = 0 then 1 else x * (f (x-1)) in print_int @@ f 5 -dlambdaでコンパイル: (seq (let (*match*/83 = (letrec (f/80 (function x/8…

OCamlのlambda IRをいじる(関数)

前回に続いて、ローカルとモジュールレベルでの関数定義がどうlambda IRにコンパイルされるかを見ていく。 ローカル関数 まずはこんな感じの簡単な関数: let () = let f x = x + 1 in print_int @@ f 5 ocamlopt -c -dlambda localfunc.mlなどとすると: (s…

OCamlのlambda IRをいじる(変数)

前回に続いて、モジュール内で変数を定義して使うプログラムがどのようなlambda IRにコンパイルされるかを見ていく。 ローカル変数1つ OCamlで変数を定義する場合、モジュールのトップレベルでの定義と、ある式の一部としてlet x = y in zのxのような定義の…

OCamlのlambda IRをいじる(はじめに)

OCamlのコンパイラの話題でよく聞くflambdaという最適化ステップについて資料を読んでいた: https://ocaml.org/meetings/ocaml/2013/slides/chambart.pdf スライド5にコンパイラの中間表現のステップと説明が書いてあったのが面白かった。 parse tree: AST…

OCamlのGADTでVariadic Function(Stack Overflowより)

このStack Overflow問答が大変面白かったのでメモ: stackoverflow.com サンプルコードは少し(自分にとっては)わかりやすいように変えてある。 何をしたいか 第一引数によって、それ以降幾つの引数をとるかが変化するような可変長引数関数を書きたい。 例…

OCaml Batteries IncludedのLazyList/Seq/Enumについて

OCamlの標準ライブラリは貧弱なことで知られている。 OCamlコミュニティの間でも「あれはOCamlコンパイラを書くためのライブラリだ」と言われていて、実際INRIAで必要最低限(つまりコンパイラを書くのに必要な分だけ)提供している側面がある。 基本的なデ…

OCamlで存在型を試してみた(その4ーーGADT)

ここまで zehnpaard.hatenablog.com zehnpaard.hatenablog.com zehnpaard.hatenablog.com とモジュール関連の機能で存在型を扱う話をしてきた。 しかし、OCamlでもっとも直接的に存在型をエンコードしたいならGADTが使える。 ダメな例 まずはうまくいかない…

OCamlで存在型を試してみた (その3ーーモジュール)

シリーズ前々回と前回に続いて存在型を探っていく。 今回はパラメトリックな機構はまったく使わないただのモジュールと存在型について。 第1級モジュールやファンクタによる抽象化機能と存在型について書いてきたが、型としての「存在型」はどちらの場合で…

OCamlで存在型を試してみた (その2ーーファンクタ)

zehnpaard.hatenablog.com の続き。 前回は第1級モジュールを非常に綺麗に存在型に対応させられることが示せた。 しかし第1級モジュールを使わずとも、OCamlだとモジュールのシグニチャ自体が存在型的だ。(ただし微妙だが重要な差異もある) 今回はファン…

OCamlで存在型を試してみた (その1ーー第1級モジュール)

Types and Programming Languagesの24章の主題は存在型(Existential Types)である。 私は何回読んでもここでつまづく。 この章に到達するまでに部分型やら再帰型やら型推論やら全称型やら出てくるが、まあ難しくとも、なんとなくどういった言語機能に関連…

モジュールシグニチャの多重継承

前回の記事で module type ADD = sig type t val add : t -> t -> t val to_string : t -> string (* ここ *) end のようなシグニチャを書いたが、書いていて「うーん、これはおかしいな」と思った。 MULでto_stringが必要だったからといってADDのインターフ…

Expression ProblemにおけるOOPと関数型の対比について

Expression Problemという計算機科学・ソフトウェア工学の世界でそれなりに有名な問題がある。 この記事がいい感じにまとめていると思う: eli.thegreenplace.net Imagine that we have a set of data types and a set of operations that act on these type…

OCamlProのOCaml Cheat Sheets

OCamlProのブログを過去に辿っていたらこういう記事を見つけた: www.ocamlpro.com OCamlの構文の1ページまとめと、標準ライブラリの2ページまとめ。(出たのは2019年9月) 流石に構文に関しては(Objects & Classes関連以外は)知らないところはなかった…

Robert Harperの型クラス批判

Robert Harperのブログに(10年くらい前に)載っていたHaskellの型クラスに対する批判について@elpin1alさんに教えていただいたのでメモ。@elpin1al ありがとうございます! 型クラスとモジュール 言語の抽象化機構の中心的存在は何かと考えると、Haskellな…

open recursionなモジュールに型定義を持たせる(下改)

open recursionの記事に関して、より良い書き方があることに気づいたので書き留めておく。 あっちの記事ではシグニチャ二つを定義していて、GT.t = GT.s greet、NT.t = NT.s named greetと、GT.t型とNT.t型の形が違っていた: module type NT = sig type s t…