Come implementare le continuazioni?

Question

Sto lavorando su un programma interprete scritto in C.Attualmente si utilizza il runtime C stack come il proprio stack, che presenta un piccolo problema con l'implementazione di continuazioni.La mia soluzione attuale è la copia manuale di C stack heap quindi la copia di nuovo quando necessario.Oltre a non essere di serie C, questa soluzione è certo l'ideale.

Che cosa è il modo più semplice per implementare le continuazioni di programma in C?

Answer 1

Mi ricordo di aver letto un articolo che possa essere di aiuto a voi: Cheney sul M. T. A. :-)

Alcune implementazioni del Regime di cui sono a conoscenza, come SISC, allocano i loro chiamata fotogrammi sul mucchio.

@mah:Non hai bisogno di fare il sollevamento di se tutte le chiamate frame sono sul mucchio.C'è un compromesso in termini di prestazioni, ovviamente:il tempo di gru, contro l'overhead necessario per allocare tutti i frame di un heap.Forse dovrebbe essere un separatore di runtime parametro nell'interprete.:-P

Answer 2

Una buona sintesi è disponibile in Strategie di attuazione di Prima Classe Continuazioni, un articolo di Clinger, Hartheimer, e Ost.Mi consiglia di guardare Chez dello Schema di attuazione, in particolare.

Stack la copia non è complesso e ci sono un certo numero di ben capito tecniche per migliorare le prestazioni.Utilizzando allocazione heap fotogrammi è anche abbastanza semplice, ma si fanno un compromesso di creazione di overhead per la "normale" situazione in cui non si utilizza esplicito continuazioni.

Se la conversione di input del codice a seguito di passaggio di stile (CPS), allora si può ottenere via con eliminando la pila del tutto.Tuttavia, mentre CPS è elegante aggiunge un altro fase di lavorazione nel front-end e richiede ulteriore ottimizzazione per superare certe implicazioni in termini di prestazioni.

Answer 3

Se stai partendo da zero, si dovrebbe davvero guardare in Continuazione il Passaggio di Stile (CPS) di trasformazione.

Buone fonti sono "LISP in piccoli pezzi" e Marc Feeley Schema in 90 minuti di presentazione.

Answer 4

Sembra Dybvig tesi è menzionato finora.È un piacere leggere.Il mucchio di base del modello è il più semplice da implementare, ma la pila di base è più efficiente.Ignorare la stringa di base del modello.

R.Kent Dybvig."Tre Modelli di Implementazione per il Regime".http://www.cs.indiana.edu/~dyb/papers/3imp.pdf

Anche controllare l'attuazione carte su ReadScheme.org.http://library.readscheme.org/page8.html

L'abstract è come segue:

Questa tesi presenta tre modelli di attuazione del programma Linguaggio di programmazione.Il primo è un heap-based modello utilizzato in alcuni modulo nella maggior parte del Regime di implementazioni per data;il secondo è un nuovo stack-based model che è notevolmente più ecace di heap-based modello di esecuzione di più programmi;e il terzo è un nuovo stringa di un modello basato su inteso per l'uso in più di processore attuazione del programma.

Heap-based model alloca più importanti strutture di dati in un heap, tra cui gli elenchi di parametri vincolanti ambienti, e chiamata cornici.

Stack-based model alloca queste stesse strutture su una pila ogni volta che è possibile.Questo si traduce in meno di allocazione heap, meno memoria i riferimenti, più brevi sequenze di istruzioni, meno di garbage collection, e un utilizzo più efficace della memoria.

La stringa di un modello basato su alloca le versioni di queste strutture in il testo del programma, che è rappresentato come una stringa di simboli.Nel stringa di base del modello, Schema di programmi sono tradotte in un FFP lingua in modo specico Regime di sostegno.Programmi in questo lingua vengono eseguite direttamente dal FFP macchina, un con più processori stringa di riduzione del computer.

Lo stack di un modello basato su di pratiche immediate del benecio;è il il modello utilizzato dall'autore Chez Schema di sistema, ad alte prestazioni attuazione del programma.La stringa di base modello sarà utile per fornendo Schema di alto livello alternativa al FFP sul FFP macchina una volta che la macchina è realizzato.

Answer 5

Oltre alle belle risposte che hai avuto finora, mi raccomando Andrew Appel La compilazione con le Continuazioni.E ' scritto molto bene e, pur non trattando direttamente con il C, è una fonte di idee per il compilatore scrittori.

Il Pollo Wiki ha anche pagine che troverete molto interessante, come struttura interna e processo di compilazione (dove CPS è spiegato con un esempio reale di compilazione).

Answer 6

Esempi che si possono guardare sono: Pollo (un Regime di attuazione, scritto in C che supportano le continuazioni);Paul Graham In Lisp - dove si crea una CPS trasformatore per implementare un sottoinsieme di continuazioni in Common Lisp;e Weblocks - una continuazione base di framework per il web, che implementa anche una forma limitata di continuazioni in Common Lisp.

Answer 7

Continuazioni non sono il problema:è possibile implementare quelli con regolare le funzioni di ordine superiore tramite CPS.Il problema con ingenuo allocazione dello stack è che la coda di chiamate non sono mai ottimizzati, il che significa che non si può essere in regime di.

Il miglior approccio attuale schema di mappatura spaghetti stack su stack utilizza trampolini:essenzialmente extra infrastruttura per gestire non-C-come la chiama e le uscite dalle procedure.Vedere Trampolined Stile (ps).

C'è un po ' di codice illustrando entrambe queste idee.

Answer 8

Il modo tradizionale è quello di utilizzare setjmp e longjmp, anche se ci sono avvertimenti.

Ecco un ragionevolmente buona spiegazione

Answer 9

Continuazioni che consistono fondamentalmente lo stato salvato nello stack e i registri della CPU al punto di contesto.Almeno non devi copiare l'intero stack heap durante il passaggio, si poteva solo reindirizzare il puntatore dello stack.

Continuazioni sono banalmente implementato utilizzando fibre. http://en.wikipedia.org/wiki/Fiber_%28computer_science%29 .Le uniche cose che hanno bisogno di attenzione incapsulamento sono di passaggio di parametri e valori di ritorno.

In Windows fibre sono fatte utilizzando il CreateFiber/SwitchToFiber famiglia di chiamate.in Posix-compliant sistemi può essere fatto con makecontext/swapcontext.

boost::coroutine ha un lavoro attuazione di coroutines per C++ che può servire come un punto di riferimento per l'attuazione.

Answer 10

Utilizzare un esplicito stack, invece.

Answer 11

Patrick è corretto, l'unico modo si può veramente fare questo è quello di utilizzare un esplicito stack, l'interprete, e paranco appropriato del segmento di stack heap quando è necessario convertire una continuazione.

Questo è fondamentalmente lo stesso come ciò che è necessario per sostenere le chiusure nelle lingue che li supportano (chiusure e le continuazioni di essere in qualche modo collegato).

Answer 12

Come soegaard sottolineato, il punto di riferimento principale rimane questo

L'idea è che una continuazione è una chiusura che mantiene la sua valutazione controllo dello stack.Il controllo dello stack è necessario per continuare la valutazione dal momento in cui la continuazione è stata creata utilizzando call/cc.

Spesso invocando la continuazione ti tempo di esecuzione e riempie la memoria con ridondanza di pile.Ho scritto questo stupido codice per dimostrare che, in mit-schema rende il regime di crash,

Il codice di somme i primi 1000 numeri 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) __)))))))))

Se si passa da 1000 a 100 000 codice passare 2 secondi, e se si a crescere il numero di input andrà in crash.