Я работаю над интерпретатором Схемы, написанным на C. В настоящее время он использует стек времени выполнения C как свой собственный стек, который представляет собой небольшую проблему с выполнением продолжений. Мое текущее решение - это ручное копирование стека C в кучу, а затем копирование при необходимости. Помимо того, что он не является стандартным C, это решение вряд ли является идеальным.
Каков самый простой способ реализации продолжений для Схемы в C?
Я помню, как читал статью, которая может вам помочь: Чейни на M.T.A.: -)
Некоторые реализации Схемы, о которых я знаю, например SISC, выделяют свои кадры вызова в куче.
@ollie: вам не нужно делать подъем, если все ваши кадры вызовов находятся в куче. Конечно, есть компромисс в производительности: время подъема, а также накладные расходы, необходимые для распределения всех кадров в куче. Возможно, это должен быть настраиваемый параметр времени выполнения в интерпретаторе.:-P
Хорошее резюме доступно в Стратегии внедрения для первоклассных континуумов, статья Клингера, Хартхаймера и Оста. Я рекомендую посмотреть, в частности, реализацию Chez Scheme.
Скопировать копии не так сложно, и для улучшения производительности существует ряд хорошо понятых методов. Использование выделенных кучей кадров также довольно просто, но вы делаете компромисс между созданием накладных расходов для "нормальной" ситуации, когда вы не используете явные продолжения.
Если вы конвертируете входной код в стиль продолжения передачи (CPS), вы можете уйти с удалением стека вообще. Однако, хотя CPS элегантный, он добавляет еще один шаг обработки в интерфейсе и требует дополнительной оптимизации для преодоления определенных последствий для производительности.
Если вы начинаете с нуля, вам действительно нужно перейти к преобразованию стиля перехода (CPS).
Хорошие источники включают "LISP в маленьких кусках" и Схема Марка Фили в 90-минутной презентации.
Кажется, тезис Дибвига не упоминается до сих пор. Это удовольствие читать. Модель на основе кучи проще всего реализовать, но на основе стека она более эффективна. Игнорировать строковую модель.
Р. Кент Дибвиг. "Три модели реализации для схемы". 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, как только машина будет реализована.
Помимо хороших ответов, которые вы получили до сих пор, я рекомендую Andrew Appel Compiling with Continuations. Он очень хорошо написан и, хотя и не имеет прямого отношения к C, он является источником действительно хороших идей для авторов компиляторов.
В Chicken Wiki также есть страницы, которые вы найдете очень интересными, такие как внутренняя структура и процесс компиляции (где CPS объясняется с помощью реального примера компиляции).
Традиционным способом является использование setjmp и longjmp, хотя есть предостережения.
Примерами, которые вы можете посмотреть, являются: Chicken (реализация схемы, написанная на C, которая поддерживает продолжения); Paul Graham В Lisp - где он создает трансформатор CPS для реализации подмножества продолжений в Common Lisp; и Weblocks - веб-каркас на основе продолжения, который также реализует ограниченную форму продолжений в Common Lisp.
Непрерывность - это не проблема: вы можете реализовать те, у которых есть регулярные функции более высокого порядка, используя CPS. Проблема с наивным распределением стека заключается в том, что хвостовые вызовы никогда не оптимизируются, а это значит, что вы не можете быть схемой.
Наилучший текущий подход к схеме спагетти в стеке заключается в использовании батутов: по существу, дополнительная инфраструктура для обработки не-C-подобных вызовов и выходов из процедур. См. Trampolined Style (ps).
Там некоторый код, иллюстрирующий обе эти идеи.
Продолжения в основном состоят из сохраненного состояния стека и регистров CPU в точке контекстных переключателей. По крайней мере, вам не нужно копировать весь стек в кучу при переключении, вы можете перенаправить указатель стека.
Продолжения тривиально реализуются с использованием волокон. http://en.wikipedia.org/wiki/Fiber_%28computer_science%29 , Единственными вещами, требующими тщательной инкапсуляции, являются значения передачи и возврата параметров.
В Windows волокна выполняются с использованием семейства вызовов CreateFiber/SwitchToFiber. в Posix-совместимых системах это можно сделать с помощью makecontext/swapcontext.
boost:: coroutine имеет рабочую реализацию сопрограмм для С++, которая может служить отправной точкой для реализации.
Как отметил soegaard, основным упоминанием остается R. Kent Dybvig. "Three Implementation Models for Scheme" 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 секунды, а при увеличении числа ввода произойдет сбой.
Вместо этого используйте явный стек.
Патрик прав, единственный способ, которым вы действительно можете это сделать, - использовать явный стек в вашем интерпретаторе и поднять соответствующий сегмент стека в кучу, когда вам нужно преобразовать его в продолжение.
Это в основном то же самое, что и для поддержки закрытий на поддерживающих их языках (замыкания и продолжение в некоторой степени связаны).