Swiftでコンパイラを書こう #Swift

この記事はIS17er Advent Calendar 2017 - AdventarとSwift Advent Calendar 2017 - Qiitaの21日目の記事です。

タイトルの通り、Swiftでコンパイラを書いてみようとして気付いた点などをまとめていきたいと思います。

全体の構成としては

東京大学理学部情報科学科の名物授業でもあるCPU実験で使われているmin-camlという言語のコンパイラをSwiftで実装しようとして気付いた、コンパイラレベルでの関数型と手続き型の違い
Swiftでコンパイラを実装しようとした時に考えられる工夫点
minSwift on Swiftで見るSwiftでのコンパイラ実装
実際のSwiftコンパイラの周辺事情

という感じです。予め断っておきますが、最初のmin-caml on Swiftの試みは途中で挫折してしまったため、どちらかと言うとその挫折経験から学んだことという方向性の記事になっています。リポジトリのリンクも貼っておくので、もしこうすればいいのではないか？というアイデアのある人がいれば気軽にプルリクしていただければと思います。

touyou/MinCamlSwift

はじめに

なぜこのような記事を書こうと思ったかと言うと、ひとつは単純に現在自分がCPU実験でコンパイラ係をしていること、それに加えてたまたま以下のようなリポジトリを見つけたのがきっかけです。

ahoppen/introduction-to-compilers

このリポジトリは最小限実装のSwiftコンパイラをSwiftで書き、それに基いてコードを実際に書いてもらいながらコンパイラについての理解を深めてもらおうといったPlaygroundになっています。これに関して詳しいことは後で書きますが、基本方針としてこの中に含まれているminSwift on Swiftのコードを改変するという形でmin-caml on Swiftの実装をしようと思いました。

ちなみにmin-camlはOCamlのサブセットで、速攻MinCamlコンパイラ概説に概要などが書かれているので詳しくはそちらを見てください。

min-caml on Swiftを書こうとして気づいたこと

結論から言ってしまうと、min-caml on Swiftで気づいたのは手続き型言語と関数型言語のコンパイラ的側面の違いです。もちろん２つは全く異なるもので、当たり前のことを言っているようにも見えますが、より深くそれを実感できました。

手続き型言語でコンパイラを書くということと関数型言語でコンパイラを書くということ

主にこれを思ったきっかけとして２点あって、まずひとつは純粋にコンパイラを書くということに対して手続き型言語のほうが書きやすいなと感じたということです。
細かい点はまた後ほど書けたら書こうと思いますが、コンパイラの処理は大きく分けて字句解析、構文解析、意味解析、解析部、最適化、コード生成といった段階があります。意味解析以前の一般にフロントエンドと呼ばれている部分の処理に関して手続き型と関数型の間にこれといった差はない（そもそもここらへんは後で少し説明するyaccやlexと呼ばれる専用ツールを各言語版に改造したものを使うことが多いのでどちらで書いても大体同じようなコードになります。）のですが、解析部や最適化の部分で使われる手法には変数の名前を区別するために使うもろもろの処理や、処理の依存関係などをあらわすための有向グラフを構築するような時にどうしても副作用のある処理が必要になってきます。大抵の関数型言語にはこの機能がプリミティブにしろライブラリにしろ備えられているので特に問題はないのですが、「副作用は絶対排除したい」みたいな気持ちを持ってる人が書く場合ここがかなりの障害になるのではないのかなと思います。
と言ってもこれは手続き型言語がコンパイラでは好まれて使われるということを言っているのではなく、パターンマッチングなどがある分関数型のほうがすっきり書ける、あるいは学術的な側面から言えば扱いやすいなどの点もあって（たぶん？）、授業ではOCamlが採用されていたりするわけです。また一部の処理では関数型のほうが書きやすいということもあるらしいです。
その意味では手続き型言語に関数型的な機能を実装している最近のモダンな言語たちはいいかもしれませんね。そう、Swiftとか笑

コンパイラを書こうとしたからこそ気付いた違い

さて、そろそろ２点目にうつりたいと思います。２点目は関数型言語は本当に全てが「式」なんだなと実感できる、ということです。ざっくりしてますが、これはAST(抽象構文木)を実装していて感じました。

元にしていたコードでのAST.swiftではざっくりと以下のような構造をしています。

AST.swift(抜粋・minSwift)

/// ASTにおけるNode
class ASTNode {}

/// ASTは木構造なのでルートになる部分が必要
class ASTRoot: ASTNode {
    let statements: [Statement]
}

/// ifやメソッドなどトップレベルにくる「文」
class Statement: ASTNode {}

/// 「文」の中に書かれる「式」
class Expression: Statement {}

つまり制御構文やメソッドと実際の処理となる「式」との間に明確な親子関係ができるのです。こうすることによってコンパイラ的にはグラフを構築する時にこの「文」をブロックにして云々みたいな判断がしやすくなります。

一方今回min-camlのために書いたAST.swiftは次のようになります。

AST.swift(抜粋・min-caml)

/// ASTにおけるNode
class ASTNode {}

/// ASTは木構造なのでルートになる部分が必要
class ASTRoot: ASTNode {
    let expressions: [Expression]
}

/// 全ては「式」
class Expression: ASTNode {}

Statementが抜けてExpressionのみがベースクラスとなりました。つまりある意味で全ての構文が対等な関係になります。今回はこのように書いてますが、OCamlのtypeとSwiftのenumは機能的にほぼ対等なものなのでenum一個で表すこともできます。例えばこんな風に。

EnumAST.swift

enum AST {
    case unit
    case bool(Bool)
    case int(Int)
    indirect case not(AST)
    indirect case add(AST, AST)
}

再帰的な列挙型、できるやろと決めてかかって書いてたのですがやっぱりありましたね。見慣れない修飾子ですがindirectというものを使うとできるみたいです。列挙型の話や、再帰的列挙型については以下の記事を見るといいかもしれません。

ちょっと脇道にそれましたが話を戻すと、この「文と式という親子関係があること」と「式しかなく全てが対等」ということはこのように実装レベルで差が出て来る上、構文解析の難易度をかなり大きく変えてくるように感じました。（この部分で今挫折中です笑）

例えばif文を考えてみましょう。手続き型の場合if文の条件式は「式」であることが必須条件になるためifの後は必ず式として変換できるはずです。つまり「文」となるif文やメソッドなどは入ってこないと保証されるため{が来るまでを「式」として変換すれば問題ありません。
一方全てが「式」であるということは条件式に入るものは構文レベルならなんでもいいということになります。if文ならまだどこで条件式で終わるかの指標があるのでまだいいのですが、これによって二項演算子などの構文解析アルゴリズムなどが少し複雑になる可能性があります。
ここらへんの事情もあってうまく自分でyaccのLALR向けにつくられたBNFをうまくSwiftのほうに落とし込むことが出来ず挫折してしまいました。

Swiftでコンパイラを書くには

これで「Swiftで関数型言語コンパイラをつくるのは厳しかったです。」というのはさすがにもったいないので次にここから得られた知見を元にどのような工夫をすることが考えられるかということについて考えていきたいと思います。

まず一つ目は先程も書きましたが列挙型でASTを書くということです。Swiftのenumは結構Haskellに影響を受けているというのをどこかで見た気がするのですが、その通り関数型言語との親和性が高いものとなっているので特に関数型言語のコンパイラを書くにあたってかなり書きやすいのではないでしょうか。
また別に関数型言語でないとしてもネストさせればうまく実装できそうですし、そうすることによってパターンマッチングがかなり楽になるという利点もありますしかなりよさそうです。

変数名を区別していくにはシングルトンなどを使うとすっきり書けて良さそうですね。コレに関しては完全にデザインパターンという感じなので好みという感じですが、コンパイラ全体を通してカウンタを保持しておきたいというのが最適化に際してあったりするのでシングルトンで変数名管理を行う、コンパイラクラスをつくっておいてそいつにstaticでカウンタを持たせておくなどの実装は考えられそうですね。

あとこれができたらスムーズそうだなぁというのがあって、こんなつぶやきをしていました。

yaccのソース、オープンソースって言われてるけどもしそうなら自分でSwiftでParserを書くよりもswiftyaccを生み出すほうが簡単な気がしてきた（ほんまか？）
— とうよう (@touyoubuntu) 2017年12月2日

うまくyaccのソース自体を見つけられていないので手を付けられていないのですが、もしこの方針に興味ある人いたらコメントなどいただければ取り掛かりたいなという気持ちでいたりいなかったりします笑

「Introduction to Compilers」の紹介

ここまでボヤッとした内容になってしまった代わりと言ってはなんですが、ここから最後に普通のSwiftユーザーに向けて（Swiftユーザーってなんて呼べばいいんでしょ？Swifter？）ahoppen/introduction-to-compilersの内容をそれっぽくまとめていきたいと思います。英語ですが実際にどう動くかなどPlaygroudの機能をうまく活用して解説してくれてるので、この記事でざっくり概要を掴んだ後はぜひPlaygroud自体にも取り組んで欲しいなと思います。（ところでPlaygroundのタイトルのせいで「馬から落馬」状態になってますがそこはご愛嬌ということで笑）

本家は7つのページ（本編6ページ、解答ページ1ページ）からできているのでこの順に書いていこうと思います。

1. Introduction

Introductionでは「コンパイラ」とはなんなのかをざっくり紹介しています。
ここでもざっくり紹介したいのですが、その大前提として一般的なプログラミング言語それ自体をコンピュータが理解することはできないということは認識しておいて欲しいなと思います。もうちょっと知ってる人であれば「アセンブリ言語を書けばコンピュータもわかるようになるんでしょ」と思っている人もいるかもしれませんがこれも正確ではありません。
コンピュータが理解できるのはあくまで0と1の羅列からなる機械語のみであり、これと人間が普段扱う高級言語と呼ばれるプログラミング言語の中間に位置するのがアセンブリ言語です。

そしてプログラミング言語からアセンブリ言語に翻訳する役割を担うのがコンパイラ(Compiler)です。英語として訳すと翻訳者なのでまさにそのまんまなネーミングですね。ちなみにアセンブリ言語を機械語に翻訳するほうはアセンブラと呼ばれているので興味があれば調べてみてください。

以降の部分ではこのコンパイラがどのようにしてプログラミング言語を翻訳していくのか、というところが紹介されています。

2. Lexer

コンパイラの第一段階はLexerというものになります。これは最初のセクションでさらっと言及した字句解析のことです。
プログラムそれ自体ではただの文字列ですよね。コンパイラもひとつのプログラムなのでいつも書いているプログラムを文字列のまま意味を取っていくことを考えてもらえばかなりつらいなぁという印象を持ってもらえると思います。

そこでコンパイラはまずこの字句解析の段階で、文字列をプログラムの解釈する最小単位に区切り何らかの変換をします。例えばPlaygroudについているものだと列挙型で表されたものになります。
最小単位とは予約語になっているifやfunc、それ自体でなんらかの意味をなす記号たち、その他変数名や関数名になりそうな単語です。これはよくトークンと呼ばれます。この時点で空白や改行もすべて取り除かれ、純粋にトークンの羅列に変換されます。
これを処理する有名なフレームワーク（？）としてlexというものがあります。

3. Parser

さて先程の段階で少しプログラムが扱いやすくなりました。（少なくとも毎回毎回これはどこまでで区切れるのかなどを一文字ずつ調べる必要はなくなりました）ですが今のままだとトークンの羅列でしかなくて、プログラムがどういう構造になっているのかはわかりません。
そのため次にParserと呼ばれる段階でこの構造を明らかにしていきます。これは先程散々苦しめられていた構文解析という段階です。

この構文解析を完璧に行うには言語モデルに対しての知識がないとかなり厳しいのですが、Playgroundではその中でも簡単な例に対して実際に手を動かして実装してみることができます。是非取り組んでみてイメージだけでも掴んでくれたらなと思います。（具体的な解説はそれをするほど自分も詳しいわけではないですしかなり長くなりそうなので割愛します）
ちなみにこのParserをBNF記法と呼ばれる言語処理系の記法に近い書き方で書けるようにしたツールがyaccです。いくつかの言語のものがあり、lexとyaccは組み合わせて使われることが多いです。

4. IR Generation

構文解析までできるとコンパイラはもうかなりプログラムのことを把握出来ていることになります。この後の段階としてmin-camlだと最適化に進むのですがPlaygroundではまずIR Generationを行います。IRとはIntermediate Representationの略でつまり中間表現の生成です。

Xcodeでクラッシュしたときに時々出てくる難しそうなファイルというか文字列というかがありますよね？あれはアセンブリ言語のように見えますが正確にはこの中間表現の一種になっています。【要出典】（間違ってたらマサカリ下さい。でも多分x86のアセンブリとはまた違う表記になっているような気がするのでそうだと思います。というかどっかでそんな記事を見た気がする…）

中間表現は端的に言ってしまえばプログラミング言語とアセンブリ言語のさらに中間となる表現です。さっきさらっと書いた通り、最適化という段階にはプログラミング言語に対してかけられるものもあるのですが、例えば変数に対してレジスターをどう割り当てるかとか、この計算は先に計算できるよねみたいな最適化はアセンブリに近いほうがかけやすかったりします。ですが完全なアセンブリにするとそれはそれで扱いにくいので、その中間を担うものとして中間表現というものがあるわけです。
本格的なコンパイラになってくるとこの中間表現が何個も使われていたりします。

5. Optimisation

ここがコンパイラの腕の見せどころでもある最適化、Optimisationです。（余談ですがこのスペルはイギリス英語みたいです。もちろんoptimizationでも可で、編集途中赤線が出てきてる当たりmacOSのスペルチェックはアメリカ英語なんだなぁというどうでもよい知見が得られました）

この最適化という段階はなくても成り立つのですが、プログラミング言語の性能を決めるかなり重要な要素になっています。手前味噌ですがSwiftで競技プログラミングを実際にやってみたところ予想以上につまづいた話 - Qiitaで正しいアルゴリズムなのに時間切れになってしまったのは某社がSwiftの最適化をかけてくれていないからでした。（とコメントでご指摘いただきました）

Playgroundでは7つの最適化をかけています。その中身までは解説されていないので少しここで紹介したいと思います。少しアセンブリなどへの知識が無いとわからない用語も使ってしまっていますがそこらへんは調べていただけると助かります。

Constant Expression Evaluation（定数評価）… 「1と2を足してレジスタの1番に入れる」と言った実行する前に計算できてしまう部分を先に計算してしまう。演算回数が純粋に減る。
Constant Propagation（定数伝播）…　「レジスタの1番に1を入れた直後にレジスタの1番を使って計算」というようにレジスタの中身がわかりきっている時にレジスタの部分を中身に置き換えておく。定数評価の効果を上げることができる。
Dead Store Elimination（デッドストア削除）… 使われないレジスタへ値を入れるコードを削除する。最終的なアセンブリのサイズが減る。レジスタが節約できる。
Dead Code Elimination（デッドコード削除）…　条件分岐やreturnなどによって確実に実行されないことになっているコードを削除する。最終的なアセンブリのサイズが減る。
Empty Block Elimination（空白ブロック削除）… どこかにジャンプするだけといった無くても変わらない部分を省略する。最終的なアセンブリのサイズが減り、無駄なジャンプも減る。
Inline Jump Targets（インラインジャンプ展開）… ジャンプ先の内容でジャンプ命令を置き換える。多分他の最適化がかかりやすくなる。
Dead Block Elimination（デッドブロック削除）… 実行されないブロックを削除する。最終的なアセンブリのサイズが減る。

効果も一応書いておきました。それでなにが嬉しいの？というものもあるかと思いますが、実際に速度などを測定してみるとここらへんのものがあるとないとではかなり大きな差となってきます。

6. Finish

最後にまとめとしてこれまでにやってきたことが紹介されています。こちらでは言及しませんでしたがParserの後の段階にある型チェックについても概要が述べられています。

以上がIntroduction to Compilersの概要です。こちらでかなり補足も入れているので、本当にコンパイラを書こうという人にとっては物足りない感があるかとは思いますが、普段使っているXcodeがどのようにして動いているかを知るにはかなりいい教材なんじゃないかなと思います。
そんなわけでこのPlayground、勝手ながら翻訳版を製作途中だったりします。マサカリでもプルリクでも歓迎していますのでぜひよろしくお願いします。

touyou/introduction-to-compilers at japanese

Swiftのコンパイラはどうなっているの？

ここまで色々書かれると、じゃあSwift自体のコンパイラはどうなってるねん？って疑問に思いますよね？（ほんまか？）

ですので書きたいなーと思ったのですが、さすがにこの後に書くには重たすぎるのでしっかり解説してくれている記事などのリンクだけ紹介して締めくくりたいなと思います。

swift/lib at master · apple/swift … Swiftのコードのうちコンパイラに該当する部分です。C++で記述されています。
Swiftコンパイラの構造と基盤テクニック - Qiita ... Swiftがどのようなアルゴリズムを採用し、どのように処理しているのかが解説されています。
Swift コンパイラのアーキテクチャ - Qiita ... Swiftコンパイラのどのファイルでどのようなことをしているのかが解説されています。

ここらへんになってくると本当に理解がないと難しいので先にもっと小さなコンパイラをつくってみる系の本に取り組んで見ることをおすすめしますが興味があれば一読しておいて損はないんじゃないかなという印象を受けました。

まとめ

以上、Swiftで簡単なコンパイラを書いてみるという挑戦から始まって「Swiftでコンパイラを書く」ことに対しての工夫や基礎などをざっと紹介してみました。

まだまだ自分自身コンパイラに対しての理解が深くないので、至らない点・間違っている点もあるかとは思いますが、少しでもコンパイラってこういうものなのかという理解の一助になれば幸いです。

今回この記事を書いてみて、コンパイラを学んでいる一学生としていつか自作言語や、コンパイラレベルでのSwiftコントリビューターになれたらいいなと思いました。ですがまずはまだCPU実験のほうが終わってないのでそちらを頑張りたいと思います笑

IS17erのアドベントカレンダーの明日の記事は同じ班員でもあるJoeくんの就活についての話、Swiftアドベントカレンダーの明日の記事も楽しみですね。
アドベントカレンダーも終盤に入ってきて少しQiitaのランキングも気になったり気にならなかったり、、、とにかく楽しんでいきましょう！！では👍

p.s. Swiftで実際に書かれているコンパイラ（見つけたら随時追記）

trill-lang/trill: A type safe, compiled language inspired by (and written in) Swift

Swiftでコンパイラを書こう