[deprecated] Julia の Macro と Iteration の実験

この記事は初投稿日から5年以上が経過しています。

[^alert5y]

【2021/04/04 追記】初めにの前に

この記事は Julia の対象バージョンが古すぎて、もはや「Macro の基本的な書き方」くらいしか有用性がありません。

• 現在の Julia（v1.0 以降）では型や型パラメータの書き方が仕様変更されています。この記事の通りにコードを書いても最新の JUlia では動作しません。
• 現在の Julia（v1.0 以降）ではイテレーションの仕様が変更されています。例えばこれらの記事を参照してください。
  • Julia 0.7-DEV の新しい Iteration に触れてみた。
  • Julia で遊ぼう フィボナッチ数列
• あとこの時作ったモノに（自分で書いておきながらもはや）有用性も感じていないので、最新版に合うように記事を修正したりリライトする予定はありません。
  • 例えばフィルターの例では、最新のJulia なら Iterators.filter() という関数（遅延版の filter()）が用意されています。遅延版の map() も（Julia v1.6.0 から）Iterators.map() が存在します。
  • 例えば @lazy [i^2+i+1 for i=1:10000] は、Julia v0.5 以降で導入された Generator を用いて (i^2+i+1 for i=1:10000) と書けば事足ります。Generator については、例えば以下の記事を参照してください。
    Julia 0.5-dev の Generator に触れてみた。
• 以上の注意書き・代替案の提示と、その他明らかに記述や用語がおかしいところの修正のみが今回の編集内容となります

以上、それでも良ければ続きをご覧ください。

初めに

ふと思いつきで、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 というマクロを定義しています¹。
これは、遅延リストでないイテレータ²も簡単に遅延リストにしてしまうスグレモノです。

例えば @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個を、取得したい」
という要望があるとしましょう³。

これを、@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個を、取得したい」
という要件を考えてみましょう⁴。

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 のマクロ

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

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. 日本語訳としては「同図像性（を持つ）」が定番のようです。ただしJuliaは同図像性を持つことを開発のモチベーションの1つとしていただけで、コードをデータ構造として直接的に扱えるわけではありません（でもワンクッション置いているだけです、https://stackoverflow.com/questions/31733766/in-what-sense-are-languages-like-elixir-and-julia-homoiconic#answer-31734725 の StefanKarpinski の返答を参照）。 ↩

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