Как реализовать продолжения? -- c поле с участием lisp поле с участием scheme поле с участием continuations пол Связанный проблема

How to implement continuations?


53
vote

проблема

русский

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

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

Английский оригинал

I'm working on a Scheme interpreter written in C. Currently it uses the C runtime stack as its own stack, which is presenting a minor problem with implementing continuations. My current solution is manual copying of the C stack to the heap then copying it back when needed. Aside from not being standard C, this solution is hardly ideal.

What is the simplest way to implement continuations for Scheme in C?

</div
           

Список ответов

18
 
vote
vote
Лучший ответ
 

Я помню, как читать статью, которая может помочь вам: cheney на MTA : -)

Некоторые реализации схемы, о которых я знаю, например, как sisc , выделяют их кадры для вызовов на кучу. < / P >.

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

 

I remember reading an article that may be of help to you: Cheney on the M.T.A. :-)

Some implementations of Scheme I know of, such as SISC, allocate their call frames on the heap.

@ollie: You don't need to do the hoisting if all your call frames are on the heap. There's a tradeoff in performance, of course: the time to hoist, versus the overhead required to allocate all frames on the heap. Maybe it should be a tunable runtime parameter in the interpreter. :-P

</div
 
 
29
 
vote

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

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

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

 

A good summary is available in Implementation Strategies for First-Class Continuations, an article by Clinger, Hartheimer, and Ost. I recommend looking at Chez Scheme's implementation in particular.

Stack copying isn't that complex and there are a number of well-understood techniques available to improve performance. Using heap-allocated frames is also fairly simple, but you make a tradeoff of creating overhead for "normal" situation where you aren't using explicit continuations.

If you convert input code to continuation passing style (CPS) then you can get away with eliminating the stack altogether. However, while CPS is elegant it adds another processing step in the front end and requires additional optimization to overcome certain performance implications.

</div
 
 
14
 
vote

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

Хорошие источники включают в себя «Lisp в небольших частях» и Схема Marc Felsey в 90 минутах презентации .

 

If you are starting from scratch, you really should look in to Continuation Passing Style (CPS) transformation.

Good sources include "LISP in small pieces" and Marc Feeley's Scheme in 90 minutes presentation.

</div
 
 
 
 
10
 
vote

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

r. Кент Дыбвиг. «Три модели реализации для схемы». http://www.c.inkiana.edu/~dyb/papers/ 3IMP.PDF

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

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

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

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

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

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

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

 

It seems Dybvig's thesis is unmentioned so far. It is a delight to read. The heap based model is the easiest to implement, but the stack based is more efficient. Ignore the string based model.

R. Kent Dybvig. "Three Implementation Models for Scheme". http://www.cs.indiana.edu/~dyb/papers/3imp.pdf

Also check out the implementation papers on ReadScheme.org. https://web.archive.org/http://library.readscheme.org/page8.html

The abstract is as follows:

This dissertation presents three implementation models for the Scheme Programming Language. The first is a heap-based model used in some form in most Scheme implementations to date; the second is a new stack-based model that is considerably more efficient than the heap-based model at executing most programs; and the third is a new string-based model intended for use in a multiple-processor implementation of Scheme.

The heap-based model allocates several important data structures in a heap, including actual parameter lists, binding environments, and call frames.

The stack-based model allocates these same structures on a stack whenever possible. This results in less heap allocation, fewer memory references, shorter instruction sequences, less garbage collection, and more efficient use of memory.

The string-based model allocates versions of these structures right in the program text, which is represented as a string of symbols. In the string-based model, Scheme programs are translated into an FFP language designed specifically to support Scheme. Programs in this language are directly executed by the FFP machine, a multiple-processor string-reduction computer.

The stack-based model is of immediate practical benefit; it is the model used by the author's Chez Scheme system, a high-performance implementation of Scheme. The string-based model will be useful for providing Scheme as a high-level alternative to FFP on the FFP machine once the machine is realized.

</div
 
 
8
 
vote

Помимо хороших ответов, которые вы настолько далеко, я рекомендую Andrew Appel's Продолжения . Это очень хорошо написано и не имея дело напрямую с C, это источник действительно хороших идей для писателей компилятора.

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

 

Besides the nice answers you've got so far, I recommend Andrew Appel's Compiling with Continuations. It's very well written and while not dealing directly with C, it is a source of really nice ideas for compiler writers.

The Chicken Wiki also has pages that you'll find very interesting, such as internal structure and compilation process (where CPS is explained with an actual example of compilation).

</div
 
 
 
 
7
 
vote

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

 

Examples that you can look at are: Chicken (a Scheme implementation, written in C that support continuations); Paul Graham's On Lisp - where he creates a CPS transformer to implement a subset of continuations in Common Lisp; and Weblocks - a continuation based web framework, which also implements a limited form of continuations in Common Lisp.

</div
 
 
   
   
7
 
vote

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

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

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

 

Continuations aren't the problem: you can implement those with regular higher-order functions using CPS. The issue with naive stack allocation is that tail calls are never optimised, which means you can't be scheme.

The best current approach to mapping scheme's spaghetti stack onto the stack is using trampolines: essentially extra infrastructure to handle non-C-like calls and exits from procedures. See Trampolined Style (ps).

There's some code illustrating both of these ideas.

</div
 
 
7
 
vote

Традиционный путь - использовать <код> setjmp и <код> longjmp , хотя есть предостережения.

Вот a разумно Хорошее объяснение

 

The traditional way is to use setjmp and longjmp, though there are caveats.

Here's a reasonably good explanation

</div
 
 
5
 
vote
Продолжения

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

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

В волокнах Windows выполняется с использованием семейства звонков CreateFibr / SwiteFiber. В Subix-совместимые системы это можно сделать с MakeContext / Swapcontext.

BOOST :: COROUTINE имеет работоспособность COROUTINES для C ++, которые могут служить контрольной точкой для реализации.

 

Continuations basically consist of the saved state of the stack and CPU registers at the point of context switches. At the very least you don't have to copy the entire stack to the heap when switching, you could only redirect the stack pointer.

Continuations are trivially implemented using fibers. http://en.wikipedia.org/wiki/Fiber_%28computer_science%29 . The only things that need careful encapsulation are parameter passing and return values.

In Windows fibers are done using the CreateFiber/SwitchToFiber family of calls. in Posix-compliant systems it can be done with makecontext/swapcontext.

boost::coroutine has a working implementation of coroutines for C++ that can serve as a reference point for implementation.

</div
 
 
2
 
vote

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

 

As soegaard pointed out, the main reference remains R. Kent Dybvig. "Three Implementation Models for Scheme".

The idea is, a continuation is a closure that keeps its evaluation control stack. The control stack is required in order to continue the evalution from the moment the continuation was created using call/cc.

Oftenly invoking the continuation makes long time of execution and fills the memory with duplicated stacks. I wrote this stupid code to prove that, in mit-scheme it makes the scheme crash,

The code sums the first 1000 numbers 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) __))))))))) 

If you switch from 1000 to 100 000 the code will spend 2 seconds, and if you grow the input number it will crash.

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

Use an explicit stack instead.

</div
 
 
 
 
1
 
vote
<Р> Патрик является правильным, единственным способом вы действительно можете сделать это, чтобы использовать явные стек интерпретатор, и поднять соответствующий сегмент стека в кучу, когда вам нужно преобразовать в продолжение. <Р> Это в основном так же, как то, что необходимо для поддержки закрытия на языках, поддерживающих их (затворы и продолжениями быть несколько связанных).
 

Patrick is correct, the only way you can really do this is to use an explicit stack in your interpreter, and hoist the appropriate segment of stack into the heap when you need to convert to a continuation.

This is basically the same as what is needed to support closures in languages that support them (closures and continuations being somewhat related).

</div
 
 
 
 

Связанный проблема

0  Ошибка сборки Android NDK  ( Android ndk build error ) 
Я написал маленькую Hello World Program в C, а вот это <код> circ.onclick = { e: dom.MouseEvent => ... } 0 Вот файл make <код> circ.onclick = { e: dom....

0  Fead вызывает ошибку сегментации  ( Fread causing segmentation fault ) 
Попытка создать файл 1024 байтов случайных данных. Когда я запускаю это, я получаю ошибку неисправности сегментации на линии FREAD. Кто-нибудь видит, что я де...

0  Реализация ARP Smooth  ( Implementing arp sweep ) 
Я играю с libpcap / jpcap. Реализация Sweeper ARP. Я отправляю запрос на все IP в блоке до вещательного адреса и чтения ответов. Теперь я не могу думать о том...

0  Если безымянный семафор инициализируется в общей памяти, Shm_unlink () уничтожает семафор?  ( If an unnamed semaphore is initialized in shared memory does shm unlink destr ) 
Я использую POSIX SEMAPHORES и совместную память для координации одного производителя и одного потребительского буфера. Я хочу полностью инициализировать эту ...

1  Lnk2001: неразрешенный внешний символ _maincrtstartup  ( Lnk2001 unresolved external symbol maincrtstartup ) 
Я пытаюсь скомпилировать пример Win32 Parrot Ardrone SDK V1.8, используя Visual Studio 2012 Express для Windows Desktop. Я использую Windows 7 64-бит. SDK нап...

0  Структура в C- Чтобы добавить атрибут во время выполнения?  ( Structure in c to add a attribute at runtime ) 
Как добавить переменную / атрибут участника на структуру из основного в C? ...

0  Как остановить программу хранения более одного символа в переменную CHAR? [Дубликат]  ( How to stop a program from storing more than a single character into a char vari ) 
<в сторону CLASS = "S-NEWACTS S-WELTIVE__info JS-Post-New Imide MB16« Роль = «Статус»> Этот вопрос уже есть ответы здесь : ...

0  Как я могу хранить разные виды операторов в 2D-массиве в C?  ( How can i store different kinds of operators in a 2d array in c ) 
Я хочу сделать функцию y = f (x) в виде строки и выяснить операторы в нем, чтобы хранить их в 2D-массиве, где каждый операторы будут рассматриваться как разде...

2  Состояние не удалось для ldrloaddll  ( Status failed for ldrloaddll ) 
Я пытаюсь разрабатывать функцию ldrloaddll и мне не повезло с этим .. Я также проушинул для некоторых примеров, нет никакой много документации или правильного...

78  Srand () - зачем называть это только один раз?  ( Srand why call it only once ) 
Этот вопрос о комментарии в этом вопросе Рекомендуемый способ инициализации Srand? Первый комментарий говорит, что <код> srand() следует вызывать только од...

-1  Могу ли я использовать бесплатно () формально в VS2013?  ( Can i use free formally in vs2013 ) 
<код> #define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> #include <string.h> #define TSIZE 45 struct film{ char title[TSIZE]; int ...

0  Подсчет и сортировка в C  ( Counting and sorting in c ) 
Я заряжаюсь с обычной программой C, которая подсчитывает ряд входов и соответственно классифицирует их. У меня на самом деле нет ни одного кода, написанного д...

1  Проблемы с проверкой программы. Пожалуйста помоги!  ( Issues with program validation please help ) 
// Ребята у меня есть проблемы с моим кодом и разрывая мои волосы, пытаясь решить это. Вопрос в том, что я пытаюсь подтвердить свой код, поэтому он не рассчит...

0  Где хранятся переменные указателя и как компилятор доступа к нормальной переменной? [закрыто]  ( Where the pointer variables are stored and how compiler access normal variable ) 
<в сторону CLASS = "S-NEWACTS S-WELTIVE__info JS-Post-New Imide MB16« Роль = «Статус»> закрыт. Этот вопрос не соответствует Рекомендациям переполнения ...

7  Как портировать родной C-код на Android  ( How to port native c code on android ) 
Кто-нибудь может сказать мне, как портировать нативную программу C на платформе Android ..умел ли я включить некоторые библиотеки C или как именно ...? Спас...

Связанный проблема

0  Ошибка сборки Android NDK 
0  Fead вызывает ошибку сегментации 
0  Реализация ARP Smooth 
0  Если безымянный семафор инициализируется в общей памяти, Shm_unlink () уничтожает семафор? 
1  Lnk2001: неразрешенный внешний символ _maincrtstartup 
0  Структура в C- Чтобы добавить атрибут во время выполнения? 
0  Как остановить программу хранения более одного символа в переменную CHAR? [Дубликат] 
0  Как я могу хранить разные виды операторов в 2D-массиве в C? 
2  Состояние не удалось для ldrloaddll 
78  Srand () - зачем называть это только один раз? 
-1  Могу ли я использовать бесплатно () формально в VS2013? 
0  Подсчет и сортировка в C 
1  Проблемы с проверкой программы. Пожалуйста помоги! 
0  Где хранятся переменные указателя и как компилятор доступа к нормальной переменной? [закрыто] 
7  Как портировать родной C-код на Android 



© 2021 www.qaru.top All Rights Reserved. Q&A House все права защищены


Licensed under cc by-sa 3.0 with attribution required.