2023 03 25 - qnighy/umo GitHub Wiki

近況

昨日は特に何も実装していないが、今日は配列操作を実装しきってチューリング完全になる予定

現状の言語仕様まとめ

現状ではML+Rust風の構文をもつ正格評価の純粋関数型言語になっている。これは今後の発展で変わる可能性がある。

字句

  • 識別子は /[a-zA-Z_][a-zA-Z0-9_]*/
  • 空白は /[ \r\n\t\x0C]+/
  • コメントは今のところなし
  • 整数 /[0-9]+/

構文

  • 変数宣言 let <ident> = <expr> in <expr>
  • 変数参照 <ident>
  • ラムダ抽象 (<ident>, <...>) => <expr> (末尾カンマOK)
  • 関数呼び出し <expr>(<expr>, <...>) (末尾カンマOK)
  • 条件式 if <expr> { <expr> } else { <expr> }
  • 配列リテラル [<expr>, <...>] (末尾カンマOK)
  • 括弧 (<expr>)

スコープ

スコープはOCamlに準じる。 let 内ではこれから定義されようとしている変数は参照できない。

組込み関数

  • add, sub, mul, div ... 四則演算を行う2引数関数
  • gt, lt, ge, le, eq, le ... 数値比較を行う2引数関数
  • array_len(a) 配列の長さ
  • array_init(len, init) 配列初期化。 init は init(index) 形式で呼ばれる
  • array_get(a, i) 配列 a の i 番目を返す
  • array_set(a, i, x) 配列 a の i 番目を x に置き換えたものを返す

値

  • 整数 - 32bit符号つき
    • 真理値は0を偽として整数にエンコードされる
  • 配列 - 任意の値の配列
  • 組込み関数
  • クロージャ

次のプラン

今の設計だとまともなオーダーで実行できないので、インタプリタの書き直しをする。1週間が目標。

インタプリタの設計

書き直すインタプリタの設計を考える必要がある。この書き直しで達成したいのは次のこと。

  • 以下の前提は維持する
    • GC, 参照カウントはまだ使わない
  • 最適化
    • クロージャは中で使われている変数のみをキャプチャする。 (ムーブキャプチャでもOK)
    • 配列を受け取る関数
      • 受け取った引数を関数の寿命より長く維持する必要がなければ、参照渡しとしてマークされる
      • 参照渡しの場合、呼び出し元はなるべく変数をコピーしないように最適化される
    • array_get は参照返しが可能
    • array_set の呼び出し元でそれ以降変数を使う余地がなければムーブされる (コピーを行わないような使い方ができる)
    • Y combinatorでも最適化が効く

上の説明はまだ完全に形式化できていないので、多分コーナーケースが色々ある。

設計をしながらそのあたりを詰めていく必要がありそう。

コピー推論

特に重要なのが、値の読み出しを以下のいずれで行うかを推論する部分。

  • 借用
  • ムーブ
  • コピー

Rustでは読み出しが借用かそうでないかは所与なので、この部分を作る上では100%参考にはできない。難しい点として以下が挙げられる:

  • コピーはパフォーマンス上の問題を除けばムーブの上位互換だが、借用とムーブ/コピーの間にはそのような明確な関係がなく、インクリメンタルなアルゴリズムがパッと出てくるわけではない。
  • ユーザーにはデフォルトではこれらの差異を意識させない設計にしたいため、各関数が期待されるシグネチャも所与ではなく推論する必要がある。

問題を整理してみる

  • 変数
    • let変数、式
      • この引数はコピー渡しを期待するか？
      • この引数は借用渡しを期待するか？ 期待するとすれば、そのライフタイムは？
    • クロージャ
      • キャプチャ変数
        • コピーキャプチャか、借用キャプチャか？ 借用キャプチャするとすれば、そのライフタイムは？
      • 引数
        • この引数はコピー渡しを期待するか？
        • この引数は借用渡しを期待するか？ 期待するとすれば、そのライフタイムは？
      • 戻り値
        • コピー戻しか、借用戻しか？ 借用戻しの場合、そのライフタイムは？
  • 制約
    • 関数呼び出し
      • 戻り値のライフタイムは引数のライフタイムに制約される
    • クロージャ
      • クロージャのライフタイムはキャプチャ変数のライフタイムに制約される
      • クロージャの戻り値のライフタイムはクロージャ本体式のライフタイムに制約される
    • ...

ここまで書いて思ったけど、ライフタイムを持ったクロージャを返したくなったときの挙動とかも考える必要がある。やっぱりまずは関数がどうあるべきかをハッキリさせないといけない。

多分基本的なアイデアとしては以下のようにするのがよい気がする。

  • 関数は原則として借用渡しかつコピー返し。
  • ただし、静的解析がうまくいったときのために代替実装を持つことができる。代替実装には以下がありえる。
    • コピー渡し・コピー返し
    • 借用渡し・借用返し
⚠️ **GitHub.com Fallback** ⚠️