Продолжения

[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

[mr-aleph.livejournal.com]

вот-вот, я так и говорю

[thedeemon.livejournal.com]

Тот твой коммент меня и вдохновил!

[sorhed.livejournal.com]

Так их, скобочников!

[theiced.livejournal.com]

http://rubygems.org/gems/lazy

[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." Сделай из такой функции (код которой менять нельзя) пассивный итератор. Собственно, идея-то в том, что конвертация "пассивный в активный" элементарна, а обратная требует либо извращений с многопоточностью, либо продолжений.

[soonts.livejournal.com]

Почитал раздел "Продолжения в практике".
Да я понимаю "зачем", не понимаю "зачем так".
Готов спорить на пиво, что моё решение на C# + async CTP (async CTP кстати очень полезное для подобных задач расширение C#) займёт столько же или меньше строк кода по сравнению с его схемой, при этом на том же железе будет работать минимум в полтора раза быстрее (какие на фиг селекты для серверов — в мире Windows IOCP, в *nix epoll, в BSD kqueue)

[thedeemon.livejournal.com]

Ну нужно было придумать какое-то применение продолжениям. :)

[usovalx.livejournal.com]

На продолжениях аналог async CTP делается абсолютно элементарно.

Да и на чистом C# 4.0 его вполне можно сделать: диспетчер, самодельный аналог ITask<> и yield return. Синтаксис правда будет тот ещё.

Так что смысл вашего коментария судя по всему сводится к тому, что у C# виртуальная машина вылизаннее и быстрее. Ну так с этим вроде никто и не спорит. Или я что-то большое пропустил?

[soonts.livejournal.com]

>на чистом C# 4.0 его вполне можно сделать: диспетчер
async CTP ощутимо сложнее диспетчера (который просто очередь для единственного потока). Например 2 async функции (если ты обе запустишь в CLR thread pool) могут исполняться сначала одновременно на ядрах 1 и 2, потом (после операторов await в каждой из них) легко могут попасть наоборот на ядра 2 и 1. Такой гибкости в использовании ресурсов с сохранением ± логической целостности кода (= instruction pointer, call stack, local variables) не получишь никакими yields.

>что-то большое пропустил?
IMO разница скорости VM в данном случае фигня, основная проблема неверно выбранная socket I/O strategy..

[usovalx.livejournal.com]

Пункт 1 дополнительно обосновать можешь? Потому как вся семантика логической целостности кода и т.п. уже обеспечивается yield return'ом.

2 - это о том что в примере используется select вместо православных epoll/kqueue/чего там в винде? Так то что нарисовано в статье должно довольно тривиально обобщаться до любого из этих вариантов (или libev/libevent).

[usovalx.livejournal.com]

Да, ещё момент касательно C# -- в условиях когда клиентов не особенно много (50-100, чтобы select не совсем уж проседал) я бы скорее поставил на версию с select на линуксах чем async CTP на винде ;) И сеть и IO в винде весьма тормознутые.

[soonts.livejournal.com]

>И сеть и IO в винде весьма тормознутые.
Bullshit. Например IIS выигрывает у apache на том же железе на десятки процентов.

Касательно C# — весь асинхронный I/O в C# использует I/O completion port, встроенный в чезвычайно эффективный CLR thread pool.

[usovalx.livejournal.com]

Блин, ну нафиг мне этот IIS/apache.

Я сужу по своему опыту -- регулярно пускаю наш плюсовый код и на винде и на линуксах. Разница более чем заметна на глаз. А если ещё вспомнить про отладочный рантайм, то это вообще финиш.

[soonts.livejournal.com]

1. Семантика может и обеспечивается. Однако чтобы на её основе сделать насколько эффективный scheduler как это сделано в CTP, надо написать довольно много кода. Например в ряде случаев return напрямую вызывает того, кто ждёт на await, без всяких kernel calls / context switches. Async CTP .DLL занимает 100kb — для managed сборки это довольно много.

2. Да. И кстати, I/O completion ports: windows NT 3.5, 1994 год. Kqueue: BSD 4.1, 2000 год. Epoll: linux kernel 2.5.44, 2002 год. Характерно, что у разработчиков ядра linux на то чтобы спиздить хорошую design-идею ушло 8 лет — прекрасный показатель по которому можно оценить отставание open source технологий.

[usovalx.livejournal.com]

1. Если я правильно понимаю их семантику, то вложенные await должны исполняться без переключения контекстов. И только возвращение значения в основной поток будет протаскиваться в ITask через thread barrier. Точнее не так -- пересекать thread barrier также прийдётся и при ожидании нескольких асинхронных задач.

2. Весьма радикальное мнение. Как по мне востребованность в них была не особенно острой. В той-же солярке /dev/poll появился только в 99м.

[umktzbsgt.livejournal.com]

Интересный пост