Очень интересная задачка - макрос Continuation
От: VladD2 Российская Империя www.nemerle.org
Дата: 22.10.09 19:29
Оценка:
Всем привет!

В Scala 2.8 появился плагин к компилятору который позволяет превратить любой класс Scala в Continuation (продолжение).

Support for continuations. A compiler plugin will support continuations as an optional feature of Scala, using a type-directed continuation passing transform. Continuations are useful to implement advanced control constructs, for instance for asynchronous I/O, user interface event handling, or dataflow concurrency.


Данная задача так же может быть решена в виде макроса Немерле. Подобный вид сontinuation-ов был бы очень полезен в работе. Такие вещи как воркфлоу, визарды, логика перемещения по сайту, реализацию эффективных итераторов по сложным структурам данных (например, по деревьям) и многое другое может делаться на них очень элегантно.

Общая идея очень проста. Берем код класса и переписываем его так, чтобы вместо вызовов реальных методов (с передачей параметров через стек) параметры помещались бы в некую специализированную структуру данных аналогичную стеку а управление просто передавалось бы в нужную точку программы. При этом так же нужно записывать последовательность возвратов. Это позволит:
1. Останавливать такие объекты в безопасных точках (а-ля yield).
2. Запускать такие объекты с того места на котором они были остановлены.
3. Клонировать такие объекты в некотором состоянии и потом запускать как клоны, так и сами объекты.
4. Сериализовать состояние таких объектов стандартными методами и в последствии восстанавливать это состояние.

Если есть смельчаки готовые взяться за данную задачу, то я (и думаю, другие читатели этого форума) готов оказать содействие.
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re: Очень интересная задачка - макрос Continuation
От: Denom Украина  
Дата: 23.10.09 12:54
Оценка:
Здравствуйте, VladD2, Вы писали:

А можно какой-нибудь маленький примерчик?
как это выглядит с макросом и без.
... << RSDN@Home 1.2.0 alpha 4 rev. 1237>>
Re: Очень интересная задачка - макрос Continuation
От: Denom Украина  
Дата: 23.10.09 13:40
Оценка:
Здравствуйте, VladD2, Вы писали:

Хочется видеть сontinuation в nemerle именно в таком виде как в скале shift reset?
... << RSDN@Home 1.2.0 alpha 4 rev. 1237>>
Re[2]: Очень интересная задачка - макрос Continuation
От: VladD2 Российская Империя www.nemerle.org
Дата: 23.10.09 13:57
Оценка:
Здравствуйте, Denom, Вы писали:

D>А можно какой-нибудь маленький примерчик?

D>как это выглядит с макросом и без.

С итераторами C# 2.0 знаком?

Их ограничения такие:
1. yield return работает только в рамках одного метода. Мы можем вызвать другие методы, но из них yield return сделать не можем.
2. Мы не можем сериализовать состояние такого объекта и не можем его клонировать.
3. Мы должны возвращать только объекты заранее заданного (в описании возвращаемого типа итератора) типа.
4. Мы можем получать информацию извне итератора только при его создании. Получить информацию при возобновлении работы, штатными методами, нельзя (если только менять объект возвращенный из итератора, но это не очень красивое решение).

Теперь представь себе, что есть объект который может как бы заморозить свое выполнение вернув некоторое значение. Такой объект можно где-то сохранить или клонировать, а потом запустить копию (клон или полученную путем десериализации). Причем он запустится с того же места где она была прервана и все состояние вычисления в нем так же будет сохранено.
Более того такому объекту вполне можно передать некоторые значения (во время пробуждения). Ну, и ко всему прочему снимается проблема стека (вместо ограниченного стека будет динамически растущая куча).

Что касается с и без, то тут очень тяжело попоставлять. Представь себе как ты будешь реализовывать логику навигации по навороченному сайту где есть возможность нажать кнопку "Назад" (на предыдущую страницу) несколько раз, а потом нажать "Веред" (тоже несколько раз). При переходе на каждую из страниц в приложении нужно восстановить то состояние которое было непосредственно перед уходом с нее.
Если у тебя нет фишки подобной континиэшонам тебе нужно будет самому заботиться о состоянии. Скорее всего это будет страшная каша из флагов размещенных черти где (в лучшем случае в объекте управляющем состоянием).
Если же есть континуэшоны, то код приложения может быть прямолинейным и простым. Нам не надо создавать флагов, заботиться о восстановлении состояния и т.п. Все что нужно — это перед уходом со страницы склонировать объект в котором ведется работа и запомнить в некотором сессионном объекте. Когда юзер нажмет Вперед или Назад, то нам нужно будет всего лишь вынуть этот объект и заменить им текущий. Текущий же точно так же сохраняется и позволяет "откатиться" к этому состоянию когда это будет нужно.
Более того. Мы можем сериализовать объект и поместить его на диск или в БД. Тогда пользователь может неделями не заходить на сайт, но зайдя на него продолжить свои действия так как-будто он и не отходил от монитора.

В общем, вот две ссылки выгугленные за 5 минут:
http://www.google.ru/url?sa=t&amp;source=web&amp;ct=res&amp;cd=5&amp;ved=0CBMQFjAE&amp;url=http%3A%2F%2Fwww.inf.tsu.ru%2Flibrary%2FDiplomaWorks%2FCompScience%2F2008%2Fjushkeev%2Fdiplom.doc&amp;ei=6LDhSpGmLNP5_AbR6vT9AQ&amp;usg=AFQjCNHkgTsdrEbOAacJFZ9XNBxDGwCqbg&amp;sig2=uUHbUfibBgpTSbToX3qTrg

http://www.ibm.com/developerworks/library/j-contin.html

Там есть и примеры и объяснения.
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[2]: Очень интересная задачка - макрос Continuation
От: VladD2 Российская Империя www.nemerle.org
Дата: 23.10.09 14:47
Оценка:
Здравствуйте, Denom, Вы писали:

D>Хочется видеть сontinuation в nemerle именно в таком виде как в скале shift reset?


В скале я не видел, откровенно говоря.

Но хочется видеть в удобном и красивом виде.
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re: Очень интересная задачка - макрос Continuation
От: Пельмешко Россия blog
Дата: 24.10.09 19:53
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Если есть смельчаки готовые взяться за данную задачу, то я (и думаю, другие читатели этого форума) готов оказать содействие.


А это вообще реально реализовать на макросах?
Только не говорите, что yield в Nemerle итак на них реализован, не поверю
Re[2]: Очень интересная задачка - макрос Continuation
От: Denom Украина  
Дата: 25.10.09 20:10
Оценка: 14 (1)
Здравствуйте, Пельмешко, Вы писали:

П>А это вообще реально реализовать на макросах?

П>Только не говорите, что yield в Nemerle итак на них реализован, не поверю

Там хитро, макрос как заглушка. А вся работа выполняется в typer'е.
Но машина сосотояния генерируется с помощью квазицитирования.
На мой неискушенный взгляд код выглядит достаточно красиво.
... << RSDN@Home 1.2.0 alpha 4 rev. 1237>>
Re[3]: Очень интересная задачка - макрос Continuation
От: Denom Украина  
Дата: 25.10.09 20:20
Оценка: +1
Здравствуйте, Denom, Вы писали:

D>Там хитро...

И главная хитрость в том что обработка yield происходит в обработчике исключения SwitchToYielding.
Насчет возможности реализации на макросах — макросам ведь доступны все внутренности компилятора.
Т.е если можно сделать внутри компиятора, значит можно и на макросах.
Учитывая что на них уже сделаны AOP, Concurrency, etc...
... << RSDN@Home 1.2.0 alpha 4 rev. 1237>>
Re[2]: Очень интересная задачка - макрос Continuation
От: VladD2 Российская Империя www.nemerle.org
Дата: 26.10.09 08:46
Оценка: 14 (1)
Здравствуйте, Пельмешко, Вы писали:

VD>>Если есть смельчаки готовые взяться за данную задачу, то я (и думаю, другие читатели этого форума) готов оказать содействие.


П>А это вообще реально реализовать на макросах?


Вполне. Хотя, задача конечно не из легких.

П>Только не говорите, что yield в Nemerle итак на них реализован, не поверю


Не, не макросом. Но есть всего лишь одна причина по которой yield нельзя сдеать макросом. Дело в том, что методы содержащие yield не помечаются каким-либо образом. Необходимость их переписывания определяется только наличием ключевого слова yield. В компиляторе по этому поводу встроен хак. Когда компилятор находит вхождение макроса yield, он генерирует исключение SwitchToYielding. Это исключение перехватывается в самом начале процесса типизации тела метода.
В перехватчике:
1. Меняется тело метода на заглушку конечного автомата.
2. Поднимается флаг inside_yielding_function (чтобы не генерировать SwitchToYielding повторно).
3. Процесс типизации тела метода запускается повторно.
4. Когда находится макрос yield, то он заменяется на лэйбл.
4. В конце процесса типизации в тело match-а добавленного на шаге 1 добавляются переходы конечного автомата сформированные при раскрытии макросов yield.

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

В случае реализации автомата для целого класса было бы разумно помечать такие классы специальным мета-атрибутом. Этот мета-атрибут и выполнит всю работу по переписыванию.
Учитывая, что в таком классе должны быть доступны вызовы методов этого же класса, генерацией конечного автомата не отделаешься. Видимо придется организовать генерацию стеков и замену вызовов на переходы с закладыванием параметров в эти стеки (если вызов рекурсивный и рекурсия концевая, можно в стеки ничего не класть).
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re: Очень интересная задачка - макрос Continuation
От: hardcase Пират http://nemerle.org
Дата: 22.02.10 20:01
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Если есть смельчаки готовые взяться за данную задачу, то я (и думаю, другие читатели этого форума) готов оказать содействие.


Я мог бы попробовать.
Надо бы только в голове уложить смысл сей логики, так как я никогда не использовал "настоящие" продолжения в своей практике — только yield-ы.

Если с кишками класса более менее понятно, то вот модель использования таких объектов не понятна.
http://nemerle.org/Banners/?t=Developer!&g=dark /* иЗвиНите зА неРовнЫй поЧерК */
Re[2]: Очень интересная задачка - макрос Continuation
От: hardcase Пират http://nemerle.org
Дата: 22.02.10 20:35
Оценка:
Здравствуйте, hardcase, Вы писали:

H>Если с кишками класса более менее понятно, то вот модель использования таких объектов не понятна.


Т.е. я хочу сказать, что область применения для меня ясна. Меня интересует способ работы с самим объектом.
http://nemerle.org/Banners/?t=Developer!&g=dark /* иЗвиНите зА неРовнЫй поЧерК */
Re[3]: Очень интересная задачка - макрос Continuation
От: VladD2 Российская Империя www.nemerle.org
Дата: 23.02.10 09:39
Оценка:
Здравствуйте, hardcase, Вы писали:

H>>Если с кишками класса более менее понятно, то вот модель использования таких объектов не понятна.


H>Т.е. я хочу сказать, что область применения для меня ясна. Меня интересует способ работы с самим объектом.


Как с обычным объектом. Только если в коде такого объекта будет вызван метод Suspend, то управление должно быть возвращено в ту точку (находящуюся во вне объекта) где был вызван метод Resume этого объека.

Примечание: Я не применяю имя yield для большей ясности. В принципе вместо Suspend можно использовать yield.

Так вот Suspend и Resume — это не настоящие методы, а средства управления потоком выполнения. Когда внутри некоторого меода вызывается Suspend, то выполнение как бы замораживается в этой точке (как бы запоминается состояние стека) и управление получает код который пред этим произвел вызов Resume. Естественно это некий код не относящийся к данному объекту (внутри объека вызывать this.Resume() запрещено, так как бессмысленно).

Кроме того такой объект должен реализовывать метод Clone который должен клонировать объект вместе с состоянием выполнения (с виртуальным стеком вызовов). Такой клонированный объект, после клонирования, должен находиться в состоянии Suspend. Его вызов продолжает выполнение с той точки в которой был сделан вызов Clone. При этом копия и оригинал должен жить независимо. Скажем если оригинал заморожен, то копия может производить выполнение.

Методы Suspend и Resume могут не иметь параметров и возвращаемых значений, а могут иметь. Если они имеют параметры, то список аргументов Suspend должен соотвествовать возвращаемому значению Resume и наоборот. Это позволит на каждом шаге возобновления исполнения передавать дополнительные данные в объект-продолжение и возвращать из него некоторые данные при его усыплении (Suspend).

Любой другой вызов объекта должен рассматриваться как обычный. При этом наверно имеет смысл позволять вызвать только те методы которые не содержат вызовов Suspend или других методов этого же объекта содержащих вызов Suspend. Таким обрезом будет гарантированно, что при заморозке в стеке не будет находиться вызовов к другим объектам (вызовы которых не могут быть сериализованы).

Таким образом мы получаем эдакие итераторы на стероидах — более гибкие и более мощные.

Такую штуку можно будет с легкостью применять для реализации сложного потока управления.
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[4]: Очень интересная задачка - макрос Continuation
От: VladD2 Российская Империя www.nemerle.org
Дата: 23.02.10 11:31
Оценка:
Здравствуйте, VladD2, Вы писали:

Да... Кроме того нужно иметь возможность передавать управление в другие продолжения (как в сопрограммах). При этом состояние текущего продолжения замораживается, а управление передается другому продолжению в котором оно может быть так же восстановлено в той точке где было заморожено в прошлый раз. Псевдокод:
[Continuation]
class A
{
  mutable counter : int = 0;

  publc Resume(otherContinuation : B) : void
  {
    while (counter < 4)
    {
      counter++;
    
      yield otherContinuation(counter);
    }
  }
}

[Continuation]
class B
{
  mutable otherCounter : int = 0;
  
  publc Resume(counter : int) : void
  {
    WriteLine($"counter is $counter");

    while (true)
    {
      Suspend();
      otherCounter += 2;
      WriteLine($"And now counter is $counter and otherCounter is $otherCounter");
    }
  }
}

module Program
{
  Main() : void
  {
    def a = A();
    a.Resume(B());
  }
}

/*
BEGIN-OUTPUT
counter is 1
And now counter is 2 and otherCounter is 2
And now counter is 3 and otherCounter is 4
And now counter is 4 and otherCounter is 6
END-OUTPUT
*/
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[4]: Очень интересная задачка - макрос Continuation
От: hardcase Пират http://nemerle.org
Дата: 23.02.10 19:30
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Любой другой вызов объекта должен рассматриваться как обычный. При этом наверно имеет смысл позволять вызвать только те методы которые не содержат вызовов Suspend или других методов этого же объекта содержащих вызов Suspend. Таким обрезом будет гарантированно, что при заморозке в стеке не будет находиться вызовов к другим объектам (вызовы которых не могут быть сериализованы).


Т.е. по аналогии с оператором yield, который определен рамках функции-генератора, операция Suspend легитимна только в методах самого Continuation-объекта (можно сказать ее семантика навязывает protected модификатор). Иными словами происходит обобщение идеи yield до масштабов класса. Я правильно понял?
http://nemerle.org/Banners/?t=Developer!&g=dark /* иЗвиНите зА неРовнЫй поЧерК */
Re[5]: Очень интересная задачка - макрос Continuation
От: VladD2 Российская Империя www.nemerle.org
Дата: 23.02.10 20:31
Оценка:
Здравствуйте, hardcase, Вы писали:

H>Здравствуйте, VladD2, Вы писали:


VD>>Любой другой вызов объекта должен рассматриваться как обычный. При этом наверно имеет смысл позволять вызвать только те методы которые не содержат вызовов Suspend или других методов этого же объекта содержащих вызов Suspend. Таким обрезом будет гарантированно, что при заморозке в стеке не будет находиться вызовов к другим объектам (вызовы которых не могут быть сериализованы).


H>Т.е. по аналогии с оператором yield, который определен рамках функции-генератора, операция Suspend легитимна только в методах самого Continuation-объекта (можно сказать ее семантика навязывает protected модификатор). Иными словами происходит обобщение идеи yield до масштабов класса. Я правильно понял?


Да. Только реализовать это дело на базе конечного автомата (как в итераторах) не получится. Так как могут вызваться другие методы объектов, нужно сохранять значение параметров вызовов (колстэк). Причем делать это нужно максимально эффективно.
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[6]: Очень интересная задачка - макрос Continuation
От: Mr.Cat  
Дата: 24.02.10 17:31
Оценка:
Здравствуйте, VladD2, Вы писали:
VD>Да. Только реализовать это дело на базе конечного автомата (как в итераторах) не получится. Так как могут вызваться другие методы объектов, нужно сохранять значение параметров вызовов (колстэк). Причем делать это нужно максимально эффективно.
На эту тему, кстати, статейка от в т.ч. Мартина есть (fulltext гуглится).
Re[3]: Очень интересная задачка - макрос Continuation
От: Mr.Cat  
Дата: 24.02.10 17:36
Оценка: 43 (1)
Здравствуйте, VladD2, Вы писали:
VD>Там есть и примеры и объяснения.
Много статей про континуации и cps: http://library.readscheme.org/page6.html
Re[7]: Очень интересная задачка - макрос Continuation
От: VladD2 Российская Империя www.nemerle.org
Дата: 24.02.10 18:25
Оценка:
Здравствуйте, Mr.Cat, Вы писали:

MC>На эту тему, кстати, статейка от в т.ч. Мартина есть (fulltext гуглится).


Дык и давал бы прямую ссылку.

Кстати, мне кажется CPS не самый эффективный путь реализации. Эффективнее было бы эмулировать стек вызовов.

Я не эксперт в этой области, так что могу ошибаться. Если у кого-то есть доводы по этому поводу, то прошу высказываться.
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[8]: Очень интересная задачка - макрос Continuation
От: Denom Украина  
Дата: 24.02.10 18:48
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>... то прошу высказываться.


Мне почему-то кажется что по другому кроме как через cps-трансформацию не получится
А в идеале — через монады — как в F#.
(без изменения .NET runtime).
Кстати в mono так и сделали.
Со стэком наверное получится только в nemerlish. Пример можно подглядеть в IronScheme.
Как вариант попробовать на фиберах.
... << RSDN@Home 1.2.0 alpha 4 rev. 1237>>
Re[9]: Очень интересная задачка - макрос Continuation
От: VladD2 Российская Империя www.nemerle.org
Дата: 24.02.10 19:25
Оценка:
Здравствуйте, Denom, Вы писали:

D>Мне почему-то кажется что по другому кроме как через cps-трансформацию не получится


А что мешает просто эмулировать стек и переписывать вызовы так, чтобы они использовали не реальный стэк, а виртуальный?

D>А в идеале — через монады — как в F#.


У нас разные понятия об идеале. На мой взгляд — это требующее лишней работы (от конечного программиста) и весьма медленное решение. Причем не дающее тех преимуществ, что могут предоставить продолжения.

В прочем, на то макросы и макросы, чтобы вместо выбора лучшего пути (тм) реализовать несколько подходов. А там уж пусть жизнь определить более жизнеспособный вариант.

D>(без изменения .NET runtime).

D>Кстати в mono так и сделали.

Что сделали? Не понял...

D>Со стэком наверное получится только в nemerlish. Пример можно подглядеть в IronScheme.


Вообще-то nemerlish компилирует исполняемые выражения, так что он мало чем отличается от компилятора.

D>Как вариант попробовать на фиберах.


А чем плох подход с переписыванием вызовов, чтобы они использовали сохраняемый в объекте стэк?
Я понимаю, что практически невозможно переписывать вызовы внутри чужих методов (особенно если не доступны исходники, т.е. код лежит в других сборках), но для вызовов методов из этого же класса таких проблем быть не должно.
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.