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

Question

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

Каков самый простой способ реализовать продолжения для Scheme на C?

Answer 1

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

Некоторые известные мне реализации Scheme, такие как СИСС, распределяют свои фреймы вызовов по куче.

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

Answer 2

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

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

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

Answer 3

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

Хорошие источники включают "LISP in small pieces" и Презентация схемы Марка Фили за 90 минут.

Answer 4

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

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

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

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

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

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

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

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

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

Answer 5

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

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

Answer 6

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

Answer 7

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

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

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

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

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

Answer 11

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

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

Answer 12

Как soegaard как уже отмечалось, основной ориентир остается этот

Идея в том, что продолжение - это замыкание, которое сохраняет свой стек управления оценкой.Стек управления необходим для продолжения вычисления с момента создания продолжения с использованием call/cc.

Частый вызов продолжения увеличивает время выполнения и заполняет память дублированными стеками.Я написал этот глупый код, чтобы доказать, что в mit-scheme это приводит к сбою схемы,

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