本記事はリンクアンドモチベーション Advent Calendar 2023の24日目です。
はじめに
バックエンドエンジニアのやまぴーと申します。
タイトル通り、作ってみたら「完全に理解した」から「なにもわからない」に近づけた気がするので、書いてみます。
「完全に理解した」
製品を利用をするためのチュートリアルを完了できたという意味。「なにもわからない」
製品が本質的に抱える問題に直面するほど熟知が進んだという意味。「チョットデキル」
同じ製品を自分でも１から作れるという意味。または開発者本人。
エンジニアの言う「完全に理解した」「なにもわからない」「チョットデキル」って本当はこういう意味？「わかる」の声多数 - Togetter
きっかけ
マニュアルのこの文章が気になったのがきっかけです。
注意
外部イテレータとしての機能は Fiber を用いて実装されているため Fiber と同じ制限があります。例えば以下のようなスレッドをまたいだ呼び出しはエラーになります。
class Enumerator (Ruby 3.2 リファレンスマニュアル)
なんとなくできそうなのは分かるのですが、コールグラフを考えると頭がこんがらがっちゅれーしょんでした。
なので、実際に作って理解しようと考えた次第です。
まずは、EnumeratorとFiberについてそれぞれ「完全に理解した」を確認します。
Enumerator 「完全に理解した」
いくつかの使いどころが思い浮かびますが、Enumeratorの基本的な役割は外部イテレータと言って良いと思います。
外部イテレータというのは、内部イテレータと対になる言葉です。
前者はループの進め方を外部から指示する必要がありますが
後者は仕組みの内部に隠蔽されているという違いがあります。
例えば
[1, 2, 3].map { |e| e * 2 } #=> [2, 4, 6]
こういうよくあるコードの時には、ループを次に進める指示は特に与えていないのに対して
外部イテレータでは次に進める指示を与える必要があります。
enum = [1, 2, 3].to_enum #=> #<Enumerator: ...>
enum.next #=> 1
enum.next #=> 2
enum.next #=> 3
そんな面倒なものを一体いつ使うのかという感じなのですが、もっと複雑な問題の時に効率よく書けたり簡単に書けたりすることがあります。
例えば、ループを進めている間に、その時々の状況によって異なる数の要素をまとめて扱いたい様な場合がそうです。
次のコードは超適当に書いてたJSONパーサの一部なのですが
先頭行で、Enumeratorをitrに格納した後、次に来る文字が数字なら続く数字をitr.nextで全て取り出したりしてまとめたJSONTokenオブジェクトをyieldしています。
itr = @str.each_char
loop do
c = itr.next
next if c == " "
if c == "{"
yield JSONToken.new(JSONToken::T_LPAREN, "{")
elsif c == "}"
yield JSONToken.new(JSONToken::T_RPAREN, "}")
elsif c == ":"
yield JSONToken.new(JSONToken::T_COLON, ":")
elsif c == '"'
buf = ""
while itr.peek != '"'
buf << itr.next
end
yield JSONToken.new(JSONToken::T_STR, buf)
itr.next
elsif c =~ /[0-9]/
buf = c
while itr.peek =~ /[0-9.]/
buf << itr.next
end
yield JSONToken.new(JSONToken::T_NUM, buf)
end
要するに、外部イテレータは面倒さと引き換えに、柔軟性の高いループ操作を実現できるという感じです。
この機能がベースとなって、Enumeratorで様々なコレクション操作を容易に組み合わせることができます。Enumerator自体もEnumerableを実装しているからです。これも例を出して簡単に確認していきます。
sexy_primes = Prime
.each_cons(2) #=> #<Enumerator: ...>
.lazy #=> #<Enumerator::Lazy: ...>
.filter { |a, b| a + 6 == b } #=> #<Enumerator::Lazy: ...>
sexy_primes.first #=> [23, 29]
隣り合う2つの素数の差が6の時にその2つをセクシー素数と呼ぶらしいのですが
#each_cons(2)は隣り合う2つの要素を列挙するEnumeratorを返却するので
続けて更なるコレクション操作を指示することができます。
で、差が6の組み合わせを絞るために#filterが後ろに控えているのですが
その前に#lazyを指定しています。これは、そうしないとプログラムが終了しないからです。
なぜなら
-
Primeは無限に素数を列挙してくれる -
#filterは全ての要素についてループ処理を行い、Arrayを返却しようとする
からです。
#lazyを呼ぶとEnumerator::LazyというEnumeratorの異なる実装が返却されます。
この実装は可能な限りループの評価を遅らせようとして、したがって#filterはArrayではなくEnumerator::Lazyを返却してくれる様になります。
最初に#firstが呼ばれたタイミングでようやく重い腰を上げて最初の要素だけ評価するわけです。
こういったことも、Enumeratorが外部イテレータとしての機能を持っているからだと言っていいんじゃないでしょうか。たぶん。
（まあ、別に外部イテレータでないといけないわけではないですが、実装する上で楽にはなっていると思います。。たぶん。）
ところで、Enumeratorは他にも次の様な方法でも作成することができます。記事の後半、作って理解するパートに出てくるので軽く紹介しておきます。
enum = Enumerator.new { |y| y.yield 1; y.yield 2 }
enum.next #=> 1
enum.next #=> 2
Fiber「完全に理解した」（？）
Fiberについては、あまり自信ないですがせめて簡単には触れたいです。
マニュアルには次の様に書いてあります。
ノンプリエンプティブな軽量スレッド(以下ファイバーと呼ぶ)を提供します。他の言語では coroutine あるいは semicoroutine と呼ばれることもあります。
class Fiber (Ruby 3.2 リファレンスマニュアル)
この説明でうんうんとなれば苦労しないのですが、それは既に理解している人な気がして複雑な気持ちです。うーん。
coroutineのco-は協調するとかそういう感じの接頭語ですから、「協調するルーチン」という意味で解釈できます。
何がどう協調するのかというと、つまるところ「いったりきたり」できます。
同じマニュアルページから例を引用します。
f = Fiber.new do
n = 0
loop do
Fiber.yield(n)
n += 1
end
end
5.times do
p f.resume
end
#=> 0
1
2
3
4
このコードは次の要領で動きます。
- 最初に
Fiber#resumeを呼ぶとFiber.newのブロックの実行が始まります。 - そして
Fiber.yieldが呼ばれると、Fiber#resumeの直後に戻ってきます（！） - 再度
Fiber#resumeが呼ばれると、Fiber.yieldの直後に戻ってきます（！？）
面白いのは、互いの引数はもう一方の返却値となることです。
上記のコードでは0〜4が順に表示されます。
「完全に理解した」というにはちょっと簡単でしょうか？まあ、だいたいできましたよね ^^; よーし。。
作って理解する
ここから本題なのですが
実際にEnumeratorがFiberで動いていることを、Rubyで再実装していくことで理解したいと思います。
CRubyのC言語で実装されたEnumeratorを良く読んだ上で、同じ様に動くREnumeratorを実装していきます。（RはRubyで実装したよの意味）
ruby/enumerator.c at v3_2_2 · ruby/ruby
で、実は一旦がーっと書いたのですが、「あっこれ説明も理解もできないサイズだな。。」と思いました笑
なので、いくつかの差分に分解しつつ、あたかもちょっとずつ実装した風を装っていこうと思います。
説明の都合上、どうしても自分で考えた風に読めてしまうかもしれませんが、基本的に全部CRubyの実装をマネしていて後から差分の形に分割してみただけです。
とはいえ、これがCRuby通りの実装だと捉えられてしまうのはそれはそれで不安なので、大変身勝手な言い分ですが、まああくまでコンセプトを理解しようとしているんだなという感じで捉えていただけると幸いです。
ステップ1. .newと#next_valuesを実装
まず、.newと#next_valuesを作ります。
前半を読んで下さった方は「next_valuesって何？nextは？」だと思うんですが
nextは次のステップ2でnext_valuesを利用する形で実装します。
細かい違いはそこで明らかになるのですが、とりあえず常に配列で返してくる#nextという理解で大丈夫です。
require 'pp'
def assert_equal(expected, actual)
return if expected == actual
puts "#{expected.pretty_inspect} expected, but got #{actual.pretty_inspect}."
end
class REnumerator
class Yielder
def initialize(&block)
@proc = block
end
def yield(*args)
@proc.call(*args)
end
end
def initialize(&block)
@proc = block
end
def next_values
@fib ||= Fiber.new { @proc.call(Yielder.new { |*args| Fiber.yield(args) }) }
@fib.resume
end
end
# REnumerator#next_values
assert_equal([1], REnumerator.new { |y| y.yield 1 }.next_values)
少ないサイズながら、今回の目的であるFiberの使い方の理解はほぼこれだけで達成できます。残りのステップはオマケみたいなものです。
冒頭のassert_equal(expected, actual)は名前の通りですが、2引数が同値であることをテストするメソッドです。
最終行でREnumerator#next_valuesが[1]を返却することをテストしている訳です。今後、テストコードは一番下に付け足していきます。
間に挟まれたのがREnumeartorで、その定義の中にREnumerator::Yielderというクラスの定義があります。
さて、サイズに反して相当ややこしいのですが、テストコードから出発すると良い感じで読めます。
assert_equal([1], REnumerator.new { |y| y.yield 1 }.next_values)
ブロックのパラメータyには実引数としてYielderのインスタンスが与えられます。
そしてy.yieldが呼ばれるとなんやかんやしてFiber.yieldが呼ばれます。
その様子は、next_valuesの実装を中心にして理解できます。
def next_values
@fib ||= Fiber.new { @proc.call(Yielder.new { |*args| Fiber.yield(args) }) }
@fib.resume
end
進みかたは、こんな感じです。
REnumerator#next_values
-> Fiber#resume
-> Fiber.newのブロック
-> REnumerator.newのブロック
-> Yielder#yield
-> Fiber.yield （引数argsがFiber#resumeとREnumerator#next_valuesの返り値になる）
ステップ2. #nextを実装
というわけで、次が#nextです。
@fib ||= Fiber.new { @proc.call(Yielder.new { |*args| Fiber.yield(args) }) }
@fib.resume
end
+
+ def next
+ vs = next_values
+ vs.count <= 1 ? vs.first : vs
+ end
end
-# REnumerator#next_values
+# REnumerator#next_values, #next
assert_equal([1], REnumerator.new { |y| y.yield 1 }.next_values)
+assert_equal(1, REnumerator.new { |y| y.yield 1 }.next)
+assert_equal([1, 2], REnumerator.new { |y| y.yield 1, 2 }.next_values)
+assert_equal([1, 2], REnumerator.new { |y| y.yield 1, 2 }.next)
（たぶんこのロジックで合っていると思うのですが。。）
複数の要素が返却された時はそのまま、0個か1個の時は先頭（0個ならnil）が返却されます。
#nextと#next_valuesの違いは、マニュアルに分かりやすい表があったので引用します。
## yield args next_values next
# yield [] nil
# yield 1 [1] 1
# yield 1, 2 [1, 2] [1, 2]
# yield nil [nil] nil
# yield [1, 2] [[1, 2]] [1, 2]
Enumerator#next_values (Ruby 3.2 リファレンスマニュアル)
で、その違いはここで吸収している感じです。
def next
vs = next_values
vs.count <= 1 ? vs.first : vs
end
ステップ3. #peek_values と #peek を実装
次の要素を覗き見る（値は取得するが、繰り返し呼んでもループの進行はしない）機能を作成します。
こちらも先程と同様に#peek_valuesと#peekとが存在します。
まずはテストコードなのですが、前半は#nextの方と全く同じです。
assert_equal(1, REnumerator.new { |y| y.yield 1 }.next)
assert_equal([1, 2], REnumerator.new { |y| y.yield 1, 2 }.next_values)
assert_equal([1, 2], REnumerator.new { |y| y.yield 1, 2 }.next)
+
+# REnumerator#peek_values, #peek
+assert_equal([1], REnumerator.new { |y| y.yield 1 }.peek_values)
+assert_equal(1, REnumerator.new { |y| y.yield 1 }.peek)
+assert_equal([1, 2], REnumerator.new { |y| y.yield 1, 2 }.peek_values)
+assert_equal([1, 2], REnumerator.new { |y| y.yield 1, 2 }.peek)
+
+# REnumerator look-ahead
+enum = REnumerator.new { |y| y.yield 1, 2 }
+enum.peek
+assert_equal([1, 2, 3], enum.peek << 3) # cached & copied
+assert_equal([1, 2], enum.next) # cached
後半では、繰り返し#peekを呼んだり、返却値を書き換えても影響がないことを確認しています。
cachedやcopiedとコメントしていたのは、一度覗き見た値を保持して再利用していたり、保持した値に対する変更が残らない様にコピーしていたりするので、その検査であることのメモです。
実装の差分と併せて確認すると、分かると思います。
vs = next_values
vs.count <= 1 ? vs.first : vs
end
+
+ def peek_values
+ return @lookahead if defined?(@lookahead)
+
+ @lookahead = next_values
+ end
+
+ def peek
+ vs = peek_values
+ vs.count <= 1 ? vs.first : vs.dup
+ end
end
# REnumerator#next_values, #next
@lookaheadは、CRubyのEnumerator実装では対応する構造体のメンバとして存在していたものです。
nilかどうかではなく未定義かどうかでキャッシュの存在を判定しているのはその実装の通りなのですが、列挙される値がnilだった場合に区別が付かないからだと考えられます。（というかそのテスト書けば良かった〜）
#next_valuesが呼ばれた際、これを未定義に戻す必要があるのですが
インスタンス変数で管理しているため、remove_instance_variableを呼ぶというちょっと不恰好な感じになっています。CRubyの実装では、未定義状態に対応する値を代入するだけなのですが。
end
def next_values
+ if defined?(@lookahead)
+ vs = @lookahead
+ remove_instance_variable(:@lookahead)
+ return vs
+ end
+
@fib ||= Fiber.new { @proc.call(Yielder.new { |*args| Fiber.yield(args) }) }
@fib.resume
end
ステップ4. Object#to_renum と Object#renum_for を実装
次はObject#to_enumとObject#enum_forなのですが
REnumeratorを返す別のメソッドとしてrを付けて#to_reunmと#renum_forとします。
記事前半の説明でもさりげなく使っていた#to_enumなのですが、#enum_forも全く同じ働きをします。
呼ぶと、そのオブジェクトの#eachメソッドを基にしたEnumeratorが生成されるという便利なやつです。（引数で#each以外も指定できるのですが、次のステップでやります。）
テストコードはコンパクトです。
enum.peek
assert_equal([1, 2, 3], enum.peek << 3) # cached & copied
assert_equal([1, 2], enum.next) # cached
+
+# Object#to_renum, #renum_for
+assert_equal([1], [1].to_renum.next_values)
+assert_equal([1], [1].renum_for.next_values)
が、実装にはちょっとしたリファクタが必要になります。
Object#to_enumで生成された場合、列挙する処理はレシーバとなるオブジェクトに委譲できる様にしたいのですが、その為には今までのREnumerator.newで生成したインスタンスの場合にもダミーとなるオブジェクトを用意するとすっきり書けます。
(もちろん、これもCRubyのマネしているだけですが、綺麗で感動しました。まあこういう順番や意図で導入されたものかは確認していないですし、しても分からないかもなのですが。)
そのダミーが、下記のREnumerator#Generatorです。本物にも同名のクラスがあります。
end
end
- def initialize(&block)
- @proc = block
+ class Generator
+ def initialize(&block)
+ @proc = block
+ end
+
+ def each
+ @proc.call(Yielder.new { |*args| yield(*args) })
+ end
+ end
+
+ def initialize(obj: nil, &block)
+ @obj = obj || Generator.new(&block)
end
def next_values
return vs
end
- @fib ||= Fiber.new { @proc.call(Yielder.new { |*args| Fiber.yield(args) }) }
+ @fib ||= Fiber.new { @obj.each { |*args| Fiber.yield args } }
@fib.resume
end
コンストラクタでキーワード引数obj:を用意して委譲先のオブジェクトを受けられる様にしています。
本物のEnumeratorにはない引数ですが、ここは妥協しました。
CRubyでは対応する構造体のメンバに初期化時に格納して管理しているのですが、Rubyでここを誤魔化すのは良い方法が思い付かなかったです。
あとは使うだけです。
end
end
+class Object
+ def to_renum
+ REnumerator.new(obj: self)
+ end
+
+ alias renum_for to_renum
+end
+
# REnumerator#next_values, #next
assert_equal([1], REnumerator.new { |y| y.yield 1 }.next_values)
assert_equal(1, REnumerator.new { |y| y.yield 1 }.next)
ステップ5. #each以外のメソッドでも使える様にする
前のステップで説明した通り、Object#to_enumには#each以外のメソッドを指定することもできます。
#each_with_indexでテストすることにします。
# Object#to_renum, #renum_for
assert_equal([1], [1].to_renum.next_values)
assert_equal([1], [1].renum_for.next_values)
+assert_equal([42, 0], [42].to_renum(:each_with_index).next)
またまた、本物には存在しないコンストラクタの引数を増やしてしまいましたが、それはそれとして特に難しいことはないです。
end
end
- def initialize(obj: nil, &block)
+ def initialize(obj: nil, method: :each, &block)
@obj = obj || Generator.new(&block)
+ @method = method
end
def next_values
return vs
end
- @fib ||= Fiber.new { @obj.each { |*args| Fiber.yield args } }
+ @fib ||= Fiber.new { @obj.send(@method) { |*args| Fiber.yield args } }
@fib.resume
end
end
class Object
- def to_renum
- REnumerator.new(obj: self)
+ def to_renum(method = :each)
+ REnumerator.new(obj: self, method: method)
end
alias renum_for to_renum
ステップ6. Array#each が REnumerator を返す様に再定義する
後から考えるとEnumeratorの理解とはあまり関係ないですが、やれるかなーと思ってやってみました。
assert_equal([1], [1].to_renum.next_values)
assert_equal([1], [1].renum_for.next_values)
assert_equal([42, 0], [42].to_renum(:each_with_index).next)
+
+# Array#each
+assert_equal([1], [1].each.next_values)
+assert_equal([1], [1].map(&:itself))
ブロックを与えて呼ぶ場合は今まで通りの実装を使用して欲しかったので、一旦エイリアスを定義して新しい#eachの定義の中で利用する様にしました。（忘れましたが、どこかで聞いた手法です。）
alias renum_for to_renum
end
+class Array
+ private alias_method :_orig_each, :each
+
+ def each(&block)
+ block ? _orig_each(&block) : to_renum
+ end
+end
+
# REnumerator#next_values, #next
assert_equal([1], REnumerator.new { |y| y.yield 1 }.next_values)
assert_equal(1, REnumerator.new { |y| y.yield 1 }.next)
#_orig_eachは残ってしまうのですが、これは非公開にするだけで妥協しました。
たぶん何か良い方法があるのでしょうが。。
ステップ7. Enumerable を include する
最後に REnumerator自身をEnumerableとして振るまえる様にして幕を閉じようと思います。
REnumerator#eachを定義して、includeすれば良いはずです。
テストコードは次の様になります。
# Array#each
assert_equal([1], [1].each.next_values)
assert_equal([1], [1].map(&:itself))
+
+# REnumerator#each
+assert_equal([1, 2], REnumerator.new { |y| y.yield 1; y.yield 2 }.each.to_a)
+assert_equal([1, 2], [1, 2].each.to_a)
REnumerator#eachを直接利用するテストと、includeしたEnumerableのメソッドである#to_aを利用するテストの両方を書いています。
さて、実装は#eachを定義するのは勿論なのですが、それはこれまでFiber.newのブロックに書いていた一部を移動するようにして作成できます。
return vs
end
- @fib ||= Fiber.new { @obj.send(@method) { |*args| Fiber.yield args } }
+ @fib ||= Fiber.new { each { |*args| Fiber.yield args } }
@fib.resume
end
vs = peek_values
vs.count <= 1 ? vs.first : vs.dup
end
+
+ def each(&block)
+ return self unless block
+
+ @obj.send(@method, &block)
+ end
end
class Object
Fiber.newからは代わりに#eachを呼ぶ形になっています。CRubyの実装が同じ様に#eachを呼んでいるのを読んで、最初は少し？？？だったのですが、分かってきたらなるほどーってなりました。これなら直接#eachに任意のブロックを渡されても大丈夫です。
あとはincludeするだけです。
end
end
+ include Enumerable
+
def initialize(obj: nil, method: :each, &block)
@obj = obj || Generator.new(&block)
@method = method
これでだいぶ本物のEnumeratorらしくなりました。書いてみて面白かったところもさらえた気がします。
おわりに
「完璧に理解した」を超えるアプローチとして再実装するというのはよくやっているのですが、今回は学びや感動も多くあったので、この機会に記事にできて良かったです。
特に学びのあった箇所を抜粋しましたが、他にも下記にトライしていました。
-
#rewindの実装 -
#sizeの実装 -
.newの残りの引数の取り扱い -
StopIteration例外の発行
あまり細かく色々書くとよく分からなくなりそうだったので省いてしまいました。委譲（転送？）する感じの時にキーワード引数も渡すのとかも、まあいいかとざっくり消していたりします。
さて、CRubyの実装については分かった様に書いていますが、実際のところそんなにちゃんとは読めておらず、まさに「なにもわからない」に近いです。上記以外にも気付いていない違いは多数あると思います。
何となく名前で類推しちゃったところもあるので、あくまでも参考程度にお願いします。誤りに気付かれた方は是非ご指摘いただきたいです。
ステップ7までのコード全文は下記に畳んでいれておきます。
コード全文
require 'pp'
def assert_equal(expected, actual)
return if expected == actual
puts "#{expected.pretty_inspect} expected, but got #{actual.pretty_inspect}."
end
class REnumerator
class Yielder
def initialize(&block)
@proc = block
end
def yield(*args)
@proc.call(*args)
end
end
class Generator
def initialize(&block)
@proc = block
end
def each
@proc.call(Yielder.new { |*args| yield(*args) })
end
end
include Enumerable
def initialize(obj: nil, method: :each, &block)
@obj = obj || Generator.new(&block)
@method = method
end
def next_values
if defined?(@lookahead)
vs = @lookahead
remove_instance_variable(:@lookahead)
return vs
end
@fib ||= Fiber.new { each { |*args| Fiber.yield args } }
@fib.resume
end
def next
vs = next_values
vs.count <= 1 ? vs.first : vs
end
def peek_values
return @lookahead if defined?(@lookahead)
@lookahead = next_values
end
def peek
vs = peek_values
vs.count <= 1 ? vs.first : vs.dup
end
def each(&block)
return self unless block
@obj.send(@method, &block)
end
end
class Object
def to_renum(method = :each)
REnumerator.new(obj: self, method: method)
end
alias renum_for to_renum
end
class Array
private alias_method :_orig_each, :each
def each(&block)
block ? _orig_each(&block) : to_renum
end
end
# REnumerator#next_values, #next
assert_equal([1], REnumerator.new { |y| y.yield 1 }.next_values)
assert_equal(1, REnumerator.new { |y| y.yield 1 }.next)
assert_equal([1, 2], REnumerator.new { |y| y.yield 1, 2 }.next_values)
assert_equal([1, 2], REnumerator.new { |y| y.yield 1, 2 }.next)
# REnumerator#peek_values, #peek
assert_equal([1], REnumerator.new { |y| y.yield 1 }.peek_values)
assert_equal(1, REnumerator.new { |y| y.yield 1 }.peek)
assert_equal([1, 2], REnumerator.new { |y| y.yield 1, 2 }.peek_values)
assert_equal([1, 2], REnumerator.new { |y| y.yield 1, 2 }.peek)
# REnumerator look-ahead
enum = REnumerator.new { |y| y.yield 1, 2 }
enum.peek
assert_equal([1, 2, 3], enum.peek << 3) # cached & copied
assert_equal([1, 2], enum.next) # cached
# Object#to_renum, #renum_for
assert_equal([1], [1].to_renum.next_values)
assert_equal([42, 0], [42].to_renum(:each_with_index).next)
# Array#each
assert_equal([1], [1].each.next_values)
assert_equal([1], [1].map(&:itself))
# REnumerator#each
assert_equal([1, 2], REnumerator.new { |y| y.yield 1; y.yield 2 }.each.to_a)
# REnumerator Enumerable
assert_equal([1, 2], [1, 2].each.to_a)
また、再掲ですが参考にしたCRubyの実装は下記になります。