Zenn
Open5

Ribbitを可変長引数に対応させたい

okuokuokuoku

Ribbitの元の論文( https://www.iro.umontreal.ca/~feeley/papers/YvonFeeleyVMIL21.pdf )では、可変長引数手続きへの対応は特に実施していない。一応、論文にはそのことへの言及はある。

Variadic Procedures

The Scheme language supports creating variadic procedures that receive the rightmost arguments in the form of a list, the rest parameter. Some common standard procedures such as +, append, and map, are often called with exactly two arguments in practice but can take a different number of arguments when necessary.

Variadic procedures could be implemented in the RVM by passing the argument count on the stack and constructing the rest parameter on entry to the procedure. They could also be implemented without changing the RVM by adopting a calling convention that passes parameters using a Scheme list. Both of these approaches would negatively impact the system’s footprint so variadic procedures are not currently supported by Ribbit.

現実的なSchemeの処理系としては無いと割と困るので何とか対応させたい。

後者のような方法だと、自然な方法で values のような手続を実装できなくなるので、何とか絶妙な方法を考えないとな。。

自然な values

元の論文では、Ribbitでの call/cc を以下のように定義している:

(define (call/cc receiver)
  ;; first get call/cc's continuation rib "c"
  (let ((c (field1 (field1 (close #f))))) ;; ← ★ close はVMのスタックに直接アクセスできるプリミティブ
    (receiver
      (lambda (r) ;; ← ★ この lambda がcall/ccで得られる継続オブジェクトになる
        ;; get current continuation rib "c2"
        (let ((c2 (field1 (field1 (close #f)))))
          (field0-set! c2 (field0 c)) ;; set "stack" field
          (field2-set! c2 (field2 c)) ;; set "pc" field
          r))))) ;; return to continuation of call/cc

しかし、この定義だと、継続は高々1つの値しか取れない。

一般に values 手続きは以下のように定義でき、

(define (values . v)
  (call/cc (lambda (k)
             (apply k v))))

最後の (apply k v) で使われる手続きが可変長引数に対応できなければ多値を渡せないことになる。

この一般的な values の定義を元に先の call/cc を書き直すと、

(define (call/cc receiver)
  ;; first get call/cc's continuation rib "c"
  (let ((c (field1 (field1 (close #f)))))
    (receiver
      (lambda r ;; ← ★ 任意長の引数を取れるようにする
        ;; get current continuation rib "c2"
        (let ((c2 (field1 (field1 (close #f)))))
          (field0-set! c2 (field0 c)) ;; set "stack" field
          (field2-set! c2 (field2 c)) ;; set "pc" field
          (apply values r)))))) ;; ← ★ ここで無限再帰になる

継続の呼出しが発生した場合に無限再帰になってしまう。このため、多値が存在する場合は call/cc が通常の lambda で表現できないことになり、何かしら専用のプリミティブが必要になることがわかる。

okuokuokuoku

作戦を考える

論文と実装をナナメ読みしたところ、論文で言うところの最初の戦略、つまり

Variadic procedures could be implemented in the RVM by passing the argument count on the stack and constructing the rest parameter on entry to the procedure.

を実装するのが良さそうだと思った。が、これだけだと呼出しが不正だったときにエラーにできないので、

  1. 呼出し時に引数の数をスタックに積むようにする (★ 以降 argc と呼ぶ)
  2. 手続きオブジェクトに記録されている期待する引数の数(論文だと nparams 、Scheme実装だと nargs)との突き合せを行う
  3. 負値の nparams を使って、可変長引数の有無を記録する

の3点を実装する。最後のはちょっとわかりづらいが、

nargs lambda の仮引数
3 (a b c)
2 (a b)
1 (a)
0 ()
-1 a
-2 (a . b)
-3 (a b . c)

のように、可変長引数を持つ場合を負数で表現する。

元々のRibbitのコードでは、呼出された側の nargs の数だけstackからpopするコードになっているが、可変長引数がある場合は調整が必要になる。

(nargs >= 0 の場合)

  1. nargs != argc だったらエラーにする
  2. argc 回 stackからpopする

(nargs < 0 の場合)

  1. (-1 - nargs) < argc だったらエラーにする -- 可変長部分の長さがゼロになる nargs = -3 argc = 2 のケースは正当なのに注意
  2. argc - (-1 - nargs) 回stackからpop、リストにして可変長部分の引数にする
  3. (-1 - nargs) 回 stackからpopする

命令列のシリアライズへの対応

EDIT: ↓ に書いたように、そもそも命令列のシリアライズ自体をやらない方向で修正したのでこの配慮は要らなくなった

Ribbitではコンパイルした命令列を専用のフォーマットでシリアライズしているが、これが負値を表現できないため専用のエンコードが別途必要になる。

nargs のエンコードは

(define const-proc-short  4) ;; 0 <= N <= 3  are encoded with 1 byte

にあるように、 0..3 とそれ以外でエンコード方法が異なっていて、 nargs > 3 の場合は通常の正の整数としてエンコードしている。このため、 nargs を以下のように事前にエンコードすることにする。

  • 0..3 の場合、そのまま
  • 4以上の正値の場合、2倍にする
  • -1 以下の場合は-2倍して+1

これにより、エンコードされた数が8以上、かつ、偶数であれば元は正の数、奇数であれば負値の絶対値ということがわかる。 4..7が使われないのはちょっともったいないが、傾向的にそこを使わないといけないようなシチュエーションはあんまり思いつかない。

新規に追加する argc の方は絶対に正またはゼロの値になるため特別な対応は必要ない。

okuokuokuoku

enter 命令を追加

https://github.com/okuoku/yuniribbit-proto/commit/cdd8bfcddbb7a8171cb09dbc0c207d614b67c903

とりあえず、VMに enter 命令を追加し、 lambda をcallするときに積んだ引数の数を通知できるようにしてみた。

... ついでにVM命令列をBase94でエンコードする機能も一旦削除したが、どうもこのエンコード/デコードの過程でグローバルシンボルの解決等も一緒にやってしまう仕組みになっているらしく(超かしこい)、相当な量の変更をすることになってしまった。。

今回は、VM上で動作するプログラムがシンボルをinternした場合にグローバル変数 symtbl を更新することを利用して、 (eqv? <ホスト言語のシンボル> <VM上のribで表現されるシンボル>) => #t が正常に動作するように配慮している。

また、Ribbit VMのシンボルは古き良きLispの "値フィールドのあるシンボル" なため、それをエミュレーションする仕組みも追加している。