Arantium Maestum

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

言語処理系

Graydon HoareのCompiler講義資料が面白かった話

Graydon Hoareが2019年にカナダのブリティッシュ・コロンビア大学でコンパイラ関連のゲスト講義した時の資料21 compilers and 3 orders of magnitude in 60 minutes - a wander through a weird landscape to the heart of compilationを読んだら大変面白か…

Compiling with ContinuationsとORBITの関係

前回の記事でも紹介したOlin ShiversのT Programming Languageに関する回顧録で It had a big influence on Andrew Appel, at Princeton, who subsequently adopted a lot of the ideas in it when he and Dave MacQueen's group at Bell Labs built the SML…

論文メモ:ORBIT: An Optimizing Compiler for Scheme

CPS形式のコンパイラIRについて調べていてORBITというコンパイラについての話が出てきたので、1986年に出た論文ORBIT: An Optimizing Compiler for Schemeを読んでみた。 ORBITはGuy SteeleのRABBITというScheme Compilerから「CPS形式をIRとして使う」とい…

論文メモ:Abstract machines for programming language implementation

Abstract machines for programming language implementationを読んだのでメモ。 どのようなAbstract Machineがどのようなプログラミング言語の実装に使われてきたのか、というサーベイ。2000年に書かれており筆頭著者はHaskell界隈ではそれなりに知られてい…

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…

参考になる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パーサ全般)について勉強し直してい…

LispKit Lisp処理系の実装 6:SECD抽象機械の状態遷移〜条件分岐、関数関連など

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

LispKit Lisp処理系の実装 5:SECD抽象機械の状態遷移〜リスト操作と比較・算術演算

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

LispKit Lisp処理系の実装 4:SECD抽象機械のメモリとレジスタ

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

LispKit Lisp処理系の実装 3:インタプリタ〜条件分岐から関数適用まで

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

LispKit Lisp処理系の実装 2:インタプリタ〜変数から算術演算子まで

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

LispKit Lisp処理系の実装 1:パーサ

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

LispKit Lisp処理系の実装 序

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

PythonでLanguage Implementation Patternsのパーサと戯れる Packratパーサのメモリ効率化

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

PythonでLanguage Implementation Patternsのパーサと戯れる Packratパーサのキャッシュクリア

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

PythonでLanguage Implementation Patternsのパーサと戯れる Packratパーサ

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

PythonでLanguage Implementation Patternsのパーサと戯れる Backtrack可能なパーサ

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

PythonでLanguage Implementation Patternsのパーサと戯れる Backtrackableストリームオブジェクト

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

PythonでLanguage Implementation Patternsのパーサと戯れる LL(2)再帰的パーサ

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

PythonでLanguage Implementation Patternsのパーサと戯れる ネストしたリストのLL(1)再帰的パーサ

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

PythonでLanguage Implementation Patternsのパーサと戯れる 簡単なリスト言語の非再帰的なパーサ

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

PythonでLanguage Implementation Patternsのパーサと戯れる lexerとPeekableストリームオブジェクト

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

PythonでLanguage Implementation Patternsのパーサと戯れる 序

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