Недавно мой патч Enumerable::Lazy был принят в ruby trunk. А это значит что в ruby 2.0 мы сможем:
a = [1,2,3,4,2,5].lazy.map { |x| x * 10 }.select { |x| x > 30 } #=> вычисление не происходит
a.to_a #=> [40, 50], объект вычисляется за один проход.
Зачем?
Ruby прекрасен, и, являясь императивным языком, тем не менее позволяет нам писать элегантный "функциональный" код. К примеру:
data.map(&:split).map(&:reverse)
выглядит намного читабельней чем:
data.map { |l| l.split.reverse }
Однако, первый пример является неэффективным: преобразовывая data, Ruby дважды проходится по данным, генерируя промежуточный массив. До тех пор пока объем данных невелик, этот недостаток не является критичным. Но, предположим, мы парсим огромный файл:
File.open("text") do |f|
f.each.flat_map(&:split).grep(/ruby/)
end
В этом случае двойной проход по массиву недопустим. К счастью, с появлением Enumerable::Lazy это уже не проблема. Ленивые версии функций map, select и многих других, переопределенные в классе Enumerable::Lazy, не производят вычисление сразу. Вместо этого они возвращают экземпляр Enumerable::Lazy, позволяя строить цепочки ленивых вычислений.
Когда?
Трудно сказать, кто первым придумал как с помощью Enumerator можно реализовать в Ruby ленивые вычисления. Возможно этот пост 2008 года был одним из первых. Идея реализации проста и основана на замечательном свойстве объктов Enumerator — их можно соединять в цепочки. С тех пор было опубликовано множество статей, а в enumerator.c были добавлены комментарии с пояснениями идеи. Дискуссия на ruby-lang длилась более трех лет, и наконец Matz проголосовал за реализацию Yataka Hara.
В ней был предложен метод Enumerable::lazy, который "оборачивает" массив в экземпляр Enumerable::Lazy, который, в свою очередь, используется для построения ленивой цепочки. Был озвучен запрос патча на Си и я незамедлительно принял вызов. К слову, я совсем недавно заинтересовался функциональным программированием, да и покопаться во внутренностях Ruby было очень интерестно. В результате я сподобился на пул реквест, который, после незначительного рефакторинга, был принят несколько дней назад. Вмерджили его в trunk и он выйдет в Ruby 2.0 (смотреть roadmap).
Как?
Enumerator (пропустить если знаете)
Для тех, кто не в курсе что такое обычный Enumerator и с чем его едят:
enum = [1, 2].each
puts enum.next #=> 1
puts enum.next #=> 2
puts enum.next #=> StopIteration exception raised
enum = Enumerator.new do |yielder|
yielder << 1
yielder << 2
end
puts enum.next #=> 1
puts enum.next #=> 2
puts enum.next #=> StopIteration exception raised
enum = "xy".enum_for(:each_byte)
enum.each { |b| puts b }
# => 120
# => 121
o = Object.new
def o.each
yield
yield 'hello'
yield [1, 2]
end
enum = o.to_enum
p enum.next #=> nil
p enum.next #=> 'hello'
p enum.next #=> [1, 2]
enum = %w{foo bar baz}.map
puts enum.with_index { |w, i| "#{i}:#{w}" } # => ["0:foo", "1:bar", "2:baz"]
# защита данных от изменений
a = [1, 2, 3]
some_method(a.enum_for)
[1,2,3].cycle.take(10) #=> [1, 2, 3, 1, 2, 3, 1, 2, 3, 1]
Как вы уже наверное догадались, методы #to_enum и #enum_for находятся в модуле Kernel, а значит доступны любому объекту. Примеры взяты из enumerator.c, если интерестно можно глянуть еще и тут: test/ruby/test_enumerator.rb. Сишные внутренности Enumerator наверное заслуживают отдельного поста, но стоит заметить, что вся эта магия с next реализована с помощью Fiber.
Lazy enumerator
Чтобы понять как работает Enumerable::Lazy достаточно взглянуть на этот код:
module Enumerable
class Lazy < Enumerator
def initialize(obj)
super() do |yielder|
obj.each do |val|
if block_given?
yield(yielder, val)
else
yielder << val
end
end
end
end
def map
Lazy.new(self) do |yielder, val|
yielder << yield(val)
end
end
end
end
a = Enumerable::Lazy.new([1,2,3])
a = a.map { |x| x * 10 }.map { |x| x - 1 }
puts a.next #=> 9
puts a.next #=> 19
Эта типичная реализация на Ruby, которую предложил Yutaka. Но обратите внимание — в этом примере я не использую &block как параметр метода (чтобы сконвертить в Proc и вызывать call). Вместо этого мы можем yieldить прямо внутри блока для each! block_given? также работает как полагается. Более того, находясь внутри блока, мы все равно можем вызывать self (как и return). Здорово, не правда ли? Замечательный пост на эту тему от Yehuda Katz (еще один).
Сам по себе код достаточно прост, но давайте разберемся подробнее: Как уже было сказано, основная идея в построении цепочки. Поэтому Enumerable::Lazy#map создает новый экземпляр Enumerable::Lazy передавая ему "предыдущий" объект как аргумент. При вызове to_a (next, each с блоком, take и т.п.) происходит вычисление: Ruby возвращается обратно к началу цепочки (Рис. 1), получает следующее значение из первоначального объекта и возвращает его наружу, последовательно модифицируя блоками ленивых методов (в том же порядке, в котором они были "навешены").
Рис.1 Цепочка ленивых енумераторов.
C patch
Мой патч на Си полностью повторяет имплементацию на Ruby. За исключением того факта, что вместо вызова super напрямую внутри lazy_initialize я создаю и инициализирую генератор (Enumerator::Generator), который передается как аргумент енумератору.
В финальном патчe nobu слегка отрефакторил код: if-else условие внутри функции-блока он разделил на два отдельных метода (lazy_init_block_i and lazy_init_block), а само условия перенес в lazy_initialize.
Также, вместо того, чтобы передавать Ruby массив как параметр в функцию-блок, он конструирует обычный Си массив с параметрами. Соответственно, теперь не нужно использовать rb_ary_entry, чтобы получить yielder и значение внутри блока.
Например, это:
static VALUE lazy_map_func(VALUE val, VALUE m, int argc, VALUE *argv)
{
VALUE result = rb_funcall(rb_block_proc(), id_call, 1,
rb_ary_entry(val, 1));
return rb_funcall(rb_ary_entry(val, 0), id_yield, 1, result);
}
превратилось в это:
static VALUE lazy_map_func(VALUE val, VALUE m, int argc, VALUE *argv)
{
VALUE result = rb_yield_values2(argc - 1, &argv[1]);
return rb_funcall(argv[0], id_yield, 1, result);
}
Откровенно говоря, я был абсолютным новичком во внутренностях Ruby, поэтому потребовалось два уикенда, чтобы написать этот достаточно тривиальный пулл реквест. Более того, сначала я попробовал пойти по другому пути: пытаясь сохранять блоки ленивых методов как процы в самом енумераторе. Первый сумасшедший пулл реквест смотреть здесь. Когда вызывался Enumerator#next, все процы "применялись" один за другим над очередным значением. Ленивые map и select работали замечательно, но, когда я попытался подправить Enumerator#each, понял, что получается как-то уж слишком сложно (или нет?).
Ты крепкий орешек раз добрался сюда, так что, если планируешь что-нибудь пропатчить в руби, есть куча замечательных статей. В качестве бонуса еще однa статья о том, почему мы должны быть ленивыми.
Выводы
Сейчас Enumerator::Lazy имеет в своем арсенале select, map, reject, grep (добавленные первым патчем), flat_map, zip, take, take_while, drop, drop_while, cycle (добавлены недавно shugo). Девелопмент и обсуждение API активно продолжается, но если хочешь "облениться" прямо сейчас — достаточно скомпилить Ruby из trunk и наслаждаться.
Примечание:
Enumerable::Lazyтеперь сталEnumerator::Lazysuper()в примере на руби должен вызываться именно так — со скобками, иначе руби автоматически передаст ему все аргументы
P.S. Это перевод моей статьи c английского языка.
Автор: gregolsen
