Continuarea ( continuare în engleză ) este o reprezentare abstractă a stării programului la un anumit moment, care poate fi salvată și utilizată pentru a trece la această stare. Continuările conțin toate informațiile pentru a continua execuția programului de la un anumit punct; starea variabilelor globale nu este de obicei păstrată, dar acest lucru nu este esențial pentru limbajele funcționale (de exemplu, salvarea selectivă și restabilirea valorilor obiectelor globale în Scheme este realizată printr-un mecanism separat dinamic-vânt). Continuările sunt similare cu BASIC sau macrocomenzile din C , deoarece vă permit, de asemenea, să săriți în orice loc din program. Dar continuările, spre deosebire de , vă permit să mergeți doar la o secțiune a programului cu o anumită stare care trebuie salvată în prealabil, în timp ce vă permite să mergeți la o secțiune a programului cu variabile neinițializate . goto setjmplongjmpgotogoto
Prima limbă care a implementat conceptul de continuare a fost Scheme , iar mai târziu a apărut suportul încorporat pentru continuări într-o serie de alte limbi.
Formal, callcc aceasta este o funcție de ordin superior care vă permite să abstrageți contextul dinamic al unei funcții existente sub forma unei alte funcții, care se numește „continuare”.
Mai succint, o continuare este „restul programului dintr-un punct dat” sau „o funcție care nu se întoarce niciodată la punctul în care a fost numit” [1] . În cursurile de programare funcțională, explicația conceptului de continuare se reduce adesea la „extinderea (complicarea) conceptului de corutine ”, dar în sens didactic, o astfel de explicație este considerată inutilă [1] . Motivul dificultății de a explica conceptul constă în faptul că continuările sunt de fapt o justificare alternativă pentru conceptul de „comportament” („chemare” în sensul cel mai larg), adică poartă un model semantic diferit, iar în acest sens În sens, tranziția inițială de la programarea funcțională „obișnuită” la programarea cu utilizare intensă a continuărilor poate fi comparată cu trecerea inițială de la programarea imperativă la programarea funcțională .
Continuările oferă fundamentul matematic pentru întreaga ordine de execuție a programului , de la buclegoto la recursivitate , excepții , generatoare , corutine și mecanismul de întoarcere [1] . În consecință, ele permit implementarea tuturor acestor elemente în limbaj printr-un singur construct.
Continuation -passing style Programming (CPS ) este un stil de programare în care controlul este transferat prin mecanismul de continuare . Stilul CPS a fost introdus pentru prima dată de Gerald Jay Sussman și Guy Steele, Jr. , în același timp cu limbajul Scheme .
Un program „în stil clasic” poate fi adesea rescris în stilul de trecere continua. De exemplu, pentru problema calculării ipotenuzei unui triunghi dreptunghic cu cod Haskell „clasic” :
pow2 :: Float -> Float pow2 a = a ** 2 adauga :: Float -> Float -> Float adauga a b = a + b pyth :: Float -> Float -> Float pyth a b = sqrt ( adaugă ( pow2 a ) ( pow2 b ))puteți adăuga un argument de tip F, unde Fînseamnă o funcție de la valoarea returnată a funcției inițiale la un tip arbitrar xși faceți din acest tip arbitrar valoarea returnată x:
pow2' :: Float -> ( Float -> a ) -> a pow2' a cont = cont ( a ** 2 ) add' :: Float -> Float -> ( Float -> a ) -> a add' a b cont = cont ( a + b ) -- tipurile a -> (b -> c) și a -> b -> c sunt echivalente, deci funcția CPS poate -- fi considerată o funcție de ordin superior a unui singur argument sqrt' :: Float -> ( ( Float -> a ) -> a ) sqrt' a = \ cont -> cont ( sqrt a ) pyth' :: Float -> Float -> ( Float -> a ) -> a pyth' a b cont = pow2' a ( \ a2 -> pow2' b ( \ b2 -> add' a2 b2 ( \ anb -> sqrt' anb cont )))Pătratul pyth'lui este calculat în funcție, iar funcția ( expresie lambdaa ) este transmisă ca o continuare , luând pătratul ca singur argument. În plus, toate valorile intermediare ulterioare sunt calculate în același mod. Pentru a efectua calcule ca o continuare, este necesar să treceți o funcție cu un argument, de exemplu, o funcție care returnează orice valoare transmisă acesteia. Astfel expresia este echivalentă cu . aidpyth' 3 4 id5.0
Biblioteca standard haskell din modulul Control.Monad.Cont conține un tip Contcare vă permite să utilizați funcții CPS într-o monada. Funcția pyth'va arăta astfel:
pow2_m :: Float -> Cont a Float pow2_m a = return ( a ** 2 ) -- funcția cont ridică funcțiile CPS normale la pyth_m monad :: Float -> Float -> Cont a Float pyth_m a b = do a2 <- pow2_m a b2 <- pow2_m b anb <- cont ( add' a2 b2 ) r <- cont ( sqrt' anb ) return rAcest modul conține și o funcție callCCde tip MonadCont m => ((a -> m b) -> m a) -> m a. Se poate observa din tipul că ia o funcție ca singur argument, care, la rândul său, are și o funcție ca singur argument, întrerupând calculele ulterioare. De exemplu, putem anula calculele suplimentare dacă cel puțin unul dintre argumente este negativ:
pyth_m :: Float -> Float -> Cont a Float pyth_m a b = callCC $ \ exitF -> do when ( b < 0 || a < 0 ) ( exitF 0.0 ) -- when :: Aplicative f => Bool -> f () -> f () a2 <- pow2_m a b2 <- pow2_m b anb <- cont ( add' a2 b2 ) r <- cont ( sqrt' anb ) return rExemple de CPS în schemă:
| stil direct | Continuare stil de trecere |
|---|---|
| ( definește ( pyth x y ) ( sqrt ( + ( * x x ) ( * y y )))) | ( definește ( pyth& x y k ) ( *& x x ( lambda ( x2 ) ( *& y y ( lambda ( y2 ) ( +& x2 y2 ( lambda ( x2py2 ) ( sqrt& x2py2 k )))))))) |
| ( definește ( factorial n ) ( dacă ( = n 0 ) 1 ; NU recursiv la coadă ( * n ( factorial ( - n 1 ))))) | ( definește ( factorial& n k ) ( =& n 0 ( lambda ( b ) ) ( dacă b ; continuă să crească ( k 1 ) ; în apel recursiv ( -& n 1 ( lambda ( nm1 ) ( factorial& nm1 ( lambda ( f ) )) ( *& n f k ))))))))) |
| ( define ( factorial n ) ( f-aux n 1 )) ( define ( f-aux n a ) ( if ( = n 0 ) a ; tail-recursive ( f-aux ( - n 1 ) ( * n a )) )) | ( define ( factorial& n k ) ( f-aux& n 1 k )) ( define ( f-aux& n a k ) ( =& n 0 ( lambda ( b ) ) ( dacă b ; continuarea păstrată ( k a ) ; în apel recursiv ( -& n 1 ( lambda ( nm1 ) ( *& n a ( lambda ( nta ) ( f-aux& nm1 nta k ))))))))) |
Într-un CPS „pur”, de fapt, nu există continuări în sine - fiecare apel se dovedește a fi un apel de coadă . Dacă limbajul nu garantează optimizarea apelului final ( TCO ), atunci cu fiecare apel imbricat , atât continuarea în sine, cât și stiva de apeluri cresc . Acest lucru nu este de obicei de dorit, dar uneori este folosit într-un mod interesant (de exemplu, în compilatorul Chicken Scheme ). Utilizarea combinată a strategiilor de optimizare TCO și CPS vă permite să eliminați complet stiva dinamică din programul executabil. O serie de compilatoare de limbaje funcționale funcționează astfel, cum ar fi compilatorul SML/NJ pentru Standard ML . callcc
Există mai multe tipuri de extensii. Cele mai comune dintre acestea sunt continuările nelimitate , implementate folosind o funcție sau analogii acesteia. Astfel de continuare reprezintă într-adevăr starea întregului program (sau a unuia dintre firele sale) la un moment dat. Apelarea unei astfel de continuare nu este ca apelarea unei funcții, deoarece corespunde „săririi” în starea salvată a programului și nu returnează nicio valoare; o astfel de continuare de obicei nu poate fi numită de mai multe ori. Continuările delimitate abstractizează dependența rezultatului unui bloc de program de rezultatul unei subexpresii a acestui bloc. Într-un anumit sens, ele corespund unui anumit segment al stivei de apeluri, și nu întregului stivă. Astfel de continuări pot fi folosite ca funcții, numite de mai multe ori și așa mai departe. Ele sunt abstractizate folosind mecanismul : înfășoară blocul exterior, acționează ca , dar primește ca argument nu o continuare globală, ci una limitată - dependența valorii blocului de resetare de valoarea în locul blocului de schimbare. Există și alte soiuri, de exemplu . call/ccshift/resetresetshiftcall/ccprompt/control
Multe limbaje de programare oferă această capacitate sub diferite nume, cum ar fi:
În orice limbă care acceptă închideri , puteți scrie programe în stilul continuării trecerii și puteți implementa manual call/cc. În special, aceasta este o practică acceptată în Haskell , unde „monadele care trec continuări” sunt ușor de construit (de exemplu, monada bibliotecii Contși transformatorul de monade ). ContTmtl