Вопросы | c

Как реализовать продолжения?

Вопрос

Kyle Cronin | 7047 просмотров | рейтинг: 1

Я работаю над интерпретатором Scheme, написанным на C. В настоящее время он использует стек времени выполнения C в качестве своего собственного стека, что представляет незначительную проблему с реализацией продолжений. Мое текущее решение - ручное копирование стека C в кучу, а затем копирование его обратно при необходимости. Помимо нестандартного C, это решение вряд ли идеально. Как проще всего реализовать продолжения для Scheme в C?



Ответы

Chris Jester-Young

+ 1 -
Вместо этого используйте явный стек.  


Patrick

+ 17 -
Я помню, как читал статью, которая может быть вам полезна: Чейни на M.T.A. :-) Некоторые реализации Схемы, о которых я знаю, такие как SISC, выделяют свои кадры вызова в куче. @ollie: Вам не нужно делать подъем, если все ваши кадры вызова находятся в куче. Конечно, существует компромисс между производительностью и временем подъема по сравнению с накладными расходами, необходимыми для размещения всех кадров в куче. Возможно, это должен быть настраиваемый параметр времени выполнения в интерпретаторе. :-П  


olliej

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


Josh Segall

+ 7 -
Традиционный способ - использовать setjmp и longjmp, хотя есть некоторые предостережения. Вот довольно хорошее объяснение  


Thomas Vander Stichele

+ 28 -
Хорошее резюме доступно в Стратегиях реализации первоклассных продолжений, статье Clinger, Hartheimer и Ost. Я рекомендую посмотреть на реализацию Chez Scheme в частности. Копирование в стеке не так сложно, и существует ряд хорошо понятных методов для повышения производительности. Использование кадров, выделенных в куче, также довольно просто, но вы компенсируете создание накладных расходов для нормальной ситуации, когда вы не используете явные продолжения. Если вы преобразуете входной код в стиль передачи продолжения (CPS), тогда вы можете избежать полного удаления стека. Однако, хотя CPS элегантен, он добавляет еще один этап обработки в интерфейс и требует дополнительной оптимизации для преодоления определенных последствий для производительности.  


Kyle Burton

+ 7 -
Примеры, которые вы можете посмотреть: Chicken (реализация Scheme, написанная на C, которая поддерживает продолжения); Пол Грэма «На Лиспе» - где он создает преобразователь CPS для реализации подмножества продолжений в Common Lisp; и Weblocks - основанная на продолжении веб-инфраструктура, которая также реализует ограниченную форму продолжений в Common Lisp.  


soegaard

+ 12 -
Если вы начинаете с нуля, вам действительно стоит обратить внимание на преобразование Continuation Passing Style (CPS). Хорошие источники включают LISP в маленьких частях и Схему Марка Фили в 90-минутной презентации.  


Joel Borggrén-Franck

+ 7 -
Продолжения не проблема: вы можете реализовать их с помощью обычных функций высшего порядка, используя CPS. Проблема с наивным выделением стека заключается в том, что хвостовые вызовы никогда не оптимизируются, а это означает, что вы не можете быть схемой. Лучший современный подход к отображению стека спагетти схемы в стек - использование трамплинов: по существу, дополнительная инфраструктура для обработки вызовов, не похожих на C, и выходов из процедур. См. Батутный стиль (пс). Там есть код, иллюстрирующий обе эти идеи.  


Charles Stewart

+ 5 -
Продолжения в основном состоят из сохраненного состояния стека и регистров ЦП в точке переключения контекста. По крайней мере, вам не нужно копировать весь стек в кучу при переключении, вы можете только перенаправить указатель стека. Продолжения тривиально реализованы с использованием волокон. http://en.wikipedia.org/wiki/Fiber_%28computer_science%29 , Единственное, что требует тщательной инкапсуляции, это передача параметров и возвращаемые значения. В Windows волокна выполняются с использованием семейства вызовов CreateFiber / SwitchToFiber. в Posix-совместимых системах это можно сделать с помощью makecontext / swapcontext. boost :: coroutine имеет рабочую реализацию сопрограмм для C ++, которая может служить ориентиром для реализации.


Chris Jester-Young

+ 1 -
Кажется, тезис Дибвига пока не упоминается. Это удовольствие читать. Модель на основе кучи проще всего реализовать, но на основе стека является более эффективным. Игнорировать строковую модель. Р. Кент Дибвиг. Три модели реализации для схемы. http://www.cs.indiana.edu/~dyb/papers/3imp.pdf Также ознакомьтесь с документами по реализации на ReadScheme.org. http://library.readscheme.org/page8.html Резюме выглядит следующим образом:
  В этой диссертации представлены три модели реализации для Схемы   Язык программирования. Первая - это модель на основе кучи, используемая в некоторых   форма в большинстве реализаций Схемы на сегодняшний день; второй новый   основанная на стеке модель, которая значительно эффективнее, чем   модель на основе кучи при выполнении большинства программ; а третий новый   строковая модель, предназначенная для использования в многопроцессорных системах   Реализация Схемы.   Модель на основе кучи выделяет несколько важных структур данных в   куча, включая фактические списки параметров, среды привязки и вызов   кадры.   Модель на основе стека размещает эти же структуры в стеке   как только возможно. Это приводит к меньшему выделению кучи, меньшему объему памяти   ссылки, более короткие последовательности команд, меньше сборка мусора,   и более рациональное использование памяти.   Строковая модель распределяет версии этих структур прямо в   текст программы, который представлен в виде строки символов. в   строковая модель, программы Scheme переводятся в FFP   язык разработан специально для поддержки схемы. Программы в этом   язык непосредственно исполняются машиной FFP,   многопроцессорный компьютер для сокращения строк.   Модель на основе стека имеет непосредственный практический смысл; это   модель, используемая авторской системой Chez Scheme, высокопроизводительная   Реализация Схемы. Строковая модель будет полезна для   предоставление Схемы как альтернативы FFP высокого уровня на машине FFP   однажды машина поняла.
 


Patrick

+ 17 -
Как указывал soegaard, основной ссылкой остается эта Идея в том, что продолжением является замыкание, которое сохраняет свой стек управления оценкой. Стек управления необходим для продолжения оценки с момента создания продолжения с использованием call/cc. Часто вызов продолжения делает длительным время выполнения и заполняет память дублирующимися стеками. Я написал этот глупый код, чтобы доказать, что в мит-схеме происходит сбой схемы, Код суммирует первые 1000 чисел 1+2+3+...+1000.
 (call-with-current-continuation
 (lambda (break)
   ((lambda (s) (s s 1000 break))
    (lambda (s n cc)
      (if (= 0 n)
          (cc 0)
          (+ n
             ;; non-tail-recursive,
             ;; the stack grows at each recursive call
             (call-with-current-continuation
              (lambda (__)
                (s s (- n 1) __)))))))))
 

Если вы переключитесь с 1000 на 100 000, код потратит 2 секунды, а при увеличении числа ввода произойдет сбой.


Теги

c | lisp | scheme | continuations