はじめに
まもなくリリースされる Emacs 25 の新機能の一つに「ジェネレータ (生成子 generator)」があります。 （ /lisp/emacs-lisp/generator.el/ )
ここでは、本機能の概要と利用法について簡単に紹介します。
ジェネレータとは
ジェネレータ（生成子 generator）は、関数を呼び出す度に、前回の呼び出した状況を覚えていて、それに基づいて新しい値を生成して返します。
なお、Emacs 25の generator.el では、次々と値を生成する関数はイテレータ（反復子 Iterator）と呼ばれ、イテレータを作り出す関数をジェネレータと呼んでいますが、以下の記事ではまとめてジェネレータと呼びます。
以下に、フィボナッチ数列の指定された番号の値を返す関数の例を示します。
単純な関数の例は以下のようになります。
(defun fibonacci (n)
(let ((a 1) (b 1) (c 0))
(dotimes (_i n)
(setq c b)
(setq b a)
(setq a (+ a c)))
c))
ここで、フィボナッチ数列の各要素に対して、何らかの処理をしたい場合は、当該関数に、処理をさせたい関数を引数として渡すことが考えられます。
(defun fibonacci (n func)
(let ((a 1) (b 1) (c 0))
(dotimes (_i n)
(funcall func c)
(setq c b)
(setq b a)
(setq a (+ a c)))))
ただ、引数となる関数 func に、色々な情報（たとえば呼び出し側の文脈など）を渡したいとなると、上記の方法では簡単にはいきません。
このような場合、ジェネレータは実行中に、呼び出し元に途中結果を返すことを可能にします。上記をジェネレータを用いて記述すると、以下のようになります。
(setq lexical-binding t) ; 字句束縛は有効にする必要がある
(require 'generator)
(iter-defun fibonacci ()
"Fibonacci Function."
(let ((a 1) (b 1) (c 0))
(while t
(iter-yield c)
(setq c b)
(setq b a)
(setq a (+ a c)))))
ここで、 iter-yeid 関数は、現在の値を呼び出し元に返して処理を一旦中断し、再度、呼び出し元が iter-next を呼ぶまで現在の状況で待ち続けます。
以下はジェネレータから１０個、値を取り出す例です。
(defun call-fibonacci ()
(let ((fib (fibonacci)))
(dotimes (_i 10)
(message "%s" (iter-next fib)))))
一時変数 fib に、ジェネレータオブジェクトが入り、それを引数として iter-next 関数を呼び出すと、ジェネレータの iter-yield で返される値が次々と帰ってきます。その間、 fib オブジェクトの内部の状態は維持されます。（一種の単純なオブジェクト指向といえるかもしれません。）
ジェネレータをループで取り出す場合は、以下のように iter-do や、 強力なループマクロ cl-loop のキーワード iter-by としても利用できます。
（注意：以下は、Emacsの扱える整数の範囲を超えると負数と正数を繰り返す無限ループになります。）
(defun call-fibonacci ()
(let ((fib (fibonacci)))
(iter-do (i fib)
(message "%s" i))))
(defun call-fibonacci ()
(let ((fib (fibonacci)))
(cl-loop
for i iter-by fib
do (message "%s" i))))
以下は、フィボナッチ関数側で、値が巨大すぎて負数になった場合に処理を終了させる（数列を生成し尽くす）例です。
(iter-defun fibonacci ()
"Fibonacci Function."
(let ((a 1) (b 1) (c 0))
(while (> c -1) ;; 負数になったら終了
(iter-yield c)
(setq c b)
(setq b a)
(setq a (+ a c)))))
この場合、 cl-loop や、 iter-do は、 fibonacci がEmacsの正の整数で扱える最大数まで到達した際、生成値を消費し尽くしたとして終了します。値を出し尽くしたジェネレータに対して、なおも iter-next を呼び出すと、 iter-end-of-sequence 例外が起動します。
データのパイプライン処理とイベント通知としてのジェネレータ
ジェネレータは iter-yield の引数で呼び出し元に値を返していますが、実は、呼び出し元も iter-next の第２引数に値を指定することで、ジェネレータ側に値を送れます。
そのため、ジェネレータを 繋げて 書くことで、次々と生成された値を分岐・パイプライン処理で渡していく、「データ処理・イベント通知グラフ」を作ることができます。
以下に、「フィボナッチ数を生成する関数」の値を、「受け取った値をそのまま表示する関数」と「受け取った関数を二倍するして次に渡すジェネレータ」の２つに分岐させ、後者をさらに、「受け取った関数を表示するジェネレータ」に繋げるデータ処理のグラフを作る単純な例を示します。
この例では、中間処理を担うジェネレータは、値を一方的に呼び出し側から渡すだけで、呼び出された側からは返さないため、 iter-yield の引数は nil になっています。
このようにジェネレータは、値を一方的に呼び出し元に渡すだけでなく、値を一方的に受け取るだけ、という使い方もできます。
(iter-defun times (num next)
(let (val)
(while t
(setq val (* num (iter-yield nil)))
(iter-next next val))))
(iter-defun message-out (format)
(while t
(message format (iter-yield nil))))
(defun pipeline-test ()
(let* ((fib (fibonacci))
(out1 (message-out "orig=%s"))
(out2 (message-out "x2=%s"))
(x2 (times 2 out2)))
(iter-do (i fib)
(iter-next out1 i)
(iter-next x2 i))))
これはそのまま、イベントの送信・受信としても利用することができます。
コルーチンとしてのジェネレータ
従来、再利用される処理はメインルーチンからはサブルーチンとして分かれており、サブルーチンとなる関数は呼び出される毎に、文脈がリセットされていました。
しかし、ジェネレータでは、呼び出される関数の 状態 および 継続 が保持されているので、以下のように２つのタスクを交互に切り替えながら、お互いに通信できます。
(iter-defun task-b ()
(let (result)
(message "task b-1")
(setq result (iter-yield 100))
(message "task b-2, result=%s" result)
(iter-yield 200)))
(defun task-a ()
(let ((task-b (task-b)) result)
(message "task a-1")
(setq result (iter-next task-b))
(message "task a-2, result=%s" result)
(setq result (iter-next task-b 1))
(message "task a-3, result=%s" result)))
上記の実行結果は以下のようになります。（メッセージバッファに出力されます。）
(task-a) ⏎
step a-1
step b-1
step a-2, result=100
step b-2, result=1
step a-3, result=200
このように、呼び出し元と、呼び出し先を交互に切り替える実行手法は コルーチン と呼ばれます。
非同期呼び出し（ノンブロッキングI/O）とジェネレータ
コルーチンの一例として、外部プロセスの非同期な呼び出し後に、一旦、実行状態を中断してEmacsのコマンドループに帰りつつも、呼び出しが終了した後、再び、中断した場所から継続する例を示します。
以下の例では、外部コマンド sleep 10 で10秒待つ処理を呼び出し、そののち、処理を再開します。非同期呼び出しの後の処理を指定するには、以下のように、 set-process-sentinel 関数に、別の関数を引数として指定していました。
(defun test-process (a)
(let* ((process (start-process "sleep" nil "sleep" (number-to-string a))))
(set-process-sentinel process 'test-sentinel)
(process-put process 'a a)))
(defun test-sentinel (process state)
(let ((a (process-get process 'a)))
(message "Process change, state=%s a=%s" state a)))
(test-process 10) ;; 10秒後に再開
この方式では、 test-sentinel が呼び出された時には、 test-process は終了しており、その状態は失われています。非同期実行が終わった後にも情報を渡すため、従来はプロセスを鍵にした、データ保存専用の関数 (process-put, process-get) を利用していました。
しかし、ジェネレータを使えば、以下のように非同期呼び出し後、 iter-yield で待機しつつ、呼び出し後に中断した場所から継続できます。
(iter-defun test-process-2 (a)
(let* ((process (start-process "sleep" nil "sleep" (number-to-string a)))
(result))
(set-process-sentinel process 'test-sentinel-2)
(setq state (iter-yield process))
(message "Process change, state=%s a=%s" state a)
(iter-yield nil)))
(defun test-sentinel-2 (process state)
(let ((gen (process-get process 'generator)))
(iter-next gen state)))
(let* ((gen (test-process-2 10)) (process (iter-next gen)))
(process-put process 'generator gen))
待機中も文脈が維持されているため、必要な情報をいちいち process-put で退避させる必要がありません。
マルチタスク管理としてのジェネレータ
上述のように、ジェネレータは、「呼び出し元と呼び出された関数との間での実行中での通信」と、「呼び出された側の自主的な待機」を実現しています。
また、ジェネレータの実行そのものを中止させる、 iter-close 関数も用意されています。
これらの機能があれば、実はマルチタスク・スケジューラを作ることはそれほど難しくはありません。
以下は、２つのタスク、ひとつ目は "Hello Hoge!" を 980回表示するタスクと、ふたつ目は "Hello Page!" を 1000回表示するタスクを、交互に実行するスケジューリング例です。
(iter-defun task-hoge ()
(dotimes (_i 980)
(message "Hello Hoge!")
(iter-yield nil)))
(iter-defun task-page ()
(dotimes (_i 1000)
(message "Hello Page!")
(iter-yield nil)))
(defun task-scheduling ()
(let ((task-table (make-hash-table :test 'equal)))
(puthash 1 (task-hoge) task-table)
(puthash 2 (task-page) task-table)
(while (/= 0 (hash-table-count task-table))
(maphash (lambda (id task)
(condition-case err
(iter-next task)
(iter-end-of-sequence
(remhash id task-table))))
task-table))))
上記の例では、タスクをまず、ハッシュテーブルにタスクIDとともに登録します。
タスクが終了してもさらに iter-next を呼ぶと、 iter-end-of-sequence 例外が発生しますので、それをキャッチしたらそのIDでタスクをテーブルから削除します。テーブルにタスクが一つも無くなったら、スケジューラは終了します。
(task-scheduling) を実行すると、以下のように、まずタスクHogeとタスク Pageが交互に980回実行され、その後、タスクPageだけが20回実行されているのがわかります。
Hello Hoge!
Hello Page!
Hello Hoge!
...
Hello Page!
Hello Hoge!
Hello Page! [21 times]
タスク間同期とジェネレータ
イベント通知と、マルチタスク管理ができるならば、タスク間のセマフォやメッセージングなども実現できます。たとえば、以下は１００個のタスクが１０のセマフォを1/2の確率でロック・リリースし、３回ロックできたタスクから終了する例です。
(iter-defun semaphore (n)
(let ((i 0) signal task-id)
(while t
(setq task-id (iter-yield nil))
(setq signal (car task-id))
(setq task-id (cdr task-id))
(if (equal signal 'lock)
(if (< n i)
(progn (iter-yield nil) t)
(incf i)
(iter-yield t))
(if (equal signal 'release)
(if (< i 1)
(iter-yield nil)
(decf i)
(iter-yield t))
(error "signal error!"))))))
(iter-defun task-sem (id sem)
(let ((count 0) lock)
(while (< count 3)
(when (= 1 (random 2))
(if (null lock)
(progn
(if (setq lock (iter-next sem `(lock ,id)))
(message "task %s: success to lock semaphore." id)
(message "task %s: failed to lock semaphore." id)))
(message "task %s: releasing semaphore!" id)
(if (setq lock (iter-next sem `(release ,id)))
(message "task %s: success to release semaphore." id)
(message "task %s: failed to release semaphre." id))
(setq lock (not lock)))
(iter-next sem))
(if lock (incf count))
(iter-yield nil))
(message "task %s: finish task." id)
(iter-next sem `(release ,id))
(iter-next sem)))
(defun run-tasks ()
(let ((task-table (make-hash-table :test 'equal))
(semaphore (semaphore 10)))
(iter-next semaphore)
(dotimes (i 100)
(puthash i (task-sem i semaphore) task-table))
(while (/= 0 (hash-table-count task-table))
(message "scheduler: current tasks =%s" (hash-table-count task-table))
(maphash (lambda (id task)
(condition-case err
(iter-next task)
(iter-end-of-sequence
(message "task %s finished." id)
(remhash id task-table))))
task-table))))
ジェネレータでのジェネレータの呼び出し
ジェネレータは、通常ではジェネレータを呼び出せません。 iter-yield での値の出力を、下位のジェネレータに以上する関数 iter-yield-from が用意されているので、これを利用します。
たとえば、通常の竹内関数は以下のようになります。
(defun tarai (x y z)
(if (<= x y) y
(tarai
(tarai (1- x) y z)
(tarai (1- y) z x)
(tarai (1- z) x y))))
これを、x,y,z の値を関数に入るたびに取り出すジェネレータとして表現すると、以下のようになります。
(iter-defun tarai (x y z)
(iter-yield (list x y z))
(if (<= x y) y
(iter-yield-from (tarai
(iter-yield-from (tarai (1- x) y z))
(iter-yield-from (tarai (1- y) z x))
(iter-yield-from (tarai (1- z) x y))))))
以下に、 condition-case を使った利用例を示します。ジェネレータの返り値（上記の y ）は、 iter-end-of-sequence 例外の cdr セルに入ります。
(let ((tarai (tarai 4 2 0)))
(condition-case err
(while t (message "%s" (iter-next tarai)))
(iter-end-of-sequence
(cdr err))))
継続渡し形式（CPS）変換とジェネレータ
ジェネレータは実行途中のプログラムを中断、待機することができます。しかし、EmacsにSchemeの call-with-current-continuation (call/cc) のような、現在の継続状況を取り出す専用の機能が組み込まれたわけではありません。
現在の generator.el では、 iter-defun で定義された関数は、コンパイル時に「継続渡し形式（Continuation Passing Style, CPS）変換」と呼ばれるアルゴリズムで、継続状態を引数として取る式に変形され、それをクロージャ（閉包 closure）として生成・評価する関数として、改めて定義しなおされています。
クロージャは、変数等を束縛した形でラムダ式を表現します。Emacs では、バージョン24より実装され、 lexical-binding 変数が t の際に有効になります。
(setq plus3 (let ((a 3)) (lambda (x) (+ a x))))
→ (closure ((a . 3) t) (x) (+ a x))
(funcall plus3 5)
→ 8
CPS変換は、通常の式を、ネストしない単純な式＋次に評価する式への引き渡し、という形に変形します。評価する順番が分かりにくい場合がある関数型言語の式を、単純式を評価する順番に並べ直すことができるため、関数型言語のコンパイラに用いられます。
Wikipedia の 継続渡しスタイル で挙げられている、ピタゴラス距離を求める関数の例を示します。ここではまず引数を二乗し、加算し、そして平方根を求める順番に実行されています。
(defun pyth (x y)
(sqrt (+ (* x x) (* y y))))
これを、乗算・加算・平方根の計算の全ての関数に対してCPS変換すると、以下のようになります。すると、入れ子が無くなった単純な式が、評価する順番（乗算→乗算→加算→平方根）の通りに並びます。
(defun pyth& (x y k)
(*& x x (lambda (x2)
(*& y y (lambda (y2)
(+& x2 y2 (lambda (x2py2)
(sqrt& x2py2 k))))))))
ここで、 *&, +&, sqrt& は、もとの *, +, sqrt 関数から、引数を評価した後に最後の引数の関数に、結果を渡すように変形した関数です。
(defun +& (a b k) (funcall k (+ a b)))
(defun *& (a b k) (funcall k (* a b)))
(defun sqrt& (a k) (funcall k (sqrt a)))
繰り返しや、関数呼び出しの式のCPS変換も定められています。Wikipediaにもある階乗を求める関数の例では、
(defun factorial (n)
(if (= n 0) 1
(* n (factorial (- n 1)))))
これをCPS変換すると以下のようになります（単純化のため、比較・乗算・減算のCPS変換は省略しています。完全版は、Wikipediaの項目を参照して下さい）。
(defun factorial& (n k)
(if (= n 0)
(funcall k 1)
(factorial& (- n 1) (lambda (x) (funcall k (* n x))))))
元の式では乗算の引数が関数呼び出しになっていましたが、変換後は、乗算の引数は変数のみになっています。例えば (factorial& 4 'identity) で評価すると、「引数を2倍にして、「引数を3倍にして、「引数を4倍する関数」 に渡す関数」に渡す関数」に、１を渡します。
この factorial& 関数を途中で停止、再開することを考えてみます。 factorial& 関数を、以下のように実行状態を呼び出し元に返すように変更してみます。上式の factorial& を list にし、これが途中であることを示す、 cont シンボルを先頭に加えてみます。
(defun factorial& (n k)
(if (= n 0)
(funcall k 1)
(list 'cont (- n 1) (lambda (x) (funcall k (* n x))))))
この関数を呼び出して、途中の中断結果を受け取り、それを再開させてみます。まず、単独で呼び出すと以下のようにクロージャが返ります。
(factorial& 3 'identity)
→ (cont 2 (closure ((c . identity) (n . 3) t) (x) (funcall c (* n x))))
これを、先頭が cont でなくなるまで、繰り返し実行してみます。
(let ((cont (factorial& 6 'identity)))
(while (equal (car-safe cont) 'cont)
(message "factorial& の継続=%s" cont)
;; 実行再開
(setq cont (apply 'factorial& (cdr cont))))
cont)
→ 720
すると、毎回、階乗の計算は中断して、呼び出し元に返り、そこでメッセージを表示した後、再開されます。
このように、式を中断・継続させたい部分でCPS変換をすると、実行の中断（を含む、様々なフローの制御）が可能になり、ジェネレータはこれを利用して実現されています。（ generator.el では、 cps--transform-1 関数が、実際に式のCPS変換を行っています。）
最後に
本記事では、Emacs 25の新機能であるジェネレータについて簡単に説明しました。ジェネレータは、値を次々と生成することから名前が付けられました。
ジェネレータは、内部状態を保持したまま、自主的に待機し、何度でも呼び出し元から呼び出せます。またその過程で相互に通信できます。これは一種のオブジェクト機能や、マルチタスクの管理機能となります。
ジェネレータは、本来の目的の他に、以下のような用途に利用できます。
- データのパイプライン処理やイベント通知処理
- 外部プロセスの非同期な呼び出し（ノンブロッキングI/O）
- ノンプリエンプティブなマルチタスクの管理
ジェネレータは、Emacs Lisp 24 から実装された字句束縛と pcase を活用した、継続渡し形式（CPS）変換を用いて実装されています。コンパイル時に、マクロを利用することで、式の変換を行なうことができるのは、Lisp系言語の大きな利点の一つです。