Continuation ( engelsk fortsættelse ) er en abstrakt repræsentation af programmets tilstand på et bestemt tidspunkt, som kan gemmes og bruges til at skifte til denne tilstand. Fortsættelser indeholder al information til at fortsætte med at køre programmet fra et bestemt tidspunkt; tilstanden af globale variabler er normalt ikke bevaret, men dette er ikke afgørende for funktionelle sprog (for eksempel opnås selektiv lagring og gendannelse af værdierne af globale objekter i Scheme ved hjælp af en separat dynamisk vindmekanisme). Fortsættelser ligner goto BASICsetjmp eller makroer longjmpi C , da de også giver dig mulighed for at hoppe til et hvilket som helst sted i programmet. Men fortsættelser, i modsætning til goto, giver dig mulighed for kun at gå til en sektion af programmet med en bestemt tilstand, der skal gemmes på forhånd, mens den gotogiver dig mulighed for at gå til en sektion af programmet med ikke-initialiserede variabler .
Det første sprog til at implementere begrebet fortsættelser var Scheme , og senere dukkede indbygget understøttelse af fortsættelser op på en række andre sprog.
Formelt er callcc dette en højere-ordens funktion , der giver dig mulighed for at abstrahere den dynamiske kontekst af en eksisterende funktion i form af en anden funktion, som kaldes "fortsættelse".
Mere kortfattet er en fortsættelse "resten af programmet fra et givet punkt," eller "en funktion, der aldrig vender tilbage til det punkt, den blev kaldt" [1] . I funktionelle programmeringskurser kommer forklaringen af begrebet fortsættelse ofte ned på at "udvide (komplicere) begrebet en coroutine ", men i didaktisk forstand anses en sådan forklaring for ubrugelig [1] . Årsagen til vanskeligheden ved at forklare begrebet ligger i, at fortsættelser faktisk er en alternativ begrundelse for begrebet "adfærd" ("kald" i bredeste forstand), det vil sige, at de bærer en anden semantisk model, og i denne Forstand kan den indledende overgang fra "almindelig" funktionel programmering til programmering med stor brug af fortsættelser sammenlignes med den indledende overgang fra imperativ til funktionel programmering .
Fortsættelser udgør det matematiske grundlag for hele rækkefølgen af programafvikling , fra loopsgoto til rekursion , undtagelser , generatorer , coroutiner og returmekanismen [1] . Som en konsekvens tillader de implementeringen af alle disse elementer i sproget gennem en enkelt konstruktion.
Continuation -passing style programmering (CPS ) er en programmeringsstil , hvor kontrol overføres gennem fortsættelsesmekanismen . CPS-stilen blev først introduceret af Gerald Jay Sussman og Guy Steele, Jr. , på samme tid som Scheme-sproget .
Et "klassisk stil"-program kan ofte omskrives i fortsættelsesstil. For eksempel til problemet med at beregne hypotenusen af en retvinklet trekant med "klassisk" Haskell -kode :
pow2 :: Float -> Float pow2 a = a ** 2 add :: Float -> Float -> Float tilføj a b = a + b pyth :: Float -> Float -> Float pyth a b = sqrt ( add ( pow2 a ) ( pow2 b ))du kan tilføje et type argument F, hvor Fbetyder en funktion fra den oprindelige funktions returværdi til en vilkårlig type x, og gøre denne vilkårlige type til returværdien 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 ) -- typerne a -> (b -> c) og a -> b -> c er ækvivalente, så CPS-funktionen kan -- betragtes som en højere ordens funktion af et enkelt 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 forts )))Kvadratet pyth'af beregnes i funktionen, og funktionen ( lambda-udtryka ) sendes som en fortsættelse , idet kvadratet tages som det eneste argument. Yderligere beregnes alle efterfølgende mellemværdier på samme måde. For at udføre beregninger som en fortsættelse er det nødvendigt at videregive en funktion af et argument, for eksempel en funktion , der returnerer enhver værdi, der er sendt til det. Udtrykket svarer således til . aidpyth' 3 4 id5.0
Standard haskell-biblioteket i Control.Monad.Cont- modulet indeholder en type Cont, der giver dig mulighed for at bruge CPS-funktioner i en monade. Funktionen pyth'vil se sådan ud:
pow2_m :: Float -> Cont a Float pow2_m a = return ( a ** 2 ) -- cont-funktion hæver normale CPS-funktioner til 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 <- forts ( sqrt' anb ) returner rDette modul indeholder også en funktion callCCaf type MonadCont m => ((a -> m b) -> m a) -> m a. Det kan ses af typen, at den tager en funktion som sit eneste argument, som igen også har en funktion som sit eneste argument, hvilket afbryder yderligere beregninger. For eksempel kan vi afbryde yderligere beregninger, hvis mindst et af argumenterne er negativt:
pyth_m :: Float -> Float -> Cont a Float pyth_m a b = callCC $ \ exitF -> do when ( b < 0 || a < 0 ) ( exitF 0.0 ) -- when :: Applikativ f => Bool -> f () -> f () a2 <- pow2_m a b2 <- pow2_m b anb <- cont ( add' a2 b2 ) r <- cont ( sqrt' anb ) return rEksempler på CPS i ordningen:
| direkte stil | Fortsættelse passerer stil |
|---|---|
| ( definer ( pyth x y ) ( sqrt ( + ( * x x ) ( * y y )))) | ( definer ( pyth& x y k ) ( *& x x ( lambda ( x2 ) ( *& y y ( lambda ( y2 ) ( +& x2 y2 ( lambda ( x2py2 )) ( sqrt& x2py2 k )))))))) |
| ( definer ( faktoriel n ) ( hvis ( = n 0 ) 1 ; IKKE hale-rekursiv ( * n ( faktoriel ( - n 1 ))))) | ( definer ( factorial& n k ) ( =& n 0 ( lambda ( b ) ( hvis b ; fortsætter med at vokse ( k 1 ) ; i rekursivt kald ( -& 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 ; hale-rekursiv ( 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 ) ( hvis b ; fortsættelse bevaret ( ka ) ; i rekursivt kald ( -& n 1 ( lambda ( nm1 ) ( *& n a ( lambda ( nta ) ( f-aux& nm1 nta k )))))))))) |
I en "ren" CPS er der faktisk ingen fortsættelser i sig selv - hvert opkald viser sig at være et haleopkald . Hvis sproget ikke garanterer tail call optimization ( TCO ) , vokser både selve fortsættelsen og opkaldsstakken med hvert indlejret kald . Dette er normalt ikke ønskeligt, men bruges nogle gange på en interessant måde (for eksempel i Chicken Scheme compiler ). Den kombinerede brug af TCO- og CPS-optimeringsstrategier giver dig mulighed for helt at eliminere den dynamiske stak fra det eksekverbare program. En række funktionelle sprogcompilatorer fungerer på denne måde, såsom SML/NJ-kompileren til Standard ML . callcc
Der er flere typer udvidelser. De mest almindelige af disse er ubegrænsede fortsættelser , implementeret ved hjælp af en funktion eller dens analoger. Sådanne fortsættelser repræsenterer virkelig tilstanden af hele programmet (eller en af dets tråde) på et bestemt tidspunkt. At kalde en sådan fortsættelse er ikke som at kalde en funktion, da det svarer til at "hoppe" ind i programmets gemte tilstand og ikke returnerer nogen værdi; en sådan fortsættelse kan normalt ikke kaldes flere gange. Afgrænsede fortsættelser abstraherer afhængigheden af resultatet af en programblok af resultatet af et underudtryk af denne blok. I en vis forstand svarer de til et eller andet segment af opkaldsstakken og ikke til hele stakken. Sådanne fortsættelser kan bruges som funktioner, kaldes flere gange, og så videre. De abstraheres ved hjælp af mekanismen : den omslutter den ydre blok, fungerer som , men modtager som argument ikke en global fortsættelse, men en begrænset - afhængigheden af værdien af nulstillingsblokken af værdien i stedet for shift-blokken. Der er andre varianter, f.eks . call/ccshift/resetresetshiftcall/ccprompt/control
Mange programmeringssprog giver denne mulighed under forskellige navne, såsom:
På ethvert sprog, der understøtter lukninger , kan du skrive programmer i fortsættelsesstil og manuelt implementere call/cc. Dette er især en accepteret praksis i Haskell , hvor "monader der passerer fortsættelser" let bygges (f.eks. bibliotekets monade Contog monadetransformator ). ContTmtl