2018/07/27
Gaucheの遅延シーケンス
TuringComplete.fm #28でGaucheの遅延シーケンスの話をしたのだけれど、 Lispユーザでない人はいきなりカーだのクダーだの言われて面食らったろうし、 音声ではClojureとclosureが区別できないし、かなりわかりにくかったかも。 Gaucheの遅延シーケンスについて、実装面から書いたことはなかった気がするので、 この機会に書いておく。
リスト
Lisp系言語のリストは通常、ポインタ二つを持つ構造体 (ペア、あるいはコンスセル)
でもって実装される。例えばリスト (1 2 3) は内部的にはこんなふうになっている。
+---+---+ +---+---+ +---+---+ | * | *----->| * | *----->| * | ()| +-|-+---+ +-|-+---+ +-|-+---+ | | | v v v 1 2 3
最後の()はリスト終端を表す。
慣習的に、このペアの最初のポインタをたどる操作をcar (カー)、
二つめのポインタをたどる操作をcdr (クダー) と呼ぶ。
Cに慣れてる人にはコードの方がわかりやすいかも:
struct ScmPairRec {
ScmObj car;
ScmObj cdr;
};
また、carとcdrのポインタを与えて新たなペアを作る操作をconsと呼ぶ。
オブジェクトのリストを受け渡して行くような処理はLisp系言語には頻出する。 例えば、「16進数の数値が1行に一つづつ書かれたファイルを読み込み、 その中に65535を越える数値があれば最初のものの位置を返す」という処理を考えよう。
ファイルdata.datを読み込んで文字列のリストにして返すのは次のとおり:
(file->string-list "data.dat")
文字列のリスト中の各文字列を16進数としてパーズし、数値のリストとして返す処理は次のとおり
(ここで、(cut number->string <> 16) は
(lambda (x) (number->string x 16)) と同じ):
(map (cut number->string <> 16) 文字列のリスト)
条件に合う要素の位置を返す処理は次のとおり(find-indexはgauche.sequenceモジュール):
(find-index (cut > <> 65535) 数値のリスト)
全部つなげると:
(find-index (cut > <> 65535)
(map (cut number->string <> 16)
(file->string-list "data.dat")))
Gaucheではこんなふうにも書ける。逆向きのパイプラインと思うとわかりやすい。
($ find-index (cut > <> 65535) $ map (cut number->string <> 16) $ file->string-list "data.dat")
この考え方はわかりやすいが、ひとつ問題がある。Schemeでは引数は関数を呼び出す前に
完全に評価されるので、まずdata.datが全て読まれて文字列のリストになり、
次にそのリスト全体が数値のリストに変換される。もしその最初の方に条件を満たす要素があれば、
それ以降は読む必要が無いのだから、無駄だ。
遅延ストリーム
遅延ストリームは、要素の列について、それぞれの要素が必要になるまでその計算を遅らせる仕組みだ。
Gaucheではutil.streamモジュールで提供される。
リストlisの各要素に手続きprocを適用して、その結果をリストとして
返す関数map1は、素直に再帰で書くとこうなる (Gauche組み込みのmapと違って
リストを1つしか取らないので、区別するためにmap1とする):
(define (map1 proc lis)
(if (null? lis)
'()
(cons (proc (car lis))
(map1 proc (cdr lis)))))
lisが空なら()を返し、そうでなければ
「(car lis)にprocを適用したもの」と、
「リストの残り(cdr lis)をmap1で処理したもの」をconsする。
次の手続きtwiceは「引数をprintしてから、それを2倍したものを返す」関数だ。
引数をprintするのは評価のタイミングを知るため。
(define (twice x) (print "x=" x) (* x 2))
リスト (1 2 3) にtwiceをマップして、結果を変数zに束縛してみよう。
gosh> (define z (map1 twice '(1 2 3))) x=1 x=2 x=3 z
最後のzはdefineが返したもの。それ以前にtwiceが3回、
要素それぞれに対して呼ばれたことがわかる。
結果のリストの0, 1, 2番目の要素を見ると、それぞれ元の要素の2倍になっている。
gosh> (list-ref z 0) 2 gosh> (list-ref z 1) 4 gosh> (list-ref z 2) 6
同じことを遅延ストリームでやってみる。
遅延ストリームを扱う手続きは、
リスト操作手続きを対応するストリーム操作手続きに置き換え、
全体をstream-delayでくくることで書ける。空リスト()
にはstream-nullが対応する。
次が遅延ストリーム版のmap1だ。
(use util.stream)
(define (stream-map1 proc strm)
(stream-delay
(if (stream-null? strm)
stream-null
(stream-cons (proc (stream-car strm))
(stream-map1 proc (stream-cdr strm))))))
上でリストにやったのと同じように、ストリームに対してtwiceをマップしてみよう。
gosh> (define z (stream-map1 twice (stream 1 2 3))) z gosh> (stream-ref z 0) x=1 2 gosh> (stream-ref z 1) x=2 4 gosh> (stream-ref z 2) x=3 6
今度は、defineがzを返した時点で、twiceは一度も呼ばれていない。
最初の要素を見に行った時に初めて1回呼ばれる。以降も、必要なだけしかtwiceは呼ばれない。
(追記2018/09/02 09:07:13 UTC: 原則として、副作用のある式を遅延評価中で使うべきではない。 どのタイミングで評価されるかわからないからだ。今回はそのタイミングを知りたいので 副作用を使ったが、例えばたまたまcurrent-output-portが置き換わっている環境で 評価が走れば想定したポートに出力が出てこない、なんてこともありえるので注意。)
ストリームは、概念的には式をくるんだものだ。最初に作られた時には、 与えられた式が評価されずにそのまま入っている。
+-stream-------+ | | | (expression) | | | +--------------+
値が必要になった時点で、まずストリームの中身が評価される(forceする、という)。 一旦forceされた式は、コンスセルになるか、空リストになる:
expressionがコンスセルになる場合 +-stream-------+ | +---+---+ | | | | *--------> stream | +---+---+ | +--------------+ expressionが空リストになる場合 +-stream-------+ | | | () | | | +--------------+
forceされた結果はstream内に記憶されるので、expresssionは1度しか評価されない。 二度目以降のforceは何もしない。
stream-* 系の関数はだいたい、streamを受け取ったらそれをforceして、
内容を取り出して何かする、というものである。
遅延ストリームはこうして「値が必要になるまで計算しない」を実現できているのだが、 いちいちリストをstreamオブジェクトに入れる必要があるため、 アクセスするのに専用の関数が必要になる。 リスト用に書いていたコードをストリーム対応にするにはほぼ全面的な書き直しになってしまう。 これはきつい。
また、ストリームを作る際にexpressionの評価を遅延するために、 expressionをlambdaでくるんでクロージャにするのだけれど、 長大なリストの1要素ごとにクロージャを作成するのは、 普通のリストアクセスに比べると重すぎる。
遅延シーケンス
Clojureではリストに限らずいろいろな「並び」をシーケンスとして統一的に扱えるうえ、 シーケンスを生成する関数はデフォルトで遅延シーケンスを作る。 これがなかなか使い勝手が良かったので、Gaucheでも実現できないかと考えた。
要件は、
- 通常のリスト関数が、変更することなく、遅延シーケンスも受け取れること。 つまりScheme側からみて、 どうしても必要な時以外はリストと遅延シーケンスの区別が見えないようにすること。
- 生のリストより多少遅くなるのは仕方ないとしても、なるべくオーバヘッドを減らすこと。 任意のexpressionをいちいちラップするストリームのアプローチは重すぎる。
そこでGaucheでは、次のような「遅延ペア」を導入した。遅延ペアは、そのcar部は ペアと同様にリストの要素であるオブジェクトを指しているが、 cdr部は「ジェネレータ」を指している。
+===+===+
| * | *----> generator
+=|=+===+
|
v
obj
ジェネレータは引数を取らない手続きで、呼ばれる度に値を生成する。
遅延ペアをforceすると、まずジェネレータが評価される。 それがEOFオブジェクトを返した場合は終端とみなし、 遅延ペアはcdrが空リストな通常のペアに「化ける」。 そうでなければ、carに返されたオブジェクト、cdrに元のジェネレータを持つ 新たな遅延ペアが作られ、元の遅延ペアはcdrが新しい遅延ペアを指す通常のペアに化ける。
generatorがEOFを返した場合:
+---+---+
| * | ()|
+-|-+---+
|
v
obj
generatorがEOF以外のオブジェクト(obj2)を返した場合:
+---+---+ +===+===+
| * | *----->| * | *----> generator
+-|-+---+ +=|=+===+
| |
v v
obj obj2
遅延ペアから通常のペアへの変化は透過的かつidentity preservingである。 透過的というのは、指している先のオブジェクトが遅延ペアか通常のペアかは 普通の方法では判別できないということ。 identity preservingとは、遅延ペアが通常のペアになった時に、 オブジェクトのidentity (Gaucheの場合は、オブジェクトのメモリ上のアドレス)が 変わらないということ。
この方法だと、リストの1要素あたりのオーバヘッドは、 ジェネレータ手続きの呼び出しと新たな遅延ペアのアロケートだけである。 通常のリストでも1要素あたりペアが一つアロケートされるから、後者はある程度相殺される。 そして、Gaucheでは手続き呼び出しは軽い。
ところでtcfmで話を出したのは、透過性をどう実現するかという点で、 Schemeレベルだけならcarやcdr手続きの中で遅延ペアかどうかをチェックして処理を変えるという 手もあるのだけれど、Cレベルではcarフィールドやcdrフィールドに直接アクセスしてる。 carやcdrにアクセスする機会は非常に多いので、そこにオーバヘッドを入れたくない。 ペアの要素にアクセスするためには、その前に必ずオブジェクトがペアであるかどうかを チェックしているはずなので、 じゃあペアかどうかのチェック手続きの時点で遅延ペアをforceしてしまえば良いじゃないか、 という発想である。
実際のコードでは次のようになっている:
#define SCM_PAIRP(obj) \
(SCM_HPTRP(obj)&&(SCM_HTAG(obj)!=7||Scm_PairP(SCM_OBJ(obj))))
前半が通常のペアかどうかの判定で、それを満たさなかった場合に
Scm_PairP()を呼び出すが、その中で遅延ペアかどうかの判定と
必要ならforceするという処理を行っている。
(Scm_PairP() を呼び出す部分はオーバヘッドになる。
が、遅延ペアはもともと少ない上に一度チェックされたら通常のペアになっちゃうんだから、
SCM_PAIRPが呼ばれるペアのほとんどは通常のペアだ。
ペアでないものに対してSCM_PAIRPを読んだ場合はペナルティがあるが、
そのほとんどの場合、続く処理はランタイム型エラーを投げるものなので問題にならない。)
なお、遅延シーケンスはリスト関数にそのまま渡せるが、上で書いたmap1に渡すと
map1自身がリストを全部読んでしまうので、そこで全てがforceされてしまう。
遅延シーケンスを「返す」関数は別に書かねばならない。
上の方で書いたmap1を素直に遅延シーケンス版にするとこうなる。consが
lconsになるだけ。
(define (lmap1 proc lis)
(if (null? lis)
'()
(lcons (proc (car lis))
(lmap1 proc (cdr lis)))))
(この定義は要素毎にクロージャを作るので最適ではない。詳しくは後述。)
さて、これまでの説明で気づいた方もいると思うが、Gaucheの遅延シーケンスでは 遅延ペアをforceした時点で「次の要素」が計算されてしまう。 つまり常に1つ先の要素が計算されることになる:
gosh> (define z (lmap1 twice '(1 2 3))) x=1 z gosh> (list-ref z 0) x=2 2 gosh> (list-ref z 1) x=3 4 gosh> (list-ref z 2) 6
たかだか一つ余分に評価するだけなので、 Gaucheとしては性能的なペナルティは気にしない方針。 但し、遅延シーケンスの計算に「自分自身のシーケンスの前の方」を参照している場合、 扱いが複雑になる場合がある。
(なお、一つ余分に計算しなければならないのは、Gaucheでは空リストが固定の定数なので、遅延ペアを空リストに「化けさせる」ことができなかったからだ。 空リストをタグ付きオブジェクトにして、空リストのインスタンスが複数あっても良いことにすれば、余分に計算しておく必要はなくなる)
遅延シーケンスを使って、最初の例題を書き直すとこんな感じになる。
ファイルから1行づつ読む遅延シーケンスは、ファイルをオープンしてportを作ってから
port->string-lseq で生成している
(遅延シーケンスは最後まで読まれるとは限らないので、途中で中断してもファイルが
クローズされるようにするために、全体をcall-with-input-fileで囲む):
(use gauche.lazy)
(call-with-input-file "data.dat"
(^[port]
($ find-index (cut > <> 65535)
$ lmap (cut number->string <> 16)
$ port->string-lseq port)))
mapは遅延させるためにlmapにする必要があるが、find-indexは
もともと必要なところまでしか読まないので遅延版を必要としない。
余再帰とジェネレータ
遅延ストリームを作る定石は、素直な再帰をするコードのconsを遅延cons (lazy-consと表記) で置き換えることだ:
(define (F ...) ... (lazy-cons item (F ...)))
この方法はしかし、lazy-consの引数にあるFの呼び出しを遅延するために クロージャの作成を必要としてしまう。
Gaucheではそれより、 一旦ジェネレータを作ってからそれを遅延シーケンスにする方が速い。 これについては以前のエントリがあるので参照して欲しい:
上で書いたlmap1のジェネレータ経由版は次のとおりだ。
(define (lmap1 proc arg)
(generator->lseq (^[] (if (null? arg)
(eof-object)
(proc (pop! arg))))))
さらに詳しく知りたい方は、マニュアルを参照して欲しい。
Tags: Gauche, Clojure, Programming
Post a comment