Продвинутым отцам: превратить блокировку в suspend

Marinavo_0507

Хочется советов, что бы такое поизучать, чтоб сделать следущее.
Пишешь программу, которая вызывает некие блокирующиеся функции (типа ожидание ввода/вывода).
А умный компилятор или среда выполнения сама преобразует это в continuation passing style,
то есть сохраняет контекст, и передаёт выполнение некоей внешней программе, в которой можно разместить
типичный или не очень event loop, чтоб в нужный момент продолжить выполнение из сохранённого контекста.
Низкоуровневые хаки не интересуют. Язык чем культурнее, тем лучше. Сделать с нуля понятное дело можно,
но меня заломает.
Желательные свойства:
1) хорошо бы чтоб контекст умел выживать при перезагрузке машины
2) неплохо бы иметь возможность продолжить один контекст несколько раз, по разным траекториям.
Кто-нибудь видел что-то подобное?

Dasar

на Smalltalk-е такая либа должна быть - они любят там такие вещи делать.

Julie16

Глупый вопрос: а для чего это нужно? Мне даже интересно стало...

Marinavo_0507

Ну например, для веб-приложений.

Dasar

В основном, это нужно - когда есть есть внешний поток событий, и при этом в программе нужно выполнять длительные действия (разнесенную по времени последовательность действий).
Так, например, в любом даже простеньком АИ такое надо.
ps
Фактически - это просто надстройка над автоматом, позволяющая в более наглядном виде записать последовательность действий.
Автоматные переходы очень ненаглядны - особенно если есть скобочные действия (последовательность вложенных контекстов - соответственно требуются какие-то действия при входе в контекст, и при выходе).

rosali

превратить блокировку в suspend
(типа ожидание ввода/вывода)
Что-то я не понял, ожидание ввода/вывода оно и так suspend, чего сделать то надо?

Dasar

Хочется писать вот такой код:


void Main

{

using (BinaryReader reader = new BinaryReader("input.data"

{

   int version = reader.ReadInt;

   string name = reader.ReadString;

    byte[] data;

    if(name.StartWith("DataStream"

        data = reader.ReadBytes(100);

    else

         data = reader.ReadBytes(15);

   }

}

}

но при этом этот код должен формировать примерно следующую программу:


struct Context

{

   BinaryReader reader;

   int version;

   string name;

   byte[] data;

   AsyncOperation operation;

}

enum RunState

{

   Start,

   End,

   OpenStream,

    ReadVersion,

    ReadVersion_Wait,

    ReadName

   //и т.д.

}



void Main

{

   RunState state = RunState.Start;

  Context context = new Context;

   while (state != RunState.End)

   {

      switch (state)

      {

        case RunState.ReadVersion;

           context.operation = reader.StartAsyncReadInt;

           state = RunState.ReadVersion_Wait;

           break;

        case RunState.ReadVersion_Wait:

           if (operation.IsComplete

           {

              version = operation.EndAsyncReadInt;

              state = RunState.ReadName;

           }



         case RunState.Start:

           state = RunState.OpenStream;

           break;

         case RunState.OpenStream;

            context.reader = new BinaryReader("input.data");

           state = RunState.ReadVersion;

           break;

      }

   }

}

т.е. фактически хочется, чтобы длительные операции переводились автоматом в асинхронные.

rosali

переводились автоматом в асинхронные
Ну чего же в них асинхронного, если они в обоих случаях друг за другом выполняются? Асинхронные с чем? Контекст замечательно хранят треды, зачем чего-то еще изобретать?

Marinavo_0507

> Контекст замечательно хранят треды, зачем чего-то еще изобретать?
Хреново хранят:
на диск в общем случае не сохранить - перезагрузку не выдерживают
разветвить поток не могут
слишком мало тредов одновременно возможно - попробуй например хотя бы 100000 сделать

rosali

попробуй например хотя бы 100000 сделать
скока там нулей? Не, не буду
Тебе вообще что-то существующее сконвертить надо, или сам что-то новое писать будешь?
Если второе, глянь Charm++, я его тут всем рекламирую Прикольная модель вычислений, может помочь. Правда то, что ты называешь контекстом придется все таки пальцами указывать, зато контрольные точки автоматически, асинхронность тоже автоматически, еще заодно распараллелишься

Marinavo_0507

Писать хочется новое, но чтоб была возможность вызывать функции из готовых библиотек.
Интерфейс к перловым модулям бы
Charm++ - походу ни одному требованию не удовлетворяет, или я что не понял?

rosali

ни одному требованию не удовлетворяет
Из этих обоих?
1) хорошо бы чтоб контекст умел выживать при перезагрузке машины
2) неплохо бы иметь возможность продолжить один контекст несколько раз, по разным траекториям.
Контекст - это С++ объект. Он умеет выживать при перезагрузке машины, это в шарме называется контрольная точка. Или что-то другое надо? Продолжить один контекст несколько раз тоже вроде без проблем, откопируй и продолжай. Charm++ - это чуть больше чем библиотека над С++, так что он дружен с перлом не больше чем сам С++ (а я не знаю что там между перлом и С++ )
Правда чтобы писать на шарме надо по-другому _думать_. Так что может это и не то что ты хотел. Но если ты расчитываешь на такую конвертацию, ты же в любом случае должен по-другому думать вроде бы...

Marinavo_0507

> Правда чтобы писать на шарме надо по-другому _думать_.
Судя по примерам, там надо всего лишь писать в CPS. Думать по-другому для этого не надо,
хватает формальных преобразований.
Это недостойно человека, так как преобразование в CPS вполне можно сделать автоматически.
То есть, не выполняется главное требование.

Dasar

> Асинхронные с чем?
Асинхронные по отношению к треду, из которого они исполняются.
> Ну чего же в них асинхронного, если они в обоих случаях друг за другом выполняются?
Они не обязательно должны выполняться непосредственно друг за другом.
Пока происходит ожидание может выполняться другая задача, анализ входных событий и т.д.
> Контекст замечательно хранят треды, зачем чего-то еще изобретать?
да, согласен.
Но треды сильно заинкапсулированы между друг другом. соответственно, треды удобны когда задачи независимы между собой. Если же задача сильно завязана на входной поток событий, то отдельный тред не подойдет, Т.к. треды не позволяют легко прервать (или изменить) контекст и выполняемую последовательность действий
Возмем, например, орка из warcraft-а - у этого орка есть следующие задачи (утрировано):
1. Передвигаться из левого нижнего угла карты в верхний правый
2. Двигать ноги
3. Размахивать топором
4. Орать боевую песню.
5. Бить по шее всех встречных
каждая из этих задач описывается примерно так:
1. Передвигаться


  while(не правый верхний угол)

  {

      найтиСвободноеМестоКотороеВедетВНужномНаправлении;

      ПерейтиНаСвободноеМесто;  

  }
2. Двигать ногами


  while(надоДвигаться)

  {

     Левой;

     Правой;

  }
2. Махать топором


  while(естьТопор)

  {

     МахнутьВлево;

     МахнутьНазад;

     МахнутьВправо;

     МахнутьВперед;

  }

и т.д.
И эти задачи бессмысленно разносить по отдельным тредам: т.к. они сильно переплетены между собой, а также любой из действий все равно надо уметь прерывать в любой точке: если топор отобрали сразу после действия МахнутьВлево, то бессмысленно выполять все последующие действия.

rosali

Ну ладно, рожайте...

Dasar

Ты же вроде был поклонник ФЯ - они-то точно должны такое уметь делать.
Чем они тебе не подходят? низкоуровневостью?

Ivan8209

Наверное, ты ищешь function и call-with-current-continuation.
Ну, и ещё что-то совсем классическое лисповое.
Чтобы "всё есть список" и Маккарти пророк его.
---
...Я работаю антинаучным аферистом...

Marinavo_0507

Сами по себе, конечно, они такого не делают.
Преобразовать код - надежда есть.

Marinavo_0507

call-with-current-continuation - звучит заманчиво, поищу

Ivan8209

Спрашивать у бродячих схематиков.
---
...Я работаю антинаучным аферистом...

Dasar

например
google: continuation passing style ML
выдает большое кол-во ссылок по теме
по остальным фун. языкам тоже самое должно быть.

Marinavo_0507

Да, про алгоритмы преобразования кода там есть, кто бы сомневался.

Dasar

кроме алгоритмов программы тоже встречаются.
например, видел преобразование ML в Java-у и т.д.
Или хочешь сказать, что все это уровня студенческих поделок?

Marinavo_0507

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

Marinavo_0507

Вот, говорят что тут ( http://seaside.st/ ) это есть, для веб-приложений, на smalltalk.
Но что-то не понятно.

Papazyan

Напиши, пожалуйста, более конкретно, как ты представляешь себе выполнение такой программы. Т.е. исходник -> реальность на псевдокоде.

Marinavo_0507

Суммирование элементов из списка.
Исходник:


int sum = 0;



while(true) {

  POSTPONE next_item IN

    Item(int a) : { sum += a; }

    Eof : {  break; }

  END

}

print(sum);

Результат:


machine Sum {

  int sum;

states:

  NEXT_ITEM: { next_item }

actions:

  INIT: init  {

    sum = 0;

    CHANGE_TO NEXT_ITEM

  }

  WHEN NEXT_ITEM: Item (int a) {

    sum += a;

    CHANGE_TO NEXT_ITEM

  }

  WHEN NEXT_ITEM: Eof  {

    print(sum);

    END

  }

}
Сам event-loop, хранящий состояния (в данном случае единственное: NEXT_ITEM
в отдельной программе, здесь не показан.
Конструкция POSTPONE означает ожидание события, с которым, в зависимости от исхода,
связано несколько continuation'ов.

bleyman

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

Ivan8209

"Languages are coming closer and closer to reinventing Lisp
along a slow and painful path."
---
...Я работаю антинаучным аферистом...

Papazyan



(let (bindings here)

   (define main-loop 

          (local (dispatch (val) 

               (cond eql val 'next-item) ...)

                          eql val 'init) ...)

                          eql val 'eof) ...

          (init ...)

          (while (t)        

            (let val (call-with-cc 

                (lambda (cc)

                     (set where-to-save cc) ('INIT

               (dispatch val





(define main-event-loop 

  (main-loop)

  (loop

     (let event (get-event

         (where-to-save event
На псевдо Scheme.
Что-то в этом роде? Я не совсем в курсе, как continuations работают в Scheme, но на Common Lisp такое можно реализовать, только будет немного корявее. Каждый раз, как мы вызываем where-to-save continuation, val в main-loop имеет значение текущего event. Контекст сохраняется автоматически, поскольку это вообще особенность всех языков с понятием closure. Можно написать специальные макросы для автоматизации создания подобной херни, добавить в них сохранение переменных и загрузку.

Marinavo_0507

(cond eql val 'next-item) ...)

                          eql val 'init) ...)

                          eql val 'eof) ...

Это вручную построенный автомат?

Papazyan



    Item(int a) : { sum += a; }

    Eof : {  break; }
Это аналог вот этого. Не забывай также, что в Лиспе с помощью макросов можно горы свернуть. Если уж CLOS можно на чистом Лиспе реализовать, то автоматную модель вообще как два пальца.

Marinavo_0507

Да я собственно верю.
А в каком виде continuation хранится, можешь посмотреть?
Туда внутрь дают лазить?

Papazyan

В Схеме не знаю, они там встроенные. На Lisp я видел реализацию только в книге On Lisp (доступна online). Там все сделано просто, по рабоче-крестьянски. Фактически тебе дают вместо обычных макросов особые - =defun, =values, =bind, =lambda, =funcall, =applay. Они неявно манипулируют переменной *cont*, она теперь передается в каждую функцию и при возвращении =value вызывает *cont* от результата. Благодаря связыванию переменных все гладко работает.
Т.е. фактически программа в полуавтоматическом режиме переводится в CPS форму. Можно реализовать и полностью автомотический перевод, но это сложно, хотя может кто-то уже и написал нужную библиотеку.
Вот пример обхода дерева (dft2 начинает обход). Для каждого листа выполнение прерывается и возобновляется через restart.


(setq *saved* nil) 



(=defun dft-node (tree) 

  (cond null tree) (restart 

    atom tree) (=values tree 

    (t (push #'(lambda  (dft-node (cdr tree *saved*) 

        (dft-node (car tree 



(=defun restart  

  (if *saved* 

    (funcall (pop *saved* 

    (=values 'done 



(=defun dft2 (tree) 

  (setq *saved* nil) 

  (=bind (node) (dft-node tree) 

    (cond eq node 'done) (=values nil 

               (t (princ node) (restart

Ivan8209

Поставить посмотреть?
Вспомнил такую вещь: в какой-то схеме видел сохранение образа
виртуальной машины на диск.
Это насчёт перезагрузок.
---
...Я работаю антинаучным аферистом...

Marinavo_0507

> Поставить посмотреть?
Сначала почитаю книжку про рабоче-крестьянский способ.
Маза это то, что надо.
> Вспомнил такую вещь: в какой-то схеме видел сохранение образа
> виртуальной машины на диск.
Это то, что я называю низкоуровневыми хаками.

Ivan8209

Ладно, а я посмотрю, как это сделано.
В Guile, насколько помню, всё встроено.
---
...Я работаю...

Papazyan

Только осторожно с ней. Она посвящена макросам и основы Лиспа в ней не даются. Несколько глав начиная с Continuations посвященны применению этой техники (точнее там цель иная, но continuations дают возможность делать все лучше и быстрее).
Состояние виртуальной машины можно сохранять и в Лиспе и это не хак, там компилятор даже так работает.

Marinavo_0507

> Состояние виртуальной машины можно сохранять и в Лиспе и это не хак, там компилятор даже так работает.
Само по себе - не хак.
А вот использовать это для того, что я хочу - хак.

Ivan8209

Мне тут подсказывают: "Yes, SISC allows you to serialize
continuations to any output port."
---
...Я работаю антинаучным аферистом...

Marinavo_0507

Ну как бы хочется не только сериализации, а ещё и выкинуть ненужное.
Что нужно, а что нет, вполне может определить разработчик, а то и транслятор.
Поэтому я и заинтересовался рабоче-крестьянским вариантом.
Я пока представляю себе язык, похожий на традиционный Бейсик,
который компилируется в Лисп.

Ivan8209

В "Мире Лиспа" известных финских сочинителей есть пример,
как делается лисп на лиспе.
Можешь заглянуть туда, если потребуется.
Обычно мусор собирается.
Нонеча системы умные пошли.
---
...Я работаю антинаучным аферистом...

Papazyan

Кстати, вот Web на Lisp через Continuations. На странице описание методики, а сам пакет называется UCW.
http://lisp.tech.coop/Web%2FContinuation

Marinavo_0507

Ну круто, осталось найти как перловые модули вызывать

Papazyan

Кстати, написал для OCaml + p4 тоже самое, что в On Lisp. Выглядит корявее, но только из-за того, что не знаю как заменить вызов функции на вызов с *cont*. Пример с деревьями работает, хочу теперь переключение процессов реализовать.

Marinavo_0507

Дочитал On Lisp до этого места.
Проблема в том, что внутрь closure не заглянуть, то есть плохо с сохранением/восстановлением.
То есть нужно всё руками делать, а тогда практически пофиг, в какой язык компилировать.

Ivan8209

В классическом лиспе, например у финнов, замыкание --- это
список, у которого первым идёт атом function, а потом всё
остальное.
У них же показано, как делается лисп на лиспе.
Это уже проще.
Я, конечно, знаю ещё один способ поизвращаться,
но он тебе вряд ли подойдёт.
---
...Я работаю антинаучным аферистом...
Оставить комментарий
Имя или ник:
Комментарий: