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

ジェネレータは、プログラムにおいて、数列の各要素の値などを次々と生成（ジェネレート）し他の手続きに渡す、という機能を持っている手続きである。値を渡す方法としては、コールバックのようにして他の手続きを呼ぶものもあれば、呼び出される度に次々と異なる値を返す関数であることもある。

 性質 
「呼び出される度に次々と異なる値を返す関数」である場合は、参照透過ではない。イテレータは、コンテナに含まれる値ひとつひとつに対して走るジェネレータの一種である。ジェネレータの実装としてはコルーチンや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・Python・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:
 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) と呼ぶが、これはジェネレータそのものである。

 反復子メソッドの戻り値には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);
}