2023 03 26 - qnighy/umo GitHub Wiki

近況

配列操作を実装した。これでチューリング完全になった。

(本当は入力システムも欲しいところだが、それはあとででいいや)

ここからはインタプリタのオーダー改善を行う。目標は1週間…… と思ったけど2週間くらいは要るかもしれない。

インタプリタ改善計画

昨日書いた設計の制約のもとで実装していく。

以下のような順番になりそう。

1. ASTにノード番号を付与
2. パフォーマンスは無視してVM化
3. 借用推論を実装

2, 3をもう少し細かく分解したいが…… ここは一気に駆け抜けるしかないかもしれない。

仮VM

まずは借用のことを一旦考えない仮のVMを作る。この時点ではまだ難しい最適化は必要ないので、実行に適したフォーマットで作る。中間フォーマットとしてのSSAをあとで検討する。

• 値
  • Valueは整数、配列、クロージャのいずれか。配列には再帰的に値を格納できる。
• プログラム
  • プログラムは複数の関数からなり、ひとつがmain関数である。
• 関数
  • 関数はnum_args, num_localsと本体を持つ。
  • 関数本体は複数のbasic blockからなり、ひとつがentrypointである。
• basic block
  • 複数の命令からなる。
• 命令
  • 末尾命令
    • ret
      • 呼び出し元関数に戻る。
    • jump
      • 指定したbasic blockにジャンプする。
    • jumpif
      • スタックの先頭をpopし、その値に応じて異なるbasic blockに分岐する。
    • tccall
      • フレームポインタはそのままで、クロージャのキャプチャ値をスタックに積んでから、関数を呼び出す。
      • 制御は戻ってこない。
  • 特殊な命令
    • read
      • フレームポインタ + 定数 位置から値を読み出し、積む。
    • write
      • スタックの先頭をpopし、フレームポインタ + 定数 位置に格納する。
    • ccall
      • スタックポインタ - 定数 を新たなフレームポインタとする。その後、クロージャのキャプチャ値をスタックに積んでから、関数を呼び出す。
      • 終了後は元の位置に戻ってくる。
    • closure
      • スタックから所定の個数を取り出し、関数と組み合わせてクロージャを作る。
  • 一般命令 …… スタックから所定の個数を取り出し、スタックに結果を積む。
    • 四則演算、比較、配列操作