Продолжения

[thedeemon]

В свежем номере ПФП замечательная статья про продолжения. К сожалению, в качестве примеров там зачем-то приведены дампы памяти интерпретатора плохо типизированного лямбда-исчисления, формат которых некоторые ошибочно называют языком программирования. К счастью, история знает пример настоящего языка программирования с поддержкой продолжений - Руби версий до 1.8 включительно (поскольку поддержка продолжений была одной из причин тормознутости интерпретатора, а сами продолжения никому не нужны, то в версии 1.9 их выкинули).

Посмотрим, как на Руби выглядит пример с поиском общего префикса у деревьев. По условию задачи у нас есть некая структура данных (в данном случае дерево) и для нее есть функция, которая последовательно обходит элементы и для каждого вызывает наш callback. Т.е. это активный итератор в стиле Руби, в отличие от пассивных итераторов в стиле С++/C#/Java. Пусть наше дерево представлено массивом, элементы которого могут быть либо листьями дерева, либо такими же массивами-деревьями:
tree1 = [1, [2,3], [[[4,5], 6]], 7, 8]
tree2 = [[1,2], [[3,4], 0,0], 1]
Тогда итератор выглядит так:

def iterate_tree(tree, &f)
if tree.is_a? Array
tree.each{|x| iterate_tree(x, &f) }
else
yield tree
end
end
Чтобы вывести последовательно все элементы дерева его можно использовать так:

iterate_tree(tree1) {|x| print x}

Теперь мы хотим определить для двух деревьев длину общего префикса - число совпадающих при последовательном обходе с начала листьев, используя такие итераторы, но не обходя деревья целиком. Для этого при создании колбэка сохраним контекст вычисления главного потока в виде продолжения с именем main_thread, вызванный итератором колбэк будет вызывать это продолжение, тем самым передавая управление главному потоку, а также передавая ему параметром собственное продолжение под именем iteration_thread, которое, будучи вызванным из главного потока, продолжит работу колбэка, чтобы итератор продолжил работу и пошел на следующую итерацию, где все повторится. Главный поток на каждой итерации цикла передает свое продолжение main_thread, которое колбэк внутри себя обновляет, чтобы возвращаться не в начало обхода, а в нужное место. Звучит страшно, но код довольно короткий:

def start_iteration(tree, main_thread)
  iterate_tree(tree) {|x| 
    main_thread = callcc {|iteration_thread| 
      main_thread.call(x, iteration_thread) 
    }
  }
  main_thread.call(nil, nil)
end

def loop(iter1, iter2, n)
  x1, it1 = callcc { |main_thread|  iter1.call(main_thread) }
  x2, it2 = callcc { |main_thread|  iter2.call(main_thread) }  
  if x1 && x2 && x1==x2 then loop(it1, it2, n+1) else n end
end

def prefix_length(tr1, tr2)
  loop( lambda {|c| start_iteration(tr1,c)}, lambda {|c| start_iteration(tr2,c)}, 0 )
end

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

Если вызвать prefix_length для описанных выше tree1 и tree2 и вывести результат,

p prefix_length(tree1, tree2)

будет выведено 4.

Comments

[soonts.livejournal.com]

>в отличие от пассивных итераторов в стиле C#
Вот тебе универсальный активный итератор в C#, всего 2 строки кода:
public static void ForEach(this IEnumerable<T> sequence, Action<T> act) { foreach( T e in sequence ) act(e); }
Если интересно почему этого extension-метода нет в составе .NET framework — link.

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

Зачем если это намного проще делается на нормальных итераторах? Заметь, код ниже тоже обходит не все элементы, т.е. если данные на входе результат ленивых вычислений (таких как рекурсивный обход дерева) - элементы после первого расхождения вычисляться не будут.

static int CommonPrefix<T>(IEnumerable<T> s1, IEnumerable<T> s2) where T: IComparable<T>
{
IEnumerator<T> e1 = s1.GetEnumerator();
IEnumerator<T> e2 = s1.GetEnumerator();
int res = 0;
for( int res = 0; true; res++ )
{
if ( !e1.MoveNext() || !e2.MoveNext() || !e1.Current.Equals( e2.Current ) )
return res;
}
}

P.S. У меня ощущение что в 95% случаев примеры задач, приводимые сторонниками ФП, можно проще решить без ФП.

[thedeemon.livejournal.com]

Когда уже есть пассивный итератор, сделать из него активный может любой дурак. А вот реши обратную задачу - из активного пассивный. Без использования C#'овского yield, где компилятор сам выворачивает код.

[soonts.livejournal.com]

>Без использования C#'овского yield
Ну он же там есть.

Собственно я сагрился именно на утверждение которое я процитировал в начале предыдущего камента.
IMO C# помимо всего прочего — прекрасный функциональный язык.
Например когда мне понадобилось реализовать аналог XPath, я довольно быстро написал пару страниц функционального кода, которые из строки с выражением строят Func<Node, Node> (ессно парсинг строки с выражением производится в момент вызова selectSingleNodeFunc, а не в момент использования сконструированного функтора, т.е. метод selectSingleNodeFunc конструирует в функторе код, весьма близкий к оптимальному).

[thedeemon.livejournal.com]

Где есть? В языке? Ок, можешь использовать yield.
"По условию задачи у нас есть некая структура данных (в данном случае дерево) и для нее есть функция, которая последовательно обходит элементы и для каждого вызывает наш callback." Сделай из такой функции (код которой менять нельзя) пассивный итератор. Собственно, идея-то в том, что конвертация "пассивный в активный" элементарна, а обратная требует либо извращений с многопоточностью, либо продолжений.