龍虎氏がこういう事を書いていた。
使いどころとしては・・いずれやろうと思ってる数学の勉強でなら使えそうですかねぇ？パッと調べた感じでは「遅延ストリーム ゲーム 応用」とか「遅延評価 ゲーム 応用」なんかでは全く引っかからないんですよねぇ・・
基本的に、先行評価の言語で一番お世話になる部分的遅延評価は何と言っても遅延リスト(ストリーム)だ。何せ「リスト」と言ってる限り、単純にリストが使えるトコは全部使える、って言って良い。
でも「リスト」でO.K.だ、って事をわざわざストリームで代用する必要はあるのか、と問われれば基本的には「無い」だろう。単純に言うと、「リスト」はメモリを食いつぶす可能性がいつもあるが、ストリームは単に「計算の約束事」を凍結したモノなんで、メモリの使用量が少ない、とは言えるかもしんないけど、今の富豪の時代、果たしてそこまで神経質になるケースがあるのか、って話になる（※1）。
じゃあ、ストリームは「理論」だけで使いどころがないのか、と言われると「ある」とは言える。これは単純に「選択肢が増えた」って事なんだけど、要するに「ゲーム」で構造的に「無限ループ前提」が何らかで関わってる時、それはストリームを使えるチャンスだ、って事だ。
代表的な例にテトリスがある。龍虎氏は一回実装してるんで分かりやすいだろう。
テトリスは「テトリミノ」と言われる、いわゆる「ブロック」を延々と作り出す。ゲームオーバー、つまり、テトリミノが積み重なって枠の上部に接触するまでそれは行われるわけだ。見方を変えると「ゲームオーバー」と言う「例外」が投げられる以外は「無限ループ」前提なんだ。
ここでは「テトリミノ」生成システムを極めて単純化してRacketでちと説明してみよう。
テトリミノは全部で7種類あり、例えばそれを大域変数で書いておく。
(define *tetrimino* '(I O S Z J L T))
ここでは単純化してI、O、S、Z、J、L、Tをそれらの名前をする(※2)。
Racketのracket/randomライブラリにはリストからランダムに要素を取り出すrandom-refと言う関数がある。
> (require racket/random)
> (random-ref *tetrimino*)
'O
> (random-ref *tetrimino*)
'J
> (random-ref *tetrimino*)
'L
> (random-ref *tetrimino*)
'L
> (random-ref *tetrimino*)
'O
>
さて、通常、テトリミノを生成する、とすると次のような無限ループ前提のコードを書くだろう。
(let loop ((tetrimino (random-ref *tetrimino*)))
(printf "落ちてきたテトリミノ: ~a~n" tetrimino)
(when (read-char)
(loop (random-ref *tetrimino*))))
ループ毎にrandom-refを走らせて大域変数*tetrimino*からランダムにテトリミノを選びそれを生成する。
一方、無限ストリーム前提なら、「落ちてくるテトリミノの無限長のストリーム」を生成する事を考え、「そこにあるデータ」から先頭を持ってくるように書けばいい。
(define *s* (stream-cons (random-ref *tetrimino*)
(stream-map (lambda (x)
(random-ref *tetrimino*)) *s*)))
(let loop ((tetrimino *s*))
(printf "落ちてきたテトリミノ: ~a~n" (stream-first tetrimino))
(when (read-char)
(loop (stream-rest tetrimino))))
最初にテトリミノの(乱数による)無限長ストリームを定義してしまう。あとは先頭を取ってきつつ、リストのcdr再帰同様、stream-rest再帰をすれば、一々テトリミノを生成するコードと見た目上は同じ結果になるわけだ。
繰り返すが、基本的には「実装法の選択肢が増えただけ」だ。
ただし、ストリームには次のような利点がある。
テトリスに限らないが、いわゆる「落ちものパズル」では、「次に落ちてくるブツ」を表示する実装が多い。
これを無限ループで表すとするとコードは次のようになるだろう。
(let loop ((tetrimino (random-ref *tetrimino*))
(next-tetrimino (random-ref *tetrimino*)))
(printf "落ちてきたテトリミノ: ~a~n" tetrimino)
(printf "次のテトリミノ: ~a~n" next-tetrimino)
(when (read-char)
(loop next-tetrimino (random-ref *tetrimino*))))
最初にテトリミノを2つ計算する。次のループでは次のテトリミノを「落ちてくる」ブツにスライドし、改めて「次のテトリミノ」を計算する。
もちろん、今のPCでは問題はないが、単純に考えると記憶域が「次のテトリミノを表示しない」ヴァージョンに比べると2倍使われてる、って事になる。
一方、ストリームを使えば記憶域はそのまま、だ。
(let loop ((tetrimino *s*))
(printf "落ちてきたテトリミノ: ~a~n" (stream-first tetrimino))
(printf "次のテトリミノ: ~a~n" (stream-ref tetrimino 1))
(when (read-char)
(loop (stream-rest tetrimino))))
単に「出力」が2つに増えるだけ、だ。何せストリームは「永続的にそこにある」んで、単純に「次の要素」を覗くだけ、で済む。結果、使用記憶域を特に増やす必要はない、と言うメリットがあるんだ(※3)。
と言うわけで、「落ちものパズル」は無限長ストリームを使えるチャンスがある典型例だと言える。
他にも「無限ループが基本?」と思えるロジックで、テトリスのように「データ生成のルールがハッキリしてる」場合、積極的にストリームを使っていって良い、と言う事だ。
数学は言わずもがな、だろう。そもそも数学はある意味「無限を扱う学問」だ。結果、ストリームと相性がいい。
例えば次のような数列を考える。
断っておくけど、この数列の意味は?とか考えなくていい(笑)。数学好きが聞けば怒りそうな事を言ってるが(笑)、実際、何らかの意味があって提示してるわけじゃないんだ。
ただし、プログラムを書く、って観点で考える時、これらは「漸化式」だと見抜かなければならない、と言う事。そして「漸化式」である以上、「再帰」で解ける式である事を見抜かなければならない。
つまり、数式の「数学的意味合い」は分からんでも構わないが、式を見た時点で「これは再帰で書き下せるな」と言う「構造」を把握せなアカン、って事だ。
さて、x、yと2つを定義する式がある、って事は応用的にはこれはx-y平面に打つ「座標」と捉える事が出来る。そしてこの2つの漸化式は一次「じゃない」変換を表している。座標を前の座標から延々と計算していく、一種の「点描」を構成する数列なんだ。
実はネタバラシをすると、これは1990年代にブームになった「カオス理論」で描くCG集から適当にサンプルとして選んだ数式だ。当時は恐竜王国の蝿男のそそのかしもあり(※4)、「カオス」はそれなりにブームとなっていた。
とは言っても「研究」がどれほど進んだのかは知らんし、当時は「コンピュータで描画すると面白い」と言うような扱いがほとんどだったと思う。
皆、高校時代に、「一次変換」(※5)と言うのを習って、平面上の点から点へ移す、と言う作業を行った事はあると思う。ところがある種の一次「じゃない」変換だと、初期値や計算に使う係数を小さく変えても、点列で形作る描画が大幅に変わる、って事が発見されたわけだ。
これを当時、「カオス理論」と呼んだんだけど、ぶっちゃけ、「理論」って程でもねぇな、ってのが僕の印象だった(笑)。また、どういう数列が「カオス」を生み出すのか、と言うのも良く知らん。本当に当時と比べて、今どれくらい研究が進んだのか、ってのは全く知らんのだ。
いずれにしても、「一次変換」だろうと一次「じゃない」変換だろうと、座標に「連続適用する」となったらそれはプログラミング・テクニックとしては単に再帰の枠組みだ(※6)。
さて、再帰って事は再帰関数で定義可能、って事だが、テーマが「遅延評価」なんで遅延評価を用いる。項がnで表されてる、って事はnはいくらでも大きく出来るわけで、データ型として考えた場合、そう、「無限長ストリーム」が使うデータ型としてふさわしい。
まずはこう書く。
(define seq
(case-lambda
((a b d x0 y0)
(define s
(stream-cons (vector x0 y0)
(stream-map (match-lambda
((vector x y)
(vector (+ (* a x) (* b y)
(/ d (add1 (expt x 2))))
(- x))))
s)))
s)
((a)
(seq a 0.9 15 1 0))))
ここではデフォルト引数としてb = 0.9、d = 15、x0 = 1、y0 = 0 としている。
また、座標を扱う、って前提なんで、x、yはベクタとしてひとまとめにする実装にした。
さて、注目すべきはローカルで定義されたストリームsだ。端的に言うと、ローカルで無限長ストリームsを定義してそれを返すだけ、の簡単なお仕事になっている。
なっている。
が。
定義を読むと
「ストリームsはストリームsの各要素に特定の計算を施したものの先頭にvector(x0 y0)を付け加えたモノ」
と読めるだろう。
確かに再帰的定義には見える。しかし、散々っぱら今まで行った再帰関数の定義と違って無限ループを起こしそうな定義に見える。何故ならsをそのままsによって定義してるのが基本だから、だ。
しかし、良く考えてみて欲しい。これは確かに無限ループを起こしそうに思うんだけど、欲しいのは「無限長の」ストリームだ。従って、「無限ループを起こしそう」はWelcomeなんだよ(笑)。それが無限ループに陥らないのは、単に評価規則が違うから、だ。そうだな、遅延評価だ。
遅延評価が厄介なのは、実は理屈じゃないんだ。遅延評価を扱う前までは「無限ループを起こさないようにループしましょう」って前提でコードを書く練習をしてきている。
しかし遅延評価で初めて「無限ループを起こすようにコードを書きましょう」って言われる(笑)。要はこれが生理的に極めて気持ち悪いんだわ(笑)。
この、練習によって培った(要は経験による後天的な)感覚と如何に決別するのか、ってのが最大の障壁なんだ。理屈じゃない。阻害してくるのは感覚なんだよ。
しかし、ここでのローカルで定義された無限長ストリームはある種パターンだ。良く見て欲しい。実はこの定義は最初に見た「無限長のテトリミノ生成ストリーム」と全く同じ構造だ。
要は「この書き方」っつーか「フォーマット」に慣れちまえば無限長ストリームは「自在に作れる」って事になる。「生理的抵抗」に対して使う「枠組み」はたった一つの「形式」が基本なんだ。
よってstream-consとstream-mapのコンビネーションである「この形式」にまずは慣れよう。全てはそこから始まる。
;; 無限長ストリームのフォーマット(define s (stream-cons 初期値 (stream-map 計算 s)))
さて、無限長の「座標」のストリームを入手した(ある意味、座標の遷移を入手した、って事だ)。
ところで、通常、僕らが座標設定をする場合は直交座標系で考える。直交座標系、ってのも厳しい名称だけど、要は僕らが中学校辺りから使ってるx-y平面、ってなぁ直交座標系だ。
一方、理論的にどうだか知らんのだけど、少なくとも、カオスCGと言われる類で使われる座標系は斜行座標系らしい。何故なのか、は知らん。CG集ではそこの理屈は書かれてなかった(※7)。
いずれにせよ、上で書いた「数列」は直交座標系のモノで、これが表す「座標」を次の変換式を使って斜行座標系での「座標」に直さなアカン。
これら計算式により、直交座標系の点(x, y)は斜交座標系の点(sx, sy)へと移される。
これをプログラムするのは簡単だろう。Racketでは次のようになる。
(define (transpose pos ksx ksy)
(match-let (((vector x y) pos))
(let ((coef (/ 1 (sqrt 2))))
(vector (* coef (+ x y) ksx)
(* coef (+ (- x) y) ksy)))))
無限長数列のプログラムと座標変換のプログラムを合わせて、カオスの点描のプログラムを作る。
(define (chaos a ksx ksy)
(stream-map (lambda (pos)
(transpose pos ksx ksy))
(seq a)))
これもハナクソだろう。「無限長ストリーム」のプログラムを書く事は「生理的な嫌悪感」さえ克服すれば大して難しくもないし、斜交座標系への変換、カオス点描を作るプログラムも書くのは全然難しくない・・・。
一方、このプログラムは「与えられた無限長のデータ」を「無限長のままで」加工してる事を示している。その辺にやっぱ「え?」とか言う違和感を感じるのか否か、ってのが問題だったりする(※8)。
ここも「理屈」じゃないんだ。拒否感を覚えるのはあくまで「感覚」なんだよ。
しかしながら遅延評価を使った結果、ここで使ってる「数学」は計算させる事自体はクソも難しくないんだ・・・。遅延評価の動作に納得がいかない、にしてもな(笑)。
もっとも「遅延評価」と「超高級言語」Lispのせいでやたらプログラミングが簡単になってるわけで、原作のC言語でのプログラムは手間ばっかではある。
 | カオスの数学 芹沢 浩 東京図書 |
カオスの座標を6万個プロットすると次のような「笹の葉」みたいな図柄になっている。
a = -0.15 ksx = 0.96 ksy = 1.04
a = -0.32 ksx = 0.92 ksy = 1.08
a = -0.70 ksx = 0.81 ksy = 1.16
a = -1.09 ksx = 0.67 ksy = 1.24
a = -1.47 ksx = 0.51 ksy = 1.32
a = -1.66 ksx = 0.41 ksy = 1.35
描画も合わせた全プログラムはこのようになる。単純には無限長ストリームであるchaos関数から先頭の60,000個のデータを引っこ抜いてきて(stream-take)リストへ変換(stream->list)、なおかつそのリストをレンダラに変換(points)した後、png画像へと出力している(plot-file)。
ぶっちゃけ、カオスのプログラムを書くより描画の方がメンドクサイ(笑)。なお、プログラムの実行はそれなりに時間がかかるんで覚悟しておくように(笑)。ストリームの処理より出力の方がメンドイんだ。
と言うわけで、龍虎氏のお題に従って遅延評価の応用の典型例の2つを挙げてみた。
繰り返すが、遅延評価は特に難しくない。実は「プログラム初心者」がいきなり遅延評価をやっても充分理解可能な機能だとは思ってる。
と言うのも、プログラム初心者がループを初めて学んで困るのがループの「停止条件」設定なんだけど、遅延リスト設計ではその「停止条件」が要らない。「停止条件」が要らない以上、実はラクなんだよ。しかも遅延評価は無限ループを起こさない。
ただし、初心者じゃないと、遅延評価は「生理的にどうも気持ち悪い」ってぇんで敬遠したくなってくる、ってのが本当のトコだろう。
この記事がその「生理的嫌悪感」を解消する手助けになる事を望む。
繰り返すが、遅延評価自体はそんなに「使うのが難しい」と言うような機能ではないんだ。
※1: 基本的なデータとしての無限ストリームの操作はSICPが詳しい。どんなユーティリティが必要になるのか、の示唆にも富んでいる。
※2: これらの名称はWikipediaより。テトリミノの「形」をアルファベットで比喩している。
※3: これはちょっと不思議な挙動かもしれない。このストリーム前提のコードでテトリミノが「乱数」で生成されたモノが「凍結」されてるとすると、「解凍」した時点で乱数が働いて前の状態での「次のテトリミノ」と「今落ちてくるテトリミノ」が食い違う可能性があるのでは?と。
前回見たが、遅延評価が単純に無引数ラムダ式で「実行部分」を包んだThunkだとすればその通りだろう。ただ、実際は、これも前回見たが、実装上遅延評価は「メモ化」されている可能性が高い。
結果、一回実体化する(つまり「覗く」)とその値はキャッシュされ、それが使い回される、って事になる。
もっとも「遅延評価」がどう実装されてるのか、と言うのは厳密に言うと「実装依存」になる。
そういう意味では、ここで紹介したコードは「実装依存だ」って事になるだろう。
※4: ジェフ・ゴールドブラムの事。映画俳優。エキセントリックな役を得意としてた。
蝿と合体してしまう悲劇の科学者を演じたSFホラー、「ザ・フライ」で一躍有名になる。
また、「ジュラシック・パーク」でカオス理論を研究している数学者を演じた人としても有名。
※5: 「一次」と言うのはザックリ言うと、「一次方程式で記述出来る」と言う事だ。
よって、「一次方程式で記述出来ない」変換は一次「じゃない」変換、って事になるが、これには色々と種類がある。
※6: 要は、x1を求めるのにx0を使い、x2を求めるのにx1を使い・・・と言うのは「計算の連続適用」に他ならない。つまり、再帰構造となっている。
この辺のロジックにイマイチ自信が持てない人はこの記事でも参考に。
※7: 座標系によってモノの見え方、が違う。ピサの斜塔は地球上での直交座標系では「斜めに立ってる」が、適した斜行座標系で眺めると「キチンと直立してる」わけだ(笑)。
そういった、ちょっとしたSF的感覚を味わって欲しい(笑)。
※8: この辺、龍虎氏みたいに、「ストリームを加工してストリームを得る」事に感動するような感性を持ってる人には問題ナッシングだろう。
Filterと言いつつも内容がストリーム生成と同じ作りなので質問。
え・・これはすごい！以前の状態が適用されたものに新たな条件を重ねたストリームを生成出来るとなると・・パッと使いみちは思いつかないけど、無限を都度、変化させることが出来るのか！しかも遅延評価ってことは再計算不要でですよね？ほぇ〜
なんか凄さがちょっとは分かってきました
つまり、stream-mapもここでのfilterと同様に、ストリームを返す関数で、無限長のストリームを引数に取っても加工すべき「計算」も凍結してストリームを返すだけ、と言う事になる。
結果、無限長のストリームを返すseq関数にstream-mapでtranspose関数を適用しても問題ないわけだ。
(require (only-in srfi/1 every) srfi/41)
(define num
(stream-filter
(lambda (x)
(every not
(map (compose1 zero?
(lambda (m) (modulo x m)))
'(2 3))))
(stream-from 2)))
SRFI-41もストリームにストリーム演算を重ねている事に注目しよう。
> (stream->list (stream-take 6 num))
'(5 7 11 13 17 19)
