今月の活動について (ミローネ言語, LR構文解析, 競プロ, HTTPS/TLS)
ミローネ言語
F# サブセットのコンパイラ
https://github.com/vain0x/milone-lang
興味深い変更点をいくつかピックアップする。
ML: 脱糖衣の AstToHir への統合
https://github.com/vain0x/milone-lang/commit/f8b98830854d9c1ca09401a4e9df6630671d2c33
脱糖衣 (x && y → if x then y else false など) を AST (抽象構文木) 上の変換で行うようになった。HIR (関数型中間言語) から糖衣構文を排除できる。
ML: 関数宣言と値の束縛のパーサによる識別
https://github.com/vain0x/milone-lang/commit/4a0df394d7ad1802505cfc05915f1b70585782dc
以下の2つを抽象構文的に区別できなかったので、パースの時点で区別するようになった。let 識別子 パターンの先頭 という並びが見えたら関数宣言 (let-fun)、そうでなければ値の束縛 (let-val)。
type A = | A of int
let A x = A 1 // 関数 A の定義
let (A x) = A 1 // バリアントの分解
ML: HIR (関数型中間表現) における2項演算の概念の見直し
https://github.com/vain0x/milone-lang/commit/075bb3383f1c670b334499b1e664a73094d0f86a
例えば x + y は ((+) x) y という関数適用に変換される。型推論が少し簡潔になる。コード生成はあまり変わらない。
ML: 字句解析の見直し
https://github.com/vain0x/milone-lang/commit/a140928d57d48bee85bdccb46009db61d8e6869a
字句解析は単一のパスでやるのが一般的だが、scan/recognize という2つのパスに分離していた。
scan は文字列の各範囲に字句の種類を割り当てるもの。例えば "\\"+str を文字列(4文字)、記号(1文字)、識別子(3文字)、といった列にする。
recognize はトークンの「意味」を解釈するもの。例えば "\\" というコードを解釈して \ という文字列を得る。
分けていた目的は関心の分離。しかし関心を分離するだけなら、使う関数を分けるだけでよく、パスまでは分けなくてもいい気がした。そのため、今回統合してみた。最大の目的は字句解析の改善自体ではなく、名前解決と型推論のステージを同様の手法で1つに統合したときにどうなるか見当をつけること。
結果として、2種類の関数 (scan 用と recognize 用) を繋ぎ合わせるための関数を羅列することになってめんどくさいが、悪くはなさそうだった。
ML: 構文解析のレイアウトルールの再検討
https://github.com/vain0x/milone-lang/commit/62f1bb8fd21d7296910c046c9e50ef2aa22b7a70
レイアウトルール (字下げに関する構文のルール) を場当たり的に処理していたので、再検討してみたら、 意外と綺麗にルール化できた (追記: わりと微妙だったので修正予定)。
簡単にいうと、文 (if/let/etc.) に関して次の2つの規則がある。
- 文の生成規則の右辺の、終端記号と最後の非終端記号は、文の最初の字句と同じかそれ以上の深さになければいけない
- 文の生成規則の右辺の、最後にない非終端記号は、文の最初の字句より1文字以上深くなければいけない
if // 文の最初の字句
cond // 最後にない非終端記号なので1文字以上深く字下げ
then // 終端記号なので if と同じかそれ以上に深く字下げ
body // cond と同様
else // then と同様
alt // 最後の非終端記号なので if と同じかそれ以上に深く字下げ
それから、文の並びはすべて同じ深さに字下げされなければいけないことと、else-if は特別扱いであること。
- 式は、前述のルールから文の最初の字句と同じかより深く字下げされないといけないが、それ以外のルールは特にない
- F# はこの字下げが足りなくても警告を出すだけでコンパイルは通してくれたりする
- F# には演算子が浅くてもよいルールがあるが、これはミローネ言語には実装していない
let isSpace (c: char) =
c = ' ' // この c の位置で文が開始する
|| c = '\t' // `||` は文の開始より浅く字下げされているが、F# ならOK
ML: 破棄パターンと変数パターンの分離
https://github.com/vain0x/milone-lang/commit/0258cf24f01c98f3c4ddc4c8e9df9d4d57904916
破棄パターン (_) と変数パターンを同様のものとして処理していたが、問題が起こったので分離した。コードが共通化できなくて冗長になると思っていたが、意外と共通化できている部分は少なくて、実はもとからくっつけておく必要がないことに気づいた。
ML: 型定義の順番の不具合
https://github.com/vain0x/milone-lang/commit/fa9a1d935b30404c5ace74c472acf8928f95afa1
C言語では後方に定義される型は不完全型として扱われ、使用に制限を受ける。
例えば struct Foo* p; と書くだけなら struct Foo は不完全型でもいいが、struct Foo foo; とするには完全型でなければいけない。
そのため、型定義を生成する順番に注意する必要がある。型定義の順番のせいでコンパイルできないCコードを吐いてしまうバグはすでに何度も出ていて、とりあえずは場当たり的に対処している。
いままでは最初に型が参照された時点で定義を生成していたが、今回それでは無理なケースが見つかったので、「完全型が最初に要求されたとき」に定義を生成するようになった。
C言語において完全型が要求される文脈について注意して生成しなければならず、そのへんでまた別のバグが出そうで心配。Cの抽象構文木を作る前に別の中間言語を用意して、完全型が要求されるタイミングを検査した方がいいかもしれない。
ML: option 型
https://github.com/vain0x/milone-lang/commit/5f77ebee9bb6eeaecbc2499ae8eb2747007c2dc8
option 型を実装した。といっても、単にリストに読み替えるだけのハリボテ。リストの尾部が無駄になるが、とりあえず動けばいい。
左を右に適当なタイミングで読み替える。
| option | list |
|---|---|
| T option | T list |
| None | [] |
| Some x | [x] |
ML: \xHH 形式のエスケープ
https://github.com/vain0x/milone-lang/commit/b1744ae4e717f965b23fa6458ad3834453fddfda
参考: Strings - F# | Microsoft Docs
いままで知らなかったが、F# は \xHH で1バイトの文字を表現できる。F# の文字列は UTF-16 だが、ミローネ言語の文字列は UTF-8 (予定) なので、こっちの方が都合がよい。
ML: Map 型
https://github.com/vain0x/milone-lang/commit/b5441c62fd67560c22ac191bcc9cf304205ebeb3 https://github.com/vain0x/milone-lang/commit/98298ed0553b81b7d4d7327d2d8d01d1fd5bd9aa
Map (イミュータブルな平衡二分探索木による連想配列) を実装するには多相な判別共用体を用意しないといけないが、時間がかかるのでセルフホストの段階ではやらないことにした。代わりに、
Map<K, V>と書かれている部分を自動で(K * V) list * (K -> K -> int)(連想リストと比較関数のペアの型) に読み替える- Map 操作関数を F# 版とミローネ言語版で差し替える
という方針にしようと思ったが、微妙なつらみがあったのでやめた。
おそらく Assoc<K, V> という別の方を定義しつつ、ミローネ言語ではこれを特別扱いする、という方針になりそう。(予定)
ML: レコード型生成ツール
https://github.com/vain0x/milone-lang/commit/7aa0f37490e846bf96de56210f291ece915f84ea
レコード型の実装は、不可能ではないが時間がかかりそうなので、セルフホストの段階ではやらないことにした。
技術的にはレコード型はすべてタプルで代替できるが、レコードの操作のたびにタプルをパターンマッチで分解・再構築するのはかなりつらい。そのため、getter/setter 関数を生成するツールを用意した。
例えば以下のようにレコードの型定義を YAML で書いておくと、
ExampleCtx:
Serial: Serial
Vars: Map<VarSerial, VarDef>
Tys: Map<TySerial, TyDef>
以下のようなコードが生成される。fooGetBar はレコード foo からフィールド Bar を取る関数、fooWithBar はレコード foo のフィールド Bar を非破壊更新する関数。
type ExampleCtx =
(
Serial
* Map<VarSerial, VarDef>
* Map<TySerial, TyDef>
)
let exampleCtxGetSerial ((serial, _, _): ExampleCtx) =
serial
let exampleCtxGetVars ((_, vars, _): ExampleCtx) =
vars
let exampleCtxGetTys ((_, _, tys): ExampleCtx) =
tys
let exampleCtxWithSerial serial ((_, vars, tys): ExampleCtx): ExampleCtx =
serial, vars, tys
let exampleCtxWithVars vars ((serial, _, tys): ExampleCtx): ExampleCtx =
serial, vars, tys
let exampleCtxWithTys tys ((serial, vars, _): ExampleCtx): ExampleCtx =
serial, vars, tys
ツール自体もミローネ言語で書いたつもりだったが、標準入力を読む API が不足していて動かせなかった。後で追加する予定。
ML: パターンマッチの網羅性検査
まだミローネ言語には取り込んでいないが、パターンマッチの網羅性検査の基礎をミローネ言語で書いてみた。Space という概念を使うとシンプルに書ける。
参考:
- A generic algorithm for checking exhaustivity of pattern matching
- Swiftコンパイラで採用されているパターンマッチの網羅性チェックの理論と実装
ML: セルフホストの進捗状況
パーサを F# とミローネ言語でそれぞれコンパイルして、パーサ自身を構文解析した結果 (のダンプ) が一致することを確認した。
https://github.com/vain0x/milone-lang/commit/bb885f876bfad563e91f28ba103fffec689b49b2
LR 構文解析
実践コンパイラ構成法 を参考にLR構文解析の勉強をした。忘れないようにメモ。
よくある再帰下降構文解析はLL文法の構文解析に相当する。parseFoo 関数を呼ぶことは、非終端記号 foo の生成規則を使うことに対応する。先読みによってどの生成規則を使うかを選んで決める、というのがLL文法の基本的な動き。
一方でLR構文解析は、いずれかの生成規則の解析が完了したタイミングで、どの生成規則を使うか選ぶ。
トークンを1つずつ読みながら、各時点で「自分が各生成規則において、どのあたりを解析しているか」を把握しておく。いずれかの生成規則を読み終わったら、その生成規則を読み始める前の時点に遡って、その生成規則を使ってパースを進めたことにする。
ただしパーサが実行中に各生成規則のどのあたりを解析しているかを判断するのは時間がかかるので、何らかのデータ構造を用意して高速化した方がよい。そのため、LR項や状態集合といった概念が出てくる。そのあたりはいったん無視して、簡単な言語で概念上の動きを追ってみよう。
字句:
IDENT AND
生成規則:
atom → IDENT
term → atom
term → term AND atom
この文法で入力 p AND q をパースしてみる。前からトークンを読むので、はじめに p (IDENT) を読む。規則 atom → IDENT を 読み終わった ので、代わりに atom を読んだことにする。(・ が現在地点)
atom ・ AND q
同様に、いま規則 term → atom を読み終わった状態なので、atom ではなく term を読んだことにする。
term ・ AND q
次に AND を読むが、この時点で読み終わった規則はない。次に q (IDENT) を読み、先ほどと同様に atom を読んだことにする。
term AND atom ・
このとき規則 term → atom と term → term AND atom のどちらかを読み終わった状態になる。ここで、term → atom を読んだと仮定して AND を読んだ状態に遡ってみると、次の記号 が term になるような規則が存在せず行き詰まる。したがって、ここでは term → term AND atom を読み終わったとしか考えられない。
(複数の規則が存在する時は 衝突 している。トークン数が多い方を選ぶとかの何らかのヒューリスティックを使って処理するか、単にエラーにする。)
というわけで最初の状態に遡って term → term AND atom のパースを進めたとみなす。
term ・
こうして受理された。
LR: LR項と状態
生成規則とパース中の位置のペアが重要なので、これをLR(0)項と呼ぶ。例えば term → term AND atom の AND を読み終わった状態は、目印のドットをつけて以下のように表す。
term → term AND ・ atom
先述の例にある通り、この状態に遡ってきたとき、次にどの記号を読めるか分かっていると嬉しい。そこで、次に読める記号を列挙するため、atom を生成する可能性がある規則のLR項もまとめて1個の状態としておく。
term → term AND ・ atom
atom → ・ IDENT
この状態で次に atom を読んだとする。つまり、いくつかのトークンを読んだ後に atom → IDENT を使うという決定をしてこの状態に遡ってきたとする。考えられる次の状態は以下である。(読んだのは atom であって IDENT ではないので、次の状態に atom → IDENT ・ は含まれない。)
term → term AND atom ・
この状態には「term → atom ・」は含まれていないので、先述の例のように term → atom を読み終わった状態と誤認せずに済む。
実用的には1トークンの先読み (生成規則を選ぶときに次のトークンを判断材料に使う) と、先読みによって分離された状態の併合 (状態数を減らすために先読みだけが異なる状態を1つにまとめる) もしないといけない。詳しくは本を参照。
LR項: パーサコンビネータの改善
再帰下降パーサを手書きしたり、パーサコンビネータを使ったりするとき、左括りだしと左再帰除去をやらないといけない。これらの操作によって変形された文法はたいてい読みづらい。
そのため、LR構文解析に基づく左再帰除去の不要なパーサコンビネータとか、自動で左再帰除去をやるパーサコンビネータを作りたい。(時期は未定)
競プロ
週末に AtCoder に参加。
- 競プロ参戦記 #62 League | ABC 139
- D完
- 競プロ参戦記 #63 Second Sum | ABC 140
- E完
- 競プロ参戦記 #64 Xor Sum 3 | ABC 141
- E完 + F練習
- 競プロ参戦記 #65 Pure | ABC 142
- E完 + F練習
ミローネ言語の動作検証をかねて競プロをやろうとしていた。そのために F# で試し書きしていたら、無限に TLE して困っていた。F# で競プロする人は (|>) に注意:
ミローネ言語は配列がないのでランダムアクセスを要求されるとつらい。純粋関数型データ構造 に載っている 2進ランダムアクセスリスト というイミュータブルな配列のデータ構造を使うとよさそう。これを使って ABC 140 の E 問題を解いた:
https://atcoder.jp/contests/abc140/submissions/7632026
ミローネ言語では多相な判別共用体を使えないので、そのあたりを手動で単相化すればミローネ言語に移植できるはず。(まだやってない。GC なしでメモリが足りるかは不明。)
ウェブアプリ
ウェブアプリの HTTPS 対応とかメールサーバの TLS 対応などをやった。忘れてもいいようにメモ。
メールの TLS は自己署名証明書でも問題なさそうだが、ウェブアプリの証明書は Let’s Encrypt を使うべき。
Let’s Encrypt から証明書を取ってくる certbot というアプリがあって、以下のページのインストラクションを読んでポチポチするといける。
Docker を使う場合は https-portal が便利。すべて自動でやってくれる。
Let’s Encrypt の証明書の再生成は週に5回まで。証明書をボリュームか何かに保存する設定は必須。
# docker-compose.yml
volumes:
# 証明書等を入れておくボリューム
certs:
services:
https-portal:
environment:
# 略
STAGE: production
volumes:
# 証明書等が入るディレクトリをボリュームにマウント
- "certs:/var/lib/https-portal/example.com/production"
メールサーバは postfix を使うことにした。
TLS 対応なしだと Gmail にはブロックされて、迷惑メールフォルダにすら入れてもらえない。DNS に SPF や DKIM の設定をした方が迷惑メール扱いされづらくて良いらしいが、まだやってない。
Docker を使う場合は以下のイメージがよさそう。
# docker-compose.yml
services:
postfix:
# 略
volumes:
# https-portal を先に起動しておくと証明書 (*.crt) と鍵 (*.key) が入っているはず
- "certs:/etc/postfix/certs"
初回起動時に証明書がないと TLS が有効化しないので注意。証明書を取得した後に起動するようにしよう。
# 初回起動時のみ証明書の取得を待つ
docker-compose up -d https-portal
docker-compose logs -f
# 待つ
docker-compose up -d