Scheme:LinearUpdate

Scheme:LinearUpdate

Schemeライブラリでは、ある操作に対して非破壊的・関数的なバージョンと、 linear update (線形更新) バージョンの二つが用意されていることがよくある。 (例: GaucheRefj:deleteGaucheRefj:delete!)。

後者に'!'がついているのは破壊的であることを示しているが、元からSchemeにあったset-car!vector-set! のような破壊的手続きとは若干意味が異なる。

linear updateバージョンは、指定の引数を破壊「してもよい」とされているが、 必ず破壊するわけではないので、callerは破壊的変更を当てにするのではなく、 戻り値を使わなければならない (この点、意味のある戻り値を戻さないvector-set!等と決定的に異なる)。 linear updateバージョンが引数を全く変更しない、 非破壊的バージョンと同じ動作をしたとしても仕様上は何ら問題はない。

;; 誤り
(let lis (make-some-list)
  (delete! 1 lis)
  lis)  ; lisが変更されていることを当てにしているが、それは保証されない!

;; 正しい
(let lis (make-some-list)
  (delete! 1 lis)) ; 1が削除されたリストが返る

関数型プログラミングでは、データは不変で、データを更新したければ 更新部分だけが異なる新たなデータを作って返す。 データが不変だとプログラムの解析がうんと楽になる、スレッド間の競合を気にしないで良い、 など色々良いことがある。

残りの部分を毎回コピーするのは無駄なように思えるが、うまく工夫すれば変わってない部分を 共有したりコピーを遅らせたりして、計算量オーダーが変更版と変わらなくできる場合も多い。 興味があればChris Okasaki "Purely Functional Data Structures" (邦訳『純粋関数型データ構造』)がおすすめ。

実際、Lisp系言語ではリスト操作について同じようなことをやっている。 連想リスト(alist)に新たな要素を付け加えるにはaconsで先頭に新たな要素を足せばよいが、 それは「データを付け加えたalistを新たに作って返している」とも言える。 でもaconsは非常に軽い処理だ。元からあったalistは共有されているから。

そして、データが不変だと、例えば何かの処理をしながらデータのリストを作ってゆく過程で、 「こっちの分岐を試して、ダメだったら別の分岐を試す」みたいな操作が出てきた時に、 「最初の分岐を途中まで実行したからデータのリストが中途半端に更新されてしまったのを戻さなきゃ」 といった心配をしなくて良い。リストに関してLisperはほとんどこのメリットを 意識することなく使っていると思う(当然のことだから)。 関数型プログラミングはこのメリットを全てのデータに敷衍していると考えられる。


ただ、たとえ計算量のオーダーを抑えられたとしても、不変データ構造はそれなりに オーバヘッドがあり、inner loopで細かく更新する場合などはそれが顕著になる。

例えば関数的にコレクションにデータを追加するcoll-addという手続きがあったとする。 (coll-add coll x)はコレクションcollの全ての要素と要素xを合わせた新たなコレクションを 作って返すとする。

今、要素のリストlist-of-elementsが与えられて、それを全て含んだコレクションを 作りたいとする。fold-leftでcoll-addをlist-of-elementsに対して回せばできる。

(fold-left coll-add (make-empty-collection) list-of-elements)

しかし、fold-leftが回っている間に作られる中間のコレクションは、 作ったら直ちに捨てられる、一時的なものだ。 そのためにどんどん新しいコレクションを作るのはいかにも無駄である。

引数に渡したデータをもう二度と使わないことがわかっているなら、 そのデータを再利用することでオーバヘッドが抑えられる。

そのために使うのがlinear updateバージョンだ。

引数に渡したデータを変更するかしないか、 あるいは変更するとしてもどのように記憶領域を使うかは手続きが任意に決めることができるので、 callerは手続きを呼び出した後でデータの状態がどうなっているかについて 一切仮定してはならない。 (なお、複数の引数を取る場合、どの引数が破壊され得るかは仕様に示してある。 だいたいは最初の引数だが。 それ以外の引数についてはそういう心配はしなくて良い。)

ここでのlinearは一度読み出したら二度と読み出せない、という性質を持つlinear type(線形型)の linearと似たようなニュアンスなんだと思う。

More ...