アキュムレータについて

Posted on 2010-08-15

コンピュータプログラミングの概念・技法・モデルの中で、アキュムレータという概念が出てきました。たぶん、いろいろなところで使ってきた手法を、一般化して名前をつけたため、違うモノのように見えるだけだと思うのですが、混乱しているので整理します。

再帰計算と反復計算

宣言的プログラミングにおいては、単純に再帰関数を書いてしまうと効率が悪いことが多いので、現実的には再帰計算の特殊な場合である、反復計算になるようにプログラムを書きます。再帰的データ構造を扱う再帰計算を反復計算にするにあたっては、問題を状態変換の列に作り直す必要がありました。

通常の場合、再帰形を書かずにに反復形を書くことが多いです。その場合に用いられる形式として、アキュムレータプログラミングという形式があります。

反復計算におけるアキュムレータ

反復計算は次のような制御抽象として表現できました:

proc {Iterate S IsDone Transform ?R}
    if {IsDone S} then R = S
    else S1 in
        S1 = {Transform S}
        {Iterate S1 IsDone Transform R}
    end
end

アキュムレータは入力と出力の状態の対になります。この場合において、 SR の対がアキュムレータとなっています。

再帰的データ構造を扱う場合の反復計算

再帰的データ構造を扱う計算をするときに、基本の場合と再帰の場合の二つの場合がありました。それを踏まえて、上述の反復計算を書き直すと次のようになります:

proc {P X S1 ?Sn}
    if {BaseCase X} then
        S1 = Sn
    else
        {P1 ... S1 S2}
        ...
        {Pn ... Sm Sn}
    end
end

基本の場合({BaseCase X} == true の場合)は、既に状態変換の列の中で、一番最後の最終状態に居ることになるので、出力状態はそのままになります。

再帰の場合はいくつかの状態変換を施した後、再帰関数を呼んでいます。このとき、呼んでいる各関数もアキュムレータスタイルで書かれています。そのため、最後に呼ばれている関数では、その関数の出力状態がそのまま、呼び出し元の関数の出力状態Sn になるようになっています。

考察

最後に再帰関数を呼ぶことによって、末尾再帰最適化がなされる(2章の練習問題で見たように、相互再帰では、自分自身の関数以外を呼んでもスタックが一定以上消費されない)のですが、その前に関数を呼んでしまうと、関数本体で一度しか再帰関数を呼ばないという条件を満たさなくなってしまうので、スタックを一定以上消費しないとは言えないと思います。

たぶんアキュムレータスタイルというのは、「再帰計算を反復計算にするときの一般的な形式」ではなく、「再帰計算を反復計算にした場合のスタイルを一般化した形式」として捉えるのが妥当だと思います。アキュムレータスタイルで、再帰の場合の本体で1つだけ相互再帰集合の関数を呼び出しており、かつその関数が本体の末尾に呼ばれているときのみ、スタックを一定以上消費しない反復計算になるのであって、それ以外の場合は「あまりメモリを消費しない」再帰計算にとどまると考えられます。このことについては、アキュムレータスタイルで書かれたマージソートのところでも「メモリ使用量は少ない」と述べられているだけなので、そういうことでしょう。再帰計算を反復計算にできる一般的な形式と思って読むと、なんでこれでスタックを消費しないと言えるの?と疑問に思ったりします。

Schemeでは再帰的データ構造としてリストに絞ったアキュムレータを提供していて、次のようになっています。

(define (fold kcons knil l)
  (let loop ((l l) (r knil))
    (if (null? l) r
        (loop (cdr l) (kcons (car l) r)))))

この場合のアキュムレータは r になります。Schemeではすべて関数なので、出力状態を明示的に指定しなくても良く、対になっているように見えませんが、最後にきちんと r を返しているので、ここからもアキュムレータが r であることを確認できます。逆からたどると、初期状態は knil となっていると言えます。 lはリストなので、 BaseCase にあたるものは null? になっています。また、この場合は末尾で直接再帰になっているので、スタックを消費しません。

蛇足

Schemeの場合、ある関数を呼び出した後にやるべき計算を取り出せるという機能があって、それは(自分も含めて)多くの人の中で「強力そうなのは知っているが、正直なところそれがどういうもので、何に有効なのかよくわからない『継続』」として知られています。

関数型プログラミングは宣言的プログラミングにおける、部分値を扱うことを制限して、完全値のみで計算するようにした計算モデルなので、継続ってある計算をするために必要な完全値が計算ができないという理由により、その値を必要とする計算を取り出しておいて、いったん制御フローを他の部分に移すためのものとしてみれるのではないでしょうか。それ以外にも、今その値は存在しているけれども、それをつかって計算をするよりも先に別の計算をしたい場合のフロー制御としても使えるとは思いますが。

Disclaimer: The opinions stated here are my own, not necessarily those of my company.