Zenn
Open6

Ribbon: 自作Schemeインタプリタのテストを通す

okuokuokuoku

とりあえず非常に小さなテストが通る程度まで実装を進めた

https://github.com/okuoku/ribbon/commit/f16f866c3e6bac07758bf493df537995254845ca

... 既にソースコードが100KiBとか超えてるんですけど。。もうちょっと段階踏むべきだろ。。しかも既にこれだけでかいのにreaderはScheme側に載っているため、別のScheme処理系でコンパイルしてやらないとSchemeプログラムを実行できない。

(いきなり実装がでかくなるのは、RibbonがそもそもPythonやRubyのようなリッチな動的型言語でScheme処理系を実装しようという企画なのに、それらが無いCで実験を始めてしまったため。これはマジで失敗したと思った。)

とりあえず手元のテストにざっと掛けてみたところ、 values の実装がバグってて動かない以外は多少動いた。まだGC無いけど。

okuokuokuoku

values0 

Test: 2/4 passed.

Failed:
    [a]  Expected: ok  Actual: (ok ok)
    [b]  Expected: (ok)  Actual: ()

テストに失敗しているのはココ。

https://github.com/okuoku/yuni/blob/4358d94c76fac52f0baca7b0f5424cb803f1595a/tests/scheme/values0.sps#L15-L19

つまり (a . b) の b に値が渡せず、 a に寄ってしまっている。多値の処理部分にデバッガでブレークポイントを張りステップ実行( next コマンドのちEnter連打)してみると、そもそも多値オブジェクトになっていない(ただのリスト)になっていることがわかった。

(gdb) p *values.value.as_rib
$2 = {header = {gc_prev = 0x0, gc_next = 0x0, gc_refinfo = 0}, field = {{
      as_int64 = 34360384272, as_double = 1.697628544669909e-313,
      as_char = 645904, as_zone0 = 645904, as_rib = 0x80009db10,
      as_vector = 0x80009db10, as_string = 0x80009db10,
      as_bytevector = 0x80009db10, as_hashtable = 0x80009db10}, {
      as_int64 = 34363935920, as_double = 1.6978040193962011e-313,
      as_char = 4197552, as_zone0 = 4197552, as_rib = 0x800400cb0,
      as_vector = 0x800400cb0, as_string = 0x800400cb0,
      as_bytevector = 0x800400cb0, as_hashtable = 0x800400cb0}, {as_int64 = 0,
      as_double = 0, as_char = 0, as_zone0 = ZZ_NIL, as_rib = 0x0,
      as_vector = 0x0, as_string = 0x0, as_bytevector = 0x0,
      as_hashtable = 0x0}}, type = {VT_RIB, VT_RIB, VT_INT64}}

type = {VT_RIB, VT_RIB, VT_INT64} より、ribの3要素目はint、その値はゼロなのでこのオブジェクトはpairであることがわかる。

https://github.com/okuoku/yuniribbit-proto/blob/ce52ed86d0d8f3ed5f2dc7e717b6adb9efbacc5a/yuniribbit/heapcore.sls#L41

... values 手続きで値をwrapしてないじゃないか。。

https://github.com/okuoku/ribbon/commit/6f50e68653f04584fb83eb403f778bcc510b056e#diff-ca89adcc14a67bc76b9fe79e3a80cc2b6c9f33e6feb0c5de49cdecdffdc690d7R659-R687

クッソしょぼいミス。

Test: 4/4 passed.
okuokuokuoku

strings0 

Test: 73/74 passed.

Failed:
    [(string-append "a" (string #\b))]  Expected: "ab"  Actual: "ba"

えぇ...

引数はスタックに逆順で積まれるため、処理も後ろからやる必要がある。

diff --git a/c-proto/prims.inc.h b/c-proto/prims.inc.h
index a2cf49f..d7d2054 100644
--- a/c-proto/prims.inc.h
+++ b/c-proto/prims.inc.h
@@ -3079,12 +3079,12 @@ ExVecAppend(RnCtx* ctx, int argc, Value* stack){
     s = (char*)malloc(total);
 
     /* Pass2: Pop args and generate total string */
-    loc = 0;
+    loc = total;
     for(i = 0; i != argc; i++){
         RnRibRef(ctx, &tmp, stack, 0);
         RnRibRef(ctx, stack, stack, 1);
+        loc -= tmp.value.as_string->len;
         memcpy(&s[loc], tmp.value.as_string->str, tmp.value.as_string->len);
-        loc += tmp.value.as_string->len;
     }
     RnString(ctx, &tmp, s, total);
     free(s);

https://github.com/okuoku/ribbon/commit/ea88d83d4422318728d650800a1dd7e9a3e239e3

okuokuokuoku

bytevectors0 

Test: 25/26 passed.

Failed:
    [(utf8->string (bytevector 97 98 99) 1 2)]  Expected: "b"  Actual: ""

... いくらなんでもこれは酷いんじゃないか。。？

diff --git a/c-proto/prims.inc.h b/c-proto/prims.inc.h
index d7d2054..a79ed42 100644
--- a/c-proto/prims.inc.h
+++ b/c-proto/prims.inc.h
@@ -761,7 +761,7 @@ ExUtf8ToString_3_1(RnCtx* ctx, Value* out, Value* bv, Value* start, Value* end){
         abort();
     }
     istart = start->value.as_int64;
-    iend = start->value.as_int64;
+    iend = end->value.as_int64;
     if(istart < 0){
         abort();
     }

https://github.com/okuoku/ribbon/commit/17bb2ed056405448b2b3f694dc79fc681e4d9681

okuokuokuoku

miniread0

さぁ本番だ。。最小ケースは

(import (yuni scheme)
        (yuni miniread reader))

(utf8-read (string->utf8 "\"abcd\""))

これで、読み取り時に (utf8->string bv 1 -3) が実行されてクラッシュする。これは文字列中の abcd を取り出すための処理なので、本来は (utf8->string bv 1 4) でなければならない。なので整数演算が怪しいな。。

diff --git a/lib/yuni/miniread/reader.sls b/lib/yuni/miniread/reader.sls
index 55d8f07..2f44d69 100644
--- a/lib/yuni/miniread/reader.sls
+++ b/lib/yuni/miniread/reader.sls
@@ -19,11 +19,13 @@
 (define (%realize-string-raw bv start end)
   ;; FIXME: really confusing API..
   ;; R7RS
+  (write (list 'REALIZE-STRING-RAW start end)) (newline)
   (utf8->string bv start (+ 1 end)))

 (define (%realize-string-fastpath bv start cur end)
   (cond
     ((= cur end)
+     (write (list 'REALIZE-STRING-CALL start end)) (newline)
      (%realize-string-raw bv (+ start 1) (- end 1)))
     ((= 92 (bytevector-u8-ref bv cur))
      #f)

デバッグprintを入れると、

(REALIZE-STRING-CALL 0 5)
(REALIZE-STRING-RAW 1 -4)

つまり (- end 1) の実装がおかしいな。(- 5 1) が -4 になっている。... 引数がスタックに 逆順 に積まれてるのを忘れてるな。不正確数のテストからいくつか抜粋してくると:

Failed:
    [(- 5 1)]  Expected: 4  Actual: -4
    [(< 1 2)]  Expected: #t  Actual: #f
    [(> 1 2)]  Expected: #f  Actual: #t
    [(>= 1 2)]  Expected: #f  Actual: #t

比較も逆順になってしまっている。 ... この状況でよく動いてんな。。

https://github.com/okuoku/ribbon/commit/28b426133fecf0741b529d43ab45aeab9412ba11

https://github.com/okuoku/ribbon/commit/96db77ba3d348a4897f13fd285563e3b755cbc6d

Test: 12/13 passed.

Failed:
    [(> 3 3)]  Expected: #f  Actual: #t

... 条件を反転させるんだから = も反転させないとダメか。。

https://github.com/okuoku/ribbon/commit/c568c49e864693aa2501e1a238dd56cda8986fec

これで一番の大物のテストが通ったと言える。。

okuokuokuoku

遅い

前試したreaderのテストを実装したインタプリタで実行してみた。

https://zenn.dev/link/comments/9a2510792f97ed

  • -O0
real    0m4.380s
user    0m3.937s
sys     0m0.421s
  • O2
real    0m1.693s
user    0m1.359s
sys     0m0.296s

Gauche上のインタプリタで13sec → 最適化したC実装(GCなし)で 2sec 。。。せめて10倍は早くなってくれないと困るんだけど、まぁVMコンパイラ側の最適化が無いとインタプリタを多少最適化したところで常識的な速度にはならないからなぁ。。そしてChez Schemeには普通に負けている。Chez Scheme上でSchemeで書いたVMの方が、C(gcc -O2)で愚直に書いたVMより早い。

Gaucheで同じreaderを動かした場合は 0.4 秒なので、Scheme処理系としてはGaucheの4倍強遅いということになる。これくらいは予想の範疇ではあるけど。

断腸の思いで一旦ステートマシンを手書きしちゃおうかな。。