В 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. Сериализовать состояние таких объектов стандартными методами и в последствии восстанавливать это состояние.
Если есть смельчаки готовые взяться за данную задачу, то я (и думаю, другие читатели этого форума) готов оказать содействие.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re: Очень интересная задачка - макрос Continuation
Здравствуйте, Denom, Вы писали:
D>А можно какой-нибудь маленький примерчик? D>как это выглядит с макросом и без.
С итераторами C# 2.0 знаком?
Их ограничения такие:
1. yield return работает только в рамках одного метода. Мы можем вызвать другие методы, но из них yield return сделать не можем.
2. Мы не можем сериализовать состояние такого объекта и не можем его клонировать.
3. Мы должны возвращать только объекты заранее заданного (в описании возвращаемого типа итератора) типа.
4. Мы можем получать информацию извне итератора только при его создании. Получить информацию при возобновлении работы, штатными методами, нельзя (если только менять объект возвращенный из итератора, но это не очень красивое решение).
Теперь представь себе, что есть объект который может как бы заморозить свое выполнение вернув некоторое значение. Такой объект можно где-то сохранить или клонировать, а потом запустить копию (клон или полученную путем десериализации). Причем он запустится с того же места где она была прервана и все состояние вычисления в нем так же будет сохранено.
Более того такому объекту вполне можно передать некоторые значения (во время пробуждения). Ну, и ко всему прочему снимается проблема стека (вместо ограниченного стека будет динамически растущая куча).
Что касается с и без, то тут очень тяжело попоставлять. Представь себе как ты будешь реализовывать логику навигации по навороченному сайту где есть возможность нажать кнопку "Назад" (на предыдущую страницу) несколько раз, а потом нажать "Веред" (тоже несколько раз). При переходе на каждую из страниц в приложении нужно восстановить то состояние которое было непосредственно перед уходом с нее.
Если у тебя нет фишки подобной континиэшонам тебе нужно будет самому заботиться о состоянии. Скорее всего это будет страшная каша из флагов размещенных черти где (в лучшем случае в объекте управляющем состоянием).
Если же есть континуэшоны, то код приложения может быть прямолинейным и простым. Нам не надо создавать флагов, заботиться о восстановлении состояния и т.п. Все что нужно — это перед уходом со страницы склонировать объект в котором ведется работа и запомнить в некотором сессионном объекте. Когда юзер нажмет Вперед или Назад, то нам нужно будет всего лишь вынуть этот объект и заменить им текущий. Текущий же точно так же сохраняется и позволяет "откатиться" к этому состоянию когда это будет нужно.
Более того. Мы можем сериализовать объект и поместить его на диск или в БД. Тогда пользователь может неделями не заходить на сайт, но зайдя на него продолжить свои действия так как-будто он и не отходил от монитора.
Здравствуйте, VladD2, Вы писали:
VD>Если есть смельчаки готовые взяться за данную задачу, то я (и думаю, другие читатели этого форума) готов оказать содействие.
А это вообще реально реализовать на макросах?
Только не говорите, что yield в Nemerle итак на них реализован, не поверю
Re[2]: Очень интересная задачка - макрос Continuation
Здравствуйте, Пельмешко, Вы писали:
П>А это вообще реально реализовать на макросах? П>Только не говорите, что yield в Nemerle итак на них реализован, не поверю
Там хитро, макрос как заглушка. А вся работа выполняется в typer'е.
Но машина сосотояния генерируется с помощью квазицитирования.
На мой неискушенный взгляд код выглядит достаточно красиво.
... << RSDN@Home 1.2.0 alpha 4 rev. 1237>>
Re[3]: Очень интересная задачка - макрос Continuation
Здравствуйте, Denom, Вы писали:
D>Там хитро...
И главная хитрость в том что обработка yield происходит в обработчике исключения SwitchToYielding.
Насчет возможности реализации на макросах — макросам ведь доступны все внутренности компилятора.
Т.е если можно сделать внутри компиятора, значит можно и на макросах.
Учитывая что на них уже сделаны AOP, Concurrency, etc...
... << RSDN@Home 1.2.0 alpha 4 rev. 1237>>
Re[2]: Очень интересная задачка - макрос Continuation
Здравствуйте, Пельмешко, Вы писали:
VD>>Если есть смельчаки готовые взяться за данную задачу, то я (и думаю, другие читатели этого форума) готов оказать содействие.
П>А это вообще реально реализовать на макросах?
Вполне. Хотя, задача конечно не из легких.
П>Только не говорите, что yield в Nemerle итак на них реализован, не поверю
Не, не макросом. Но есть всего лишь одна причина по которой yield нельзя сдеать макросом. Дело в том, что методы содержащие yield не помечаются каким-либо образом. Необходимость их переписывания определяется только наличием ключевого слова yield. В компиляторе по этому поводу встроен хак. Когда компилятор находит вхождение макроса yield, он генерирует исключение SwitchToYielding. Это исключение перехватывается в самом начале процесса типизации тела метода.
В перехватчике:
1. Меняется тело метода на заглушку конечного автомата.
2. Поднимается флаг inside_yielding_function (чтобы не генерировать SwitchToYielding повторно).
3. Процесс типизации тела метода запускается повторно.
4. Когда находится макрос yield, то он заменяется на лэйбл.
4. В конце процесса типизации в тело match-а добавленного на шаге 1 добавляются переходы конечного автомата сформированные при раскрытии макросов yield.
Если бы было заранее известно, что функцию нужно переписывать в конечный автомат, то все остальное можно было бы спокойно реализовать в виде макроса.
В случае реализации автомата для целого класса было бы разумно помечать такие классы специальным мета-атрибутом. Этот мета-атрибут и выполнит всю работу по переписыванию.
Учитывая, что в таком классе должны быть доступны вызовы методов этого же класса, генерацией конечного автомата не отделаешься. Видимо придется организовать генерацию стеков и замену вызовов на переходы с закладыванием параметров в эти стеки (если вызов рекурсивный и рекурсия концевая, можно в стеки ничего не класть).
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re: Очень интересная задачка - макрос Continuation
Здравствуйте, VladD2, Вы писали:
VD>Если есть смельчаки готовые взяться за данную задачу, то я (и думаю, другие читатели этого форума) готов оказать содействие.
Я мог бы попробовать.
Надо бы только в голове уложить смысл сей логики, так как я никогда не использовал "настоящие" продолжения в своей практике — только yield-ы.
Если с кишками класса более менее понятно, то вот модель использования таких объектов не понятна.
/* иЗвиНите зА неРовнЫй поЧерК */
Re[2]: Очень интересная задачка - макрос Continuation
Здравствуйте, hardcase, Вы писали:
H>>Если с кишками класса более менее понятно, то вот модель использования таких объектов не понятна.
H>Т.е. я хочу сказать, что область применения для меня ясна. Меня интересует способ работы с самим объектом.
Как с обычным объектом. Только если в коде такого объекта будет вызван метод Suspend, то управление должно быть возвращено в ту точку (находящуюся во вне объекта) где был вызван метод Resume этого объека.
Примечание: Я не применяю имя yield для большей ясности. В принципе вместо Suspend можно использовать yield.
Так вот Suspend и Resume — это не настоящие методы, а средства управления потоком выполнения. Когда внутри некоторого меода вызывается Suspend, то выполнение как бы замораживается в этой точке (как бы запоминается состояние стека) и управление получает код который пред этим произвел вызов Resume. Естественно это некий код не относящийся к данному объекту (внутри объека вызывать this.Resume() запрещено, так как бессмысленно).
Кроме того такой объект должен реализовывать метод Clone который должен клонировать объект вместе с состоянием выполнения (с виртуальным стеком вызовов). Такой клонированный объект, после клонирования, должен находиться в состоянии Suspend. Его вызов продолжает выполнение с той точки в которой был сделан вызов Clone. При этом копия и оригинал должен жить независимо. Скажем если оригинал заморожен, то копия может производить выполнение.
Методы Suspend и Resume могут не иметь параметров и возвращаемых значений, а могут иметь. Если они имеют параметры, то список аргументов Suspend должен соотвествовать возвращаемому значению Resume и наоборот. Это позволит на каждом шаге возобновления исполнения передавать дополнительные данные в объект-продолжение и возвращать из него некоторые данные при его усыплении (Suspend).
Любой другой вызов объекта должен рассматриваться как обычный. При этом наверно имеет смысл позволять вызвать только те методы которые не содержат вызовов Suspend или других методов этого же объекта содержащих вызов Suspend. Таким обрезом будет гарантированно, что при заморозке в стеке не будет находиться вызовов к другим объектам (вызовы которых не могут быть сериализованы).
Таким образом мы получаем эдакие итераторы на стероидах — более гибкие и более мощные.
Такую штуку можно будет с легкостью применять для реализации сложного потока управления.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[4]: Очень интересная задачка - макрос Continuation
Да... Кроме того нужно иметь возможность передавать управление в другие продолжения (как в сопрограммах). При этом состояние текущего продолжения замораживается, а управление передается другому продолжению в котором оно может быть так же восстановлено в той точке где было заморожено в прошлый раз. Псевдокод:
[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
*/
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[4]: Очень интересная задачка - макрос Continuation
Здравствуйте, VladD2, Вы писали:
VD>Любой другой вызов объекта должен рассматриваться как обычный. При этом наверно имеет смысл позволять вызвать только те методы которые не содержат вызовов Suspend или других методов этого же объекта содержащих вызов Suspend. Таким обрезом будет гарантированно, что при заморозке в стеке не будет находиться вызовов к другим объектам (вызовы которых не могут быть сериализованы).
Т.е. по аналогии с оператором yield, который определен рамках функции-генератора, операция Suspend легитимна только в методах самого Continuation-объекта (можно сказать ее семантика навязывает protected модификатор). Иными словами происходит обобщение идеи yield до масштабов класса. Я правильно понял?
/* иЗвиНите зА неРовнЫй поЧерК */
Re[5]: Очень интересная задачка - макрос Continuation
Здравствуйте, hardcase, Вы писали:
H>Здравствуйте, VladD2, Вы писали:
VD>>Любой другой вызов объекта должен рассматриваться как обычный. При этом наверно имеет смысл позволять вызвать только те методы которые не содержат вызовов Suspend или других методов этого же объекта содержащих вызов Suspend. Таким обрезом будет гарантированно, что при заморозке в стеке не будет находиться вызовов к другим объектам (вызовы которых не могут быть сериализованы).
H>Т.е. по аналогии с оператором yield, который определен рамках функции-генератора, операция Suspend легитимна только в методах самого Continuation-объекта (можно сказать ее семантика навязывает protected модификатор). Иными словами происходит обобщение идеи yield до масштабов класса. Я правильно понял?
Да. Только реализовать это дело на базе конечного автомата (как в итераторах) не получится. Так как могут вызваться другие методы объектов, нужно сохранять значение параметров вызовов (колстэк). Причем делать это нужно максимально эффективно.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[6]: Очень интересная задачка - макрос Continuation
Здравствуйте, VladD2, Вы писали: VD>Да. Только реализовать это дело на базе конечного автомата (как в итераторах) не получится. Так как могут вызваться другие методы объектов, нужно сохранять значение параметров вызовов (колстэк). Причем делать это нужно максимально эффективно.
На эту тему, кстати, статейка от в т.ч. Мартина есть (fulltext гуглится).
Re[3]: Очень интересная задачка - макрос Continuation
Здравствуйте, VladD2, Вы писали:
VD>... то прошу высказываться.
Мне почему-то кажется что по другому кроме как через cps-трансформацию не получится
А в идеале — через монады — как в F#.
(без изменения .NET runtime).
Кстати в mono так и сделали.
Со стэком наверное получится только в nemerlish. Пример можно подглядеть в IronScheme.
Как вариант попробовать на фиберах.
... << RSDN@Home 1.2.0 alpha 4 rev. 1237>>
Re[9]: Очень интересная задачка - макрос Continuation
Здравствуйте, Denom, Вы писали:
D>Мне почему-то кажется что по другому кроме как через cps-трансформацию не получится
А что мешает просто эмулировать стек и переписывать вызовы так, чтобы они использовали не реальный стэк, а виртуальный?
D>А в идеале — через монады — как в F#.
У нас разные понятия об идеале. На мой взгляд — это требующее лишней работы (от конечного программиста) и весьма медленное решение. Причем не дающее тех преимуществ, что могут предоставить продолжения.
В прочем, на то макросы и макросы, чтобы вместо выбора лучшего пути (тм) реализовать несколько подходов. А там уж пусть жизнь определить более жизнеспособный вариант.
D>(без изменения .NET runtime). D>Кстати в mono так и сделали.
Что сделали? Не понял...
D>Со стэком наверное получится только в nemerlish. Пример можно подглядеть в IronScheme.
Вообще-то nemerlish компилирует исполняемые выражения, так что он мало чем отличается от компилятора.
D>Как вариант попробовать на фиберах.
А чем плох подход с переписыванием вызовов, чтобы они использовали сохраняемый в объекте стэк?
Я понимаю, что практически невозможно переписывать вызовы внутри чужих методов (особенно если не доступны исходники, т.е. код лежит в других сборках), но для вызовов методов из этого же класса таких проблем быть не должно.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[8]: Очень интересная задачка - макрос Continuation
Здравствуйте, VladD2, Вы писали: MC>>На эту тему, кстати, статейка от в т.ч. Мартина есть (fulltext гуглится). VD>Дык и давал бы прямую ссылку.
Просто прямые ссылки иногда мрут (вот, на readscheme, который я упоминал, таких полно), а эта, по идее, должна жить долго.
VD>Кстати, мне кажется CPS не самый эффективный путь реализации. Эффективнее было бы эмулировать стек вызовов.
Да, глобальный cps по идее тормозит код. Я статью проглядел мельком — там cps не глобальный предлагается, а по месту. Mark Feeley, кстати, про свой Gambit тоже что-то такое говорил. Плюс в статье есть ссылки всякие, на другие статьи и в т.ч. на другие подходы. По идее, должно сойти за отправную точку в изучении вопроса.
Re[9]: Очень интересная задачка - макрос Continuation
Здравствуйте, Denom, Вы писали:
D>Здравствуйте, VladD2, Вы писали:
VD>>... то прошу высказываться.
D>Мне почему-то кажется что по другому кроме как через cps-трансформацию не получится D>А в идеале — через монады — как в F#. D>(без изменения .NET runtime). D>Кстати в mono так и сделали. D>Со стэком наверное получится только в nemerlish. Пример можно подглядеть в IronScheme. D>Как вариант попробовать на фиберах.
В Mono вся эта штука сделана на уровне рантайма, но внятных примеров использования я к сожалению не обнаружил (это еще в те времена когда они анонсировали фичу). Если махнуть рукой на решение в общем виде и ограничиться только "обобщением yield до масштабов класса" мне задача видится вполне решаемой на макросах.
/* иЗвиНите зА неРовнЫй поЧерК */
Re[9]: Очень интересная задачка - макрос Continuation
Здравствуйте, Denom, Вы писали: D>А в идеале — через монады — как в F#.
Ну тогда достаточно скопипастить в nemerle do-notation. Получится хелпер для ручной cps-трансформации.
D>Кстати в mono так и сделали.
А там континуации можно многократно вызывать?
D>Пример можно подглядеть в IronScheme.
А там разве полноценные континуации без cps сделаны?
Re[10]: Очень интересная задачка - макрос Continuation
Здравствуйте, hardcase, Вы писали:
H> Если махнуть рукой на решение в общем виде и ограничиться только "обобщением yield до масштабов класса" мне задача видится вполне решаемой на макросах.
На мой взгляд полноценные продолжения (т.е. сохраняющие контекст вычислений в любом месте и в любое время) невозможно реализовать эффективно, по крайней мере без поддержки рантайма. Но на практике такая круть не особо нужна. Полноценные продолжения — это слишком мощное оружие. Через них можно реализовать половину фич языка (например, исключения). Но большая часть фич уже есть в дотнете и стало быть в немерле. Так что продолжения нужны в основном ради реализации форк-флоу сценариев в виде "плоского" кода (без обработчиков событий и т.п.). И тут "обобщением yield до масштабов класса" или если смотреть с другой стороны "ограничение продолжений до масштаба класса" — это то что нужно. Все равно бессмысленно описывать ворк-флоу-логику размазывая ее по нескольким классам.
С точки зрения многопоточности тоже будет достаточно класса в котором можно будет заморозить вычисления и продолжить их в другом потоке (или даже в другом процессе на другом компьютере).
Мне кажется, будет не очень сложно организовать переписывание вызовов методов так чтобы они использовали эмуляцию стека. Для эффективности для каждого метода можно заводить свой стек вызовов (чтобы в них лежали однородные данные). Кроме того нужно будет завести еще один простой стек для учета того в каком из специализированных стеков находится аргументы конкретного вызова. Сами списки аргументы можно описывать структурами и передавать их по ссылке. Думаю решение будет несколько менее эффективно чем использование полноценного стека, но все же соизмеримо с нормальным выполнением.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[10]: Очень интересная задачка - макрос Continuation
Здравствуйте, Mr.Cat, Вы писали:
MC>Ну тогда достаточно скопипастить в nemerle do-notation. Получится хелпер для ручной cps-трансформации.
Я с хаскелем можно сказать не знаком... А вот идея из F# с computation workflows мне понравилась — красиво...
MC>А там континуации можно многократно вызывать?
Судя по той версии что у меня (если я правильно понимаю)сохранённый стек при восстановлении не удаляется...
MC>А там разве полноценные континуации без cps сделаны?
Там 2 реализации с условной компиляцией... в моей ревизии CPS версия сломана...
... << RSDN@Home 1.2.0 alpha 4 rev. 1237>>
Re[11]: Очень интересная задачка - макрос Continuation
Здравствуйте, Denom, Вы писали: MC>>Ну тогда достаточно скопипастить в nemerle do-notation. Получится хелпер для ручной cps-трансформации. D>Я с хаскелем можно сказать не знаком... А вот идея из F# с computation workflows мне понравилась — красиво...
Я f# плохо понимаю, но там ведь суть в том, что последовательность выражений вида let x = f(y) заменяется на цепочку вызовов bind соответствующей монады? Вроде и в скала такое имеется (эээ... sequence comprehensions что-ли).
MC>>А там континуации можно многократно вызывать? D>Судя по той версии что у меня (если я правильно понимаю)сохранённый стек при восстановлении не удаляется...
Хм... Тогда смахивает на полноценный shift/reset или call/cc, в которых можно с континуацией делать что угодно, что можно с обычной функцией.
MC>>А там разве полноценные континуации без cps сделаны? D>Там 2 реализации с условной компиляцией... в моей ревизии CPS версия сломана...
Просто та, которая без cps — там ведь неполноценные континуации? Или вру?
Re[12]: Очень интересная задачка - макрос Continuation
Здравствуйте, Mr.Cat, Вы писали:
MC>Я f# плохо понимаю, но там ведь суть в том, что последовательность выражений вида let x = f(y) заменяется на цепочку вызовов bind соответствующей монады? Вроде и в скала такое имеется (эээ... sequence comprehensions что-ли).
допустим есть монада async в ней описаны let, bind, return
и мы пишем
async
{
let a = func1()
let! b = func2()
a + b
}
только второе выражение, которое с ! заменится на bind, а всё что после него передастся в bind в стиле cps...
MC>Хм... Тогда смахивает на полноценный shift/reset или call/cc, в которых можно с континуацией делать что угодно, что можно с обычной функцией.
ну ну это call/cc и есть...
MC>Просто та, которая без cps — там ведь неполноценные континуации? Или вру?
хз... я код по диагонали просмотрел...
