近況 2020-07-31

今月の活動 (ジャッコ言語など) や、気になった記事の感想など

前回 (2020-06-30) https://vain0x.github.io/blog/2020-06-30/diary/

ジャッコ言語

vain0x/jacco-lang

ジャッコ言語の処理系の実装を進めた。

数値の型の種類を増やしたり、enum をタグ付きユニオンにコンパイルできるようにした。あまり興味深い機能はないので、そのあたりは略。

処理系内部の設計の変更が多かった。

言語処理系の使い道

言語処理系の使い道 (ユースケース) は複数ある。

バッチコンパイル: ソースコードをパースして抽象構文木を組み立て、名前解決や型検査などを行ってコードを生成するコマンド
- いわゆる普通のコンパイラの仕事
リント/フォーマット/フィックス: ソースコードを検査して問題を検出したり、それを自動で修復する変更を提案・実行したりするコマンド
- cargo fmt や cargo fix など
IDE バックエンド: ソースコードをバックグラウンドで解析しながら、その構文や意味に関するクエリに応答するサービス
- LSP サーバなど
- データベースサーバの一種だと考えられる

単一の実装を複数の使い道に適切なものにする、あるいは可能なかぎり流用可能にする方法を模索したい。

A Few More Reasons Rust Compiles Slowly

単一ファイルに閉じた操作・閉じていない操作

1つのソースコードの内部だけ見て、他のソースコードを一切参照することなく進めることができる操作を、単一ファイルに閉じた操作 と呼ぶことにする。

例えば Rust の構文解析は単一ファイルに閉じた操作。他のファイルにかかれている内容によって、構文解析の結果が変わることはない。そうなるように注意深く設計されている。

一方、C言語の構文解析は単一ファイルに閉じていない。例えば #include の先を見ないと、後続の構文解析の結果が確定しない:

#include "another.h"

void f() {
    t*x; /* 変数宣言かもしれないし、掛け算かもしれない */
}

単一ファイルに閉じた操作は、閉じていない操作に比べて2つの利点がある。

並列で実行できる
他のファイルの変更により結果が無効化しない

IDE バックエンドとして使うとき、リクエストが来てからソースコードを読んで解析するのでは遅すぎるので、解析結果をいくらか記録している。単一ファイルに閉じた操作の記録は、他のファイルが書き換わることでは無効化しないので、再解析の頻度が少ない。

Three Architectures for a Responsive IDE

配列ベースのデータ構造

処理系内部のデータを配列で持つようになった。例:

// ast.rs

struct ATyTag;
type ATyId = VecArenaId<ATyTag>; // ≒ u32
type ATyArena = VecArena<ATyTag, ATy>; // ≒ Vec<ATy>

struct APtrTy {
    mut_opt: Option<KMut>,
    ty_opt: Option<ATyId>, // ≒ Option<u32>
}

enum ATy {
    Unit,
    Ptr(APtrTy),
    // ...
}

struct ATree {
    tys: ATyArena, // ≒ Vec<ATy>
    ty_events: VecArena<ATyTag, TyEnd>, // ≒ Vec<usize>
    // ...
}

型の構文は再帰的なので、抽象構文木の型のノード (ATy) は再帰的になる。型の一部である型はポインタなどにより間接的に指さなければいけない。

ここでは型のノードを1本の配列 (ATyArena) に詰めて、そのインデックス (ATyId) を使って型を間接参照している。

この方法にはいくつか利点がある。

同一のオブジェクトに対するフィールドを外付けしやすい
- 同じ長さの配列をもう1本持てばいい
- 片方の配列は & で、他方は &mut で持つ、というようにすることで、単一のオブジェクトのフィールドへの可変参照と不変参照を同時に持てる
同種のオブジェクトの列挙が効率的
- 型のノードだけ列挙したいとき、構文木を辿るより配列の上を走査する方が速い
Box よりも大きな単位でメモリ確保を行うので、メモリ管理効率の改善を見込める
- ID は32ビットで十分なので、ポインタより小さい、というのもある

欠点もある。

ID のデバッグ出力が虚無！
- 番号しか出ない、あるいはデバッグ出力のためだけに配列への参照を持ってくる必要がある
- デバッグ版のみ、配列への弱参照をグローバルに置く試みはある
アクセスするたびにインデックスの範囲検査が行われるのが無駄
ポインタと違って借用検査の影響下にないので、インデックスの指す先が無効化してもコンパイルエラーにならない
記述が冗長になりがち

構文解析の結果の持ち方

前回の近況で書いたように、構文解析の結果をどう持つかで悩んでいた。

いままでは full-typed な具象構文木を持っていた。ノードの種類ごとに構造体を定義し、子要素はノードもトークンも含めて、すべてフィールドにした。例:

// jl_compiler/src/parse/parse_tree.rs

struct PUnitTy {
    left_paren: PToken,
    right_paren_opt: Option<PToken>,
}

struct PPtrTy {
    star: PToken,
    mut_opt: Option<PMut>,
    ty_opt: Option<Box<PTy>>,
}

enum PTy {
    Unit(PUnitTy),
    Ptr(PPtrTy),
    // ...
}

これはいまいち。コンパイルでは記号トークンなどは位置情報ぐらいにしか使わないので冗長。IDE バックエンドからするとトラバース処理を書きにくくて、使いにくい。

また、データを外付けしにくい。例えば名前解決の結果として得られた情報をノードに割り当てるために、専用のフィールドをもたせている。

そういうわけで、次の方針を試す。

パーサーは抽象構文木を組み立てる。構文木のノードは配列ベースで持つ。
パーサーはパースイベントを発行する。パースの完了後、パースイベントから型なし具象構文木を復元する。

前者はすでに上で見ている。抽象構文木は定石通り、コンパイルに必要な情報だけ持たせている。配列ベースで持つことで、後続のパスの情報をノードに関連付けしやすくなる。

後者は以前の近況記事 (2019-05-31#その他) で書いた。

おそらく、バッチコンパイルのときは型なし具象構文木の復元をスキップできると予想している。(まだ試してない。)

条件式のカッコ

Rust では if cond { body } のように、条件式をカッコで囲まなくてもよいが、そのせいで「cond の直下にはレコードリテラルが出現しない」という妙な制約が入っている。

制約のせいで文法は context-free ではなくなっている。頑張れば context-free な文法を作れるかもしれないが、かなり複雑になりそう。

ジャッコ言語では if (cond) { body } にしていた。しかし誤ってカッコを忘れて if cond { body } と書いたとき、パーサーは実際にレコードリテラルのパースを進めてしまうので、body の部分やその後ろで構文エラーが起こることが分かった。

この手の「本来の問題とは別のところで発生する」エラーは不快なので、可能なかぎり避けたい。とりあえず Rust と同じくカッコなし、cond の部分にはレコードリテラルが出現できない構文でいくことにする。

テキスト上の位置の表現

t_pos.rs

テキスト上の位置を複数の表現で計算したものを表す構造体を作った。テキスト上の位置は主に次の3種類の計量がある:

UTF-8 コードユニット数。内部的な位置計算に使う。
UTF-8 ベースの (行番号, 列番号) 表示。エラーメッセージで使う。
UTF-16 ベースの (行番号, 列番号) 表示。LSP で使う。

これを1個の構造体に詰め込んだもの:

pub struct TPos {
    /// インデックス: ソースコードの先頭から、この位置の手前までの文字数。0 から始まる。
    /// 文字列の長さは UTF-8 でエンコードしたときのバイト数で計算する。
    index: u32,

    /// 行番号: テキスト中の改行の個数。0 から始まる。
    row: u32,

    /// 列番号: テキスト中の最後の改行より後にある文字列の長さ。0 から始まる。
    /// 文字列の長さは UTF-8 でエンコードしたときのバイト数で計算する。
    column8: u32,

    /// 列番号: テキスト中の最後の改行より後にある文字列の長さ。0 から始まる。
    /// 文字列の長さは UTF-16 でエンコードしたときのコードユニット数で計算する。
    column16: u32,
}

そろそろ以前に書いた記事 (テキスト上の位置の計算と合成 or 累積和の一例) の伏線を回収したい。

位置情報の持ち方

AST のノードやシンボルに対応するソースコードの位置情報をどう持つか。(ソースコードID, 開始位置, 終了位置) で持つのが一般的。

空白やコメントが変更されるたびに LSP に計算の再実行をさせたくない (少なくとも字句解析の再試行で止めたい) ので、開始位置や終了位置をインデックスや行番号・列番号などの絶対座標で持たない方がよさそう。

トークンや構文木のノードのインデックスを使って指し、エラーメッセージの出力などの際に絶対座標に変換する方針を試している。

また、構文木は1つのファイルに含まれるものなので、構文ノードの位置にはソースコードのID (Doc) を持たせないようにしている。

すなわち、単一ファイルに閉じているデータのための位置情報と、複数のファイルが関わるデータのための位置情報の2種類に分けている。

// jl_compiler/src/parse/parse_tree.rs,
// jl_compiler/src/source/loc.rs などを参照。コードはイメージ

// 単一ファイル内での位置情報
enum PLoc {
    Unknown(&'static str),
    Range(TRange),
    Token(PToken),
    TokenBehind(PToken),
    TokenRange { first: PToken, last: PToken },
    Element(PElement),
}

// 複数のファイルにまたがる部分の位置情報
struct Loc {
    doc: Doc,
    loc: PLoc,
}

このあたりはまだまだ模索中なので、後で変わるかもしれない。

CPS 変換パスの分割

CPS 変換の実装に2つの課題が出てきた。

構文木にべったり依存しているので、上述のように構文木の設計をまるっと変更したせいで、大幅な書き換えが必要になった
構文エラーがないことを前提にしていて、構文エラーを含む構文木を CPS 変換にかけると即座にクラッシュするので、LSP サーバが型検査の結果を参照できなくて困った

そういうわけで CPS 変換をまるっと書き直した。

他のファイルに見える部分 (仮に「アウトライン」と呼ぶ) と見えない部分をそれぞれ別のパスで生成することにした。

見える部分と見えない部分とは、例えば関数でいうと、名前やパラメータの個数と型、結果の型は見えるが、本体は見えない、ということ。

ソースコードの大部分は他のファイルには見えない。見える部分だけ先に処理しておくことで、他のファイルが後続の工程により早く進めるようになる……かもしれない。

例えばファイル a.jacco に use b::B と書かれていて、ファイル b.jacco の型 B を参照しているとする。b のアウトラインの構築が済めば、a.jacco は B の情報を見れるようになるので、後続の CPS 変換の工程に進める。つまり a.jacco, b.jacco の見えない部分の CPS 変換を並列で行える……かもしれない。

ちなみに、いまのところ見えない部分も含めて CPS 変換は単一ファイルに閉じた操作になるように書いているが、これはおそらく無理がある。例えば、いまの実装ではエイリアスに基づくレコードリテラル B { x: 1, y: 2 } を変換できない。フィールドの過不足を検査したり、順番を定義順に並び替えたりしているが、それには B の定義を参照しないといけない。

ジャッコ言語によるジャッコ言語の字句解析

LSP サーバが名前解決までは安定して動くようになったので、ジャッコ言語の字句解析をジャッコ言語自身で書く試みをした。(Str 型を実装するところからスタート、きびしい)

自動脱参照も -> もないので、(*ts).kind のような記述が頻発してアレになってる。

その他

|> の結合規則をどうすべきか、よく分からない。要調査
- x + y |> f() は (x + y) |> f() と x + (y |> f()) のどっちであるべき？
- x && y |> f() は？
|> 、意外と使い道が少なくて、いまの時点で実装しておく必要はなさそうだった。とりあえず削除した
** を累乗のために入れようと思ったが、2重の脱参照 (**p) と衝突するのがアレ。とりあえず削除した

競技プログラミング

ABC 173 (D完) https://atcoder.jp/contests/abc173/submissions?f.Task=&f.Language=&f.Status=&f.User=vain0

気になった記事など

man bash を読め

https://twitter.com/kimiyuki_u/status/1280545911408488448

man bash を読んでみたら知らない挙動がいろいろあった

データベースとしてのコードベース

Turning the IDE Inside Out with Datalog | Pete’s Blog

概要:

LSP によりエディタから IDE バックエンドへのクエリのインターフェイスは統一されつつある
IDE バックエンドの内部的な表現 (構文解析や意味解析の結果のデータの持ち方) はかなりバラバラ
Datalog という論理型プログラミング言語を使って言語非依存な意味論を表現する試み
汎用的、効率的、 追跡可能 なクエリベースのアルゴリズムを記述できて嬉しい

意味解析の追跡可能性 (traceability) に言及しているのを初めてみた。

Traceability: The ability to follow a result (for instance, a type error or a completion) back through the language’s inference rules to base facts about the program’s AST. The IDE user should be able to see all of the reasoning behind what the IDE is telling them.

例えば、ある変数の型 A に推論されると思って書いたが、なぜか B に推論されてしまう、変数名にホバーしたら B に推論されることは分かるが、なぜそう推論されたのかは分からない、といった状況に役立つ。

持論注意: ソースコードはデータベースの一種という観点はとても重要。<ソースコード as データベース> のクエリへの応答性の良さは、入力補完などの IDE 機能や追加機能の影響調査や不具合調査などの、効率と質に影響する。

IDE バックエンドのアーキテクチャ

Three Architectures for a Responsive IDE

In this post, we’ll learn how to make a snappy IDE, in three different ways :-)

map-reduce アーキテクチャ:

各ソースコードを解析した結果をキャッシュしておき、クエリが飛んできたときに必要な情報を収集する、というモデル
解析結果を統合しないままおいておくことで、ソースコードの変更によるキャッシュの無効化を抑えるのがポイント (上に書いた単一のファイルに閉じた操作の話と似ている)
Rust には適用できない

ヘッダーファイルを活用するアーキテクチャ:

C++ や OCaml などのヘッダーファイル (インターフェイスファイル) の概念を持つ言語の場合
ソースコードの前方のヘッダーファイルが書かれている部分の解析結果をキャッシュに持つ
バッチコンパイルのために書かれた処理系の実装を流用しやすい
Rust には適用できない

クエリベースのアーキテクチャ:

rust-analyzer の手法
通常の関数ではなく、クエリの組み合わせで実装する
クエリは一種の決定性を持つ: 与えられた入力と、処理中に実行した他のクエリの結果が同じなら、結果は必ず同じになる
状態が変化してクエリを再計算したとき、あるクエリの結果が同じだったら、そのクエリに依存するクエリの結果は必ずしも無効化されない (無効化の伝播が止まる)
これによりマクロ展開による解析への影響を抑えている、らしい

その他: nodemailer-frontends

nodemailer-frontends

nodemailer ライブラリの関数を CLI や http 経由で呼べるようにするだけのもの