Итераторы

Реализация итераторов в Julia - это еще один плюс языку за дизайн.

Как и в некоторых объектно-ориентированнных языках, итератором может быть любой объект, на котором будут вызваться методы (в случае Julia - функции), для управления процессом итерации. Это start, next и done. А также желателен метод eltype, который напрямую не относится к процессу итерации. Если эти три метода определены, объект может быть итерируемым.

Прежде чем вникать в детали - небольшое отступление.
Немного непривычно то, что в Julia нет способа на уровне типов сообщить, что ожидается любой итерируемый объект, хотя варианты известных типов итераторов указать, конечно можно. Данная возможность обсуждалась разработчиками. Неизвестно, будет ли прогресс в этом направлении. Сейчас, как правило, тип агрумента, от которого ожидается поведение итератора или не уточняется совсем, или уточняется отдельно для каждого типа, если реализации отличаются.

Вызовы методов итерации встроены в синтаксис языка (как в Python, Ruby), поэтому программист, используя итератор, не вызывает их напрямую:

a1 = [2,3,4]
for i in a1
    println(i)
end

Данный фрагмент кода внутренне будет превращен в это:

let state = start(a1)
   while !done(a1, state)
       (i, state) = next(a1, state)
       println(i)
   end
end

Вы можете запустить оба фрагмента кода в REPL и убедиться, что они работают одинаково.

Интересно отметить, что в Julia итератор, обычно, не хранит свое состояние. Состояние хранится на потребляющей стороне. Почему это важно? Потому, что, если мы передаем объект итератора из одного контекста в другой, то мы не передадим вместе с ним его состояние. Переданы будут только те данные, доступ к которым предоставляется. Это значит, что вы никогда не получите итератор, который начнет отдавать последовательность не сначала.

Дополнительно, в случае , когда мы совершаем итерации путем явного вызова функций start, next, done, а этим мы занимаемся, когда разрабатываем собственные типы данных, или добавляем методы итерации к существующим объектам - мы застрахованы от того, чтобы случайно забыть про start, так как без него нам не получить состояние итерации, а оно необходимо, чтобы вызвать next.

В случае, когда мы делаем обход массива или какой-нибудь другой коллекции, неизменность состояния является естественным поведением, о котором мало задумываются. Но вся очевидность поведения исчезает, когда мы получаем итератор извне и не знаем его внутреннего устройства. Julia объявляет итераторы, как унифицированный доступ к последовательностям, независимо от их происхождения.

Примеры итераторов в стандартной библиотеке

Давайте посмотрим, как это реализовано в стандартной библиотеке, например на массивах.

Макрос @less открывает просмотр кода (как правило через линуксовый less), который будет вызван для указанного после @less выражения. Для выхода из него нужно нажать q:

julia> @less start([3,4,5])


start(A::Array) = 1
next(a::Array,i) = (a[i],i+1)
done(a::Array,i) = i == length(a)+1

Очень простая реализация. Как видно из примера, хранимое на принимающей стороне состояние - это, в случае массивов - просто индекс элемента, который будет возвращен на следующей итерации во время вызова next(). Напомню, что индексация массивов начинается с единицы. Итак, start() возвращает 1, и с этим индексом, мы приходим к done() и спрашиваем, "не закончились ли итерации?". done() принимающая (ссылку на) массив и состояние, проверяет не равен ли переданный ей индекс длине массива плюс один. К, примеру, если массив пуст, его длина равна нулю. Единица, в случае пустого массива, подпадает под условие done(). Все правильно: итерации закончатся, не начавшись. Если массив не пуст, на первой итерации done() вернет false, что даст добро на вызов next(). Мы идем к next() и просим ее вернуть нам следующий элемент, предоднося ей сам массив и хранимое у себя состояние. next() принимает массив (технически - ссылку на него) и состояние, равное единице на первой итерации и возвращает нам значение первого элемента массива и увеличенный на единицу индекс, который будет следующим, если done() разрешит. И так далее.

Создание собственных итераторов

Пусть мы захотели написать функцию mapfilter(f::Function, itr) -> itr, работающую с любыми итерируемыми объектами. Она должна принимать функцию и итератор, а возвращать новый итератор. На каждой итерации к текущему элементу i будет применена функция ( f(i) ), как это делается в функции map(). Если функция f примененная к элементу i вернет nothing, то этот результат исключается из результата.

Чтобы создать собственный итератор, нужно добиться того, чтобы start, next и done заработали, применительно к нему. Реализовать собственные методы этих функций, конечно, проще всего, определив их на собственном типе данных (множественная диспетчеризация в действии). Назовем его EMapFil:

immutable EMapFil{F,I}
     f::F
     i::I
end

Объект этого типа будет хранить указанную нами функцию, чтобы иметь возможность применять ее на элементах итератора-источника и ссылку на сам итератор-источник, чтобы иметь возможность вызывать его методы итерации.

Функция mapfilter создает объект EMapFil, сохраняя в нем итератор-источник в поле EMapFil.i и функцию в поле EMapFil.f :

mapfilter(f::Function, itr) = EMapFil(f,itr)

Теперь определим функции итерации на EMapFil:

start() будучи вызвана, передает вызов start() итератору-источнику.

function Base.start(itr::EMapFil)
     si = start(itr.i)
     try_advance_itr(itr, si)
end

После этого она вызывает try_advance_itr(), которая решает вопрос, какое состояние вернуть на хранение вызывающему коду.

Происходит это следующим образом. try_advance_itr() продвигает итератор-источник, если он не закончился. Если она смогла получить элемент, она применяет функцию f на этом элементе, и, если результат не равен nothing, возвращает результат, как результат текущей итерации. В случае результата равного nothing, она делает попытку получить следующий элемент. Когда же результат не равен nothing, вместе с результатом она отдает и состояние итератора-источника (полученное от него), чтобы start() или next() могли его передать вызывающей стороне. Если итератор-источник закончился (его done() вернула true), try_advance_itr возвращает пару значений (nothing, nothing). Так как, по определению, наш итератор не может возвращать элементы, равные nothing, то это значение выбрано как условный сигнал для функции done(), тому, что try_advance_itr() получила конец итерации и, вообще, пора заканчивать.

function try_advance_itr(itr,si)
     while !done(itr.i,si)
         (v,si)=next(itr.i,si)
         rv=itr.f(v)
         if rv!=nothing
             return (rv,si)
         end
     end
     (nothing,)
end

next() тоже вызывает try_advance_itr() для получения информации о возможности следующей итерации:

function Base.next(itr::EMapFil, s)
     (rv,si) = s
     si2 = try_advance_itr(itr, si)
     (rv,si2)
end

Функция done просто проверяет состояние итерации:

Base.done(itr::EMapFil, s) = s[1]==nothing

Отметим, что, так как start, next, done объявлены в Base, то чтобы определить новые их методы из своего модуля, нужно либо предварительно сделать import Base , либо использовать полностью квалифицированные имена при определении (здесь выбрано второе).

Теперь проверим mapfilter:

julia> mapfilter(i->i>=4? "number $i": nothing , [2,3,4,5])
EMapFil{Function,Array{Int64,1}}((anonymous function),[2,3,4,5])

Возвращен новый итератор:

for i in mapfilter(i->i>=4? "number $i": nothing , [2,3,4,5])
  println(i)
end

number 4
number 5

А может сделать вариант с частичным применением аргументов?

mapfilter(f::Function) = itr->mapfilter(f,itr)

Если нужно сделать наш итератор полноправным жителем, то потребуется определить функцию length() на нем. Это из-за того, что многие функции, вроде collect() вызвывают ее при работе. Понятно, что при этом произойдет материализация элементов.

Base.length(mf::EMapFil) = sum(1 for i in mf)

Теперь можно делать так:

[2,3,4,5] |> mapfilter(i->i>=4? "number $i": nothing )|> collect

А теперь протестируем устойчивость состояния итератора:

julia> iter = [2,3,4,5]|>mapfilter(i->i>=4? "number $i": nothing)
It.EMapFil{##3#4,Array{Int64,1}}(#3,[2,3,4,5])

julia> for i in iter
        for j in iter
         println("$i -- $j")
        end
       end
number 4 -- number 4
number 4 -- number 5
number 5 -- number 4
number 5 -- number 5

Вложенный цикл for j in iter использует тот же объект итератора iter, что и внешний for i in iter. Несмотря на то, что объект итератора один - каждый цикл использует свое собственное состояние и они не мешают друг другу.

Итераторы и чтение потоков ввода-вывода

Исключение составляют итераторы, работающие там, где нельзя вернуться к началу: например, при последовательном чтении потоков ввода-вывода.

Там состояние итератора зависит от состояния указателя на читаемый объект. Здесь изменяемого состояния не избежать. Возможно, и вам придется создавать однонаправленные итераторы. В таком случае, вы можете хранить состояние в самом итераторе или читаемом объекте.

В примере ниже стандартная функция eachline, примененная к IOStream возвращает итератор типа EachLine.

julia> ll = open("a.txt")|> eachline
EachLine(IOStream(<file a.txt>),Base.#281)

Этот итератор - однонаправленный, первый цикл for выберет все строки, а второй не сделает ни одной итерации:

julia> for l in ll print(l) end
a*123
b*345

julia> for l in ll print(l) end  # do nothing

Вот, что можно увидеть в стандартной библиотеке, вызвав

@less EachLine("")

type EachLine
    stream::IO
    ondone::Function
    EachLine(stream) = EachLine(stream, ()->nothing)
    EachLine(stream, ondone) = new(stream, ondone)
end

eachline(stream::IO) = EachLine(stream)

function eachline(filename::AbstractString)
    s = open(filename)
    EachLine(s, ()->close(s))
end

start(itr::EachLine) = nothing

function done(itr::EachLine, nada)
    if !eof(itr.stream)
        return false
    end
    itr.ondone()
    true
end

next(itr::EachLine, nada) = (readline(itr.stream), nothing)

Как видно в коде выше, функция start возвращает nothing - т.е. прозрачно намекает нам, что хранимого на приемнике состояния не будет, next - читает строку через readline, игнорируя передаваемый второй аргумент, который в обычной ситуации был бы состоянием , а done - проверяет eof открытого потока.

Если, же вам необходим итератор по строкам файла, который может работать независимо от состояния, то вы можете создать массив строк. Но, в этом случае, все строки будут загружены в память:

julia> ll = open("a.txt")|> readlines
2-element Array{String,1}:
 "a*123\n"
 "b*345\n"

Создание собственных итераторов для ввода-вывода

Доступность кода стандартной библиотеки из REPL, поощряет, заглядывать туда за примерами реализации типичных задач. Присмотревшись к итератору на типе EachLine, можно увидеть интересную деталь: поле ondone типа EachLine предполагает, что там должна быть функция:

type EachLine
    stream::IO
    ondone::Function
    ...

Из кода видно, что done вызывает ее, когда достигнут eof:

function done(itr::EachLine, nada)
    if !eof(itr.stream)
        return false
    end
    itr.ondone()
    true
end

Функция eachline на filename::AbstractString, после открытия файла передает конструктору итератора вместе с IOStream, функцию-замыкание, которая, будучи вызвана, закроет открытый поток (s):

function eachline(filename::AbstractString)
    s = open(filename)
    EachLine(s, ()->close(s))
end

Но eachline на IOStream не делает этого, по принципу "сам не открывал - не закрывай":

eachline(stream::IO) = EachLine(stream)

Мы можем, по аналогии, создать что-то полезное для себя. Вот функция, которую мы могли бы написать, создающая итератор, который будет построчно читать результат выполнения внешней команды, а по окончании чтения - автоматически закроет поток ввода-вывода и дождется завершения дочернего процесса:

function lines(cmd::Cmd)
    (rio,rpr) = open(cmd)
    el_iter = eachline(rio)
    el_iter.ondone = ()->(close(rio); wait(rpr))
    el_iter
end

запустим ее на объекте Cmd:

julia> ll = ls -l |> lines
EachLine(Pipe(closed => open, 0 bytes waiting),#1)

теперь этот итератор может быть передан в любой код, без необходимости помнить о том, что нам нужно что-то закрывать.

for l in ll print(l) end

Но изобретенная функция оказалась велосипедом: такая функция уже существует: eachline работает на имени файла (AbstractString), на объектах IO и на объектах типа Cmd. В этом можно убедиться, набрав в REPL имя функции с открывающей скобкой и нажать TAB:

julia> eachline(
eachline(stream::IO) at io.jl:382                        eachline(cmd::Base.AbstractCmd) at process.jl:532
eachline(filename::AbstractString) at io.jl:384          eachline(cmd::Base.AbstractCmd, stdin) at process.jl:525

Хотя в документации про Cmd ничего не сказано:

help?> eachline
search: eachline EachLine

  eachline(stream::IO)
  eachline(filename::AbstractString)

  Create an iterable object that will yield each line from an I/O stream or a file. The text is assumed to be encoded in UTF-8.

Посмотреть, как она реализована, можно так:

ulia> @less eachline(``) # - обратные кавычки

...
function eachline(cmd::AbstractCmd, stdin)
    stdout = Pipe()
    processes = spawn(cmd, (stdin,stdout,STDERR))
    close(stdout.in)
    out = stdout.out
    # implicitly close after reading lines, since we opened
    return EachLine(out, ()->(close(out); success(processes) || pipeline_error(processes)))
end

eachline(cmd::AbstractCmd) = eachline(cmd, DevNull)
...

Итератор чтения потока, который может повторять первую строку

Итераторы, вроде STDIN|>eachline удобны тем, что их можно отдавать функциям, обрабатывающим последовательности. Но иногда, прежде чем отдавать его на обработку, хочется проверить первую строку ввода. Например, чтобы убедиться что количество полей соответствует ожидаемому. Возникает проблема, потому что после чтения первой строки такой итератор уже никогда не вернется к ней. Это можно продемонстрировать:

julia> iter = `echo -e "aa\nbb\ncc"`|>eachline # итератор который должен отдать три строки
EachLine(Base.PipeEndpoint(open, 0 bytes waiting),Base.#418)

julia> iter|>first # получили первую
"aa\n"

# но теперь у нас неполные данные ("aa" исчезла):
julia> for i in iter 
        print(i)
       end
bb
cc

Для этого, после прочтения первой строки, нам нужно прилепить ее спереди к нашему итератору.

julia> iter = `echo -e "aa\nbb\ncc"`|>eachline; # итератор который должен отдать три строки

julia> first_line = iter|>first
"aa\n"

julia> iter = (l for ii in [ [first_line], iter] for l in ii );

julia> iter|>first
"aa\n"

julia> iter|>first
"aa\n"

julia> for i in iter # данные полные
        print(i)
       end
aa
bb
cc

Нужно иметь ввиду, что если вы хоть раз прочитаете вторую строку такого итератора, она уже никогда не повторится, хотя первая будет продолжать повторяться с каждым циклом по итератору. Также такой итератор никогда не станет пустым.

Генераторы

Если вы не пришли из мира функционального программирования, виновника всех этих новых сомнительно-позитивных веяний, где распухание головы на стадии обучения считается явлением нормальным, то вышеописанные способы создания собственной логики для итераторов вам могли показаться слишком сложными. Видимо, полученный плюсик за дизайн итераторов слишком часто нивелировался минусиком за сложность теми, кто пришел из Python'а. Так, под влиянием общественности в версии Julia 0.5 появился новый синтаксис спискового включения, который создает генератор. Наконец-то теперь можно делать так:

julia> ("number $i" for i in [2,3,4,5] if i>=4)|>collect

2-element Array{String,1}:
"number 4"
"number 5"

Проверим:

julia> iter = ("number $i" for i in [2,3,4,5] if i>=4);

julia> for i in iter
 for j in iter
  println("$i -- $j")
 end
end

number 4 -- number 4
number 4 -- number 5
number 5 -- number 4
number 5 -- number 5

Обратите внимание, на разницу двух вариантов:

Генератор (инициализация элементов по мере надобности, требуется collect, чтобы собрать элементы):

("number $i" for i in [2,3,4,5] if i>=4)

Массив (инициализация всех элементов сразу):

["number $i" for i in [2,3,4,5] if i>=4]

Вызов функции, принимающей генератор выглядит так: функция(выражение генератора) . Повторять круглые скобки не требуется, если синтаксически он - единственный аргумент. Например, вот, как мы можем отфильтровать конечные результаты генератора снаружи:

julia> filter("number $i" for i in 1:100 if i<=45) do s ismatch( r"4\d", s) end |> collect

6-element Array{String,1}:
"number 40"
"number 41"
"number 42"
"number 43"
"number 44"
"number 45"

Смотрите, выражение генератора вложено прямо внутрь скобок функции filter. Если итератор возвращает пары значений, то его можно использовать для передачи в конструктор словаря:

julia> Dict( (i=>"number $i") for i in 1:10 if i>5)

Dict{Int64,String} with 5 entries:
7 => "number 7"
9 => "number 9"
10 => "number 10"
8 => "number 8"
6 => "number 6"

То, есть, выражение генератора подойдет в любую функцию, если возвращаемая им последовательность соответствует тому, что ожидает получить функция.

Порядок операций

Технически, выражение (под выражением я оставляю ответ REPL, чтобы вы могли сравнить два варианта):

julia> ("number $i" for i in [2,3,4,5] if i>=4)
Base.Generator{Filter{##48#50,Array{Int64,1}},##47#49}(#47,Filter{##48#50,Array{Int64,1}}(#48,[2,3,4,5]))

равносильно этому:

julia> Base.Generator(i->"number $i", Filter(i->i>4, [2,3,4,5]))
Base.Generator{Filter{##52#54,Array{Int64,1}},##51#53}(#51,Filter{##52#54,Array{Int64,1}}(#52,[2,3,4,5]))

Таким образом, явно видно, что к исходной коллекции сначала применяется фильтр i->i>4, а потом генератор отдает результаты функции i->"number $i", примененной к каждому элементу из фильтра.

Если вы хотите сделать наоборот, то вы можете написать:

julia> filter(i->i>=4, (i*2 for i in [2,3,4,5]))
Filter{##127#129,Base.Generator{Array{Int64,1},##128#130}}(#127,Base.Generator{Array{Int64,1},##128#130}(#128,[2,3,4,5]))

Обратите внимание: в указанном выше выражении круглые скобки и вокруг всех параметров функции filter и вокруг генератора дополнительно.

Это будет равносильно:

Filter(i->i>=4, Base.Generator(i->i*2, [2,3,4,5]) )
Filter{##131#133,Base.Generator{Array{Int64,1},##132#134}}(#131,Base.Generator{Array{Int64,1},##132#134}(#132,[2,3,4,5]))

Здесь сначала создается генератор, возвращающий на каждое исходное значение i результат i*2, а потом результаты фильтруются.

Декомпозиция генератора

Работая с Julia, вы возможно заметите, что термин сокрытие плохо подходит для характеристики языка. Не вдаваясь в споры, о том плохо это или хорошо, давайте исследуем, как мы можем использовать знание внутренней структуры объектов, таких как генераторы.

Так как генераторы чрезвычайно удобны, у вас может возникнуть соблазн составлять длинные цепочки из генераторов (или других итераторов). Например, у вас много функций, каждая из которых поэлементно лениво обрабатывает итератор поданный на вход и возвращающая новый итератор. Комбинируя такие функции вы можете программировать на высоком уровне, как это делается в функциональных языках. Но когда такие цепочки становятся длинными (больше десяти), то при большом количестве элементов итератора и при отсутствии других замедляющих факторов (долгих расчетов каждого элемента или ожидания доступности данных ) станут заметно видны издержки на промежуточные вызовы. По сути, вызовы done и next проходят вдоль всей итоговой цепочки итераторов от последнего к первому за каждым новым элементом. Упрощенно (в целях демонстрации) это может выглядеть так:

julia> f1(iter) = (i+1 for i in iter)
f1 (generic function with 1 method)

julia> f2(iter) = (i+2 for i in iter)
f2 (generic function with 1 method)

julia> f3(iter) = (i+3 for i in iter)
f3 (generic function with 1 method)

julia> iter4 = 1:10_000_000 |> f1 |> f2 |> f3
Base.Generator{Base.Generator{Base.Generator{UnitRange{Int64},##1#2},##3#4},##5#6}(#5,Base.Generator{Base.Generator{UnitRange{Int64},##1#2},##3#4}(#3,Base.Generator{UnitRange{Int64},##1#2}(#1,1:10000000)))

В этой цепочке функция f3 возвращает исходный диапазон трижды обернутый в генераторы. Это видно в ответе REPL. Когда вы попросите первый элемент у итератора iter4, он в свою очередь попросит первый элемент у своего вложенного итератора и так далее, пока вызовы не дойдут до исходного диапазона 1:10_000_000, который вернет единицу. Потом возвращенное значение, поедет в обратную сторону, останавливаясь в каждом генераторе чтобы произвести сложение и получить новый результат и так до инициатора вызова.

Я попробовал создавать длинные цепочки генераторов и сравнивать их производительность с идентичным алгоритмом, который не использует вложенность итераторов друг в друга а производит все нужные действия над текущим элементом в одной итерации цикла. Приблизительно после десяти сцепленных генераторов становятся заметны издержки на промежуточные вызовы, и они растут тем сильнее, чем длиннее цепочка итераторов. Что же мы можем сделать в условиях, когда до жути хочется пользоваться такими длинными цепочками? Вы уже догадались: нужно избавиться от вложенности итераторов. Будем помнить, что существуют итерируемые объекты и других типов, но для простоты, пока ограничимся рассмотрением только цепочки генераторов, обернувших исходный диапазон.

Нехитрым способом можно узнать из чего состоит объект генератора:

julia> (i+1 for i in 1:10) |> dump
Base.Generator{UnitRange{Int64},##7#8}
  f: #7 (function of type ##7#8)
  iter: UnitRange{Int64}
    start: Int64 1
    stop: Int64 10

Это экземпляр типа Base.Generator (подробности опустим) у которого есть два поля: f - функция применяемая к каждому элементу исходного итератора и iter - ссылка на исходный итератор. Теперь мы можем создать функцию принимающую первым параметром функцию, которая должна быть применена к каждому элементу исходного итератора и итератор типа Base.Generator вторым параметром. Функция будет возвращать новый генератор. Но в отличие от старой стратегии, она не будет оборачивать исходный генератор новым, а разберет исходный и создаст вместо него новый, заменив исходную функцию на другую, которая будет результатом композиции двух функций. Пожалуй, пример кода выглядит понятней тысячи слов:

julia> function newgen( f2::Function, i::Base.Generator)
        f = i.f
        iter = i.iter
        ( f2(f(x)) for x in iter )
       end

Хочется сделать небольшое отступление по поводу временных переменных f и iter, которые используются в этой функции. Они введены для того, чтобы возвращаемое выражение генератора (в конце функции в круглых скобках) не замыкало в себе ссылку на объект исходного генератора. Мы берем его содержимое, но оболочку выбрасываем. Иначе выражение генератора таскало бы за собой эту ссылку. Сами понимаете, что накапливать эти ссылки нам совершенно незачем.

А чтобы удобно было составлять цепочки функций определим вспомогательный метод:

julia> newgen( f2::Function ) = i->newgen( f2, i )

На вход newgen может поступить не только итератор типа Generator , но и диапазон и любой другой итератор, поэтому, для таких случаев оставим старую стратегию обертывания:

julia> newgen( f2::Function, i ) = ( f2(x) for x in i )

Теперь мы можем составить аналогичную цепочку вызовов:

julia> iter5 = 1:10_000_000 |> newgen(x->x+1) |> newgen(x->x+2) |> newgen(x->x+3)
Base.Generator{UnitRange{Int64},##1#2{##9#12,##1#2{##8#11,##7#10}}}(#1,1:10000000)

Если сравнить с результатом прошлой цепочки, то можно заметить, что теперь это не трижды обернутый в генераторы диапазон, а лишь один генератор, содержащий диапазон и вложенные друг в друга функции. Проверив этот подход на длинной цепочке функций (десять или больше), вы сможете заметить значительный прирост производительности при тех же результатах. Проверить производительность можно примитивным способом:

julia> @time for i in iter5
        i
       end
  1.377759 seconds (30.00 M allocations: 610.336 MB, 7.72% gc time)

Напомню, замеры нужно производить несколько раз и первый раз исключить из показаний, т.к. в первый раз производится компиляция функций. Как видно, на нашем примере разницы в производительности практически нет, так как цепочка состояла всего из трех вложенностей:

julia> @time for i in iter4
        i
       end
  1.386471 seconds (30.00 M allocations: 610.336 MB, 7.69% gc time)

Но, если вам интересно, проведите эксперимент на десяти или более вложенностях и увидите разницу.