言語ゲーム

とあるエンジニアが嘘ばかり書く日記

Twitter: @propella
トップ > lazy > ふつうの言語で Lazy list について考える(6)。

ふつうの言語で Lazy list について考える(6)。

lazy

Scheme, Ruby, Squeak のそれぞれで実装された Lazy List を比較して特徴を味わってみます。それぞれ次のライブラリを使いました。

ODD か EVEN か？

命令型言語で作った Lazy List には ODD か EVEN かの違いがあります。ODD の方が API が簡単になりますが、常に一つ余計に評価するという欠点があります。ある Lazy List がどちらの性質になっているかを調べるには、例えば 4 番目にゼロ除算が起こるようなリストを作って、三番目の要素にアクセスしてみると分かります。

Scheme = EVEN (実は、gauche ではゼロ除算がエラーにならないみたいですが、マニュアルを信じて EVEN とします)

$ gosh
gosh> (use util.stream)
#<undef>
gosh> (stream-ref (stream-map (lambda (x) (/ 1 x)) (stream 3 2 1 0)) 2)
1

Ruby = EVEN

$ irb
>> require "lazylist"
require "lazylist"
=> true
>> list(3,2,1,0).map { |x| 1 / x }[2]
list(3,2,1,0).map { |x| 1 / x }[2]
=> 1

Squeak = ODD

(((LazyList fromArray: #(3 2 1 0)) collect: [ :x | 1 / x ]) take: 3) asOrderedCollection last
=> ZeroDivide

実装

Scheme と Ruby はどちらも EVEN な Lazy List だと分かりましたが、実装は微妙に違います。

  • Scheme
    • lazy list は一つの promise
    • promise を force すると cons セルになります
    • cons セルの car が現在の値、cdr が次のリスト
  • Ruby
    • lazy list は二つの要素 head と tail で出来ている
    • head と tail のそれぞれは、普通の値か promise のどちらか
    • head と tail のそれぞれのアクセッサでそれぞれの promise を force する
  • Squeak
    • lazy list は二つの要素 head と tail で出来ている
    • head は普通の値。tail は promise
    • tail のアクセッサで promise を force する

Squeak は SCIP http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-24.html の設計と同じです。Scheme はその改良型ですが、Ruby のは promise が二つというちょっと面白い設計になっています。もともと、遅延評価というのは引き数を遅延評価する事なので、リストコンストラクタの二つの引き数をそれぞれ promise にするというのは素直な設計なのかも知れませんが、わざわざ二つ必要な理由も思い浮かびませんでした。

コンストラクタ

それぞれ永遠に続く 1 の数列を作ってみます。大体どれも同じです。scheme だけはマクロが使えるので、ブロック構文が不要です。

Scheme

gosh> (define ones (stream-cons 1 ones))
(define ones (stream-cons 1 ones))
ones
gosh> (stream->list (stream-take ones 5))
(stream->list (stream-take ones 5))
(1 1 1 1 1)

Ruby

>> ones = LazyList.new(1) { ones }
ones = LazyList.new(1) { ones }
=> [1,... ]
>> ones.take 5
ones.take 5
=> [1, 1, 1, 1, 1]

Squeak

LazyList class >> ones
	^ LazyList cons: 1 with: (LazyValue delay: [self ones])

(LazyList ones take: 5) asOrderedCollection
=> an OrderedCollection(1 1 1 1 1)

面白いコンストラクタ

Ruby の lazylist には、Ruby ならではの文法を駆使した変わったコンストラクタが用意されています。list 関数は可変長引き数の関数で、最初に引き数に指定した数の要素、その後でブロックの処理が続くリストを作成します。引き数、ブロック共に省略可能です。

>> list(5,4,3,2) {ones}.take 10
list(5,4,3,2) {ones}.take 10
=> [5, 4, 3, 2, 1, 1, 1, 1, 1, 1]

また、引き数が一つのブロックの時は特別に、リスト内包的な表記でリストが作れます。この x のスコープはどうなってるんだ？！この辺 ruby ってきもいな。

>> list { x * 2 }.where(:x => ones).take 5
list { x * 2 }.where(:x => ones).take 5
=> [2, 2, 2, 2, 2]

あと、ちょっと便利かもしれない関数として、1 づつ増える数列から新しいリストを作る tablate というのが gauche と Ruby に用意されています。

gosh> (stream->list (stream-tabulate 10 (lambda (x) (* x 2))))
(stream->list (stream-tabulate 10 (lambda (x) (* x 2))))
(0 2 4 6 8 10 12 14 16 18)

>> LazyList.tabulate { |x| x * 2 }.take 10
LazyList.tabulate { |x| x * 2 }.take 10
=> [0, 2, 4, 6, 8, 10, 12, 14, 16, 18]

まとめ

  • Scheme、Ruby、Squeak それぞれで lazy list の内部構造は違うが、Scheme と Ruby の動作は大体同じ
  • Scheme はマクロがあるので promise を囲む必要が無い
  • Ruby はブロック構文と可変長引き数の組み合わせで変わったコンストラクタを持つ。