![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
Продолжения
Apr. 17th, 2011 04:58 pmВ свежем номере ПФП замечательная статья про продолжения. К сожалению, в качестве примеров там зачем-то приведены дампы памяти интерпретатора плохо типизированного лямбда-исчисления, формат которых некоторые ошибочно называют языком программирования. К счастью, история знает пример настоящего языка программирования с поддержкой продолжений - Руби версий до 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
Чтобы вывести последовательно все элементы дерева его можно использовать так:
Если вызвать prefix_length для описанных выше tree1 и tree2 и вывести результат,
Посмотрим, как на Руби выглядит пример с поиском общего префикса у деревьев. По условию задачи у нас есть некая структура данных (в данном случае дерево) и для нее есть функция, которая последовательно обходит элементы и для каждого вызывает наш 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)В функции loop мы передаем продолжение главного потока 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
Если вызвать prefix_length для описанных выше tree1 и tree2 и вывести результат,
p prefix_length(tree1, tree2)будет выведено 4.
