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

Question

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

Как проще всего реализовать продолжения для Scheme в C?

Answer 1

Хорошее резюме доступно в Стратегии реализации для первоклассных продолжений , статья Clinger, Hartheimer и Ost. Я рекомендую посмотреть на реализацию Chez Scheme в частности.

Копирование в стеке не так сложно, и существует ряд хорошо понятных методов, позволяющих повысить производительность. Использование кадров, выделенных в куче, также довольно просто, но вы компенсируете создание накладных расходов для «нормальной» ситуации, когда вы не используете явные продолжения.

Если вы преобразуете входной код в стиль продолжения передачи (CPS), тогда вы можете полностью избавиться от стека. Однако, хотя CPS элегантен, он добавляет еще один этап обработки во внешний интерфейс и требует дополнительной оптимизации для преодоления определенных последствий для производительности.

Answer 2

Я помню, как читал статью, которая может вам помочь: Чейни на M.T.A. : -)

Некоторые известные мне реализации схем, такие как SISC , выделяют свои кадры вызова в куче.

@ ollie: Вам не нужно поднимать, если все ваши кадры вызова находятся в куче. Конечно, существует компромисс между производительностью и временем подъема по сравнению с накладными расходами, необходимыми для размещения всех кадров в куче. Возможно, это должен быть настраиваемый параметр времени выполнения в интерпретаторе. : -Р

Answer 3

Если вы начинаете с нуля, вам действительно стоит обратить внимание на преобразование Continuous Passing Style (CPS).

Хорошие источники включают «LISP в маленьких частях» и Схема Марка Фили в 90-минутной презентации .

Answer 4

Кажется, тезис Дибвига не упоминается до сих пор. Это удовольствие читать. Модель на основе кучи проще всего реализовать, но на основе стека является более эффективным. Игнорировать строковую модель.

R. Кент Дибвиг. «Три модели реализации для схемы». http://www.cs.indiana.edu/~dyb/papers/3imp.pdf

Также ознакомьтесь с документами по реализации на ReadScheme.org. http://library.readscheme.org/page8.html

Аннотация выглядит следующим образом:

В этой диссертации представлены три модели реализации Схемы. Язык программирования. Первая - это модель на основе кучи, используемая в некоторых форма в большинстве реализаций Схемы на сегодняшний день; вторая новая основанная на стеке модель, которая значительно эффективнее, чем модель на основе кучи при выполнении большинства программ; а третий новый строковая модель, предназначенная для использования в многопроцессорных системах Реализация Схемы.

Модель на основе кучи выделяет несколько важных структур данных в куча, включая фактические списки параметров, среды привязки и вызов кадры.

Модель на основе стека размещает эти же структуры в стеке когда возможно. Это приводит к меньшему выделению кучи, меньшему объему памяти ссылки, более короткие последовательности команд, меньше сборка мусора, и более рациональное использование памяти.

Строковая модель распределяет версии этих структур прямо в текст программы, который представлен в виде строки символов. в строковая модель, программы Scheme переводятся в FFP язык разработан специально для поддержки схемы. Программы в этом язык непосредственно исполняются машиной FFP, многопроцессорный компьютер для сокращения строк.

Модель на основе стека имеет непосредственный практический смысл; это модель, используемая авторской системой Chez Scheme, высокопроизводительная Реализация Схемы. Строковая модель будет полезна для предоставление Схемы как альтернативы FFP высокого уровня на машине FFP как только машина реализована.

Answer 5

Помимо хороших ответов, которые вы получили до сих пор, я рекомендую Эндрю Аппеля Компиляция с продолжениями . Он очень хорошо написан, и хотя он не имеет прямого отношения к C, он является источником действительно хороших идей для авторов компиляторов.

В Chicken Wiki также есть страницы, которые вы найдете очень интересными, такие как внутренняя структура и процесс компиляции (где CPS объясняется с помощью реального примера компиляции). 1009 *

Answer 6

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

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

Есть некоторый код , иллюстрирующий обе эти идеи.

Answer 7

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

Answer 8

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

Вот достаточно хорошее объяснение

Answer 9

Продолжения в основном состоят из сохраненного состояния стека и регистров ЦП в точке переключения контекста. По крайней мере, вам не нужно копировать весь стек в кучу при переключении, вы можете только перенаправить указатель стека.

Продолжения тривиально реализуются с использованием волокон. http://en.wikipedia.org/wiki/Fiber_%28computer_science%29 , Единственное, что требует тщательной инкапсуляции, это передача параметров и возвращаемые значения.

В Windows волокна выполняются с использованием семейства вызовов CreateFiber / SwitchToFiber. в Posix-совместимых системах это можно сделать с помощью makecontext / swapcontext.

boost :: coroutine имеет работающую реализацию сопрограмм для C ++, которая может служить ориентиром для реализации.

Answer 10

Как указывалось 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 секунды, а при увеличении числа ввода произойдет сбой.