継続と隠蔽

Schemeではループの替わりに再帰を使う。便宜的にそう説明することはあるが、正確とは言えないと思う。末尾再帰とループは本質的に同じものであり、再帰で表わされる表現が基本として在ると言うべきだろう。必要ならいかにもループ風の表現にすることも可能なわけで、実際にwhile構文なども用意されている。処理系によっては他の様々な拡張もあるだろう。自前で定義するのもそれほど難しくはない。例えばN88-BASIC風のfor文の定義はこのように書ける。

(define-syntax for
  (syntax-rules (= to step)
    ((_ counter = init-value to limit-value step d body ...)
     (let loop ((counter init-value))
       (if (<= counter limit-value)
           (begin body ... (loop (+ counter d)))
           #f)))))

実際の使い方はこんな要領で。

(for a = 1 to 10 step 2 (display a) (newline))

使う方ではこれが再帰に展開されることは意識しなくてよい。これはループであると思っても何の不都合もないのだ。一塊の処理を括り出して抽象的なものとして扱えるようにするのはプログラミングの基本だが、Schemeの場合は「構文」を定義できるところが興味深い点だと思う。define-syntaxという構文の名称からして凄い。Schemeの言語設計における思想として機能を積み重ねるのではなく、追加機能が必要と考えられがちであった弱点や制約を取り除いていくことというのがあるが、言語機能というものを枝葉の部分でなくより根本的な部分で提供しようとする姿勢になって表われていると言えよう。
他にSchemeSchemeたらしめている根本的な言語機能のひとつとして「継続」の概念がある。これはあらゆるフロー制御を抽象化した概念で、C/C++等には相当する機能は無い。強いて言えばgotoだろうか。gotoと他の命令の組合せによってbreak, continue, for, while等と同等のことができるのと同じように、Schemeでは継続を利用することで様々なことができるのである。C/C++ではbreakの替わりにgotoを使ったりすれば大顰蹙だが、Schemeではそうでもない。適切な形に隠蔽されていれば。そしてSchemeでは容易に隠蔽可能なのである。と、言うわけでここからが本題。
最近のEcmaScriptを見てみると、ジェネレータという機能が追加されていた。私が見たのはFirefox関連のサイトだが、そこでは以下のようなコードが例として挙げられていた。(実際にはまだこのコードがまともに走る処理系はほとんど無い。)

function fib() {
  var i = 0, j = 1;
  while (true) {
    yield i;
    var t = i;
    i = j;
    j += t;
  }
}

var g = fib();
for (var i = 0; i < 10; i++) {
  document.write(g.next() + "<BR>\n");
}

プログラミングに慣れた人ならこの例だけでもおおよそ意味はわかるだろう。要はyieldステートメントに値を渡した時点で一旦停止し、nextメソッドを呼ぶと再度動き始めるということだ。これをSchemeで実装してみた。

(define (make-generator proc)
  (let ((next '()))
    (lambda()
      (if (null? next)
          (call/cc
           (lambda(break)
             (proc
              (lambda arg
                (call/cc
                 (lambda(cc)
                   (set! next cc)
                   (apply break arg)))))
             #f))
          (next)))))

(define (fib)
  (make-generator
   (lambda(yield)
     (let loop ((i 0)
                (j 1))
       (yield i)
       (loop j (+ j i))))))

(let ((g (fib))
      (i 0))
  (while (< i 10)
	 (display (g))
	 (newline)
	 (inc! i)))

make-generatorの定義をぱっと見で把握するのは難しいだろうが、それの利用はあたかもEcmaScriptのジェネレータと同じような感覚である。このように、新しい概念を実現し、その定義を隠蔽することが容易であることを納得できただろうか?
などと言いつつもこのコードを書くのに何時間も考えた。隠蔽はともかく、継続をまともに扱うのはなかなか容易ではない。のーみそコネコネ。
追記:このジェネレータの実装には問題がある。本家WiLiKiにて質問したところ詳細な解説と正しい実装をくれた。とても為になる話。以下のURLを参考のこと。
http://practical-scheme.net/wiliki/wiliki.cgi?Scheme%3agenerator%e3%81%a8do%e3%81%a8while
Document ID: ee1517283987b9c807ecebaed0ad0b84