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

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

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

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

前回に続いてstep関数内の命令コードに対するパターンマッチを見ていく。 今回見ていくのは以下の命令コード： 条件分岐のSEL、JOIN スタックに値を乗せるLD、LDC、LDF 関数適用のAP、RTN 再帰関数のためのDUM、RAP プログラム停止のSTOP 条件分岐のSEL、JOI…

前回の記事ではSECD抽象機械のメモリとレジスタを定義していった。今回（と次回）はSECD抽象機械が実際にどうやってプログラムを実行するかを見ていく。 SECDマシン上でプログラムを実行するということは、Controlレジスタcが指し示すコンパイルされたプログ…

前回はLispKit Lispの挙動を確認するためもあってASTを直接実行するインタプリタを実装した。これからはLispKit LispのプログラムをSECD抽象機械上で実行するために必要なものを揃えていく。 今回と次回はSECDマシン自体の実装の話。 SECDマシン SECD抽象機…

前回に続いてインタプリタの実装。今回はeval_の後半、IFによる条件分岐以降の項目を見ていく。 条件分岐のパターンマッチ 条件式を評価してその結果に対してパターンマッチ、分岐部分の式は片方しか評価されない。 case Cons(Alpha("IF"), Cons(e1, Cons(e2…

前回のパーサの出力するASTをそのまま実行するインタプリタを実装する。 インタプリタを実装する意義 「SECD抽象機械へのコンパイラ実装の前にインタプリタを作る」というのはHendersonのFunctional Programming Application & Implementationでの流れに従っ…

前回書いたとおりまずはパーサを実装する。 最近散々パーサ実装について書いてきてなんだが、Lispなのでかなりの手抜きパーサ。 字句解析 まずはトークンの定義： from dataclasses import dataclass @dataclass class Lparen: pass @dataclass class Rparen…

純粋関数型Lisp方言であるLispKit LispのインタプリタとSECD抽象機械の機械語へのコンパイラを作成する。 タネ本はHendersonの「Functional Programming - Application & Interpretation」で、この本に載っているISWIMやPASCALのコードを大体なぞるようにPyt…

前回まで見てきたBacktrackingパーサ、Packratパーサは「これまで見たすべてのトークン」をメモリ上のバッファに保持し続け、それらに対してのパース結果もすべてキャッシュに残し続ける実装になっていて、パース終了直前にはソースファイルのすべてのトーク…

前回のコードだとparse関数を複数回呼び出すと前回のキャッシュが残っていてパースがうまくいかない問題があった。parse呼び出しごとにキャッシュをクリアするようにしたい。 キャッシュ xparser.pyモジュールのトップレベルにキャッシュのリストとそのリス…

前回の記事は同じパースを何回も繰り返すので非効率だと書いたが、まずはどの程度非効率なのかを計測してからPackratパーサで効率化を図る。 計測 まずは問題の程度を計測したい。 こんなデコレータを定義する： def _print_call(func): @functools.wraps(fu…

前回実装したBacktrackableストリームを使って「任意のトークンを消費してパースを試した上でバックトラックできる」パーサを実装していく。 言語 前回同様の言語。再掲するとこのようなもの： list : '[' elements ']'; elements : element (',' element)*;…

前回のような固定数のトークン先読みではなく、任意のトークンを消費しつつパースし続け、失敗したらバックトラックするようなパーサを作りたい。 今回の記事はまずバックトラック機能を提供するトークンストリームのクラスを作成する。（パーサ本体は次回）…

先読み要素を増やすことで前回のLL(1)パーサより複雑な構文をパースできるようになる。 言語 ここまで見てきたリスト言語に変数間の代入を追加する： list : '[' elements ']'; elements : element (',' element)*; element : NAME | assign | list; assign …

前回の記事の言語とパーサを拡張して、ネストありリスト言語の再帰下降パーサを作る。 言語 文法はこの通り： list : '[' elements ']'; elements : element (',' element)*; element : NAME | list; # elementが再帰的にlistになり得る NAME : ('a'..'z' | …

（注：この記事を出した当初はパースが成功した場合Trueを返す実装にしていたが、Language Implementation Patternsと同じように成功した場合は何も返さないように修正した。実装がスッキリするということと、失敗は例外で表現しているので返り値には意味が…

パーサを作るにあたってまずはlexerから。 lexerと簡単なパーサで共通しているのは「消費可能なストリームの先頭を『消費することなく』先読みする必要がある」という点。lexerだと入力の文字のストリーム、パーサだとlexerの返すトークンストリーム、と対象…

前２回の記事でも書いたとおり、Language Implementation Patternsのはじめの方をPythonで実装している。 具体的にはPackrat Parsingまで、本に出てくるクラスベースな実装ではなく、lookaheadやbacktrackの機能はトークンストリームの方に持たせた上で相互…

前回に続いてLanguage Implementation PatternsのJava実装例をPythonでやってみる。 今回はLL(1) Recursive Descent Parser。 パース対象 パースする言語は前回と同様： list : '[' elements ']'; elements : element (',' element)*; element : NAME | list…

Language Implementation Patternsという本がある。翻訳もされていて、邦題は「言語実装パターン―コンパイラ技術によるテキスト処理から言語実装まで」。作者はTerrence Parrで、ANTLRというJavaベースのパーサ・ジェネレータの開発者。 パーサ作成から始め…

私は趣味の言語処理系実装でocamllex/menhirというパーサジェネレータにお世話になることが多い。（このブログの過去記事を参照） js_of_ocamlは基本的にFFIを使わないライブラリだったらJavaScriptにコンパイルしてくれるはずなので、ブラウザでパーサが使…

前回に続いてCPS変換の話。 前回はパーサから帰ってくるExp.t型のASTを同じExp.t型のCPS形式になっているASTに変換してからインタプリタに実行させていた。 インタプリタが（特にビルトイン関数について）関数の最終引数を継続だと認識するようになったので…

インタプリタ自作によってプログラミング言語の諸概念を学んでいく「Essentials of Programming Languages」の第5章、第6章はどちらも継続渡しスタイルについて語っている。 第5章は「インタプリタを継続渡しスタイルで書くとどうなるか」という話を掘り下げ…

実装したモナドやmap、fold_leftなどの関数をライブラリ化することで毎回定義し直さなくても済むようにしたい。 その準備段階としてモジュールを実装する。（ファイルから読み込む場合もモジュールとして扱いたいため） 具体的には (module [...])という構文…

前回こう書いた： ちなみにこの記事を書いている最中にListモナド実装にも重大なミスがあることに気づいた 今回はその話。 reifyの型 Representing Monadsのreifyとreflectの型定義： signature RMONAD = sig structure M : MONAD val reflect : '1a M.t -> …

前回このように書いた： Stateモナドにはreflectに直接当たる処理はなく、getとputの二つの関数がモナディックな処理を担う。 しかし「限定継続を使ってモナドを表現する」というアイデアの元となるRepresenting Monadsという論文を読み直していたらちゃんと…

shiftとresetを使ってStateモナドを実装する。ちなみに今まで実装したモナドの中で随一のややこしさである。 Stateモナドはその名のとおり、計算に局所的な「状態」を持たせることができるモナドである。状態とは「値を参照したり書き換えたりできる何か」を…