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

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

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

9.08.2008 01:18:37
12 ОТВЕТОВ
РЕШЕНИЕ

Я помню, как читал статью, которая может быть вам полезна : Чейни на MTA :-)

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

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

19
9.08.2008 03:20:13

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

1
9.08.2008 01:29:33
-1: явный стек это что? Выделенная куча структура данных, моделирующая стек? Выделенная куча структура данных, моделирующая историю использования стека? Актуальность в вопросе?
Charles Stewart 26.12.2009 18:11:22

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

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

1
9.08.2008 02:55:01
Но, чтобы поддержать закрытие, не могли бы вы просто сделать лямбда-лифтинг?
apg 1.10.2008 17:25:06

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

Вот довольно хорошее объяснение

7
31.01.2016 14:08:37

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

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

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

29
2.05.2013 16:05:42

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

7
25.09.2008 17:59:39
на какую главу On Lisp вы ссылаетесь, пожалуйста?
Will Ness 22.08.2018 06:05:39
Глава 20 о продолжениях - в частности, 20,3
Kyle Burton 25.08.2018 17:29:06

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

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

14
31.01.2016 21:34:05
Книга Queinnec в Лиспе В маленьких пьесах в наличии (по крайней мере , в его французском издании от Paracampus)
Basile Starynkevitch 30.01.2016 12:20:02

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

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

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

7
3.12.2009 13:04:35

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

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

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

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

5
22.11.2016 20:54:30
реализовано тривиально ... требуется тщательная инкапсуляция - в этом абзаце есть определенное напряжение. Этот ответ будет улучшен с помощью ссылки на некоторый код.
Charles Stewart 12.04.2011 18:56:58

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

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

8
30.01.2016 12:30:03
Мне очень нравится книга Аппеля. Одним из преимуществ является то, что вы можете ссылаться на исходный код компилятора SML / NJ, который является довольно хорошим живым примером процесса, описанного Аппелем в книге.
Nate C-K 19.03.2015 01:00:14

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

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

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

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

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

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

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

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

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

10
26.06.2019 15:40:34

Как soegaardуказано, основная ссылка остается R. Kent Dybvig. "Three Implementation Models for Scheme".

Идея в том, что продолжение - это замыкание, которое сохраняет свой стек управления оценкой. Стек управления необходим для продолжения оценки с момента создания продолжения 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 секунды, а при увеличении числа ввода произойдет сбой.

2
26.06.2019 10:25:33