Help us understand the problem. What is going on with this article?

Julia 0.7-DEV の新しい Iteration に触れてみた。

More than 1 year has passed since last update.

TL;DR

  • Julia の Iteration は iterate() 関数を実装(多重定義)する(ように仕様変更された)。
    • それまでは start()/done()/next() の3つの関数を実装(多重定義)する仕様だった。

前置き

やっと色々落ち着いてきました1
週明けからまた色々忙しくなるはずなので、この合間に Julia の最新開発版をインストールして新機能を試してみて近未来を覗いたりしました2

もうすぐ v0.7.0-alpha が出るようですが、その直前(約1週間前)に、Iteration Protocol の仕様変更が入りました!
「何それおいしいの?」て訝しがる人も多いかもしれませんが、破壊的な変更3だったし個人的にちょっと意外だったので少し掘り下げてみました。

注意

以降に出てくる『新形式』の Iteration Protocol(詳細後述)は、
公式サイトで公開されている Nightly Build の Windows バイナリ(64-bit)(0.7.0-DEV.5228), Linux for X86(64-bit)(0.7.0-DEV.5187)、macOS バイナリ4(0.7.0-DEV.5236)で動作します(2018/05/29 07:00 現在)。

Julia の Iteration の仕組み

Julia のイテレーションについては、過去にも記事にしています(Julia の Macro と Iteration の実験
ズンドコキヨシ.jl with Iteration (追記あり))。
特に後者の ズンドコキヨシ の例がわかりやすいと思うのですが、Julia である型に対して特定の関数を実装(多重定義)すると、その型のインスタンスを for 式(の in 節)に渡せるようになります。

for cw in Zundoko()
    print(cw)
end

これは実は一種のシンタックスシュガーになっており、構文解析時に while 式に変換されます。
Julia v0.6.x まで5は、上のコードは以下と等価です(旧形式と呼ぶことにします)。

iter = Zundoko()
state = start(iter)
while !done(iter, state)
    (cw, state) = next(iter, state)
    print(cw)
end

なので先の記事では
start()/done()/next() の3つの関数を多重定義していたわけです。

これが v0.7.0 以降5は、以下と等価となります(新形式と呼ぶことにします)。

iter = Zundoko()
_next = iterate(iter)
while _next !== nothing
    (cw, state) = _next
    print(cw)
    _next = iterate(iter, state)
end

start()/done()/next() の関数呼び出しがなくなり、代わりに iterate() 関数呼び出しが2箇所に出現しています。
あと旧形式に比べて新形式は見た目1行増えていますが、関数呼び出しが1回減っていますし while の条件節は変数が nothing かどうかを見ているだけ(しかも !== なので純粋にオブジェクトとして同一かどうかの判定)なので、軽くなっていそうな気がしますね。
実際 プルリクのコメント を見てみるとベンチマークを取った上で master にマージしているようなので、パフォーマンスはきちんと検証されているのでしょう。

新旧比較

新形式の iterate() と旧形式の start()/done()/next() はどこが違うのか。まとめてみました。

まずは新形式の iterate() 関数が実装すべき仕様はこんな感じ:

  • iterate(iter)
    • 引数:
      • iter:イテレーション対象のオブジェクト
    • 戻り値:最初の要素と『初期状態オブジェクト』からなる Tuple、または nothing(列挙すべき要素が1つもない場合)
  • iterate(iter, state)
    • 引数:
      • iter:イテレーション対象のオブジェクト
      • state:一つ前の『状態オブジェクト』
    • 戻り値:次の要素と次の『状態オブジェクト』からなる Tuple、または nothing(すべて列挙し終えた場合)

続いて旧形式の start()/done()/next() 各関数が実装すべき仕様:

  • start(iter)
    • 引数:
      • iter:イテレーション対象のオブジェクト
    • 戻り値:『初期状態オブジェクト』
  • done(iter, state)
    • 引数:
      • iter:イテレーション対象のオブジェクト
      • state:『状態オブジェクト』
    • 戻り値:もう列挙すべき要素が残っていない(イテレーション終了の)場合 true、そうでなければ false
  • next(iter, state)
    • 引数:
      • iter:イテレーション対象のオブジェクト
      • state:一つ前の『状態オブジェクト』
    • 戻り値:次の要素と次の『状態オブジェクト』からなる Tuple

少し違うけれど、大体同じようなことをしているのは分かるのではないでしょうか。
特に注目すべきは、旧形式で start()/done()/next() の3つの関数が分担していた仕事を iterate() 関数1つで賄うようになった、ということ。引数1つの iterate(iter)start()+done()+next() 相当、引数2つ(以上)の iterate(iter, state)done()+next() 相当です。
1つにまとめることで効率化が図れる、という利点は先ほどから触れているとおりです。

でもただ1つにまとめただけでなく、戻り値の違いなどから、別の利点?もあるようです。

新形式の利点?

新形式は、Iteration の内部的な動きに一貫性を持たせることが出来る 模様です。
特に、『Iteration の開始時』において。

どういうことか。詳しく説明します。

例として、「テキストファイルから1行ずつ読み込んで列挙する」というユースケースを考えます。
なお、テキストファイルの行数は不定とします(数百行かもしれないし、数万行かもしれないし、0行かもしれません)。

そのような動きをする(ものとして設計された)オブジェクト iter があるとします。
この時

for line in iter
    println(line)
end

は、新形式では以下と等価となります:

_next = iterate(iter)
while _next !== nothing
    (line, state) = _next
    println(line)
    _next = iterate(iter, state)
end

この最初の _next = iterate(iter) を実行した結果 _next に代入されるのは、以下のいずれかとなります:

  • ファイルの1行目(文字列)と、ある『状態オブジェクト』からなる Tuple(ファイルが1行以上ある場合)。
  • nothing(ファイルが0行(つまり空)の場合)

そして nothing でなければ、その1行目の内容はもう取得済なのでそれを利用した処理をするだけ(println(line))。

while ループ最後の _next = iterate(iter, state) を実行した際も同様です(n回目のループの場合):

  • ファイルのn+1行目(文字列)と、ある『状態オブジェクト』からなる Tuple(ファイルがn+1行以上ある場合)。
  • nothing(ファイルがn行(つまりもう読み込む行がない)の場合)

nothing でなければその行の内容はもう取得済なのでそれを利用した処理をするだけ。
うん、一貫性ありますね。
仕様としても考えやすいと思います、とにかく「次の行があればその行となんらかの『状態オブジェクト』を返せば良い、なければ nothing を返せば良い」のですから。

これが旧形式だと以下のコードと等価となり:

state = start(iter)
while !done(iter, state)
    (line, state) = next(iter, state)
    println(line)
end

最初の state = start(iter) は:

  • 何らかの『初期状態オブジェクト』を返す(だけ)

while の条件部の done(iter, state) は:

  • (一つ前の)『状態オブジェクト』を参考にして、ファイルに次の行があるかどうかを判定(なければ true

その直後の (line, state) = next(iter, state) は:

  • 次の行(もし以前に next() 呼び出しがなく start()done() の直後なら、最初の行)と、次の『状態オブジェクト』の Tuple を返す

となります。

なんだかごちゃごちゃしているイメージですよね。
それに、一番のポイントは「done(iter, state)」と「next(iter, state)」。同じ引数の組で別々の関数を呼び出しています。そして前者は「次の行があるかどうかの判定」をするだけで、後者は「次の行(と状態オブジェクト)を返す」という動作。これ、「done() の時点で実際に次の行を読み込んで、読込に失敗したら true 返せば良くて、成功したらその行をどこかに覚えておいて次に next() 呼び出されたときにそれを利用するようにした方が効率良くね?」とか思う方もいらっしゃるかもしれません6

そのあたりを色々考えると、この3関数の実装方法には、少なくとも3つの実装方針が考えられます。

方針1:

  • start() 関数は、何らかの適切な『状態オブジェクト』を返す。
  • done() は、与えられたイテレータと『状態オブジェクト』から(のみ)終了判定をする(実際に要素を取得してみることはしない)
  • next() で、与えられた『状態オブジェクト』を参考に実際に値の取得をして(新しい状態オブジェクトと共に)返す

方針2:

  • start() 関数は、何らかの適切な『状態オブジェクト』を返す。
    ポイントはその『状態オブジェクト』を mutable にしておくこと。
  • done() 関数で、実際に次の要素を読み込んでしまう。
    読込に成功したら、引数で受け取った『状態オブジェクト』にその読み込んだ要素を格納しておく。
  • next() 関数では、『状態オブジェクト』に格納された(読込済の)要素を返すだけ(『状態オブジェクト』は使い回し)。

方針3:

  • start() 関数呼び出し時点で、最初の要素取得を試みる。
    それを格納した『状態オブジェクト』を返す。ただし取得に失敗したら『要素を格納していない状態オブジェクト』を返す。
  • done() 関数では、『状態オブジェクト』に要素が格納されていなかったら true を返す。
  • next() 関数では、『状態オブジェクト』に格納された(読込済の)要素を返す。
    その前に次の要素を取得し、成功したらそれを格納した『状態オブジェクト』を、失敗したら要素を格納していない『状態オブジェクト』を一緒に返す。

ほら、一貫していませんね。
start()/done()/next() という関数名とは裏腹に、設計方針によって全然違う動作となる実装(具体的には「要素を取得する」タイミングとそれをどの関数の役割として持たせるか)が可能なのです。

ちなみに本来想定している仕様は、最前者の「方針1」。『状態』を実際の要素の取得とは分離された概念として考えて、各関数にそれぞれ適切な役割を持たせる、というのが本来の思想。
ただし先ほど挙げた例からも分かるとおり、どうしてもその方針で実装出来ないパターンも出てきます。その場合、「方針2」または「方針3」の実装を余儀なくされる場合もあるのです。

これと比較して新形式は、1つの関数で1つの方針で実装出来る。よりシンプルな仕様となったわけです。

旧→新 変換

もしあなたが、今までの Julia(v0.6.xまで)で、独自の列挙可能な型を定義していて、旧形式で Iteration Protocol を実装したことがある場合。
以下のような方針で新形式に変換できます。

先述の「方針1」で実装した旧形式から新形式への変換:

  • start(iter) = hogeiterate(iter) = iterate(iter, hoge) に変換
    • ↓の第2引数の初期値として hoge を与えても良い。
  • done(iter, state)+next(iter, state)iterate(iter, state) とする(ただし終了時は true ではなく nothing を返す)

具体例(先述の ズンドコキヨシ.jl7

zundoko_iter_v06.jl
struct ZunDoko end

Base.start(::ZunDoko) = 0
Base.done(::ZunDoko, i::Int) = i == 6
function Base.next(::ZunDoko, i::Int)
    if i == 5
        ("キ・ヨ・シ!", 6)
    elseif i == 4
        rand([("ズン", 4), ("ドコ", 5)])
    else
        rand([("ズン", i + 1), ("ドコ", 0)])
    end
end

zundoko_iter_v07.jl
struct ZunDoko end

function Base.iterate(::ZunDoko, i::Int = 0)
    i == 6 && return nothing
    if i == 5
        ("キ・ヨ・シ!", 6)
    elseif i == 4
        rand([("ズン", 4), ("ドコ", 5)])
    else
        rand([("ズン", i + 1), ("ドコ", 0)])
    end
end

先述の「方針2」または「方針3」で実装した旧形式から新形式への変換:

  • まず『状態オブジェクト』を、取得した要素を格納できる mutable なものではなくもっと単純なものにする(1関数内で完結するので持ち回る必要が無いから)。
  • 終了判定が可能で実際『終了』と判定できた場合、もしくは要素を取得してみて失敗した場合は、nothing を返して終了。
  • そうでなければ、取得した次の要素と『状態オブジェクト』を返せばOK。

事例省略8

参考


  1. 某検査結果もどうやら異常なさそうですし。 

  2. 過去にも勉強が捗らないときに「Julia 0.5-dev の Generator に触れてみた。」り、「Julia 0.6-dev の新しい Type System に触れてみた。」りしています。 

  3. 移行措置は採られていて、従来の書き方でも Deprecated Warning が出るだけで(v0.7 ではまだ)使えますが、v1.0 では完全に移行する模様です。 

  4. 先日「macOS バイナリではまだ動作しません」としていましたが、やっと最新ビルドが通って動作するようになった模様です。 

  5. より正確には、Julia v0.7.0-DEV.5126 より前までは旧形式、以降は新形式となります。 

  6. C言語等、もっと低レベルな(≒よりコンピュータのアーキテクチャに近い)言語でのプログラミングを経験している方は「done() は オープンしたファイルディスクリプタに対して EOF をチェックすれば良いからわざわざ試しに1行読んでみることしなくても良い」てすぐに気付くかもしれません(実際 Julia でもファイル読込はそのような動作をするよう実装されています)が、あくまで例なので。そこまで考えが及ぶ方は「シンプルな終了チェックの出来ない何らかの『長さの分からないもの』から1つずつ要素を読み込む例」に置き換えて考えてください。 

  7. あの記事は2年以上前に書いた記事で、対象が Julia v0.4.x となっております。この記事ではそれを Julia v0.6.x 用に変換したコードを紹介しておきます(immutable キーワードを struct に置き換えただけですが)。 

  8. 例えば base/channels.jl の実装変更例 が参考になると思います。 

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした