近況 2020-10-31

 2020年10月31日 投稿 日記

今月の活動 (ミローネ言語の高速化、クロージャ変換の手順の話、IDE 風のターミナルエミュレータ、など)

ジャッコ言語は迷走してきたので今月は休み。

milone-lang

https://github.com/vain0x/milone-lang

  • F# の VSCode 用のプラグイン (ionide-fsharp) で、以前は動かせるコードフォーマッターがなかった (あるいは私が設定ミスで動かせてなかった) が、最近試したら設定しなくてもフォーマットが効くようになっていた
  • ミローネ言語のコードをフォーマットしたら、セルフコンパイルでパースが失敗するようになったので、微調整して直した
    • 原因は type A = | A of int のような形の判別共用体の定義から先頭のパイプを削って type A = A of int に書き換えられたため
    • ミローネ言語のパーサは先頭にパイプがないケースをサポートしていなかったが、サポートするようにした
  • せっかくだからセルフコンパイルが遅すぎる問題を調査した
    • (以前試したときは20秒ぐらいだった記憶があるが、いま試すと) 1分近くかかっていた
  • 各ステージの処理時間を計測するようにした。名前解決と型推論が遅かった
  • 名前解決時にスコープを表現するデータ構造をハッシュマップのリストにした
    • スコープが深くなるたびにリストの末尾に空のハッシュマップを入れて、探索するときはリストの末尾から順次マップを見て探す、というよくあるやつ
    • 以前はすべてのシンボルを1本のリストに入れて、線形探索でルックアップしていた。遅いに決まっている
    • これにより10秒ぐらいまで縮んだ
  • 型推論時の「型変数の深さ」の計算や型変数の生成の無駄を減らしたら速くなった
    • 型変数の深さは HM 型推論において過剰な汎化を防ぐテク。OCaml でも採用されているレベルベースの多相型型推論とは を参照。また、Efficient and Insightful Generalization に実装上の技法がめっちゃ詳しく書いてあった。
    • 型変数 v に型 t を束縛するとき、「型 t に含まれる自由変数のレベルを、それらの現在のレベルの最小値に引き下げる」という処理をしていた
    • 実際には「型 t に含まれる自由変数のレベルを、v のレベルを超えていたら、v のレベルまで下げる」とするだけでよかった
  • これでセルフコンパイルのボトルネックはおよそ GCC でミローネ言語が吐いたC言語のコードをコンパイルする部分になった
    • 吐くコードが長くて非効率すぎるという課題はある

現時点での各ステージの時間は CI のログから見れる。

.NET 上で実行したとき:

+./milone_netcore --profile MiloneLang

Begin compiling project=MiloneLang  (注: 字句解析・構文解析)
profile: time=   0.640 mem=  261,955,984

Name resolution
profile: time=   0.568 mem=  252,938,664

Type inference
profile: time=   1.637 mem=  686,742,704

Hoist main
profile: time=   0.002 mem=    0,112,784

Closure conversion
profile: time=   0.753 mem=  323,201,504

Eta expansion
profile: time=   0.059 mem=   13,096,760

Hoist
profile: time=   0.012 mem=    5,242,848

Monomorphization
profile: time=   0.676 mem=  212,658,536

Mir generation
profile: time=   0.354 mem=  102,653,056

Cir generation
profile: time=   1.061 mem=  567,140,848

Finished

セルフコンパイルで作ったコンパイラを実行したとき:

+./milone --profile MiloneLang

Begin compiling project=MiloneLang  (注: 字句解析・構文解析)
profile: time=   0.642 mem=  174,376,658

Name resolution
profile: time=   1.012 mem=  194,460,416

Type inference
profile: time=   2.608 mem=  507,818,652

Hoist main

profile: time=   0.001 mem=    0,086,400
Closure conversion

profile: time=   0.972 mem=  151,428,196

Eta expansion
profile: time=   0.054 mem=    8,023,460

Hoist
profile: time=   0.012 mem=    2,155,976

Monomorphization
profile: time=   0.876 mem=  149,950,520

Mir generation
profile: time=   0.363 mem=   77,342,899

Cir generation
profile: time=   1.687 mem=  374,045,525

Finished

動的なリージョンに基づくメモリ管理

Memory Management | milone-lang/notes.md

  • ミローネ言語はオブジェクトの書き換えを許してない
  • クロージャの外から中への参照は存在しない
  • クロージャの呼び出しの返り値を deep clone したら、クロージャの実行に中に割り当てたメモリはすべて捨てられる、はず
  • そのための inRegion プリミティブを (返り値型が int のケースだけ) 実装した
    • inRegion にクロージャ f を渡すと f を呼び出して、その返り値がそのまま返る
    • ただし、クロージャ f の実行中に確保するヒープメモリは外側から分離される
    • クロージャの実行中にヒープメモリを確保するときは、すべてアロケータ A を使って割り当てる
    • クロージャの返り値 r は、外側のアロケータを使って deep clone して、inRegion の返り値にする
    • そのときクロージャの実行中に割り当てたヒープメモリは全く参照されないから、一括で捨てられる、はず

疑問

  • C FFI を使って外から中への参照を作ったら死ぬ
    • FFI でメモリ関連のエラーを起こすのは元から簡単だからヨシ！
  • inRegion の外側のヒープメモリが増え続ける
    • inRegion の返り値は int などのヒープ確保をしない値で十分なケースが多いはず
    • 例えばサーバーならレスポンスをストリームに流した後はデータを捨てられる
    • 仮にデータを持ち出す必要があるとしても、それは mysql や redis などの外部サービスに送ってしまうという手もある
    • 他には inRegion の返り値は手動で解放するとか、スコープを抜けたら自動で解放する (これはエスケープしないように保守的に解析する) などの案もある
  • とりあえず動的リージョンベースのメモリ管理の先行研究を探る必要がある
    • 論文(英語)の山は険しい

reterm: IDE 風のターミナルエミュレータ

vain0x/reterm: (would be) terminal emulator with IDE-like UI

IDE みたいな外観のターミナルエミュレータを作ろうとしている。やることが多くてすでに停滞気味……

普通のターミナルエミュレータは他のアプリと操作感が異なる。

  • 例えば入力欄をマウスでクリックしてもカーソルが押した位置に移動しない。reterm では入力欄は普通の input/textarea にしたい。

UI が分かりづらい。

  • 例えば入力と出力の表示が見た目の上で分離されていない。reterm ではタスクごとの入力欄と出力、それからコマンドを記述する入力欄は分けたい。

ターミナルエミュレータの内的なステータスの操作が GUI 上でできない。

  • 例えば作業ディレクトリの移動に cd コマンドを使う必要がある。ファイルツリー上の項目をクリックするだけでもできるようにしたい。

その他: Ungrammar について

rust-analyzer の作者が公式ブログで Ungrammar というツールについて記事を書いていた:

Introducing Ungrammar

Ungrammar は拡張 BNF 風で、パット見、パーサジェネレータに似ているが、パーサはジェネレートできない。そうではなく、具象構文木を操作するコードを生成するのを目的としている。

具象構文木を操作するコードは非常に冗長なので、自動で生成したい圧力があった。具象構文木を操作するコードとは、例えば関数宣言の文から関数名の部分を取り出すとか。

パーサジェネレータのための構文定義は、文字列から構文を読み取る (構文解析する) ため、演算子の結合や左再帰などを考慮する必要があって、かなり冗長になりがち。

一方 Ungrammar の構文定義は、具象構文木がすでに与えられているという前提だから、演算子の結合や左再帰は関係ない。実際 Rust の構文定義 が600行ぐらいで書かれている。

(余談: この手の N 行で書かれていて短い系の言説は、コードから可能なかぎり改行を除去して読みづらいフォーマットにした上で言われがちだが、この構文定義は普通に読みやすい。)

その他: F# の判別共用体の定義

F# の判別共用体を普通に定義すると、各バリアントが型と同じ名前空間に含まれる。

type U = A | B

let a () = A // U.A じゃなくてもいい

この挙動は RequireQualifiedAttribute 属性をつけると抑制できる。バリアントはスコープに展開されず、型名を使ってアクセスすることが強制される。

[<RequireQualified>]
type U = A | B

let a () = U.A // A ではダメ

この方が「正しい」ような気がして、常に RequireQualified を指定していた。しかし、これだと入力補完の候補を見るために U. を書く必要がある。F# の入力補完のためのツールの応答はいまのところあまり速くないので、これは問題になる。

そのため RequireQualified は使わない派に転向した。名前の衝突や、バリアント名だけでは意味が分かりづらいなどの問題がある場合は、バリアント名に型名のようなものを含めてしまってよい気がする。

type Expr =
    | IntExpr of int
    | AddExpr of Expr * Expr

Expr と入力すると (部分一致なので) IntExpr, AddExpr が入力補完候補に出る。これらのシンボルははじめからローカルスコープに入っていて、解析結果のキャッシュがすでにあるので、補完候補のリストがすぐに出る。

関連記事