Zenn
☄️

Erg開発進捗2023

2023/12/23に公開
Python
Rust
#
型推論
#
言語処理系
#
erg
tech

2022に引き続き私が開発している言語Ergの経過を報告していきたいと思いますが、訳あって本年はマニアックな話を中心にしたいと思います。
今年Erg本体に入れた変更・改善・実装のうちこれは知見だなと思ったものを中心にいくつかピックアップしています。

双方向型検査

関連PR:
#456

通常Ergの型推論はボトムアップに進行します。
例えば、関数呼び出しは引数の式の型から推論され、最後に全体のシグネチャが導出されます。
しかし逆に、関数のシグネチャから引数型の推論をしてほしいこともままあります。

for! [1, 2], i => # i: Nat
 ...

...の中で出てくるiについての計算がi + 1程度ならi: Add(Nat)(Nat <: Add(Nat))と推論できるのですが、iのプロパティにアクセスされたりなどするとダメになってしまいます。

ところで、for!のシグネチャは以下のようになっています。

for!: |T: Type| iter: Iterable(T), proc!: T => NoneType

これを見ればわかるとおり、先にiterの型が分かっていて(T == Nat)、proc!の入力型Tに反映させることができれば、iの型がNatと導出できることになります。なお、これがうまくいくためにはオーバーロードがない、すなわち関数の名前だけでシグネチャが一意に定まるという条件が必要になりますが、幸いErgの多相関数は基本的にパラメトリックのみです[1]。

こういう風に、型検査・型推論がボトムアップだけでなくトップダウンにも進行するようなものを双方向型検査(bidirectional typechecking)といい、最近の型推論研究のトレンドらしい?です。

Ergに双方向型検査(みたいなもの)を導入するために、ASTの型検査・型推論ルーチンに変更を加えました。
Ergのコンパイルプロセスでは、ASTに対して型検査を行った結果としてHIR(≒完全な型情報付きのAST)が得られます。

TokenStream \xrightarrow{parse} AST \xrightarrow{type-check} HIR \xrightarrow{code-generate} Bytecode

ErgコンパイラではASTをHIRに変換するプロセスをloweringと呼んでいます(type-checking以外のこともやっているため)。

lower: fn(ast: ast::AST) -> hir::HIR
lower_expr: fn(expr: ast::Expr) -> hir::Expr

lower_exprのシグネチャを少し変更して、「期待される型」をオプショナルに取れるようにしました。

lower_expr: fn(expr: ast::Expr, expect: Option<Type>) -> hir::Expr

expectは以下のような場合にnon-nullになります。

  • 明示的に型指定された場合。
    • 変数、関数定義に型指定が付いている場合、その型が右辺値、関数bodyのexpectに入ります。
  • シグネチャが判明している関数呼び出しの引数である場合。

for!の場合2つ目が効きます。まずfor!の第一引数の推論で

lower_expr([1, 2], Some(Iterable(T)))

となるわけです。結果としては[1, 2]: Array(Nat, 2)が得られますが、処理の中で型引数の単一化処理が入り、T == Natと決定されます。これのおかげで、第二引数の推論で具体的な型を得られます。

lower_expr(i => ..., Some(Nat => NoneType))

expectは現時点ではあくまで型推論の精度向上のためだけに入っており、矛盾する型が入っていても処理自体は成功します。

lower_expr(1, Some(Nat => NoneType)) == (1: Nat)

関数呼び出しの引数型の相違などは引数の型が全てlowerされた後に検証されます。しかしこの辺はうまく工夫すれば一度に両方とも実行できるかもしれません。

しかし、これでもまだ問題があります。例えば以下のようなコード。

map(i -> f(i), [1, 2])

ErgはPythonのAPIを踏襲しているため、map関数もそのままのシグネチャで輸入しています。それで、Pythonのmap関数は高階関数が第一引数というシグネチャになっています。
これを見ると微妙な問題が浮き彫りになります。具体的な型は第二引数の方にあるので、引数を左から順に推論して行くとすると、この関数の推論は失敗し得ます。
プレーンなHindley-Milner型推論では引数の順番は問題になりませんが、Ergの型システムは射影型などを持っており、型推論の可換性を失っています。
しかし引数の順番を変えただけで型推論が通ったり通らなかったりするのは不便です。

そこで、以下のようなヒューリスティックスを導入しました。

  • 構文要素にcomplexity(複雑性)という概念を導入する。
    • 型の明らかな要素(リテラル、型明示されている式)のcomplexityを0とする。
    • 変数のcomplexityを1とする。attributeのcomplexityはレシーバ(左辺)のcomplexity+1とする。
    • 無名関数のcomplexityは、型が指定されていない引数数+bodyのcomplexity+(戻り値型が指定されていれば0, さもなくば1)とする。
    • コンテナ(配列、辞書など)のcomplexityは、要素のcomplexityの総和とする。
    • 関数呼び出しのcomplexityは、callableのcomplexity+引数のcomplexityの総和とする。
  • 型推論時は、complexityの低い引数から推論を始める。

点数計算の細かい部分は今後調整する可能性がありますが、要は、変数の多い項ほど型推論が面倒になるので後回しにしようというアイデアです。
complexityが項のsemanticsに関係なくsyntaxだけで決まることが重要です。

先ほどの例でcomplexityを計算してみましょう。例えば、map中の無名関数のcomplexityは1 (引数) + 1 (戻り値) + (1 (f) + 1 (i)) (body) = 4です。一方、第二引数のcomplexityは0です。よって、complexityがより低い第二引数から推論を始めます。

順序変更は引数のsortによって実現しています。
そのままだと引数の順序が崩れてしまうので、HIRのargumentsはダミー式で埋めておきます。
型検査器は元々引数の推論が失敗したときボトム型のダミー式を嵌め込むことで検査を続行させていたのですが、このsort処理によって不要になるという副次的なメリットもありました。

コンパイラのライブラリ化

関連PR:
#467

Ergは(主に)CPythonインタプリタ上で動くトランスパイル言語です。
コンパイラはRustで実装されているので、本来Ergモジュールを動的にロードさせたりErg ASTを実行時に触ったりすることはできないのですが、もし出来たら例えばErgを設定ファイルなどに使えて便利ですし、今後やるかは未定ですがAST構築方式の衛生的マクロシステムを導入する足掛かりにもなります。

というわけで、実現しました。

要はコンパイラをライブラリ化してCPythonにバインディングしてやればいいわけです。バインディングにはpyo3を使いました。
基本的には、structにはpyo3::plelude::pyclassというmacroをつけてやり、implにはpyo3::plelude::pymethodsをつけてやればいいだけです。

#[pyclass(get_all, set_all)]
#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub struct Lambda {
    pub sig: LambdaSignature,
    pub op: Token,
    pub body: Block,
    pub id: DefId,
}

#[pymethods]
impl Lambda {
    #[staticmethod]
    pub const fn new(sig: LambdaSignature, op: Token, body: Block, id: DefId) -> Self {
        Self { sig, op, body, id }
    }

    pub fn is_procedural(&self) -> bool {
        self.op.is(TokenKind::ProcArrow)
    }
}

あとはlib.rsでパッケージ名の関数を作ってやるだけです。

#[cfg(feature = "pylib")]
#[pyfunction]
#[pyo3(name = "parse")]
fn _parse(code: String) -> Result<ast::Module, error::ParseErrors> {
    parse::SimpleParser::parse(code)
        .map(|art| art.ast)
        .map_err(|iart| iart.errors)
}

#[cfg(feature = "pylib")]
#[cfg_attr(feature = "pylib_parser", pymodule)]
pub fn erg_parser(py: Python<'_>, m: &PyModule) -> PyResult<()> {
    m.add_function(wrap_pyfunction!(_parse, m)?)?;
    let expr = PyModule::new(py, "expr")?;
    expr.add_class::<ast::Literal>()?;
    ...
    m.add_submodule(expr)?;
    ...
    Ok(())
}

enumも単純な1 element tuple variantのみからなるようにしておき、自動変換できるようにしました。

macro_rules! impl_into_py_for_enum {
    ($Enum: ident; $($Variant: ident $(,)?)*) => {
        #[cfg(feature = "pylib")]
        impl IntoPy<PyObject> for $Enum {
            fn into_py(self, py: Python<'_>) -> PyObject {
                match self {
                    $(Self::$Variant(v) => v.into_py(py),)*
                }
            }
        }
    };
}

macro_rules! impl_from_py_for_enum {
    ($Ty: ty; $($Variant: ident ($inner: ident) $(,)*)*) => {
        #[cfg(feature = "pylib")]
        impl FromPyObject<'_> for $Ty {
            fn extract(ob: &PyAny) -> PyResult<Self> {
                $(if let Ok(extracted) = ob.extract::<$inner>() {
                    return Ok(Self::$Variant(extracted));
                } else)* {
                    Err(PyErr::new::<pyo3::exceptions::PyTypeError, _>(
                        format!("expected one of {:?}, but got {}", &[$(stringify!($Variant),)*], ob.get_type().name()?),
                    ))
                }
            }
        }
    };
}

少し躓いた点として、RustアプリケーションとしてErgコンパイラをコンパイルするときにpyo3は要りませんのでoptional featureにしたいところですが、そうするとpyclassなどのattributeが邪魔になります。

解決策として、何もしないダミーのproc macroを定義して、feature flagがonにならなければこちらをuseするようにしました。

// https://github.com/erg-lang/erg/blob/1b824d78e1f4b4996d763432cb6f2220475642e7/crates/erg_proc_macros/src/lib.rs#L61-L71

/// dummy attribute
#[proc_macro_attribute]
pub fn pyo3(_attr: TokenStream, item: TokenStream) -> TokenStream {
    item
}

/// dummy attribute
#[proc_macro_attribute]
pub fn pyclass(_attr: TokenStream, item: TokenStream) -> TokenStream {
    item
}

// https://github.com/erg-lang/erg/blob/1b824d78e1f4b4996d763432cb6f2220475642e7/crates/erg_parser/ast.rs#L27-L31

#[cfg(not(feature = "pylib"))]
use erg_proc_macros::{getter, pyclass, pymethods, pyo3, setter, staticmethod};
#[cfg(feature = "pylib")]
use pyo3::prelude::*;

Pythonパッケージの内容としては、コンパイラ、パーサー、ASTが付属するようにしました。
こんな感じで使えます。

erg_compiler = pyimport "erg_compiler"
erg_parser = pyimport "erg_compiler/erg_parser"
erg_ast = pyimport "erg_compiler/erg_parser/ast"

mod = erg_parser.parse ".i = 1"
ast = erg_ast.AST.new "test", mod
test = erg_compiler.exec_ast ast
i = test.__dict__.get("i")
assert i in Int
assert i == 1

test2 = erg_compiler.exec ".i = 1"
i2 = test2.__dict__.get("i")
assert i2 in Int
assert i2 == i

これでErgは実行時にも静的型検査できるという謎の言語になりました(Scalaとかもできるらしいですけど)。

コンパイラの並列化

関連PR:
#434
#435
#462

正直やらない方が良かったかと思っている事項の一つです。いわゆる「早すぎる最適化」ではなかったかと。
まあ自分自身が非同期Rustの理解を深めたいという動機もあったのですが、コンパイラがもう少し成熟してから取り掛かっても良かったと思っています。

行っている並列化は、コンパイル単位毎にthreadを立ち上げ、RwLockでデータを共有するという方式です。stdだけでは不便なのでparking_lot, thread_localという外部crateを利用しています。

parking_lotはRwLock{Read, Write}Guardにmapメソッドを付けたというただそれだけのcrate(として使っている)ですが、std::syncよりもかなり便利です。stdの非同期データ構造の面倒な点が、データの一部の参照を取り出すことができないというところです。例えばFooという構造体の中にbar: Barというフィールドがあったとしましょう。FooをMutexなりRwLockなりで包んでしまうと、barの値が欲しくなったらその度に

let Ok(foo) = foo.try_read() {
    let bar = &foo.bar;
    ...
}

としなくてはなりません。要はstruct SharedFoo(RwLock<Foo>);みたいなnew typeを作ってもget_barみたいなメソッドを安全に生やすことができないんですね。
parking_lotならそれができます。

struct SharedFoo(Arc<RwLock<Foo>>);

impl SharedFoo {
    pub fn get_bar(&self) -> MappedRwLockReadGuard<Bar> {
        RwLockReadGuard::map(self.try_read().unwrap(), |foo| &foo.bar)
    }
}

保持するデータの型が変わってもロックを取り続けることができるというわけです。

もう一つのthread_localも地味に便利なcrateです。
stdのthread_local!マクロで作れる定数は静的領域にしかデータを置けません。thread_local::ThreadLocalを使えば一時領域にスレッドローカルなデータを置けるのです。これは型変数の管理などで非常に便利でした。

コンパイラを並列化するという作業は、コンパイルの実行単位を厳密に決める作業でもあります。
Rustではcrateが今のところ並列化の最小単位ですが(今後はもっと細かい単位でコンパイルできるようになるらしいですが)、Ergはもっと細かくモジュール単位並列を実現しています。ここで問題になるのが循環参照の扱いです。
モジュール同士の循環参照を禁止するというのも解決策の一つで、実際Goがそういうスタンスですが(Goの場合並列コンパイルのためというわけでもなさそう)、Ergの場合Pythonがモジュールの循環参照はOKという事情があります。

Ergは、実装が面倒になりますが基本モジュール単位で並列コンパイルし、循環モジュールを見つけたら結合して一つのコンパイル単位とする方式にしました。

以上のようにしてコンパイラの並列化を行い、効果が出ていることは確認できたのですが、副作用として確率的にCIが落ちるようになりました。
language serverのテストはserverのバグなのかコンパイラのバグなのかよくわからない、デバッグログも複数スレッドから同時に流れてきて見にくいなどといった問題が発生しています。
language serverのテストの方は1回までretryするというworkaroundを導入して凌いでいますが、なんだかなあという感じです。

パターンマッチの改善

関連PR:
#460

これまでのErgの課題として、パターンマッチが貧弱でしかも期待される通りに動かないというものがありました。具体的にはネストしたパターンが使えなかったり、配列パターンの長さチェックをおざなりにしていました。
そこでパターンマッチにおいて内部的にguard節を導入しました(将来的にユーザーも使えるようにするかもしれません)。

[x, 1, [y, z]] -> ...
# ↓ desugar ↓ (脱糖後のコードは具象構文としてはinvalidであることに注意)
_1 if len(_1) == 3 and _1[1] == 1 and len(_2) == 2;
    x = _1[0];
    _2 = _1[2];
    y = _2[0];
    z = _2[1];
->
    ...

このようにパターンマッチを単純なコンポーネントに分解することで実装を簡便かつ一貫性あるものにできました。今後パターンの種類を増やしてもguard節にdesugarするだけで対応できるでしょう。

終わりに(&宣伝)

冒頭でちょっと仄めかしましたが、2023年は筆者とErgにとって激動の年でした。
ありがたいことにErgプロジェクトが「Pythonにトランスパイル可能な静的型付けプログラミング言語の開発」という題目で2023年度の未踏IT人材発掘・育成事業にて支援されることになったのです。
今はまだ内緒ですが、コンパイラ本体以外にも色々なものを開発中です。開発成果は2024年2月17/18日に開催されます成果報告会にて詳細に報告する予定です(だから本記事では報告会で絶対話さないようなマニアックな話をした次第です)。是非ご覧ください。

脚注

  1. 正確には、Ergにもオーバーロード型(関数の交差型)があります。が、PythonのAPIの中には実質的にオーバーロードのような振る舞いをするものがあるため仕方なく導入したものであり、Ergで定義した関数はオーバーロードできません。 ↩︎

Discussion