Ruby に >>> 演算子を実装して遊ぶ

私は Ruby ビギナーなんですが、最近ちょっとしたきっかけがあって、Ruby に興味津々です。

そこで、Ruby(MRI)をちょっとだけ改造して遊んでみました。

Ruby に貢献！みたいな良い話ではなくて、自分の手元の Ruby に対してあんまり意味のない改造を施して、楽しいね！ っていう類の話です。

ちなみに C 言語はほとんど書いたことありません。

どう遊ぶか

私はパーサーがちょっとだけ好きなので、パーサーを触ってみたいと思いました。

パーサーを触るような改造をするなら、新しい構文を追加してみるのがてっとり早そうです。その中でも二項演算子なら簡単なのではないかと考えました。

ということで、(私が日頃から書いている)JavaScript にあって Ruby にはない演算子として、>>> 演算子を実装してみることにしました。

>>> 演算子は、符号なし右シフト演算子というやつで、JavaScript とか Java とか Scala などの一部の言語にはあるらしいです。

左辺が正の値のときの挙動は普通の右シフト演算子と同じです。が、左辺が負の値のときは符号ビットが 0 になるので、結果が(デカめの)正の値になります。

なお、他のビット演算子とは違い、>>> は符号なし 32 ビット整数として結果を返します。

console.log(9 >> 2); // 2
console.log(9 >>> 2); // 2
console.log(-9 >>> 2); // 1073741821

MDN を見ればなんとなくわかると思います。

どうやって Ruby を触っていくのか

笹田耕一さん の https://github.com/ko1/rubyhackchallenge に従って進めていくと、ビルドしたりテストしたり miniruby でサクッとためして開発を始められるところまでは簡単に構築できると思います。

こういう資料が日本語で読めるのは本当にありがたいです。

この資料内では Bison についての言及がありますが、今では lrama が使われているはずなので、それは修正したほうがいいのかもしれません（ビルドステップは変わらないので、このドキュメントとしては大した問題ではない）。

また、Ruby のしくみの最初の方をチラチラ読んだりもしました。でも結果として、今回やったこととはあんまり関係ありませんでした。コンパイルとか VM 周りとか触っていないので。

パーサー

MRI のパーサーは、parse.y から生成されているので、そのファイルをいじってやれば新しい演算子を追加できそうです。

普通の右シフト演算子を参考に、同じように書く方針でいきました。

まず次のようにしてトークンを定義します(多分)。https://github.com/ruby/ruby/blob/4bbeed61346d6016e2d72818e8068bedcb9f006d/parse.y#L1526-L1527 に。

%token tURSHFT      RUBY_TOKEN(URSHFT) ">>>"

次に、BNF 風な感じで構文を定義してみます。他の演算子と同じノリで規則を追加してみます。https://github.com/ruby/ruby/blob/4bbeed61346d6016e2d72818e8068bedcb9f006d/parse.y#L2827-L2830 に。

| arg tURSHFT arg
    {
        $$ = call_bin_op(p, $1, idGTGTGT, $3, &@2, &@$);
    }

次に、通常の左右のシフト演算子と同じように優先順位を書きます。https://github.com/ruby/ruby/blob/4bbeed61346d6016e2d72818e8068bedcb9f006d/parse.y#L1579 に。

- %left tLSHFT tRSHFT
+ %left tLSHFT tRSHFT tURSHFT

次に、なんかめっちゃトーカナイザーっぽいところに雰囲気で処理を書いていきます。あんまわかってないですが、> を見つけたら、それそのものか、>= か >> だと解釈してそうな感じだったので、>>> も解釈できそうな感じにしました。https://github.com/ruby/ruby/blob/4bbeed61346d6016e2d72818e8068bedcb9f006d/parse.y#L10051-L10066 に。

case '>':
  SET_LEX_STATE(IS_AFTER_OPERATOR() ? EXPR_ARG : EXPR_BEG);
  if ((c = nextc(p)) == '=') {
    return tGEQ;
  }
  if (c == '>') {
    if ((c = nextc(p)) == '=') {
      set_yylval_id(idGTGT);
      SET_LEX_STATE(EXPR_BEG);
      return tOP_ASGN;
    }
    pushback(p, c);
+    if ((c = nextc(p)) == '>') {
+      return tURSHFT;
+    }
+    pushback(p, c);
    return tRSHFT;
  }
  pushback(p, c);
  return '>';

次に、こんな感じのやつを雰囲気で追加しました。これは本当になんだかわかりません。ここでいう ID っていうのはなんなんだろうか。https://github.com/ruby/ruby/blob/4bbeed61346d6016e2d72818e8068bedcb9f006d/parse.y#L583 あたりの話です。

TOKEN2ID(tURSHFT);

次に、こんな感じの規則も雰囲気で追加しました。これもなんだかあんまりわかってません。少なくともなんか Ripper 用の情報みたいなのを残しているみたいです。https://github.com/ruby/ruby/blob/4bbeed61346d6016e2d72818e8068bedcb9f006d/parse.y#L2580-L2594 です。

op		: '|'		{ ifndef_ripper($$ = '|'); }
                // 略
                | tURSHFT   { ifndef_ripper($$ = tURSHFT); }
                // 略
                ;

parse.y はこのように修正しました。これで動くかと思ったのですが、ビルドしてみると parse.y を C にコンパイルするときに lrama がエラーを吐きました。

そのときのエラーを正確には記録してないですが、https://github.com/ruby/lrama/blob/c4d6bf6d42fc96debad7fd2445ce44128bfa0932/lib/lrama/lexer.rb#L223 で raise されてる unknown token のエラーでした。

defs/id.def の token_ops に

  GTGTGT        >>>     URSHFT

を追加したらちゃんとパースできるようになりました。これも全然わかってないです。

全然わかってないですが、なんとかパースができるようになりました。

>>> を実装する

この時点で

-9 >>> 2

のようなコードを実行しようとすると「>>> に対応するメソッドがありません」のようなエラーが出ます。まあ実装していないので当然ですよね。

なので、numeric.c に

rb_define_method(rb_cInteger, ">>>", rb_int_urshift, 1);

のように追記して、rb_int_urshift を実装していきます。

こんな感じです。

static VALUE
fix_urshift(long val, unsigned long i)
{
    uint32_t uval = (uint32_t)val;
    return LONG2FIX(uval >> i);
}

static VALUE
rb_fix_urshift(VALUE x, VALUE y)
{
    long i, val;

    val = FIX2LONG(x);
    if (!val) return (rb_to_int(y), INT2FIX(0));
    if (!FIXNUM_P(y))
        return rb_big_rshift(rb_int2big(val), y);
    i = FIX2ULONG(y);
    if (i == 0) return x;
    if (i < 0)
        return fix_lshift(val, (unsigned long)-i);
    return fix_urshift(val, i);
}

static VALUE
rb_int_urshift(VALUE x, VALUE y)
{
    if (FIXNUM_P(x)) {
        return rb_fix_urshift(x, y);
    }
    return Qnil;
}

通常の右シフトであるrb_int_rshiftの実装を参考にしつつ、JSの>>>と同じように32ビット符号なし整数で結果が返されるように実装しました。本当はもっと良い実装方法があるんだろうなあと思いつつ、ガッとキャストしてやってます。

rb_int_rshift は Bignum のことも考慮しているみたいなんですが、今回は Fixnum のことしか考えていません。

ここまで実装したら、

-9 >>> 2

のようなコードは JS と同じように 1073741821 を返すようになりました。

テスト

テストは多分 /test/ruby/test_fixnum.rb とかに書けばいいんだろうなあと思ったので

def test_urshift
  assert_equal(0x20000000, 0x40000000 >>> 1)
  assert_equal(0x60000000, (-0x40000000) >>> 1)
  assert_equal(0x40000000, (-0x80000000) >>> 1)
end

のようなのを追加して、通ったので終わりです。

成果物

最後に、成果物の PR を載せておきます。ただ、普通によくわかってないことが多いのであんまり参考にはしない方が良いと思います。

https://github.com/sosukesuzuki/ruby/pull/1

もし、時間に余裕のある Ruby コミッターの方がいましたら、Zenn のコメントかこの PR のコメントで、私がこの記事内でよくわからないと書いている箇所等について教えてくれたらすごくうれしいです。

感想

大体雰囲気でやったのであんまりわかってないんですが、あんまりハマりどころもなく、意外と動くんだなーという感想です。もちろん、今回のケースも入力によっては簡単に壊れるかもしれないんですが...。

parse.y や lrama をもっと読み込んでいじってみたいなーと思っているのと、VM もちょっと気になっています。それなりに簡単にビルドできて、日本語情報も豊富なので楽しいです。いずれは Ruby に意味のある貢献ができたら良いですね。

これと似たような大学の課題とかは全然やる気が出ないのに、こういうあまり意味のない虚無の作業は手が止まらないのってなんなんですかね。