A folytatás ( angolul continuation ) a program egy adott pillanatban fennálló állapotának absztrakt ábrázolása , amely elmentve ebbe az állapotba való átmenetre használható. A folytatások tartalmazzák az összes információt a program végrehajtásának egy bizonyos ponttól való folytatásához; a globális változók állapota általában nem őrződik meg, de ez nem nélkülözhetetlen a funkcionális nyelveknél (például a globális objektumok értékeinek szelektív mentése és visszaállítása a Scheme -ben egy különálló dinamikus szél mechanizmussal történik). A folytatások hasonlóak a goto BASICsetjmp -hez vagy a makrókhoz Clongjmp -ben , mivel ezek lehetővé teszik a program bármely helyére történő ugrást is. De a folytatások, ellentétben a -val, lehetővé teszik, hogy a programnak csak egy bizonyos állapotú szakaszára lépjen, amelyet előre el kell menteni, míg lehetővé teszi a program egy olyan szakaszát, amely nem inicializált változókat tartalmaz . gotogoto
Az első nyelv, amely a folytatások koncepcióját implementálta, a Scheme volt , később pedig számos más nyelven is megjelent a folytatások beépített támogatása.
Formálisan callcc ez egy magasabb rendű függvény , amely lehetővé teszi egy meglévő függvény dinamikus kontextusának elvonatkoztatását egy másik függvény formájában, amelyet „folytatásnak” neveznek.
Tömörebben fogalmazva, a folytatás a "program többi része egy adott ponttól", vagy "egy függvény, amely soha nem tér vissza arra a pontra, amelynek hívták" [1] . A funkcionális programozási kurzusokon a folytatás fogalmának magyarázata gyakran a " korutína fogalmának kiterjesztésére (bonyolítására) " vezet le, de didaktikai értelemben az ilyen magyarázatot haszontalannak tekintik [1] . A fogalommagyarázat nehézségének oka abban rejlik, hogy a folytatások valójában a „behavior” (tágabb értelemben vett „hívás”) fogalmának alternatív igazolását jelentik, vagyis más szemantikai modellt hordoznak, és ebben Értelemszerűen a kezdeti átmenet a „hétköznapi” funkcionális programozásról a programozásra a folytatások erős használatával összehasonlítható az imperatív programozásról a funkcionális programozásra való kezdeti átmenettel .
A folytatások matematikai alapot adnak a programvégrehajtás teljes sorrendjéhez , a ciklusoktólgoto a rekurzióig , a kivételekig , a generátorokig , a korutinokig és a visszatérési mechanizmusig [1] . Következésképpen lehetővé teszik mindezen elemek implementálását a nyelvben egyetlen konstrukción keresztül.
A Continuation -passing style programozás (CPS ) egy olyan programozási stílus , amelyben a vezérlés a folytatási mechanizmuson keresztül történik . A CPS stílust először Gerald Jay Sussman és Guy Steele, Jr. vezette be, a Scheme nyelvvel egy időben .
Egy "klasszikus stílusú" program gyakran átírható folytatásos stílusban. Például egy derékszögű háromszög befogójának kiszámításához "klasszikus" Haskell -kóddal :
pow2 :: Float -> Float pow2 a = a ** 2 add :: Float -> Float -> Float add a b = a + b pyth :: Float -> Float -> Float pyth a b = sqrt ( add ( pow2 a ) ( pow2 b ))hozzáadhat egy típusú argumentumot F, ahol Faz eredeti függvény visszatérési értékéből származó függvényt jelent egy tetszőleges típushoz x, és ezt a tetszőleges típust állíthatja vissza visszatérési értékké 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 ) -- az a -> (b -> c) és a -> b -> c típusok egyenértékűek, így a CPS függvény -- egyetlen argumentum magasabb rendű függvényének tekinthető 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 )))A pyth'négyzet kiszámítása a függvényben történik, és a függvény ( lambda kifejezésa ) folytatásként kerül átadásra, a négyzetet véve egyetlen argumentumnak. Ezenkívül az összes későbbi közbenső értéket ugyanúgy számítják ki. A számítások folytatásaként való végrehajtásához át kell adni egy argumentum függvényét, például egy olyan függvényt , amely visszaadja a neki átadott bármely értéket. Így a kifejezés ekvivalens a . aidpyth' 3 4 id5.0
A Control.Monad.Cont modul szabványos haskell könyvtára tartalmaz egy típust Cont, amely lehetővé teszi a CPS függvények monádban való használatát. A függvény pyth'így fog kinézni:
pow2_m :: Float -> Cont a Float pow2_m a = return ( a ** 2 ) -- a cont függvény a normál CPS függvényeket pyth_m monadra emeli :: 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 rEz a modul egy callCCtípusú függvényt is tartalmaz MonadCont m => ((a -> m b) -> m a) -> m a. A típusból látható, hogy egyetlen argumentumként egy függvényt vesz fel, aminek viszont egy függvény is az egyetlen argumentuma, ami megszakítja a további számításokat. Például megszakíthatjuk a további számításokat, ha legalább az egyik argumentum negatív:
pyth_m :: Float -> Float -> Cont a Float pyth_m a b = callCC $ \ exitF -> do when ( b < 0 || a < 0 ) ( exitF 0.0 ) -- when :: Applikatív f => Bool -> f () -> f () a2 <- pow2_m a b2 <- pow2_m b anb <- cont ( add' a2 b2 ) r <- cont ( sqrt' anb ) return rPéldák a CPS-re a sémában:
| közvetlen stílus | Passzírozási stílus folytatása |
|---|---|
| ( define ( pyth x y ) ( sqrt ( + ( * x x ) ( * y y )))) | ( define ( pyth& x y k ) ( *& x x ( lambda ( x2 ) ( *& y y ( lambda ( y2 ) ) ( +& x2 y2 ( lambda ( x2py2 ) ( sqrt& x2py2 k )))))))))) |
| ( define ( faktoriális n ) ( if ( = n 0 ) 1 ; NEM farokrekurzív ( * n ( faktoriális ( - n 1 ))))) | ( define ( faktoriális& n k ) ( =& n 0 ( lambda ( b ) ( ha b ; tovább növekszik ( k 1 ) ; rekurzív hívásban ( -& n 1 ( lambda ( nm1 ) ) ( faktoriális& nm1 ) ( lambda ( f ) ) ) *& n f k ))))))))) |
| ( define ( faktoriális n ) ( f-aux n 1 )) ( define ( f-aux n a ) ( if ( = n 0 ) a ; farok-rekurzív ( f-aux ( - n 1 ) ( * n a )) )) | ( define ( faktoriális& n k ) ( f-aux& n 1 k )) ( define ( f-aux& n a k ) ( =& n 0 ( lambda ( b ) ( ha b ; a folytatás megmarad ( k a ) ; rekurzív hívásban ) ( -& n 1 ( lambda ( nm1 ) ( *& n a ( lambda ( nta ) ( f-aux& nm1 nta k ) ))))))))) |
Egy „tiszta” CPS-ben valójában nincsenek maguknak folytatások – minden hívás farokhívásnak bizonyul . Ha a nyelv nem garantálja a farokhívás -optimalizálást ( TCO ), akkor minden beágyazott hívásnál maga a folytatás és a hívásverem is növekszik . Ez általában nem kívánatos, de néha érdekes módon használják (például a Chicken Scheme fordítójában ). A TCO és a CPS optimalizálási stratégiák együttes használata lehetővé teszi a dinamikus verem teljes eltávolítását a végrehajtható programból. Számos funkcionális nyelvi fordító működik így, például a Standard ML SML/NJ fordítója . callcc
A bővítményeknek többféle típusa van. Ezek közül a leggyakoribbak a korlátlan folytatások , amelyeket egy függvény vagy annak analógjai segítségével valósítanak meg. Az ilyen folytatások valóban az egész program (vagy annak egyik szálának) adott pillanatban fennálló állapotát reprezentálják. Egy ilyen folytatás hívása nem olyan, mint egy függvény meghívása, mivel ez a program mentett állapotába való "ugrásnak" felel meg, és nem ad vissza semmilyen értéket; egy ilyen folytatás általában nem hívható többször. A behatárolt folytatások elvonatkoztatják valamely programmondat eredményének e mondat valamely részkifejezésének eredményétől való függését . Bizonyos értelemben a hívásverem valamely szegmensének felelnek meg, nem pedig a teljes veremnek. Az ilyen folytatások függvényként használhatók, többször hívhatók stb. A mechanizmus segítségével absztrahálják őket : beburkolja a külső blokkot, úgy viselkedik, mint , de argumentumként nem egy globális folytatást, hanem egy korlátozottat kap - a reset blokk értékének függőségét a shift blokk helyén lévő értéktől. Vannak más fajták is, pl . call/ccshift/resetresetshiftcall/ccprompt/control
Számos programozási nyelv biztosítja ezt a lehetőséget különböző neveken, például:
Bármilyen nyelven, amely támogatja a lezárásokat , írhat folytatásos stílusú programokat, és manuálisan implementálhatja a call/cc. Ez különösen elfogadott gyakorlat a Haskell -ben, ahol könnyen megépíthetők "folytatásokon áthaladó monádok" (például a könyvtár monádja Contés monádtranszformátora ). ContTmtl