Вопрос:

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

c lisp scheme continuations

7336 просмотра

12 ответа

60689 Репутация автора

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

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

Автор: Kyle Cronin Источник Размещён: 09.08.2008 01:18

Ответы (12)


1 плюс

62793 Репутация автора

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

Автор: Patrick Размещён: 09.08.2008 01:29

17 плюса

186308 Репутация автора

Решение

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

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

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

Автор: Chris Jester-Young Размещён: 09.08.2008 02:49

1 плюс

29101 Репутация автора

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

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

Автор: olliej Размещён: 09.08.2008 02:55

7 плюса

29868 Репутация автора

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

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

Автор: Thomas Vander Stichele Размещён: 28.08.2008 10:05

28 плюса

3207 Репутация автора

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

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

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

Автор: Josh Segall Размещён: 31.08.2008 05:02

7 плюса

20693 Репутация автора

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

Автор: Kyle Burton Размещён: 25.09.2008 05:59

12 плюса

1040 Репутация автора

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

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

Автор: Joel Borggrén-Franck Размещён: 05.12.2008 08:00

7 плюса

10018 Репутация автора

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

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

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

Автор: Charles Stewart Размещён: 03.12.2009 01:04

5 плюса

8336 Репутация автора

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

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

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

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

Автор: Stefan Dragnev Размещён: 04.01.2010 10:33

8 плюса

6460 Репутация автора

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

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

Автор: Jay Размещён: 08.06.2010 12:25

9 плюса

25072 Репутация автора

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

Р. Кент Дибвиг. «Три модели реализации для схемы». 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, как только машина будет реализована.

Автор: soegaard Размещён: 30.10.2011 03:31

2 плюса

10011 Репутация автора

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

Автор: alinsoar Размещён: 25.10.2017 08:17
32x32