11.2.5. Использование продолжений для реализации генератора

11.2.5. Использование продолжений для реализации генератора

Одно из самых трудных для понимания средств Ruby — продолжение (continuation). Это структурированный способ выполнить нелокальный переход и возврат. В объекте продолжения хранятся адрес возврата и контекст выполнения. В каком-то смысле это аналог функций setjmp/longjmp в языке С, но объем сохраняемого контекста больше.

Метод callcc из модуля Kernel принимает блок и возвращает объект класса Continuation. Возвращаемый объект передается в блок как параметр, что еще больше все запутывает.

В классе Continuation есть всего один метод call, который обеспечивает нелокальный возврат в конец блока callсс. Выйти из метода callcc можно либо достигнув конца блока, либо вызвав метод call.

Считайте, что продолжение — что-то вроде операции «сохранить игру» в классических «бродилках». Вы сохраняете игру в точке, где все спокойно, а потом пробуете выполнить нечто потенциально опасное. Если эксперимент заканчивается гибелью, то вы восстанавливаете сохраненное состояние игры и пробуете пойти другим путем.

Самый лучший способ разобраться в продолжениях — посмотреть фильм «Беги, Лола, беги».

Есть несколько хороших примеров того, как пользоваться продолжениями. Самые лучшие предложил Джим Вайрих (Jim Weirich). Ниже показано, как Джим реализовал «генератор» после дискуссии еще с одним программистом на Ruby, Хью Сассе (Hugh Sasse).

Идея генератора навеяна методом suspend из языка Icon (он есть также в Prolog), который позволяет возобновить выполнение функции с места, следующего за тем, где она в последний раз вернула значение. Хью называет это «yield наоборот».

Библиотека generator теперь входит в дистрибутив Ruby. Дополнительную информацию по этому вопросу вы найдете в разделе 8.3.7.

В листинге 11.15 представлена предложенная Джимом реализация генератора чисел Фибоначчи. Продолжения применяются для того, чтобы сохранить состояние между вызовами.

Листинг 11.15. Генератор чисел Фибоначчи

class Generator

 def initialize

  do_generation

 end

 def next

  callcc do |here|

   @main_context = here;

   @generator_context.call

  end

 end

 private

 def do_generation

  callcc do |context|

   @generator_context = context;

   return

  end

  generating_loop

 end

 def generate(value)

  callcc do |context|

   @generator_context = context;

   @main_context.call(value)

  end

 end

end

# Порождаем подкласс и определяем метод generating_loop.

class FibGenerator < Generator

 def generating_loop

  generate(1)

  a, b = 1, 1

  loop do

   generate(b)

   a, b = b, a+b

  end

 end

end

# Создаем объект этого класса...

fib = FibGenerator.new

puts fib.next # 1

puts fib.next # 1

puts fib.next # 2

puts fib.next # 3

puts fib.next # 5

puts fib.next # 8

puts fib.next # 13

# И так далее...

Есть, конечно, и более практичные применения продолжений. Один из примеров — каркас Borges для разработки Web-приложений (названный в честь Хорхе Луиса Борхеса), который построен по образу Seaside. В этой парадигме традиционный поток управления в Web-приложении «вывернут с изнанки на лицо», так что логика представляется «нормальной». Например, вы отображаете страницу, получаете результат из формы, отображаете следующую страницу и так далее, ни в чем не противореча интуитивным ожиданиям.

Проблема в том, что продолжение — «дорогая» операция. Необходимо сохранить состояние и потратить заметное время на переключение контекста. Если производительность для вас критична, прибегайте к продолжениям с осторожностью.