ジェネレータは、プログラムにおいて、数列の各要素の値などを次々と生成（ジェネレート）し他の手続きに渡す、という機能を持っている手続きである。値を渡す方法としては、コールバックのようにして他の手続きを呼ぶものもあれば、呼び出される度に次々と異なる値を返す関数であることもある。
性質 「呼び出される度に次々と異なる値を返す関数」である場合は、参照透過ではない。イテレータは、コンテナに含まれる値ひとつひとつに対して走るジェネレータの一種である。ジェネレータの実装としてはコルーチンやcall/ccやマルチスレッドを使う方法が考えられる。また、言語によって詳細が異なるものを「ジェネレータ」と呼んでいる。擬似乱数発生器は、ジェネレータの一例である。
なおyieldというキーワードを使っていればジェネレータ、と取られることもあるが間違いである。
歴史 CLU(1975年初出)の歴史を記した "A History of CLU" には、「Iterators were inspired by a construct in Alphard called a "generator"」（(CLUの)イテレータはAlphardのジェネレータと呼ばれる構成要素に影響を受けた）とある。AlphardのジェネレータはIPL-Vに由来する。IPL-Vにおけるジェネレータは、関数プログラミングにおける代表的な高階関数のひとつであるmap関数に似た働きをするもので、リストの各要素に適用するための手続きと、リストを受け取って、各要素にその手続きを適用したリストを生成する。
他に、Icon・PythonPython Enhancement Proposals PEP 255: Simple Generators, PEP 289: Generator Expressions, PEP 342: Coroutines via Enhanced Generators・JavaScript にジェネレータと呼ばれるものがある（イテレータも参照）。
例 Python Pythonでは、関数定義の中にyield文があると、その関数定義は通常の関数を定義するのではなく、一種のコルーチンの記述のようになる。yield文を含む関数は、イテレータと同じインタフェースを持つ呼び出し可能オブジェクトを返す関数になる。ジェネレータの語は、「yield文を含む関数定義により定義された関数」と、それが返す「イテレータと同じインタフェースを持つ呼び出し可能オブジェクト」を、はっきりと区別せずに使われているが、ここでは、前者をジェネレータ、後者をイテレータと呼ぶ。
このイテレータは、ジェネレータの定義中の各yield文の所まで実行した状態を保存するスタックフレームを保持するオブジェクトであると考えることができる。イテレータのnext()が呼び出されると、Pythonは保存されたフレームを復帰し、次のyield文に到達するまで実行する。yield文の実行によりフレームは再び保存され、yieldの引数の値がnext()の呼び出し元に返される。
def countfrom(n): while True: yield n n += 1
# Example use: 10 から 20 までの整数を表示する。
for i in countfrom(10): if i <= 20: print i else: break
# もう一つのジェネレータ。必要に応じて素数をいくらでも作成する
def primes(): n = 2 p = [] while True: if not any( n % f == 0 for f in p ): yield n p.append( n ) n += 1
>>> f = primes() >>> f.next() 2 >>> f.next() 3 >>> f.next() 5 >>> f.next() 7 上記の例は Python 2.5 以上か、NumPy モジュールの any() 関数を使用できる環境で動作する。
Scheme Schemeでは、単純には遅延評価を利用した実装が考えられる。 ;; SRFI 41と言うライブラリを使用(この辺は実装依存) (import streams-primitive) (import streams-derived)
(define (countfrom n) (let ((str (stream-from n))) (lambda () (let ((head (stream-car str)) (tail (stream-cdr str))) (set! str tail) head))))
;; Example use: 10 から 20 までの整数を表示する。
(call/cc (lambda (break) (letrec ((iter (countfrom 10))) (let loop ((i (iter))) (if (<= i 20) (begin (display i) (newline) (loop (iter))) break)))))
;; 必要に応じて素数をいくらでも作成するジェネレータ
(define (primes) (letrec ((sieve (lambda (stream) (let ((obj (stream-car stream))) (stream-cons obj (sieve (stream-filter (lambda (x) (not (zero? (remainder x obj)))) (stream-cdr stream)))))))) (let ((p (sieve (stream-from 2)))) (lambda (message) (case message ((next) (let ((head (stream-car p)) (tail (stream-cdr p))) (set! p tail) head)) (else 'hoge))))))
> (define f (primes)) > (f 'next) 2 > (f 'next) 3 > (f 'next) 5 > (f 'next) 7 > また、Schemeにおいては、継続を使って実装したサンプルがある。
C# C#にもyieldキーワードがある。
yieldステートメントを含むブロックを反復子 (iterator) もしくは反復子ブロック (iterator block) と呼ぶyield (C# リファレンス)yield (C# リファレンス) | Microsoft Docsが、これはジェネレータそのものである。
反復子メソッドの戻り値にはIEnumerable/IEnumeratorもしくはジェネリック版のIEnumerable<T>/IEnumerator<T>のいずれかを指定する yield returnは値を生成する yield breakは値の生成を終了する
// startからendまでの整数を生成するジェネレータ static IEnumerable<int> CountTo(int start, int end) { for (int i = start; i <= end; ++i) { yield return i;
yield break; } // 上記ジェネレータを使用して、10から20までの整数を表示 foreach (int i in CountTo(10, 20)) { Console.WriteLine(i); }
// 素数を必要なだけ生成するジェネレータ static IEnumerator<long> Primes() { long n = 2L; var p = new List<long>(); while (true) { if (!p.Any(x => n % x == 0)) { yield return n; p.Add(n);
n++;
// 上記ジェネレータを使用して、1000以下の素数を表示 var primes = Primes(); while (primes.MoveNext()) { if (1000 < primes.Current) { break; } Console.WriteLine(primes.Current); }
参考文献
Stephan Murer, Stephen Omohundro, David Stoutamire and Clemens Szyperski: Iteration abstraction in Sather. ACM Transactions on Programming Languages and Systems, 18(1):1-15 (1996)