イテレーターについて考えた。

ふと、こんなことを考えた。


そこから始まる、イテレーターについての考察。

Iterator パターン

GoF のデザイン パターンのひとつに、Iterator パターンというのがある。

f:id:aetos382:20171228020105p:plain

コンテナ オブジェクトの要素を列挙する手段を独立させることによって、コンテナの内部仕様に依存しない反復子を提供することを目的とする。

Iterator パターン - Wikipedia

だそうである。

上のクラス図でいう、Aggregate が抽象的なコンテナ インターフェイス(コレクション)で、ConcreateAggregate が具体的なコンテナ型。
Iterator が抽象的なイテレータ インターフェイスで、ConcreteIterator が具体的なイテレータ型。

.NET でいうと…

クラス図 .NET の場合
Aggregate IEnumerable<T>
ConcreateAggregate List<T> など
iterator() GetEnumerator()
Iterator IEnumerator<T>
ConcreteIterator List<T>.Enumerator など
next() MoveNext()
hasNext() MoveNext()

というように、割と素直に対応する。
従って、IEnumerable<T> / IEnumerator<T> は、Iterator パターンの実装である、ということになる。

Java の Iterable<T> / Iterator<T> も、だいたい似たようなものだ。

なお、ややこしいことに、C# では yield return によって IEnumerable<T> を生成するメソッドのこともイテレーターと呼んだりする。
が、本記事中では、イテレーターと言えば IEnumerator<T> のことを指すものとする。

C++イテレータ

C++イテレーターはちょっと毛色が異なる。
C で、配列の要素を指すポインターを使って、配列を反復処理していたのを高度化させたものが、C++イテレーターである。
.NET や Java では、イテレーターを使ってコレクションの要素を書き換えることはできないが、C++ ならばできる。
また、ある要素の前の要素を指し示したり、ポインターと同じように、i + 3 のように数値を足すことで 3 つ先の要素にジャンプできたりもする。

C++イテレーターは、それが備える機能によっていくつかのクラスに分けられる。
以下のどのクラスであっても、コレクションのある要素を指しているイテレーターを、次の要素を指すように進める(Iterator パターンでいうところの next())はできる。

C++ はダック タイピングな言語なので、Iterator パターンでいうところの、すべてのイテレーターが継承すべき抽象的な Iterator クラスのようなものはない。*1
が、強いて言うならば、Input Iterator が、Iterator パターンに相当すると言える。

Input Iterator

イテレーターが指す要素の値を取得できる。

Output Iterator

イテレーターが指す場所の値を書き換えられる。

Forward Iterator

Input Iterator と Output Iterator の機能を兼ね備えたもの。

Bidirectional Iterator

Forward Iterator の機能に加え、ある要素の前の要素に戻ることができる。

Random Access Iterator

Bidirectional Iterator の機能に加え、i + 3 で 3 つ先の要素を指すイテレーターを得たり、i += 3 で 3 つ先の要素に進めたりできる。*2

シングル パスとマルチ パス

雑にイテレーターのクラスについて説明したが、もうひとつ、重要な性質がある。
いま調べていて初めて知ったのだが、Input Iterator と Output Iterator には、シングル パスの保証しかなく、Forward Iterator 以上であれば、マルチ パス保証があるのだそうだ。うん、何のことやらわからんね。*3
どうも、「シングル パス保証しかない」ということは、同一のコレクションを指す複数のイテレーターがある時に、そのうちの一つでインクリメント*4をすると、他のイテレーターが無効になる可能性がある(そのような実装が許される)らしいのだ。
ざっくり言うと、シングル パス保証しかないイテレーターでは、イテレーターを保存しておいて後で使うということはしない方がいいみたいだ。

値型と参照型

なんでイテレーターの文脈でこんな話が出てくるんだと思われるかもしれないが、まぁ聞いて頂きたい。

.NET には、値型と参照型がある。int とか DateTime といった構造体や列挙型は値型で、string やインターフェイスやデリゲートや、その他のオブジェクトは参照型である。*5

値型とは、そのオブジェクトの実体そのものを扱うことができる型である。特に禁止されていない限り、コピーすることができる。
参照型とは、そのオブジェクトの実体そのものに触れることはできず、ポインター*6を通して間接的に扱うことしかできない型である。ポインターが指す先のオブジェクトにコピー機能が実装されていない限り、コピーはできない。
ポインター自体は値である。

.NET の IEnumerator<T> はインターフェイスだから参照型である。一般的にコピーはできない。
C++イテレーターはポインターの親戚なので値であり、コピーができる。

最初のつぶやきはそういうわけで、.NET でも IEnumerator<T> のある時点の状態をコピーして保存しておいて、そこから再度列挙し直すということをやりたいな、と思ったのであった。
が、IEnumerator<T> は参照型であって、コピーが作れないので、状態を保存しておくということはできないのだ。残念。

なお、「一般的には」コピーできない、としつこく言っている点に注意されたい。
コピーして過去の値を保存しておけるような IEnumerator<T> を作ることは可能である。
が、すべての IEnumerator<T> が過去の状態を保存しておけるわけではない、ということだ。
一方、C++イテレーターは、(明示的に禁止されない限り)基本的にはすべてが、コピーして状態を保存しておける(たぶん)。

イテレーターとジェネレーター

これまで、ずっと「イテレーター」と言ってきたのだが、Wikipedia を見ると、どうやらジェネレーターというのもあるらしい。

イテレータ(英語: iterator)とは、プログラミング言語において配列やそれに類似する集合的データ構造(コレクションあるいはコンテナ)の各要素に対する繰り返し処理の抽象化である。

イテレータ - Wikipedia

ジェネレータは、プログラムにおいて、数列の各要素の値などを次々と生成(ジェネレート)し他の手続きに渡す、という機能を持っている手続きである。

ジェネレータ (プログラミング) - Wikipedia

また、ジェネレーターの記事には、

イテレータは、コンテナに含まれる値ひとつひとつに対して走るジェネレータの一種である。

とも書いてあるので、どうやら、ジェネレーターの方がより抽象的で広い概念であるようだ。
というわけで、今後は「イテレーター」という言葉は「何らかのコレクションの要素を指し示すもの」という意味に限定することにする。

そうしてみると、IEnumerator<T> というのは、必ずしもコレクションに結び付くわけではない(yield return で生成される場合など)ので、これは(一般的には)イテレーターではなくジェネレーターなのだ。
冒頭で挙げた Iterator パターンも、この定義に従えばジェネレーターである。
ジェネレーターだからといってイテレーターではないということではない点に注意されたい。ジェネレーターの中にはイテレーターも含まれる。

対して、C++イテレーターは、狭義の意味でのイテレーターであると言ってもよさそうな気がする。

イテレーターは、それ自身の寿命よりも長寿命のコレクションに属している。だから、保存しておいて後で使ったり、前の位置に戻したりすることができる。
ジェネレーターは、それ自体が単一の値を抱え込んでいて、外部の何かに属しているわけではないものがある(yield return なんかはそう)。なので、保存しておいたり、前の位置に戻したりすることは、一般にはできないのだ。「前の値」などというものは、もう消えてしまっていてどこにもない(かもしれない)のだから。

ということは、IEnumerator<T> をラップして、状態を保存しておけるイテレーターを作るとするならば、MoveNext() を呼ぶごとに Current の値を保存しておく必要がありそうだ。

一見、ジェネレーターの方が機能が足りないように見えるが、制約が緩いということは活用の幅が広いということでもある。
もしも .NET の IEnumerator<T> が最初からコピーをサポートしていたら(サポートしなければならないという制約があったとしたら)、こんなに活用されることはなかっただろう。

余談:JavaScript

JavaScript には、イテレーターとジェネレーターの両方がある。
developer.mozilla.org

JavaScript でいうところのイテレーターというのは、前節の定義によれば一般的にはジェネレーターである。
そして、JavaScript のジェネレーターというのは、イテレーターを生成するための関数の糖衣構文である。
つまりは C# で yield return を含むメソッドのこともイテレーターと呼ぶように、JavaScript では yield を含む関数をジェネレーターと呼び、それによって生成されるオブジェクトをイテレーターと呼んでいるのである(C# でも yield return を使わなくても IEnumerable<T> が作れるのと同じように、JavaScript でもジェネレーター機能を使わなくてもイテレーター オブジェクトは作れる)。
そして、ジェネレーター関数によって生成されるイテレーター オブジェクトは、一般的にはジェネレーターと呼ばれることもある、のである。
わけわからんな。

ジェネレーター関数は、イテレーターのファクトリーとして働く、特別な種類の関数です。

なお、JavaScript では、ユーザー定義の値型は作れないので、イテレーターは一般にコピー可能ではない。

で、結局何がしたかったの?

ちょっと、パーサー的なものを作ってみようかと思っている。

*1:イテレーターの実装を簡単にするための std::iterator という型はあるが、これを継承することは必須ではないうえに、C++17 からは非推奨となったらしい。

*2:定数時間で、という要件がある?

*3:よく「シングル パス」とか「マルチ パス」というと、「パス」は「path」であるわけだが、この C++イテレーターの文脈では「single pass」「multi pass」らしい。

*4:Iterator パターンでいうと next()

*5:列挙型は値型だが、その基底型である System.Enum は値型ではないようだ。へー。

*6:参照ともいう