More than 1 year has passed since last update.

初めに

ふと思いつきで、Julia の Macro とか Iteration とかの実験をしてみました。

一般的な目的のプログラミングではあまり使わないかもしれないけれど、言語仕様として押さえておくと後々いろいろ幸せになれると思うので。

対象は、Julia v0.4.x です(0.3.x では一部動作しませんたぶん)。

先に成果物

結果として、こんなの書きました。

lazy.jl
immutable Lazy{I}
    it::I
end

@inline Base.eltype{I}(::Lazy{I}) = eltype(I)
@inline Base.start{I}(lz::Lazy{I}) = start(lz.it)
@inline Base.next{I}(lz::Lazy{I}, st) = next(lz.it, st)
@inline Base.done{I}(lz::Lazy{I}, st) = done(lz.it, st)

immutable LazyComprehension{I}
    it::I
    next::Function
end

@inline Base.start{I}(lz::LazyComprehension{I}) = start(lz.it)
@inline Base.next{I}(lz::LazyComprehension{I}, st) = lz.next(lz.it, st)
@inline Base.done{I}(lz::LazyComprehension{I}, st) = done(lz.it, st)

macro lazy(ex)
    if ex.head == :comprehension
        return _comprehension2lazy(ex)
    end
    :(Lazy($ex))
end

function _comprehension2lazy(ex)
    body_ex = ex.args[1]
    vars_ex = ex.args[2].args[1]
    it_ex = ex.args[2].args[2]
    quote
        @inline donext(it, st) = (($vars_ex, next_st) = next(it, st); ($body_ex, next_st))
        LazyComprehension($it_ex, donext)
    end
end

これは何?

@lazy というマクロを定義しています1
これは、遅延リストでないイテレータ2も簡単に遅延リストにしてしまうスグレモノです。

例えば @lazy 1:10000 とすると、元のイテレータが Range<: AbstractArray) であることを隠し、start(),next(),done() 関数へのメソッドのみ提供することで、各種の処理をするときに計算済の値で最適化するのを抑制し、要素を一つずつ取り出して(or 算出して)必要なだけ計算するようになります。

またリスト内包表記にも対応しており、例えば普通に [i^2+i+1 for i=1:10000] と書いてしまうと要素数10000のリスト(1次元の配列)を返してしまいますが、@lazy [i^2+i+1 for i=1:10000] と書くことで、計算結果を一つずつ列挙する遅延リスト(イテレータ)を返すようになっています。

何に使うの?

例えば
「1〜10000の整数のうち、素数を、最初の10個は除いて、その後の10個を、取得したい」
という要望があるとしましょう3

これを、@lazy を使う場合と使わない場合とで比較してみましょう。

julia> @time collect(take(drop(filter(isprime,1:10000),10),10))
  0.001234 seconds (17.43 k allocations: 292.609 KB)
10-element Array{Int64,1}:
 31
 37
 41
 43
 47
 53
 59
 61
 67
 71

julia> @time collect(take(drop(filter(isprime,@lazy 1:10000),10),10))
  0.000084 seconds (127 allocations: 5.000 KB)
10-element Array{Any,1}:
 31
 37
 41
 43
 47
 53
 59
 61
 67
 71

julia> 

お分かりでしょう。
@lazy を使った方が、スピードもメモリ使用量も圧倒的に少なく済んでいます。
これは、通常のRangeオブジェクトが、filter()関数で処理するときに「全要素をチェックして条件を満たしたものを集めたリスト(配列)」を作ってしまう(10000件チェックして要素数1229のリストが作られる)のに対して、遅延リストは「必要な要素のみ処理する仕組み」になっている(結果としてfilter時は71件だけチェックし20件だけ次の処理に渡している)からです。

もう一つ。
「i^2+i+1(i=1〜10000)のうち、素数を、最初の10個は除いて、その後の10個を、取得したい」
という要件を考えてみましょう4

julia> @time collect(take(drop(filter(isprime,[i^2+i+1 for i=1:10000]),10),10))
  0.026909 seconds (120.48 k allocations: 2.427 MB)
10-element Array{Int64,1}:
  421
  463
  601
  757
 1123
 1483
 1723
 2551
 2971
 3307

julia> @time collect(take(drop(filter(isprime,@lazy [i^2+i+1 for i=1:10000]),10),10))
  0.002591 seconds (2.07 k allocations: 88.080 KB)
10-element Array{Any,1}:
  421
  463
  601
  757
 1123
 1483
 1723
 2551
 2971
 3307

julia> 

うん。期待通り。
使えそうな気がしてきましたよね?

改めて少し解説

Julia のイテレータ

公式マニュアルの Interfaces - Iteration を見ていただければ、まあ分かるかなとは思いますが、簡単に。

最低限、start(),next(),done()の3つのメソッドを備えたものがイテレータ(iterable object)と呼ばれるものになります。

  • start() …イテレーションの開始。引数はイテレータのみ、戻り値は「状態」を表すオブジェクト。
  • next() …イテレーションを次の状態に進める。引数はイテレータと、1つ前の「状態」オブジェクト。戻り値は、次の値と次の「状態」オブジェクトからなる tuple。
  • done() …イテレーションが終了状態かどうかを判定。引数はイテレータと「状態」オブジェクト、戻り値は、終了状態ならtrue、そうでなければfalse

今回実験で作った lazy.jl では、2つの immutable 型を定義し、それぞれについて start(),next(),done() メソッドを定義しています。つまり2種類のイテレータを定義している、ということになります。

Julia のマクロ

最近の言語でもよく見られる5、homoiconic な6マクロ。つまり「プログラムをプログラム中でデータ構造として扱うことができる」仕組みになっています。
function キーワードの代わりに macro キーワードで定義を開始したものがマクロになります。その引数は Expr 型で7、それがプログラムの構造をツリーデータとして持ったものになっています。
そこから各種情報を抜き出して利用することもできますし、構造を変更して新しいコードを生成することもできます。それこそがマクロの目的な訳ですね。

lazy.jl では、引数 ex が「リスト内包表記」かどうかを判定し、そうなら別の関数に処理を委譲、そうでなければ単純な Lazy(it) というコードに置き換えています。
ちなみにリスト内包表記だった場合はさらに、「body部(実際の値を計算している箇所、forの前)」と「変数部(forの後、inまたは=の前)」と「イテレータ部(inまたは=の後)」の3つを抜き出し、それを組み合わせて新しいコード(関数の定義+LazyComprehension(it, donext))を生成しています。

関数呼び出しも「呼び出そうとしてる関数」と「引数」を抜き出すことができるので、別の関数呼び出しに置き換えてしまったり、全く違うコードにしてしまうことも可能です。
余裕があったら、map() 関数、これが引数が遅延リストであっても結果が通常のリスト(1次元配列)になってしまうものなので、@lazy map(〜) と書くとリストではなく遅延リストを返すように lazy.jl を拡張してみようかな。


  1. Lazy.jl というサードパーティの追加パッケージがあり、そちらにも @lazy というマクロが用意されていますが、それとは別物です。仕様も使い方も違います。 

  2. 公式マニュアルには "Iterator" という言葉は出てこない("iterable object" という言葉なら出てくる)のですが、 Iteration Interface を備えた object を表す言葉として便利なので、この記事ではそれを「イテレータ」と呼ぶことにします。便利なので。 

  3. 現実にそういう要望がどれだけあるか、ということは考えてはいけません。それは野暮ってもんです。 

  4. 深く突っ込まないでください。 

  5. 個人の感想です。 

  6. 日本語訳としては「同図像性(を持つ)」が定番のようです。 

  7. より正確には、それとは限らないのですが、詳しくは公式マニュアルを見てください。