SECDV Schemeの実装 - writeとapplyとcall-with-values

nmosh

...readは無いゾ
readに関してはまぁ後回しでも良いんじゃないかということで。。readは特に浮動小数点のreadどうすんのか問題が有り、http://www.ryanjuckett.com/programming/printing-floating-point-numbers/ のような記事に引いてある論文の著者を見ても、Guy Steele Jr(Scheme原作者)、Kent Dybvig(Chez Scheme)、William Clinger(Larceny)とScheme関係者ばっかりじゃないか状態になっている。
今回はとりあえずバックエンド言語の浮動小数点I/Oをそのまま使うのを基本線に考える。どこかのタイミングでちゃんとした奴を実装したいけど。。(なのでwriteの実装でも容赦なくホストSchemeのnumber→stringを使っている。)

writeとdisplay

一般的にSchemeはC言語で言うとprintfにあたるデータ出力(印刷)APIとして2種類を規定している。
writeは、基本的にread手続きで元に戻るようにデータを出力する。このため、文字列を出力する場合はダブルクオートで囲んだり、改行をエスケープする等の配慮が必要になる。
displayは、人間用にデータを出力する。文字列はエスケープされず、文字は単なる1文字として出力される。displayで出力した文字列はreadで読み取れる必要は無い。
ペアとかリストのような一部のオブジェクトはwriteとdisplayで出力アルゴリズムが同一なため、"writeモード出力"パラメタを出力手続に設けて引き回しコードを共通化している。
R7RSでは更にwriteをwrite-simpleやwrite-sharedのように細分化しているが、今回は無視する。

プリミティブ手続表現の変更

今後VMをCやBASICに移植していくことを見据えて、プリミティブと呼んでいる言語コア手続きの実装手法をちょっと変更することにした。
プリミティブは http://d.hatena.ne.jp/mjt/20170619/p1 で書いたところのHeap + Core部に相当する。今、VMはScheme-on-Schemeで実装されているため、このプリミティブもScheme手続き(= procedure?が真)で表現していた。しかし、Scheme手続きオブジェクトはエミュレートされるヒープには載せられないため、基本的な型で表現できるようにする必要がある。
(今の実装では、ヒープのエミュレーションにホストSchemeのオブジェクトシステムをほぼそのまま使用している。これは、エミュレートされるヒープのGCを現時点では実装したくないため。今後はエミュレートされるヒープでもGCの実装をしないといけなくなるため、ヒープの表現力を適切に制約する必要がある。)
既に同様の対策を行ったものとしてはportがある。open-input-fileのようなI/O手続きをエミュレートするためにホストSchemeのポートを使用しているが、ホストSchemeのポートを直接エミュレートされるヒープに載せるのではなく、開いている port それぞれに整数を割り当て、その整数をハンドルとして扱ってアクセスしている。

当然、このような実装は寿命のハッキリしているオブジェクトにしか適用できない(GCが無いと、割り当てた整数をいつ解放すれば良いのかがわからない)が、ポートにはclose手続きがあるし、プリミティブは不変なのでこのような方法を採用できる。

というわけで、エミュレートされるヒープにprimitive?型とvmclosure?型を追加し https://github.com/okuoku/yuni/blob/20401edf1abe6b10de89fd389e0b79313396c88b/lib/yunivm/heap/fake/coreops.sls#L271 primitive?型は整数1つ、vmclosure?型はヒープオブジェクト2つ(クロージャとしての環境とコードのアドレス)を格納できるようにした。
これに対応して、VM命令のCALLは従来、オブジェクトとしてホストSchemeの手続き、つまりprocedure?を取っていたが、これをprimitive?またはvmclosure?を取れるように変更している。

applyとcall-with-values

プリミティブ手続表現の変更のついでに、プリミティブはエミュレートされるSchemeの手続きを受け取らないルールを徹底することにした。従来は、mapやfor-each等もプリミティブとして実装されていたため、プリミティブにエミュレートされるScheme手続きを渡せるようにしていた(ある種のターゲット→ホストcallback)。
このcallbackを実現するためには、エミュレートされたヒープにホストSchemeのprocedure?を置けるようにしておく必要があったが、前述のルールを徹底することで、ヒープはホストSchemeのprocedure?を扱えなくてもよくなる。
この煽りを受けるのが apply や call-with-values のような、手続きを受け取らないと機能しないがプリミティブとして実装するしか無い手続き類で、このようなプリミティブを実装できるような仕組をVMに導入した。

これらのプリミティブは一種のマクロ命令であり、実装中に(TCALLM)のようなVM命令 http://d.hatena.ne.jp/mjt/20170512/p1 が直接出ている。
一旦、これらのマクロ命令手続きは負値のプリミティブ番号を当て、他のプリミティブと区別できるようにしてみた。applyやcall-with-valuesではVMレジスタを直接改変する必要があり、他の手続きとは必要な操作が異なる。

次の一手

というわけで、ライブラリ実装は終わり(使わないのは飛ばしたけど)！
次は、いよいよC言語上での処理系の実装を見据えて:

  1. Tree IRにデバッグ情報を埋め込んでバックトレースくらいは見られるようにする
  2. Tree IRをシリアライズしてfixnum列にする方法を考える
  3. Fixnum heapの設計と実装
  4. ライブラリキャッシュの実装手法を考える
  5. REPLとかをSchemeで作る
  6. Cに移植する
  7. Ship It!

たぶん最大のトピックはFixnum heapの設計と実装だろう。今回のSECDV Schemeではヒープの実装のために3段階踏んでいる:

  • pass heap。ホストSchemeのヒープをそのまま使用する。要するにSICPのような教科書であつかうScheme-on-Schemeによくある奴。
  • fake heap。ホストSchemeのヒープにタグを付与してホストSchemeのオブジェクトなのかSECDV側のオブジェクトなのか区別ができるようにする。GCはホストSchemeのものをそのまま使用する。
  • fixnum heap。ホストSchemeのfixnum(とflonum)のvector上で実現する。GCも自前のものを実装する。C実装の完全なエミュレーション。

この3つのヒープは同じI/F(coreops)を提供する必要があり、ヒープの問題と評価器(= VM)の問題を切り分けできるように配慮している。
今回企画上の要請から、同じゲームをC、Java、C#、BASIC、...といった各種言語処理系で動かす必要があり、それぞれの処理系でそれぞれのScheme処理系を別々に用意してしまうとメンテナンスのコストが大変になってしまう。このため、Scheme上でリッチなエミュレーション実装を最初に用意し、パフォーマンスやリソース消費のシミュレーションといった解析作業はScheme上で完結できるようなプランにしている。
fixnum heapも、実際にはCやBASICの言語仕様に合わせた微妙なバリエーションは多分必要だが、先にScheme実装を用意してからターゲット言語への実装を行うようにしたい。