これは、ドリコム Advent Calendar 2014 - Adventar の15日目の記事です。
14日目は、id:shouyu7144 さんによる、 VPC PeeringされたAWS環境に、単一のVPN接続でアクセスする - ¯_(ツ)_/¯ です。
- ソーシャルゲーム大好きおじさんです。
- スマホゲーム大好きおじさんです。
- もう3年くらいコンソールのゲームを触っていません。
計算機プログラムの構造と解釈 (原文) (日本語訳) (以下、SICP) という、計算機科学の教科書の、3.5.2 無限ストリーム の節が好きです。無限っていう響きがいいですね。厨二っぽいので。
今回はその内容の一部をRubyで写経してみます。遅延評価ストリームには lazy_stream gem という既存の実装がありますが、学習のため、あえて写経します。
ここでいうストリームとは、データの並びの抽象化のひとつで、必要な時になるまで計算を遅延させるようなもののことを言います。他に、典型的なデータの並びには配列があります。配列は、全ての要素があらかじめ計算済みであることを前提としていますが、ストリームはそうではありません。
配列は全ての要素をメモリに置く必要があるので要素数に制限がありますが、必要に応じて都度計算するストリームにはその制限がありません。無限の長さを持つストリームを無限ストリームと呼びます。
Rubyでは並びを Enumerator (列挙)で抽象化することができます。Enumerator#new にブロックを渡して生成したインスタンスは、あらかじめ全要素を作成してメモリに置くのでなく、#each が呼び出されるたびにブロックを評価して次の要素を生成するので、本稿のストリームの定義に合致しています。本稿ではこの Enumerator を使用してストリームを実装します。これにより、Enumerable のメソッド(の一部)をそのまま使用してストリームにアクセスすることができます。
Enumerator::Lazy というクラスもありますが、本稿では遅延評価を自分で実装するので、使用しません。
Enumerator を使用して、整数の無限ストリームを以下のように定義することができます。
def integers_starting_from(n)
Enumerator.new do |y|
loop do
y << n
n += 1
end
end
end
def integers
integers_starting_from(1)
end
p integers.first(10)
# => [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
p integers.first(10000).last
# => 10000Enumerator#new のブロック内には停止条件が書いてありませんが、#first は先頭から見て必要な個数分しかブロックを評価しないので、無限ループにはなりません。試しに integers.to_a などとすると無限ループします。
しかし、ここではSICPの例にならい、ループでなく再帰で整数ストリームを定義し直します。(理由は写経だからです。) そのための基盤として cons_stream, stream_carcdr を以下のように定義します。これはSICPの3.5.1にならっています。
# carのリテラルと、cdrの「評価結果がストリームとなるようなブロック」を合成して、新しいストリームとして返す
def cons_stream(car, &cdr_proc)
Enumerator.new do |y|
loop do
y << car
car, cdr = stream_carcdr(cdr_proc.call)
cdr_proc = -> { cdr }
end
end
end
# ストリームの先頭要素と、後続のストリームの組を返す
def stream_carcdr(stream)
car = stream.next
cdr = stream
[car, cdr]
endこれを使って integers_starting_from を定義し直します。
# nから始まる整数のストリームとは、先頭要素がnで、後続要素が「n+1から始まる整数のストリーム」であるようなもの
def integers_starting_from(n)
cons_stream(n) { integers_starting_from(n+1) }
end
def integers
integers_starting_from(1)
end
p integers.first(10)
# => [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
#p integers.first(10000).last
#めちゃくちゃ重いcons_stream で呼び出し側がブロックを定義して評価を遅延させているあたり苦しいです。Rubyにはスペシャルフォームがないので、いたしかたありません。またRubyには末尾呼出し最適化がないので、再帰はスタックを消費し、SICPのSchemeと比べて高コストです。あまり大きな数を指定しないことで凌ぎます。
配列に対する Array#select のように、ストリームに対して、条件を満たす要素だけを含む新しいストリームを生成して返す stream_filter を定義します。
def stream_filter(stream, &pred)
# stream.lazy.select(&pred) でもいいけど
# ストリームに対し、先頭要素を条件判定関数(pred)の引数に渡して、
# 条件を満たすなら「先頭要素+後続要素をフィルタにかけたもの」を返し、
# 満たさないなら「後続要素をフィルタにかけたもの」を返す
# (無限ストリームしか扱わないので、終端の処理は省略)
car, cdr = stream_carcdr(stream)
if pred.call(car)
cons_stream(car) { stream_filter(cdr, &pred) }
else
stream_filter(cdr, &pred)
end
endこれを使うと、「7で割り切れない整数」を以下のように得ることができます。
def no_sevens
stream_filter(integers_starting_from(1)) { |x| x % 7 != 0 }
end
p no_sevens.first(20)
# => [1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 15, 16, 17, 18, 19, 20, 22, 23]次に、フィルタを使って素数の無限ストリームを定義します。素数判定には エラトステネスのふるい を使用するのですが、そのストリーム版は以下のように定義します。
def sieve(stream)
car, cdr = stream_carcdr(stream)
cons_stream(car) {
sieve(stream_filter(cdr) { |x| x % car != 0 })
}
end
def primes
sieve(integers_starting_from(2))
end
p primes.first(20)
# => [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]解説します。sieve は以下のような動作をします。
- 2で始まる整数のストリームに対して処理を開始する
- 先頭の要素は素数なので、これは戻り値のストリームに含める
- 後続の要素は先頭の要素で割り切れてはいけないので、「先頭の要素で割り切れない」という条件でフィルタする
- 2.に再帰して繰り返す
具体的に最初の数ステップを取り出すと、
- まず2が取り出され、後続は「3で始まり、2で割り切れない整数のストリーム」になる
- 次に3が取り出され、後続は「5で始まり、2でも3でも割り切れない整数のストリーム」になる (3の次の4は2で割り切れてしまうので)
- 次に5が取り出され、後続は「7で始まり、2でも3でも5でも割り切れない整数のストリーム」になる (5の次の6は2や3で割り切れてしまうので)
これはWikipediaの解説にある通りだということが分かると思います。
裏では複雑な計算が行われているのに、定義はまるで単に数式を書いているような感覚が伝わるでしょうか。
ストリームはその名の通りストリーミングと相性が良いです。上記の素数ストリームを rack-stream に載せて、ブラウザからアクセスできるようにしました。
実装を primes_rackapp で公開しています。
素数ストリームの実装 primes.rb は
本稿に掲載したのと同じものです。
config.ru の after_open フックで素数ストリームを初期化し、
EventMachine のタイマ
を使って1秒ごとに順次素数を取り出して出力しています。
これだけやってもSICPのうち3ページくらいしかカバーできませんでした！！！！！ 第4章 のメタサーキュラーインタプリタ、非決定性計算、論理型プログラミングも面白くて頭が痛くなります。 SICPはとにかくボリュームがあるので、皆様もゲームのスタミナ回復待ちの間につまんでみてはいかがでしょうか。無料です。
16日目は takkjoga さんです。