Cum să implementați continuările?

Îmi amintesc că am citit un articol care ți-ar putea ajuta: Cheney on the MTA a> :-)

Unele implementări ale Schemei I cunosc, cum ar fi SISC , alocarea cadrelor lor de apel pe heap.

@ollie: Nu aveți nevoie să faceți ridicarea dacă toate cadrele de apel sunt pe halda. Există un compromis în performanță, desigur: timpul de ridicare, comparativ cu costurile suplimentare necesare pentru alocarea tuturor cadrelor pe heap. Poate ar trebui să fie un parametru de execuție tunabil în interpret. :-P

Utilizați în schimb un teanc explicit.

Patrick este corect, singurul mod în care poți să faci asta este să folosești un teanc explicit în interpretul tău și să ridici segmentul corespunzător de stivă în heap când trebuie să te transformi într-o continuare.

Acest lucru este în esență același cu ceea ce este necesar pentru a sprijini închiderea limbilor care le susțin (închiderile și continuările fiind oarecum legate).

Continuile constau în principal din starea salvată a registrelor stack și CPU în punctul comutatoarelor de context. Cel puțin nu trebuie să copiați întreaga teanc la morman atunci când comutați, ați putea redirecționa doar pointerul de stivă.

Continuările sunt implementate trivial folosind fibre. http://en.wikipedia.org/wiki/Fiber_%28computer_science%29 . Singurele lucruri care necesită o încapsulare atentă sunt valorile de trecere a parametrilor și de întoarcere.

În Windows, fibrele se fac folosind familia de apeluri CreateFiber / SwitchToFiber. în sistemele compatibile cu Posix se poate face cu makecontext / swapcontext.

boost :: coroutine are o implementare de lucru a corutinelor pentru C ++ care pot servi drept punct de referinta pentru implementare.

Continuarea nu este problema: puteți implementa acelea cu funcții regulate de ordin superior, utilizând CPS. Problema cu alocarea naivă a coșurilor este că apelurile de coadă nu sunt niciodată optimizate, ceea ce înseamnă că nu puteți fi schematică.

Cea mai bună abordare curentă a stivei de spaghete a schemelor de cartografiere pe stivă utilizează trambuline: în esență, infrastructură suplimentară pentru a gestiona apelurile și ieșirile de la proceduri care nu sunt de tip C. Consultați Stilul trampolizat (ps) .

Există un cod care ilustrează ambele idei.

Se pare că teza lui Dybvig nu este menționată până acum. Este o plăcere să citiți. Modelul bazat pe heap este cel mai ușor de implementat, dar bazat pe stiva este mai eficientă. Ignorați modelul bazat pe șir.

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. http://library.readscheme.org/page8.html

Rezumatul este după cum urmează:

Această teză prezintă trei modele de implementare a schemei   Limbaj de programare. Primul este un model bazat pe heap utilizat în unele   în majoritatea implementărilor Schemei până în prezent; al doilea este unul nou   model pe bază de stive care este mult mai ecient decât modelul   heap-based model la executarea majorității programelor; iar al treilea este nou   pe bază de șir, destinat utilizării într-un procesor multiplu   implementarea schemei.

     

Modelul bazat pe heap alocă câteva structuri de date importante într-un   heap, inclusiv liste de parametri reali, medii obligatorii și apeluri   cadre.

     

Modelul bazat pe stiva alocă aceleași structuri pe o stivă   ori de câte ori este posibil. Acest lucru duce la o alocare mai mică a heapului, mai puțină memorie   referințe, secvențe de instrucțiuni mai scurte, mai puțin colectare de gunoi,   și utilizarea mai etică a memoriei.

     

Modelul bazat pe șir alocă versiuni ale acestor structuri chiar în   textul programului, care este reprezentat ca un șir de simboluri. În   string-based model, programele de programe sunt traduse într-un FFP   limba special concepută pentru a sprijini schema. Programe în acest sens   limbajul este executat direct de către mașina FFP, a   computer multi-procesor de reducere a șirului.

     

Modelul bazat pe stiva este de bun simt imediat; este   model utilizat de sistemul autorului Chez Scheme, o performanță de înaltă performanță   implementarea schemei. Modelul bazat pe șir va fi util pentru   oferind Schema ca o alternativă la nivel înalt la FFP pe mașina FFP   odată ce mașina este realizată.

Dacă începi de la zero, ar trebui să te uiți la transformarea Stilului de Trecere Continuă (CPS).

Sursele bune includ "LISP în bucăți mici" și .

As soegaard pointed out, the main reference remains this one

Ideea este că o continuare este o închidere care își păstrează stackul de control al evaluării. Setul de control este necesar pentru a continua evaluarea din momentul în care a fost creată continuarea folosind call / cc .

Deseori invocarea continuării face mult timp de execuție și umple memoria cu stive duplicate. Am scris acest cod stupid pentru a dovedi că, în mit-schema, face ca sistemul să se prăbușească,

Codul însumează primele 1000 de numere 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) __)))))))))

Dacă treceți 1000 la 100 000 codul va cheltui 2 secunde, iar dacă crește numărul de intrare se va prăbuși.

Modul tradițional este de a utiliza setjmp și longjmp , deși există limitări.

Here's a reasonably good explanation

Un rezumat bun este disponibil în Strategii de implementare a continuărilor de primă clasă , un articol de Clinger, Hartheimer și Ost. Vă recomandăm să vă uitați în special la implementarea programului Chez Scheme.

Copierea stivei nu este atât de complexă și există un număr de tehnici bine înțelese pentru îmbunătățirea performanței. Utilizarea cadrelor alocate în heap este, de asemenea, destul de simplă, dar faceți un compromis de a crea cheltuieli generale pentru situația "normală" în care nu utilizați continuări explicite.

Dacă convertiți codul de intrare la stilul de trecere continuă (CPS), atunci puteți să scăpați cu eliminarea totală a stivei. Cu toate acestea, în timp ce CPS este elegant, acesta adaugă un alt pas de prelucrare în partea din față și necesită o optimizare suplimentară pentru a depăși anumite implicații privind performanța.

Exemple pe care le puteți viziona sunt: ​​ Pui (o implementare a Schemei, scrisă în C, care continuare); Paul Graham Pe Lisp - unde creează un transformator CPS pentru a implementa un subset de continuări în Common Lisp; și Weblocks - un cadru web bazat pe o continuare, care implementează, de asemenea, o formă limitată de continuări în Common Lisp.

Pe lângă răspunsurile plăcute pe care le-ați obținut până acum, vă recomandăm Compilarea cu continuări de Andrew Appel . Este foarte bine scris și în timp ce nu se ocupă direct cu C, este o sursă de idei foarte frumos pentru scriitorii de compilatoare.

Chicken Wiki are, de asemenea, pagini pe care le veți găsi foarte interesante, cum ar fi structură internă și procesul de compilare (unde CPS este explicat cu un exemplu real de compilare ).