型システムにバリアント型とケースに対するパターンマッチを追加する。 こういうやつ： type t = Name of string | Id of int let to_str = function Name s -> s | Id n -> string_of_int n 代数的データ型における直和型であり、前回の直積型と合わせると…

前回のLetまで実装した型システムにレコードを追加する。 gist.github.com レコードというのは{x=1; y=true}のような値にラベルのついたデータ構造。ちなみにタプルは型システム的にはレコードの亜種と考えていい（ラベルが0~の整数だと見做せる）。どちらも…

前回のコードにLetによる変数束縛を追加する。 gist.github.com コードの追加としては2行のみと非常に短い。 型 変更なし 式 追加するのはLetだけ： type exp = ... | ELet of string * exp * exp ELet(変数、変数を束縛する式、本体の式）という構成になっ…

前回のSTLC+Boolに自然数と関連する機能を追加していく。 gist.github.com 型 TNatという自然数を表す型を追加： type ty = ... | TNat 式 三種類の式を追加： type exp = ... | ENat of int | EAdd of exp * exp | EIsZero of exp 自然数リテラルを表すENat…

前回のSTLCにBool型と関連する式を追加してみる： gist.github.com まずは型にTBoolを追加： type ty = ... | TBool 式にTrue, FalseとIf式を追加： type exp = ... | ETrue | EFalse | EIf of exp * exp * exp If式はcondition式、if-true-branch式、if-fal…

前回Simple Boolからはじめると書いたのだが、よく考えると単純型付きラムダ計算（STLC）ではじめるのが当然な筋な気がしてきた。 ので急遽Simple BoolからBoolを取っ払ってSTLCだけをまずみてみる： gist.github.com 定義されるものとしては 「型」を表す型…

最近は言語処理系に関してまったく手を動かしていなかった＆ブログに何も書いていなかったので練習がてら・・・ Types and Programming Languagesには非常にたくさんの型システムの実例と関連したOCamlコードが載っている。ただし多くは写経したらそのまま実…

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抽象機械はControl（実行する式）、Environment（変数環境）、Kontinuation（継続）の三つの要素を持つ。 CESK抽象機械はそこにStore（格納）を…

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

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

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

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

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

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

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

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

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

代数型データ型とそれに対するパターンマッチの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…

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

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

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

再帰関数のことを忘れていた！ というわけで幕間的な記事。 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…

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

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

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

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

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

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

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