Fortsättning ( engelsk fortsättning ) är en abstrakt representation av programmets tillstånd vid ett visst tillfälle, som kan sparas och användas för att övergå till detta tillstånd. Fortsättningar innehåller all information för att fortsätta körningen av programmet från en viss punkt; tillståndet för globala variabler bevaras vanligtvis inte, men detta är inte nödvändigt för funktionella språk (till exempel selektiv lagring och återställning av värdena för globala objekt i Schema uppnås med en separat dynamisk vindmekanism). Fortsättningar liknar goto BASICsetjmp eller makron longjmpi C , eftersom de också låter dig hoppa till valfri plats i programmet. Men fortsättningar, till skillnad från goto, låter dig bara gå till en del av programmet med ett visst tillstånd som måste sparas i förväg, medan det gotolåter dig gå till en del av programmet med oinitierade variabler .
Det första språket som implementerade konceptet fortsättningar var Scheme , och senare dök inbyggt stöd för fortsättningar upp på ett antal andra språk.
Formellt är callcc detta en högre ordningsfunktion som låter dig abstrahera det dynamiska sammanhanget för en befintlig funktion i form av en annan funktion, som kallas "fortsättning".
Mer kortfattat är en fortsättning "resten av programmet från en given punkt" eller "en funktion som aldrig återvänder till den punkt som den kallades" [1] . I kurser i funktionell programmering kommer förklaringen av begreppet fortsättning ofta ner på att "utvidga (komplicera) begreppet en koroutin ", men i didaktisk mening anses en sådan förklaring vara värdelös [1] . Anledningen till svårigheten att förklara begreppet ligger i det faktum att fortsättningar faktiskt är en alternativ motivering till begreppet ”beteende” (”samtal” i vid bemärkelse), det vill säga de bär på en annan semantisk modell, och i denna känsla kan den initiala övergången från "vanlig" funktionell programmering till programmering med stor användning av fortsättningar jämföras med den initiala övergången från imperativ till funktionell programmering .
Fortsättningar ger den matematiska grunden för hela ordningen för programexekvering , från loopargoto till rekursion , undantag , generatorer , koroutiner och returmekanismen [1] . Som en konsekvens tillåter de implementeringen av alla dessa element i språket genom en enda konstruktion.
Continuation -passing style programmering (CPS ) är en programmeringsstil där kontroll överförs via fortsättningsmekanismen . CPS-stilen introducerades först av Gerald Jay Sussman och Guy Steele, Jr. , samtidigt som Scheme-språket .
Ett "klassisk stil"-program kan ofta skrivas om i fortsättningspasseringsstil. Till exempel, för problemet med att beräkna hypotenusan för en rätvinklig triangel med "klassisk" Haskell -kod :
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 ))du kan lägga till ett typargument F, där Fbetyder en funktion från returvärdet för den ursprungliga funktionen till en godtycklig typ x, och göra denna godtyckliga typ till returvärdet 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 ) -- typerna a -> (b -> c) och a -> b -> c är ekvivalenta, så CPS-funktionen kan -- betraktas som en högre ordningsfunktion av ett enda 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 )))Kvadraten pyth'på beräknas i funktionen, och funktionen ( lambda uttrycka ) skickas som en fortsättning , med kvadraten som det enda argumentet. Vidare beräknas alla efterföljande mellanvärden på samma sätt. För att utföra beräkningar som en fortsättning är det nödvändigt att skicka en funktion av ett argument, till exempel en funktion som returnerar alla värden som skickas till det. Således är uttrycket ekvivalent med . aidpyth' 3 4 id5.0
Standard-haskell-biblioteket i Control.Monad.Cont- modulen innehåller en typ Contsom låter dig använda CPS-funktioner i en monad. Funktionen pyth'kommer att se ut så här:
pow2_m :: Float -> Cont a Float pow2_m a = retur ( a ** 2 ) -- cont-funktionen höjer normala CPS-funktioner till 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 ) return rDenna modul innehåller också en funktion callCCav typ MonadCont m => ((a -> m b) -> m a) -> m a. Det kan ses av typen att den tar en funktion som sitt enda argument, som i sin tur också har en funktion som sitt enda argument, vilket avbryter ytterligare beräkningar. Till exempel kan vi avbryta ytterligare beräkningar om minst ett av argumenten är negativt:
pyth_m :: Float -> Float -> Cont a Float pyth_m a b = callCC $ \ exitF -> gör när ( b < 0 || a < 0 ) ( exitF 0.0 ) -- när :: Applikativ f => Bool -> f () -> f () a2 <- pow2_m a b2 <- pow2_m b anb <- cont ( add' a2 b2 ) r <- cont ( sqrt' anb ) return rExempel på CPS i schema:
| direkt stil | Fortsättning passningsstil |
|---|---|
| ( definiera ( pyth x y ) ( sqrt ( + ( * x x ) ( * y y )))) | ( definiera ( pyth& x y k ) ( *& x x ( lambda ( x2 ) ( *& y y ( lambda ( y2 ) ( +& x2 y2 ( lambda ( x2py2 ) ( sqrt& x2py2 k )))))))) |
| ( definiera ( faktoriellt n ) ( om ( = n 0 ) 1 ; INTE svansrekursiv ( * n ( faktoriell ( - n 1 )))))) | ( definiera ( faktoriell& n k ) ( =& n 0 ( lambda ( b ) ( om b ; fortsätter att växa ( k 1 ) ; i rekursiv anrop ( -& n 1 ( lambda ( nm1 ) ( faktoriell & nm1 ( lambda ( f )) ) *& n f k ))))))))) |
| ( definiera ( faktoriellt n ) ( f-aux n 1 )) ( definiera ( f-aux n a ) ( if ( = n 0 ) a ; svansrekursiv ( f-aux ( - n 1 ) ( * n a )) )) | ( definiera ( faktoriell& n k ) ( f-aux& n 1 k )) ( definiera ( f -aux& n a k ) ( =& n 0 ( lambda ( b ) ( om b ; fortsättning bevarad ( ka ) ; i rekursivt anrop ( -& n 1 ( lambda ( nm1 ) ( *& n a ( lambda ( nta ) ( f-aux& nm1 nta k )))))))))) |
I en "ren" CPS finns det faktiskt inga fortsättningar i sig - varje samtal visar sig vara ett slutsamtal . Om språket inte garanterar optimering av slutanrop ( TCO ), växer både själva fortsättningen och anropsstacken med varje kapslat anrop . Detta är vanligtvis inte önskvärt, men används ibland på ett intressant sätt (till exempel i Chicken Scheme kompilatorn ). Den kombinerade användningen av TCO- och CPS-optimeringsstrategier gör att du helt kan eliminera den dynamiska stacken från det körbara programmet. Ett antal funktionella språkkompilatorer fungerar på detta sätt, till exempel SML/NJ-kompilatorn för Standard ML . callcc
Det finns flera typer av tillägg. De vanligaste av dessa är oavgränsade fortsättningar , implementerade med hjälp av en funktion eller dess analoger. Sådana fortsättningar representerar verkligen tillståndet för hela programmet (eller en av dess trådar) vid ett visst tillfälle. Att anropa en sådan fortsättning är inte som att anropa en funktion, eftersom det motsvarar att "hoppa" in i programmets sparade tillstånd och inte returnerar något värde; en sådan fortsättning kan vanligtvis inte kallas flera gånger. Avgränsade fortsättningar abstraherar beroendet av resultatet av något programblock på resultatet av något underuttryck av detta block. I en viss mening motsvarar de något segment av samtalsstacken och inte hela stacken. Sådana fortsättningar kan användas som funktioner, anropas flera gånger och så vidare. De abstraheras med hjälp av mekanismen : den omsluter det yttre blocket, fungerar som , men tar inte emot som ett argument en global fortsättning, utan en begränsad sådan - beroendet av värdet på återställningsblocket på värdet i stället för skiftblocket. Det finns andra sorter, till exempel . call/ccshift/resetresetshiftcall/ccprompt/control
Många programmeringsspråk tillhandahåller denna förmåga under olika namn, såsom:
På vilket språk som helst som stöder stängningar kan du skriva fortsättningsprogram och implementera call/cc. I synnerhet är detta en vedertagen praxis i Haskell , där "monader som passerar fortsättningar" enkelt byggs (till exempel bibliotekets monad Contoch monadtransformator ). ContTmtl