Ruby 2.0 Ленивый Enumerable

Недавно мой патч 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, позволяя строить цепочки ленивых вычислений.

Update

Сейчас, когда большая часть работ по Enumerator::Lazy закончена, я решил протестить какой в действительности выигрыш он дает. Результаты были неутешительными (первый раз с бенчмарком я ошибся — отсюда и оптимистический комент снизу). В среднем ленивый Enumerator в 4 (!) раза медленнее чем операции над обычными массивами. Это следствие того что при вычислении ленивой цепчки операция вызова блока происходит слишком часто. Смотреть обсуждение на ruby-lang.org. Несмотря на это — выгоды ленивого енумератора все те же — это элегантный и читабельный код, при этом за счет медленности кол-во юзкейсов сокращается.
Хороший пример привел Yusuke Endoh:

a = []
Prime.each do |x|
  next if x % 4 != 3
  a << x
  break if a.size == 10
end

с использованием ленивости превращается в:

Prime.lazy.select {|x| x % 4 == 3 }.take(10).to_a

Когда?

Трудно сказать, кто первым придумал как с помощью 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::Lazy
• super() в примере на руби должен вызываться именно так — со скобками, иначе руби автоматически передаст ему все аргументы

P.S. Это перевод моей статьи c английского языка.