Ribbitを多値とapplyに対応させる
okuokuとりあえず可変長引数に対応できたので次は多値のサポートを考える。この2つはちょうど対応するもので、
- 可変長引数: 継続に多値を入力する
- 多値の返却: 継続が多値を出力する
と考えられる。前回 https://zenn.dev/okuoku/scraps/435083f4e2e991 の values の自然な定義
(define (values . v)
(call/cc (lambda (k)
(apply k v))))
は後者を現わしている。実装面では、 call-with-values values apply の実装を行うことになる。
okuokuプリミティブが多値を受けとれるようにする
まず、プリミティブがスタックに何個引数がpushされたかわかるようにする。元々のRibbitは可変長引数をサポートしていなかったので (+ 1 2 3 4) のような処理はできず、 (+ 1 2) のように必ず2引数のオペレータとして実装する必要があった。
これを、引数の個数の情報を使って可変長引数に対応させることができる。
okuoku実装計画
多値の入力は非常に多く使われる ...というか大抵の手続きは複数の入力を持つのに比較して、多値の出力は殆ど使われない ...大抵の手続きは0〜1個の値を返却するという 非対称性 が存在する。というわけで、多値の出力についてはVMに専用レジスタを設けるのではなく O(N) になっても構わないのでスタックをスキャンして実装する方針にする。
逆に、引数の個数をレジスタにしてしまったので、 apply や call-with-valuesは特殊なプリミティブとして実装する必要がある。
apply
apply は以下のように使われる。
(apply f 1 2 3 '(4 5 6)) ;; => (f 1 2 3 4 5 6)
このとき、 f を呼びだす前にはスタックに値を 1 → 2 → ... → 6 の順で積む必要がある(スタックトップが引数の末尾になる)。
call-with-values と values
RibbitのVMでは 引数の積み過ぎは問題ない という特徴がある。スタックには継続と引数の両方が積まれるが、継続とその他の値のribはフォーマットが異なっており識別が可能となっている。このため、 get-cont 処理によってスタックを単に巻き戻す処理が入っている。
これは、元の論文 https://www.iro.umontreal.ca/~feeley/papers/YvonFeeleyVMIL21.pdf で言うところの
ダークグリーンのところまでスタックを巻き戻すということを指している。(ライトグリーンの部分は list でfield2(右端)がゼロというのがpairを表現している。つまり、RibbitのVMにおけるスタックは、listで表現された引数スタックをcontinuation ribを挟んで繋げたもの と表現できる。)
よって、 EDIT: これ間違いだった。全ての values は単に何もしない手続き、 call-with-values は自分の呼出しフレームまでスタックを巻き戻して values で積まれていた多値を得る手続きとして実装できる。lambda には末尾に id の呼出しが挿入されるので、そこでスタックが巻き戻され、1値を返却することが保証される。 ...ダメじゃん。
okuoku
list->values プリミティブ
(values 1 2 3) と同じ効果を持つ、 list->values プリミティブを考える。
(values 1 2 3) ;; 呼出し後のスタックトップは #<values (1 2 3)>
(list->values '(1 2 3)) ;; 呼出し後のスタックトップは #<values (1 2 3)>
(#<values (1 2 3)> は多値を表わす専用の基本型)
このプリミティブがあると apply は call-with-values で実装できる。
(define (apply1 f lis) ;; 実際のapplyは追加の引数を持てるがここでは一旦無視する
(call-with-values (lambda () (list->values lis))
f))
(普通のSchemeでは list->values は (apply values lis) として実装できるが、apply を実装しようとしている現状ではこれは使えない。言い換えれば、 list->values は values 専用の apply 手続きとも言える。)
プリミティブは可能な限り少い方が良いので、これで apply の実装をサボろうと思う。 list->values の方は call/cc の実装でも使うし。
okuoku
call-with-values を実装
結局
valueslist->valuesapply-values
の3つのプリミティブを実装した。 (apply-values f v) は、valuesオブジェクトまたは単値 v を引数として f を呼ぶ。
このやりかたがベストなのかはちょっと自信がない。というか apply-values は call/cc と同様にライブラリ手続きとして実装できるはず(原理的には)。