Я работаю над интерпретатором Scheme, написанным на C. В настоящее время он использует стек среды выполнения C в качестве собственного стека, что создает небольшую проблему с реализацией продолжений. Моим текущим решением является ручное копирование стека C в кучу, а затем копирование его обратно при необходимости. Помимо того, что это решение не является стандартным C, это решение едва ли можно назвать идеальным.
Каков самый простой способ реализовать продолжения для схемы в C?
Я помню, как читал статью, которая может быть вам полезна: Чейни о MTA :-)
Некоторые известные мне реализации Scheme, такие как SISC, размещают свои кадры вызовов в куче.
@ollie: вам не нужно поднимать, если все ваши кадры вызовов находятся в куче. Конечно, есть компромисс в производительности: время на подъем по сравнению с накладными расходами, необходимыми для выделения всех кадров в куче. Возможно, это должен быть настраиваемый параметр времени выполнения в интерпретаторе. :-П
Хорошее резюме доступно в статье Implementation Strategies for First Class Continuations Клингер, Хартхаймер и Ост. Я рекомендую обратить внимание на реализацию Chez Scheme, в частности.
Копирование стека не так уж сложно, и существует ряд хорошо изученных методов повышения производительности. Использование кадров, выделенных в куче, также довольно просто, но вы идете на компромисс, создавая накладные расходы для «нормальной» ситуации, когда вы не используете явные продолжения.
Если вы преобразуете входной код в стиль передачи продолжения (CPS), вы можете полностью избавиться от стека. Однако, хотя CPS элегантен, он добавляет еще один шаг обработки во внешнем интерфейсе и требует дополнительной оптимизации для преодоления определенных последствий для производительности.
Если вы начинаете с нуля, вам действительно следует обратить внимание на преобразование стиля передачи продолжения (CPS).
Хорошие источники включают «LISP в небольших частях» и minute-en.html" rel="noreferrer">Схема Марка Фили в 90-минутной презентации.
Похоже, что тезис Дибвига пока не упоминается. Это удовольствие читать. Модель на основе кучи проще всего реализовать, но стековая модель более эффективна. Игнорируйте модель на основе строк.
Р. Кент Дибвиг. «Три модели реализации схемы». http://www.cs.indiana.edu/~dyb/papers/3imp.pdf
Также ознакомьтесь с документами по реализации на ReadScheme.org. https://web.archive.org/http://library.readscheme.org/page8.html
Аннотация выглядит следующим образом:
В данной диссертации представлены три модели реализации языка программирования Scheme. Первая — это модель на основе кучи, используемая в той или иной форме в большинстве реализаций Scheme на сегодняшний день; вторая — новая модель на основе стека, которая значительно более эффективна, чем модель на основе кучи, при выполнении большинства программ; и третья — новая модель на основе строк, предназначенная для использования в многопроцессорной реализации Scheme.
Модель на основе кучи размещает в куче несколько важных структур данных, включая фактические списки параметров, среды привязки и кадры вызовов.
Модель на основе стека по возможности размещает те же самые структуры в стеке. Это приводит к меньшему выделению кучи, меньшему количеству ссылок на память, более коротким последовательностям инструкций, меньшей сборке мусора и более эффективному использованию памяти.
Строковая модель размещает версии этих структур прямо в тексте программы, который представлен в виде строки символов. В модели на основе строк программы Scheme переводятся на язык FFP, специально разработанный для поддержки Scheme. Программы на этом языке непосредственно выполняются машиной FFP, многопроцессорным компьютером для сокращения строк.
Модель на основе стека имеет немедленную практическую пользу; это модель, используемая авторской системой Chez Scheme, высокопроизводительной реализацией Scheme. Модель на основе строк будет полезна для предоставления Scheme в качестве высокоуровневой альтернативы FFP на машине FFP после того, как машина будет реализована.
Помимо хороших ответов, которые вы получили до сих пор, я рекомендую Эндрю Аппеля Компиляция с продолжениями. Он очень хорошо написан и, хотя не имеет прямого отношения к C, является источником действительно хороших идей для авторов компиляторов.
В Куриной Вики также есть страницы, которые могут показаться вам очень интересными, например, внутренняя структура и процесс компиляции (где CPS объясняется на реальном примере компиляции ).
Примеры, на которые вы можете обратить внимание: Chicken (реализация Scheme, написанная на C, которая поддержка продолжений); On Lisp Пола Грэма, где он создает преобразователь CPS для реализации подмножества продолжений в Common Lisp; и Weblocks — веб-фреймворк, основанный на продолжении, который также реализует ограниченную форму продолжений в Общий Лисп.
Продолжения не проблема: вы можете реализовать их с обычными функциями более высокого порядка, используя CPS. Проблема с наивным распределением стека заключается в том, что хвостовые вызовы никогда не оптимизируются, что означает, что вы не можете быть схемой.
Наилучший текущий подход к отображению стека спагетти схемы в стек - это использование трамплинов: по сути, дополнительная инфраструктура для обработки вызовов, не похожих на C, и выходов из процедур. См. Стиль батута (ps).
Существует некоторый код, иллюстрирующий обе эти идеи.
Традиционный способ — использовать setjmp и longjmp, хотя и с некоторыми оговорками.
Вот достаточно хорошее объяснение< /а>
Продолжения в основном состоят из сохраненного состояния стека и регистров ЦП в момент переключения контекста. По крайней мере, вам не нужно копировать весь стек в кучу при переключении, вы можете только перенаправить указатель стека.
Продолжения тривиально реализуются с помощью волокон. http://en.wikipedia.org/wiki/Fiber_%28computer_science%29 . Единственное, что требует тщательной инкапсуляции, — это передача параметров и возвращаемые значения.
В Windows волокна создаются с использованием семейства вызовов CreateFiber/SwitchToFiber. в Posix-совместимых системах это можно сделать с помощью makecontext/swapcontext.
В boost::coroutine есть работающая реализация сопрограмм для C++, которая может служить ориентиром для реализации.
Как указал soegaard, основной ссылкой остается R. Kent Dybvig. "Three Implementation Models for Scheme".
Идея в том, что продолжение — это замыкание, которое сохраняет свой стек управления оценкой. Стек управления необходим для того, чтобы продолжить оценку с момента создания продолжения с помощью call/cc.
Часто вызов продолжения увеличивает время выполнения и заполняет память дублированными стеками. Я написал этот глупый код, чтобы доказать, что в mit-схеме он приводит к сбою схемы,
Код суммирует первые 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 секунды, а если вы увеличите введенное число, он вылетит.
Вместо этого используйте явный стек.
Патрик прав, единственный способ сделать это - использовать явный стек в вашем интерпретаторе и поднимать соответствующий сегмент стека в кучу, когда вам нужно преобразовать в продолжение.
Это в основном то же самое, что необходимо для поддержки замыканий в языках, которые их поддерживают (замыкания и продолжения несколько связаны).
