Julia 0.5-dev の Generator に触れてみた。

## 前置き

GW いかがお過ごしでしょうか？
私は、色々あって超暇なのでCNNとかRNNとかいろいろ実験しようと思ってた[^1]のですが、体調崩して連休の半分くらい寝てました[^2]。

[^1]: あと勉強会の資料作りとか進捗ダメです。。。
[^2]: ちなみに昨日はBlu-rayにダビングしてあった5年前の某アニメを一気見してました。ヴィクトリカかわいー

ということでちょっとリハビリに、[Julia](http://julialang.org/ "The Julia Language") の HEAD（2016/05/06 13:00 時点の最新 v0.5.0-dev+3922）をインストールして試してみました。
その中で「これ Julia に欲しかった！」が実装されていたので紹介します。

## Generator 式

Julia には、Python に類似の **リスト内包表記** があります：

```jlcon
julia> ls0 = [i for i in 1:10000]
10000-element Array{Int64,1}:
     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
     ⋮
  9992
  9993
  9994
  9995
  9996
  9997
  9998
  9999
 10000

julia>
```

Python では、この `[〜]` を `(〜)` に置き換えると、リスト（配列）ではなく `generator` オブジェクトが生成されます。これは実際の値をその都度算出するイテレータです。
Julia に、この機能が実装されます（ました）。

```jlcon
julia> it0 = (i for i in 1:10000)
Base.Generator{UnitRange{Int64},##1#2}(#1,1:10000)

julia> take(it0, 10)
Base.Take{Base.Generator{UnitRange{Int64},##1#2}}(Base.Generator{UnitRange{Int64},##1#2}(#1,1:10000),10)

julia> collect(take(it0, 10))
10-element Array{Int64,1}:
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10

julia> 
```

何に使えるのか。
例えば、約半年前に [Julia Advent Calendar 2015](http://qiita.com/advent-calendar/2015/julialang "Julia Advent Calendar 2015 - Qiita") で [実験](http://qiita.com/antimon2/items/1673fea71fc7b4e98bb4 "Julia の Macro と Iteration の実験 - Qiita") した、「たくさんある中からフィルターかけてほんの一部のみ抽出」する場合に、高いパフォーマンスが得られます。

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

julia> @time collect(take(drop(filter(isprime,it0),10),10))
  0.000051 seconds (128 allocations: 5.313 KB)
10-element Array{Int64,1}:
 31
 37
 41
 43
 47
 53
 59
 61
 67
 71

julia> 
```

これは、通常のRangeオブジェクトが、filter()関数で処理するときに「全要素をチェックして条件を満たしたものを集めたリスト（配列）」を作ってしまう（10000件チェックして要素数1229のリストが作られる）のに対して、Generator オブジェクトを利用した方は「必要な要素のみ処理する仕組み」になっている（結果としてfilter時は71件だけチェックし20件だけ次の処理に渡している）からです[^3]。

[^3]: ほぼ前回記事からのコピペ。

ただ注意点として、以下のようにインラインで記述しても、期待したパフォーマンスが得られません。

```jlcon
julia> @time collect(take(drop(filter(isprime,(i for i in 1:10000)),10),10))
  0.142189 seconds (133.55 k allocations: 5.504 MB)
10-element Array{Int64,1}:
 31
 37
 41
 43
 47
 53
 59
 61
 67
 71

julia> 
```

これは、`(〜for〜in〜)` を記述する度に毎回 Generator オブジェクトが生成されるのですが、その型が（型パラメータレベルで）毎回異なるものになるので、イテレーションの基本となる `start()` `next()` `done()` 各関数のJITコンパイルがその都度発生するためです（だと思われます）。
一度変数に入れておいて（且つ一度少しイテレーションを実行するなどして）からでないと（さらにそれを使い回すようにしないと）、最適化された結果を利用出来ない、ということですね[^4]。

[^4]: この辺、将来的にどうにかうまく最適化されるようにならないかな、と淡い期待。

## `Generator` 型

※この節の内容は、現在の Julia-HEAD(v0.5.0-dev+3922) に基づいています。将来的には仕様変更となる可能性があります。

前節 を見ていただけると分かる通り、Generator 式で得られるオブジェクトは `Generator` 型のオブジェクトのようです。

```jlcon

julia> ?Base.Generator
  Generator(f, iter)

  Given a function f and an iterator iter, construct an iterator that yields
  the values of f applied to the elements of iter. The syntax f(x) for x in
  iter is syntax for constructing an instance of this type.

julia>
```

ソース（[オリジナル](https://github.com/JuliaLang/julia/blob/master/base/generator.jl "julia/generator.jl at master · JuliaLang/julia") から抜粋）：

```jl:generator.jl
"""
    Generator(f, iter)
Given a function `f` and an iterator `iter`, construct an iterator that yields
the values of `f` applied to the elements of `iter`.
The syntax `f(x) for x in iter` is syntax for constructing an instance of this
type.
"""
immutable Generator{I,F}
    f::F
    iter::I
end

# 《中略》

start(g::Generator) = start(g.iter)
done(g::Generator, s) = done(g.iter, s)
function next(g::Generator, s)
    v, s2 = next(g.iter, s)
    g.f(v), s2
end

# 《後略》
```

こんな感じの実装です。
先述の [実験](http://qiita.com/antimon2/items/1673fea71fc7b4e98bb4 "Julia の Macro と Iteration の実験 - Qiita") で書いた、lazy.jl の `Lazy` 型や `LazyComprehension` 型と同様、（この辺だけを見れば）至ってシンプルな実装です。

あと、これを直接利用すれば、Generator式 を使わなくても `Generator`オブジェクト は作れますね。

```jlcon
julia> it1 = Base.Generator(Base.identity, 1:10000)
Base.Generator{UnitRange{Int64},Base.#identity}(identity,1:10000)

julia> collect(take(it1, 10))
10-element Array{Int64,1}:
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10

julia> @time collect(take(drop(filter(isprime,it1),10),10))
  0.000055 seconds (128 allocations: 5.313 KB)
10-element Array{Int64,1}:
 31
 37
 41
 43
 47
 53
 59
 61
 67
 71

julia> 
```

うん、生成されるオブジェクトの型パラメータ以外はまったく同様の結果ですね。
しかも。一度↑を実行すると、`Generator`オブジェクト をインラインで生成してもほぼ同等のパフォーマンスが得られます↓。

```jlcon
julia> @time collect(take(drop(filter(isprime,Base.Generator(Base.identity, 1:10000)),10),10))
  0.000064 seconds (130 allocations: 5.375 KB)
10-element Array{Int64,1}:
 31
 37
 41
 43
 47
 53
 59
 61
 67
 71

julia> 
```

同じ型パラメータを持つ `Generator`オブジェクト ならばJITコンパイルが有効に働いて最適化された結果が利用されるので、期待したパフォーマンスが得られる、というわけですね[^5]。

[^5]: 正式リリース時、あるいは将来的なバージョンアップで、こんな小手先テクニックを使わなくて済むようになることを願います。。。

## おまけ：関数の型

Julia v0.5 からは、関数（無名関数含む）に個別の型が設定されるようです。

```jlcon
julia> it0.f
(::#1) (generic function with 1 method)

julia> typeof(it0.f)
##1#2

julia> supertype(typeof(it0.f))
Function

julia> 
```

`#1` というのが、`(i for i in 1:10000)` という Generator の関数（の文字列表現）。
`##1#2` が、その関数の型（の文字列表現）。その super type[^6] は `Function`。
ついでに `#1` というのは、無名関数につけられた仮の名前のようなものみたいです。

`isleaftype(typeof(it0.f))` が `true` になるので、本当に個別の型のようです。abstract でないので、継承はできません[^7]。また関数型言語とかでよくある「引数と戻り値の型で関数の型を表現する」というような仕組みでもない模様です。
ただ無名関数（ラムダ式で定義された関数）にも型が設定される[^8]ので、JITコンパイルの対象になるようです。それもパフォーマンス向上の一役を担っているようです。

## おまけ2：Julia HEAD のインストールについて

Julia HEAD は、[以前](http://qiita.com/antimon2/items/a8cd98257219773b9ef3#julia-040-dev "Julia の共存インストール - Julia 0.4.0-dev") にも homebrew-julia でインストールしていました（環境は Mac OSX 10.11.4 です）。
今回も以下の手順でインストールしました。時間がかかった以外は特に難しいことはありませんでした。

```bash
$ brew update
$ brew reinstall julia --HEAD --with-accelerate
$ julia --version
julia version 0.5.0-dev
$ julia
               _
   _       _ _(_)_     |  A fresh approach to technical computing
  (_)     | (_) (_)    |  Documentation: http://docs.julialang.org
   _ _   _| |_  __ _   |  Type "?help" for help.
  | | | | | | |/ _` |  |
  | | |_| | | | (_| |  |  Version 0.5.0-dev+3922 (2016-05-05 18:51 UTC)
 _/ |\__'_|_|_|\__'_|  |  Commit e0e93fc* (0 days old master)
|__/                   |  x86_64-apple-darwin15.4.0

julia>
```

インストール中のログを消してしまったのですが、openblas-julia, suite-sparse-julia, arpack-julia といった依存パッケージが、 El Capitan 用のビルド済バイナリがインストールされたような気がします。
問題が起きたら、この辺をまた [ソースから入れ直す](http://qiita.com/chezou/items/136959635463a918b8be "homebrewでjuliaのHEADのインストールに失敗した時にするといいこと - Qiita") とかしないとダメかも。今のところは問題なく動いているので様子見です。

## 参考：

+ [Julia（公式サイト）](http://julialang.org/ "The Julia Language")
+ [Julia（ソースコード）](https://github.com/JuliaLang/julia "JuliaLang/julia: The Julia Language: A fresh approach to technical computing.")
+ [Julia v0.5.0 Release Notes](https://github.com/JuliaLang/julia/blob/v0.5.0/NEWS.md#julia-v050-release-notes "julia/NEWS.md at master · JuliaLang/julia")
+ [homebrew-julia](https://github.com/staticfloat/homebrew-julia/ "staticfloat/homebrew-julia: small repository to install julia")

[^6]: ちなみに super type を返す関数も v0.4 までの `super()` が deprecated になって新しく `supertype()` という関数になるみたいです。どんどん仕様が変わるー
[^7]: `isleaftype()` は、その型が「具象型（`abstract` でない型）」かどうかを返す関数。Julia では abstract でない型は継承出来ません（＝subtype を作れません＝type tree では必ず leaf になる）。
[^8]: それに加えて「全ての関数は generic になる」という仕様変更もあるようです。