Language Implementation PatternsのLL(1) ParserをPythonで実装してみる
前回に続いてLanguage Implementation PatternsのJava実装例をPythonでやってみる。
今回はLL(1) Recursive Descent Parser。
パース対象
パースする言語は前回と同様：
list : '[' elements ']';
elements : element (',' element)*;
element : NAME | list;
NAME : ('a'..'z' | 'A'..'Z')+;
（Language Implementation Patternsより引用）
基本方針
再帰下降構文解析でやっていくので、上記の文法に対応するような形の関数群が相互再帰しながらトークンのストリームを消費していく、という流れになる。
またLL(1)ということで「ストリームを消費せずに先頭のトークン１個を参照できる」という機能が必要になる。
実装１
まずは前回同様Language Implementation Patternsの実装にそれなりに忠実なやり方：
import liptoken as t import liplex2 as l class Parse: def __init__(self, str_input): self.input = l.lex(str_input) self.lookahead = next(self.input) def _consume(self): self.lookahead = next(self.input) def _match(self, target): if self.lookahead == target: self._consume() else: raise ValueError(f"{self.lookahead} encountered when expecting {target}") def list(self): self._match(t.Lbrack()) self.elements() self._match(t.Rbrack()) def elements(self): self.element() while self.lookahead == t.Comma(): self._consume() self.element() def element(self): match self.lookahead: case t.Name(_): self._consume() case t.Lbrack(): self.list() case token: raise ValueError(f"Invalid token {token} encountered at start of element {[token]+list(self.input)}")
Parseクラスを定義し、ストリームの状態管理（先頭要素のLookaheadも含めて）とパースするための相互再帰的なメソッドの両方を持たせている。
_consumeや_matchといった内部実装のメソッド（Pythonなのでprivateとして隠蔽はされていないが）で、メンバデータのトークンストリームに対するマッチや消費を行う。この実装ではストリームを消費しきった状態でself._consumeすると、StopIteration例外が発生するのをそのまま上に投げるようになっているが、もう少しエラーメッセージなどを頑張ってもいいかもしれない・・・
list、elements、elementといったメソッドがが文法の各項目に１対１で対応している。
このパーサは「文法に従っている文字列を受け取れば黙って消費して何も返さない、文法に違反していればエラー」というバリデータになっている。言語処理系などでみる「構文木を返す」ものではないことに注意。
>>> p1 = Parse("[abc, def, [x,y,z] , [a]]") >>> p1.element() >>> p2 = Parse("[abc, def, [x,y,z] , []]") >>> p2.element() Traceback (most recent call last): ... ValueError: Invalid token Rbrack() encountered at start of element [Rbrack(), Rbrack(), Eof()]
ちなみに明示的にEOFを調べないので、文字列の先頭にelementとしてパース可能な文字列が来ていればエラーは出ない。
>>> p = Parse("[abc, def, [x,y,z]] []")
>>> p.element()
実装２
次にパーサをクラス化せず、「Lookahead可能なストリームオブジェクトとそれに対する再帰下降な関数」という形での実装を試す。
まずはLookahead可能なストリームオブジェクト：
class Lookaheadable: def __init__(self, iterator): self.lookahead = [next(iterator)] self._stream = iterator def __iter__(self): return self def __next__(self): if not self.lookahead: raise StopIteration res = self.lookahead.pop() try: self.lookahead.append(next(self._stream)) except StopIteration: pass return res
__iter__と__next__があるのでこのLookaheadableクラスもIteratorとして使える。さらにx.lookaheadというメンバ変数が要素数１か０となっていて、これで次の要素を参照できる（あれば）。ここでリストを使っているのはPoor man's option typeだが、LL(k)に拡張するときはこの方が便利かもしれない。
あとはこのストリームを消費する関数群を再帰下降で書く：
import liptoken as t import liplex2 as l def parse(s): tokens = Lookaheadable(l.lex(s)) _element(tokens) def _list(tokens): _match(tokens, t.Lbrack()) _elements(tokens) _match(tokens, t.Rbrack()) def _elements(tokens): _element(tokens) while tokens.lookahead[0] != t.Rbrack(): _match(tokens, t.Comma()) _element(tokens) def _element(tokens): match tokens.lookahead[0]: case t.Name(_): next(tokens) case t.Lbrack(): _list(tokens) case token: raise ValueError(f"Invalid token {token} encountered at start of element {list(tokens)}") def _match(tokens, target): if tokens.lookahead[0] == target: next(tokens) else: raise ValueError(f"{tokens.lookahead[0]} encountered when expecting {target}")
ここのロジックはクラスベースの実装とそこまで違いはない。ただ、トップレベルで使うparse関数を新たに定義し、_list、_elements、_elementはすべて内部実装とした。
ちなみに前回の実装に関して言及した「文字列の先頭さえちゃんとパースできればエラーにならない」問題はこの実装でも存在する。ただし解決法は簡単で、parse関数を少しいじってEOFを明示的にチェックすればいい：
def parse(s): tokens = Lookaheadable(l.lex(s)) _element(tokens) _match(tokens, t.Eof())
これで"[abc, def, [x,y,z]] []"のように全体としては文法に従っていない文字列をパースしようとするとエラーになる：
>>> parse("[abc, def, [x,y,z]] []") Traceback (most recent call last): ... ValueError: Lbrack() encountered when expecting Eof()
実装３
実装２を修正して、ネストしたPythonリストと文字列をパース結果として返すようにしてみる：
def parse(s): tokens = Lookaheadable(l.lex(s)) return _element(tokens) def _list(tokens): _match(tokens, t.Lbrack()) res = _elements(tokens) _match(tokens, t.Rbrack()) return res def _elements(tokens): res = [_element(tokens)] while tokens.lookahead[0] != t.Rbrack(): _match(tokens, t.Comma()) res.append(_element(tokens)) return res def _element(tokens): match tokens.lookahead[0]: case t.Name(s): next(tokens) return s case t.Lbrack(): return _list(tokens) case token: raise ValueError(f"Invalid token {token} encountered at start of element {list(tokens)}") def _match(tokens, target): if tokens.lookahead[0] == target: next(tokens) else: raise ValueError(f"{tokens.lookahead[0]} encountered when expecting {target}")
各関数にreturnを追加していくだけなのがほとんど（_listの場合は返す結果を集めるPythonリストを作成していく修正が少し入るが）。
以下のように使える：
>>> parse("[abc, def, [x,y,z] , [a]]") ['abc', 'def', ['x', 'y', 'z'], ['a']]
これだと文字列やリストをそのまま返しているが、言語処理系のためにASTのノードを作成していって返すのも変更量としては大して違わない。ノードを表すオブジェクトにラップしてから返すだけ。
結論
個人的には全部を一つのクラスにするより、Lookaheadを可能とする状態とそれに対する操作だけをまとめたクラスを定義し、パースはそれに対する関数群として作る方が好み。
Language Implementation PatternsのLL(1) LexerをPythonで実装してみる
Language Implementation Patternsという本がある。翻訳もされていて、邦題は「言語実装パターン―コンパイラ技術によるテキスト処理から言語実装まで」。作者はTerrence Parrで、ANTLRというJavaベースのパーサ・ジェネレータの開発者。
パーサ作成から始めて、構文木の歩き方から型検査、バイトコードインタプリタやトランスパイラなどの話題を実装例を出しながら解説している。以前ぱらっと読んで大変面白かったのだが、手を動かして実装はしたことがなかった。実装言語がJavaで、私はJavaはなんとか読めるけどほとんど書いたことがないので少し敬遠してしまっていた。
最近Python3.10にパターンマッチが入ったので、それを使ってちょっとした言語処理系を実装してみたいという気分になっている。PythonだったらJavaコードのオブジェクト指向もそれなりに忠実に実装できるのでは？と思ってLanguage Implementation Patternsの最初の実装例であるLL(1) Lexerを試してみた。
パースしたい「言語」
今回のパースしたい言語（≠プログラミング言語）は「ネスト可能なリスト。アトミックな要素は一個以上のアルファベットからなる」というもの。
以下がその文法（Language Implementation Patternsより引用）：
list : '[' elements ']';
elements : element (',' element)*;
element : NAME | list;
NAME : ('a'..'z' | 'A'..'Z')+;
今回はLexerのみの実装なので'['、']'、','、'a'..'z'|'A'..'Z'の部分をトークンとして出力できるようになれば完了。
トークン
Pythonのdataclassを使ってトークンを表す（dataclassにするとプリント出力を自動的にいい感じに整えてくれたりする。今回の実装では出てこないがパターンマッチとの相性も非常に良さそうで、今後Pythonで代数的データ型を表現する場合はdataclassを使うのが主流になるんじゃないか？）：
from dataclasses import dataclass @dataclass class Eof: pass @dataclass class Comma: pass @dataclass class Lbrack: pass @dataclass class Rbrack: pass @dataclass class Name: s : str
これはLanguage Implementation Patternsの実装とは結構違っている。LIPではTokenクラスが定義されていて、トークンの種類を表す整数とLexされた文字列の二つをデータとして保持している。
Lexer実装１
というわけでLexer自体の実装にうつる。
まずLanguage Implementation PatternsのJava実装にまあまあ忠実なやり方：
import string from liptoken import Eof, Comma, Lbrack, Rbrack, Name class Lex: def __init__(self, s): self.s = s self.p = 0 self.c = s[0] if s else 'EOF' def next_token(self): while True: match self.c: case c if c in string.whitespace: self._consume() continue case 'EOF': return Eof() case ',': self._consume() return Comma() case '[': self._consume() return Lbrack() case ']': self._consume() return Rbrack() case c if _is_letter(c): return self._name() case c: raise ValueError(f"Invalid character {c}") def _consume(self): self.p += 1 try: self.c = self.s[self.p] except IndexError: self.c = 'EOF' def _name(self): cs = [] while _is_letter(self.c): cs.append(self.c) self._consume() return Name(''.join(cs)) def _is_letter(c): return c in string.ascii_letters
Lexerクラスに入力を文字列self.sとして持たせ、どの文字まで消費したかを表す「ポインタ」的なデータself.pをself._consumeメンバ関数を使って進めながら、１トークンごとにself.next_tokenで返していく。
self.next_tokenでは現在の文字であるself.cにパターンマッチして何のトークンを出力するかを決めていく。アルファベットに遭遇した場合はself._name関数を呼び出して複数の文字を消費するが、それ以外だと１文字につき１トークンなので楽だ。
ファイル終端に関してはちょっとPythonのダイナミックさやら文字列・文字の関係やらを少し悪用して、self.cに"EOF"という文字列をそのまま入れる形で扱っている。複数の文字からなる文字列はこのケース以外ではself.cに入らないので、この文字列に対してパターンマッチしても入力とかぶるリスクはない。
（ちなみに「Language Implementation Patternsに忠実」とは言っても、LIPではLexerをベースクラスにして継承したNameListLexerを作成しているのに対してここではそのまま一つのクラスとして実装しているので微妙な違いはある）
使ってみる：
>>> tokens = [] >>> lexer = Lex("[abc, def,[g,h,i],[]]") >>> while not tokens or tokens[-1] != Eof(): ... tokens.append(lexer.next_token()) ... >>> tokens [Lbrack(), Name(s='abc'), Comma(), Name(s='def'), Comma(), Lbrack(), Name(s='g'), Comma(), Name(s='h'), Comma(), Name(s='i'), Rbrack(), Comma(), Lbrack(), Rbrack(), Rbrack(), Eof()]
Lexer実装２ - Iterator Protocol
next_tokenのように一個ずつオブジェクトを返してくるストリーム的なものはIterator Protocolに従うように実装した方がよりPythonっぽい：
import string from liptoken import Eof, Comma, Lbrack, Rbrack, Name class Lex: def __init__(self, s): self.s = s self.p = 0 self.c = s[0] if s else 'EOF' self.done = False def __iter__(self): return self def __next__(self): while not self.done: match self.c: case c if c in string.whitespace: self._consume() continue case 'EOF': self.done = True return Eof() case ',': self._consume() return Comma() case '[': self._consume() return Lbrack() case ']': self._consume() return Rbrack() case c if _is_letter(c): return self._name() case c: raise ValueError(f"Invalid character {c}") raise StopIteration def _consume(self): self.p += 1 try: self.c = self.s[self.p] except IndexError: self.c = 'EOF' def _name(self): cs = [] while _is_letter(self.c): cs.append(self.c) self._consume() return Name(''.join(cs)) def _is_letter(c): return c in string.ascii_letters
実装１とほとんど変わっていないが、これでLexオブジェクトはIteratorになる。
あるオブジェクトがIteratorであるためには__iter__と__next__が定義されている必要がある。__iter__はオブジェクトその物を返し、__next__はストリームの次の要素を返すか、ストリーム終端を表すStopIteration例外を投げる。
まず__iter__は簡単：
__iter__(self):
return self
__next__はnext_tokenを微修正しただけ。self.doneフラグを追加、EOFのパターンでTrueにし、フラグがTrueだと大元のwhileループから出てStopIterationを投げる。
Iteratorにすることで、こんな使いかたができる：
>>> for token in Lex("[abc, def,[g,h,i],[]]"): ... print(token) ... Lbrack() Name(s='abc') Comma() Name(s='def') Comma() Lbrack() Name(s='g') Comma() Name(s='h') Comma() Name(s='i') Rbrack() Comma() Lbrack() Rbrack() Rbrack() Eof()
Lexer実装３ - Character Stackを使ったGenerator
Generator関数を使うとIterator Protocolを持ったクラスを定義するよりも手軽にIteratorオブジェクトを作成できる。
Lexクラスが保持している状態というのは単に文字列とその中での位置であり、さらにいうと一旦消費してしまった文字には戻る必要がない。なのでその状態を「文字のスタック」として表してしまえば、あとはクラスである必要はない。
というわけでgenerator関数としてのLexer実装：
import string from liptoken import Eof, Comma, Lbrack, Rbrack, Name def lex(s): char_stack = list(reversed(s)) while char_stack: match char_stack.pop(): case c if c in string.whitespace: continue case ',': yield Comma() case '[': yield Lbrack() case ']': yield Rbrack() case c if _is_letter(c): yield _name(c, char_stack) case c: raise ValueError(f"Invalid character {c}") yield Eof() def _name(c, char_stack): name_cs = [c] while char_stack and _is_letter(char_stack[-1]): name_cs.append(char_stack.pop()) return Name(''.join(name_cs)) def _is_letter(c): return c in string.ascii_letters
Pythonのリストは末尾からのpopがO(1)なので、入力文字列のすべての文字を逆順に入れたリストを「文字スタック」として扱い、self.consumeの代わりにchar_stack.popしていく。あとはnext_tokenがlexそのものになり、returnの代わりにyieldすることでgenerator関数としてトークンのストリームを返すようになる。
>>> for token in lex("[abc, def,[g,h,i],[]]"): ... print(token) ... Lbrack() Name(s='abc') Comma() Name(s='def') Comma() Lbrack() Name(s='g') Comma() Name(s='h') Comma() Name(s='i') Rbrack() Comma() Lbrack() Rbrack() Rbrack() Eof()
結論
あまり複雑な状態管理が必要ないLexer（やパーサ）ならPythonだったらgenerator関数でスッキリ書ける。
ただし実際に言語処理系の実装などでLexerを自前で書く場合はエラーメッセージの出力だとかで複雑化してクラスにする必要が出てきそうだ。
どちらにせよ、Lexerのような遅延ストリームはまさにIterator Protocolで表現されるべきものなので、クラスで書く場合なら__iter__と__next__を実装するようにしたい。
疑問点
Language Implementation PatternsではこのLexerのことをLL(1)だとかrecursive descentだとか書いてあるのだが、Lexerに文法があるわけでもないのでLL(1)なのか？という点と構文木のようなネストした構造を出力するわけでもないので再帰する必要ないのでは？という点がもやもやしている。
Pythonで参照渡し
最近こういうツイートを見た。
なんか参照渡しでツイッター検索すると、Pythonに参照渡しがあるという一大宗教があるらしい
— (call me #'knjname) (@knjname) August 22, 2021
誰が教祖だ？
実際「値渡し」「参照渡し」という用語はCやC++などの「変数が多くの場合１対１で特定のメモリ箇所と対応している言語」に関しては自然な概念だが、Pythonのように変数がメモリ箇所と対応しない（＝変数への再代入がメモリの書き換えではなく、指し示すメモリ箇所のすり替わりで行われる）言語だとあまりしっくりこない。
「Pythonでは参照渡しはできない」というのは「Pythonの関数は呼び出し元の変数の指すオブジェクトを入れ替えることはできない」という意味で言われる：
x = 1 some_func(x) print(x) // ここでx = 2になったりはしない
ただし引数として渡されるオブジェクトを操作して変化させた場合、その変化は関数呼び出し元からも観測できる：
x = [1] some_func(x) print(x) // ここでx = [2]になることはあり得る
この定義からすると「Pythonには参照渡しは存在しない」は概ね正しい。実用上はほぼ１００％正しいといっていい。
のだが・・・
なんとかならんかな？というのがこのネタ記事の主旨である。
結論から言うと、特定の条件下では可能だ。
以下のコードがその一例：
def add1(x): x.cell_contents = x.cell_contents + 1 def f(): x = 0 def g(): nonlocal x add1(g.__closure__[0]) print(x) // 1と出力される！
何をしているかというと、f関数内で定義されている変数xを関数gのclosureに（nonlocal xという文で）捕捉させることで変数をcell objectにしている。あとは直接g.__closure__[0]とそのcell objectにアクセスして関数add1を適用すれば、呼び出し元のf関数内での変数xが書き換わる。add1は引数としてcell objectを期待しているけどf関数の外部で定義されていても問題ない。
残念ながらこの方法はモジュールのトップレベルでは使えない。f関数の中で定義された変数x、のようにglobalではない変数のみがこのように関数のclosureに捕捉され得る。
モジュールのトップレベルの変数を関数内から書き換えたいならglobals()を使えばいい：
def modify_var(varname): globals()[varname] += 1 x = 0 modify_var('x') print(x) // 1と出力される
この二つの手法をうまく組み合わせて汎用的な参照渡し機構が作れないか試してみたが今のところうまくいっていない。残念なことである（？）
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_int 3
type t = A | B | Cと直和型でタグ以外の型を何も持たせていない。列挙型といってもいいかも（言語によっては列挙型の意味も違うようだが・・・）
-dlambdaでコンパイル：
(seq
(let
(*match*/89 =
(let (x/84 = 2a)
(switch* x/84
case int 0: (apply (field 43 (global Stdlib!)) 1)
case int 1: (apply (field 43 (global Stdlib!)) 2)
case int 2: (apply (field 43 (global Stdlib!)) 3))))
0a)
0a)
レコードの時と同じく、type t = ...の部分は完全にlambda IRでは消えている。
let x = C in ...が(let (x/84 = 2a) ...)になっているので、タグのみ直和型の場合は0a, 1a, 2aのような値にコンパイルされるようだ。
パターンマッチは(switch* ... case int 0: ... case int 1: ... case int 2: ...)のような形になっている。
直和型＆直積型
タグだけではなく、値も持った代数的データ型を定義・使ってみる：
type t = | A | B of int | C of string * bool let () = let x = A in let y = B 2 in let z = C("hi",true) in let f = function | A -> print_int 1 | B n -> print_int n | C(s,b) -> print_endline @@ if b then s else "hello" in f x; f y; f z;
-dlambdaでコンパイル：
(seq
(let
(*match*/95 =
(let
(x/84 = 0a
y/85 = [0: 2]
z/86 = [1: "hi" 1a]
f/87 =
(function param/92
(switch* param/92
case int 0: (apply (field 43 (global Stdlib!)) 1)
case tag 0:
(apply (field 43 (global Stdlib!)) (field 0 param/92))
case tag 1:
(apply (field 45 (global Stdlib!))
(if (field 1 param/92) (field 0 param/92) "hello")))))
(seq (apply f/87 x/84) (apply f/87 y/85) (apply f/87 z/86))))
0a)
0a)
タグのみのケースは先ほどと同じように0aに、そして値を持つタグは[0: ...]のような（タプルやリスト、レコードと同じ）ブロックにコンパイルされている。
値を持つタグが複数ある場合 [0: ...]、[1: ...]、[2: ...]とブロックの最初の部分であるn:で差別化している。（タプルのコンパイル結果を見たときからの「[0: ...]の0:部分はなんだ？」という疑問がここにきてようやく解ける）
パターンマッチは
- タグのみのケースは
case int 0: - 値つきのケースは
case tag 0:
のようにコンパイルされており、case tag n:が[n: ...]のブロックと対応するようになっている。
直積型とタグ付きタプル
直積型とタグ付きタプルは、定義の仕方も使い勝手も非常に似ている：
type t = A of int * string | B of (int * string) let () = let x = A(1,"hi") in let y = B(2,"ho") in let f = function | A(n,s) -> print_int n; print_endline s | B(n,s) -> print_int n; print_endline s in f x; f y
A of int * stringとB of (int * string)という違いだけで、あとはコンストラクタとしての使い方もパターンマッチもまったく同じ記法になっている。
-dlambdaでコンパイルしてみると：
(seq
(let
(*match*/95 =
(let
(x/83 = [0: 1 "hi"]
y/84 = [1: [0: 2 "ho"]]
f/85 =
(function param/91
(switch* param/91
case tag 0:
(seq (apply (field 43 (global Stdlib!)) (field 0 param/91))
(apply (field 45 (global Stdlib!)) (field 1 param/91)))
case tag 1:
(let (*match*/93 =a (field 0 param/91))
(seq
(apply (field 43 (global Stdlib!)) (field 0 *match*/93))
(apply (field 45 (global Stdlib!)) (field 1 *match*/93)))))))
(seq (apply f/85 x/83) (apply f/85 y/84))))
0a)
0a)
実装は違っていることがはっきりわかる。
A of int * stringは二つのフィールドのあるブロック、B of (int * string)はそれ自体がブロックである一つのフィールドを持つブロックになっており、パターンマッチに関してもデータの実装の違いが反映されている。
次回
次はミュータブルなrefがどのようにコンパイルされるのか見ていく。
OCamlのlambda IRをいじる（レコード）
レコード型を定義して使うコードがどのようにlambda IRにコンパイルされるかを見ていく。
定義して使う
簡単なレコード型を定義した上でa.xなどとアクセスして使ってみる：
type t = { x : int; y : string } let () = let a = {x=1; y="hello"} in print_endline @@ a.y ^ (string_of_int a.x)
-dlambdaでコンパイル：
(seq
(let
(*match*/87 =
(let (a/83 = [0: 1 "hello"])
(apply (field 45 (global Stdlib!))
(apply (field 27 (global Stdlib!)) (field 1 a/83)
(apply (field 32 (global Stdlib!)) (field 0 a/83))))))
0a)
0a)
lambda IRでは型は消去されているので、type t = ...の部分は完全に消えている。
その上でレコードはデータとしてはタプルとまったく同じ表現になっている。a.xなどのフィールドアクセスは(field 0 a/83)といったタプル要素のインデックスアクセスにコンパイルされる。
withでコピー
レコードのwith構文で、部分的変更を加えたコピーをしてみる：
type t = { x : int; y : string; z : bool } let () = let a = {x=1; y="hello"; z=true } in let b = {a with y="hi"} in print_endline @@ a.y ^ b.y
-dlambdaでコンパイル：
(seq
(let
(*match*/90 =
(let
(a/84 = [0: 1 "hello" 1a]
b/85 = (makeblock 0 (int,*,*) (field 0 a/84) "hi" (field 2 a/84)))
(apply (field 45 (global Stdlib!))
(apply (field 27 (global Stdlib!)) (field 1 a/84) (field 1 b/85)))))
0a)
0a)
let b = {a with y="hi"}が(makeblock 0 (int,*,*) (field 0 a/84) "hi" (field 2 a/84))になっている。
makeblockで[0: 1 "hello" 1a]のようなタプル的データ構造を作る。後者はlambda IRにおけるデータ構造リテラルなのだろう。要素がリテラルでない場合はmakeblockで作成する形にコンパイルされるようだ。
(makeblock 0 ...の0はデータのタグ（[0: ...]の0:部分）で、それに続く(int,*,*)は各要素の大まかな型でboxされない整数かポインタか、を差別化している。
それ以降は実際にデータ構造に含まれる要素の羅列。
タプルでmakeblock
確認のためリテラルではない要素が含まれるタプルがどうコンパイルされるか見てみる：
let () = let a = 1 in let x = (a, 2) in let y = (1+2, 4) in print_int (snd x + snd y)
-dlambdaでコンパイル：
(seq
(let
(*match*/84 =
(let
(a/80 =[int] 1
x/81 = (makeblock 0 (int,int) a/80 2)
y/82 = (makeblock 0 (int,int) (+ 1 2) 4))
(apply (field 43 (global Stdlib!))
(+ (field 1 x/81) (field 1 y/82)))))
0a)
0a)
タプルの場合も変数や非リテラル式が要素になっている場合、[0: ...]という形ではなくmakeblockにコンパイルされることが確認できる。
次回
次は代数的データ型とそれに対するパターンマッチのコンパイルについて。
OCamlのlambda IRをいじる（リスト）
リストとパターンマッチ、Listモジュール使用のコンパイルを見ていく。
簡単なパターンマッチ
簡単なリストを作り、リストのコンストラクタ２つに対しての素直なパターンマッチをする：
let () = let xs = [1;2] in match xs with | [] -> print_endline "hello" | n::_ -> print_int n
-dlambdaでコンパイル：
(seq
(let
(*match*/85 =
(let (xs/80 = [0: 1 [0: 2 0a]])
(if xs/80 (apply (field 43 (global Stdlib!)) (field 0 xs/80))
(apply (field 45 (global Stdlib!)) "hello"))))
0a)
0a)
OCamlの[1; 2]がlambda IRでは[0: 1 [0: 2 0a]]になっている。[]つまりnilは0aで表現され（ちなみにユニット型()やブール型のfalseも同じ表現にコンパイルされていた）、cons a bは[0: a b]つまり２要素のタプルと同じ形で表現されている。
パターンマッチに関しては、ただのifに変換されている。空リストとfalseがどちらも0aで表現されることを利用してなのか、リスト自体をifの条件にして、もしリストが真（つまり空リストじゃないなら）なら(field 0 xs/80)`とフィールドアクセスしている。
-drawlambdaでコンパイルすると：
(seq
(let
(*match*/85 =
(let (xs/80 = [0: 1 [0: 2 0a]])
(if xs/80
(let (*match*/82 =a (field 1 xs/80) n/81 =a (field 0 xs/80))
(apply (field 43 (global Stdlib!)) n/81))
(apply (field 45 (global Stdlib!)) "hello"))))
0a)
0a)
パターンマッチはやはりifに変換されているが、その後| n::_ -> ...の部分に対応する変数束縛が残っている。let () = ...と同じく、_への束縛は(let (*match*/xx =...) ...)という形に変換されるようだ。そしてタプルの記事の追記で@camloeba さんに教えていただいたと書いたとおり、-drawlambdaでコンパイルしたlambda IRに出てくるlet (... =a ...)がaliasとして-dlambdaでコンパイルされた形ではインライン化されている。
複雑なケースのあるパターンマッチ
パターンマッチのケースわけをもう少し複雑にしてみる。[x] -> ...と、リストに一つだけ要素が含まれている特殊ケースのパターンを追加：
let () = let xs = [1;2] in match xs with | [] -> print_endline "hello" | [n] -> print_int n | n::_ -> print_int (n + 1)
-dlambdaでコンパイル：
(seq
(let
(*match*/88 =
(let (xs/80 = [0: 1 [0: 2 0a]])
(if xs/80
(let (n/81 =a (field 0 xs/80))
(if (field 1 xs/80)
(apply (field 43 (global Stdlib!)) (+ n/81 1))
(apply (field 43 (global Stdlib!)) n/81)))
(apply (field 45 (global Stdlib!)) "hello"))))
0a)
0a)
ネストしたifになっている。
-drawlambdaでコンパイル：
(seq
(let
(*match*/88 =
(let (xs/80 = [0: 1 [0: 2 0a]])
(if xs/80
(let (n/81 =a (field 0 xs/80))
(catch
(let (*match*/83 =a (field 1 xs/80))
(if *match*/83 (exit 1)
(apply (field 43 (global Stdlib!)) n/81)))
with (1)
(let (n/82 =a n/81 *match*/84 =a (field 1 xs/80))
(apply (field 43 (global Stdlib!)) (+ n/82 1)))))
(apply (field 45 (global Stdlib!)) "hello"))))
0a)
0a)
分岐に例外を使っている！
[n] -> ...とn::_ -> ...の処理の分岐で、リストのcdr部分が0aでなければ(exit 1)で例外を投げて、(catch ... with (1) ...)の後者の処理に回るようになっている。
この例だと正直なぜこんなややこしいことをするのかわからない。(exit 1)のところにwith (1) ...の部分にある処理を書けばいいのでは？と思うが、より複雑なパターンマッチなどではこの方が書きやすいのかもしれない。さらにこういった例外処理を-drawlambdaから-dlambdaの間のステップでただのネストしたifにコンパイルしているのも面白い＆ぱっと見大変そう・・・
Listモジュール内の関数を使ってみる
最後にOCamlの標準ライブラリに含まれているListモジュールを使ったコードを見てみる：
let () = let xs = [1;2] in print_int @@ List.fold_left (+) 0 xs
-dlambdaでコンパイル：
(seq
(let
(*match*/145 =
(let (xs/80 = [0: 1 [0: 2 0a]])
(apply (field 43 (global Stdlib!))
(apply (field 22 (global Stdlib__list!))
(function prim/143 prim/142 stub (+ prim/143 prim/142)) 0 xs/80))))
0a)
0a)
List.fold_leftが(field 22 (global Stdlib__list!))に変換されているのは比較的わかりやすい。
(+)が(function prim/143 prim/142 stub (+ prim/143 prim/142))になっているのが面白いところで、(+)は標準ライブラリにあるわけではなくその場で関数が作成されるらしい。
この中に出てくるstubというのがどういう意味を持つのかいまいちわからない・・・
次回
次はレコードの定義と利用を見てみる。
OCamlのlambda IRをいじる（タプル）
タプルとそれに対するパターンマッチがどうlambda IRにコンパイルされるかを見ていく。
fst/snd
まずは非常に簡単なタプルと、その値をfst/sndでアクセスするコード：
let () = let x = (1,2) in print_int @@ (fst x) + (snd x)
-dlambdaでコンパイル：
(seq
(let
(*match*/82 =
(let (x/80 = [0: 1 2])
(apply (field 43 (global Stdlib!))
(+ (field 0 x/80) (field 1 x/80)))))
0a)
0a)
(1, 2)が[0: 1 2]になっているのがわかる。0:の意味はADTについて調べるときにわかるのでいったん置いておくとして、それ以降が格納されている値だ。そしてその最初の要素にアクセスするのに(field 0 x)、第二要素にアクセスするのに(field 1 x)などとしている（これはモジュールのフィールドをアクセスする方法としてすでに既出なことに注意）。
fstやsndが関数適用として現れてこないのが面白い。直接(field 0 x/80)のようにデータ構造に対するフィールドアクセスにコンパイルされている。
最適化なしだとどうなるか？-drawlambdaで試してみると：
(seq
(let
(*match*/82 =
(let (x/80 = [0: 1 2])
(dirapply (field 43 (global Stdlib!))
(+ (field 0 x/80) (field 1 x/80)))))
0a)
0a)
まったく変わらないlambda IRになる。
letによるパターンマッチ
fst/sndを使わず、let (a,b) = ...のような形でパターンマッチしてみる：
let () = let x = (1, 2) in let (a, b) = x in print_int @@ a + b
-dlambdaでコンパイル：
(seq
(let
(*match*/86 =
(let (x/80 = [0: 1 2])
(apply (field 43 (global Stdlib!))
(+ (field 0 x/80) (field 1 x/80)))))
0a)
0a)
さきほどとまったく同じlambda IRになっている。
-drawlambdaだと：
(seq
(let
(*match*/86 =
(let (x/80 = [0: 1 2] b/82 =a (field 1 x/80) a/81 =a (field 0 x/80))
(dirapply (field 43 (global Stdlib!)) (+ a/81 b/82))))
0a)
0a)
ちゃんとa/81とb/80という変数が出てくる。ちなみにlet (a, b) = ...なのだがletにコンパイルされると順序が入れ替わっているのも興味深い。OCamlの標準実装だとタプルの要素の評価順が右側からなので当然ではあるのだが。
またb/82 =a (field 1 x/80)などで=aという構文が出てくるのも面白い。なぜ=[int]ではダメなのかが不思議だが・・・
matchによるパターンマッチ
match構文でのパターンマッチ：
let () = let x = (1,2) in match x with (a,b) -> print_int @@ a + b
-dlambdaだと前述の例二つとまったく同一になる：
(seq
(let
(*match*/84 =
(let (x/80 = [0: 1 2])
(apply (field 43 (global Stdlib!))
(+ (field 0 x/80) (field 1 x/80)))))
0a)
0a)
面白いのは-drawlambdaだとletによるパターンマッチと同じ表現になること：
(seq
(let
(*match*/84 =
(let (x/80 = [0: 1 2] b/82 =a (field 1 x/80) a/81 =a (field 0 x/80))
(dirapply (field 43 (global Stdlib!)) (+ a/81 b/82))))
0a)
0a)
タプルだとパターンが一つしかありえないので同じ表現になる。
違う型が含まれるタプル
タプルに含まれる要素は型が違っていても問題ない：
let () = let x = (true, 1, "hello") in let (a,b,c) = x in if a then print_int b else print_endline c
-dlambdaでコンパイル：
(seq
(let
(*match*/89 =
(let (x/80 = [0: 1a 1 "hello"])
(if (field 0 x/80)
(apply (field 43 (global Stdlib!)) (field 1 x/80))
(apply (field 45 (global Stdlib!)) (field 2 x/80)))))
0a)
0a)
[0: 1a 1 "hello"]といろんな型の要素が問題なく[0: ...]というデータ構造の中に入ることがわかる。
次回
次はリストがどうコンパイルされるかをみてみる。
追記
=aに関して@camloeba さんから以下のとおりご教示いただいた。ありがとうございます！
=a は alias ですね。副作用起きないので変数使用を右辺定義に展開してもオッケーなやつです
— Jun Furuse 🐫🌴 (@camloeba) May 10, 2021
