Pokračování ( anglicky continuation ) je abstraktní znázornění stavu programu v určitém okamžiku, které lze uložit a použít k přechodu do tohoto stavu. Pokračování obsahují všechny informace pro pokračování provádění programu od určitého bodu; stav globálních proměnných obvykle není zachován, ale to není u funkčních jazyků podstatné (například selektivní ukládání a obnovování hodnot globálních objektů ve Scheme je dosaženo samostatným dynamickým mechanismem větru). Pokračování jsou podobná jako goto BASICsetjmp nebo makra longjmpv C , protože také umožňují přeskočit na libovolné místo v programu. Pokračování vám ale na rozdíl od goto, umožňuje přejít pouze do části programu s určitým stavem, který je nutné předem uložit, zatímco gotoumožňuje přejít do části programu s neinicializovanými proměnnými .
První jazyk, který implementoval koncept pokračování, byl Scheme a později se vestavěná podpora pro pokračování objevila v řadě dalších jazyků.
Formálně se callcc jedná o funkci vyššího řádu , která vám umožňuje abstrahovat dynamický kontext existující funkce ve formě jiné funkce, která se nazývá „pokračování“.
Přesněji řečeno, pokračování je „zbytek programu z daného bodu“ nebo „funkce, která se nikdy nevrátí do bodu, ve kterém byla volána“ [1] . V kurzech funkcionálního programování se vysvětlení pojmu pokračování často snižuje na „rozšíření (komplikování) pojmu korutina “, ale v didaktickém smyslu je takové vysvětlení považováno za zbytečné [1] . Důvod obtížnosti vysvětlení pojmu spočívá ve skutečnosti, že pokračování jsou vlastně alternativním zdůvodněním pojmu „chování“ („volání“ v nejširším slova smyslu), to znamená, že nesou jiný sémantický model, a to Počáteční přechod od „obyčejného“ funkcionálního programování k programování s intenzivním používáním pokračování lze přirovnat k počátečnímu přechodu od imperativního k funkcionálnímu programování .
Pokračování poskytují matematický základ pro celé pořadí provádění programu , od smyčekgoto po rekurzi , výjimky , generátory , korutiny a návratový mechanismus [1] . V důsledku toho umožňují implementaci všech těchto prvků v jazyce prostřednictvím jediného konstruktu.
Programování ve stylu pokračování a předávání (CPS ) je styl programování, ve kterém se řízení přenáší prostřednictvím mechanismu pokračování . Styl CPS poprvé představili Gerald Jay Sussman a Guy Steele, Jr. , ve stejnou dobu jako jazyk Scheme .
Program "klasického stylu" může být často přepsán ve stylu pokračování. Například pro problém výpočtu přepony pravoúhlého trojúhelníku s "klasickým" Haskellovým kódem :
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 ))můžete přidat jeden argument typu F, kde Fznamená funkci z návratové hodnoty původní funkce do libovolného typu x, a z tohoto libovolného typu učinit návratovou hodnotu 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 ) -- typy a -> (b -> c) a a -> b -> c jsou ekvivalentní, takže funkci CPS lze -- považovat za funkci vyššího řádu jednoho argumentu 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 )))Ve funkci pyth'se vypočítá druhá mocnina a funkce ( výraz lambdaa ) se předá jako pokračování , přičemž jako jediný argument se použije druhá mocnina. Dále jsou všechny následující mezilehlé hodnoty vypočteny stejným způsobem. Aby bylo možné provádět výpočty jako pokračování, je nutné předat funkci jednoho argumentu, například funkci , která vrátí libovolnou hodnotu, která jí byla předána. Výraz je tedy ekvivalentní . aidpyth' 3 4 id5.0
Standardní knihovna haskell v modulu Control.Monad.Cont obsahuje typ Cont, který umožňuje používat funkce CPS v monadě. Funkce pyth'bude vypadat takto:
pow2_m :: Float -> Cont a Float pow2_m a = return ( a ** 2 ) -- funkce cont zvýší normální funkce CPS na 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 rTento modul také obsahuje funkci callCCtypu MonadCont m => ((a -> m b) -> m a) -> m a. Z typu je vidět, že jako jediný argument bere funkci, která má zase funkci jako jediný argument, přerušující další výpočty. Můžeme například přerušit další výpočty, pokud je alespoň jeden z argumentů záporný:
pyth_m :: Float -> Float -> Cont a Float pyth_m a b = callCC $ \ exitF -> do when ( b < 0 || a < 0 ) ( exitF 0.0 ) -- when :: Aplikativní f => Bool -> f () -> f () a2 <- pow2_m a b2 <- pow2_m b anb <- cont ( add' a2 b2 ) r <- cont ( sqrt' anb ) return rPříklady CPS ve schématu:
| přímý styl | Pokračování ve stylu předávání |
|---|---|
| ( definovat ( pyth x y ) ( sqrt ( + ( * x x ) ( * y y )))) | ( definujte ( pyth& x y k ) ( *& x x ( lambda ( x2 ) ( *& y y ( lambda ( y2 ) ( +& x2 y2 ( lambda ( x2py2 ) ( sqrt& x2py2 k )))))))) |
| ( definovat ( faktoriál n ) ( if ( = n 0 ) 1 ; NOT tail-rekurzivní ( * n ( faktoriál ( - n 1 ))))) | ( definovat ( faktoriál& n k ) ( =& n 0 ( lambda ( b ) ( pokud b ; pokračuje v růstu ( k 1 ) ; v rekurzivním volání ( -& n 1 ( lambda ( nm1 ) ( faktoriál& nm1 ( lambda ( f ) ) *& n f k ))))))))) |
| ( definovat ( faktoriál n ) ( f-aux n 1 )) ( definovat ( f-aux n a ) ( if ( = n 0 ) a ; tail-rekurzivní ( f-aux ( - n 1 ) ( * n a )) )) | ( definovat ( faktoriál& n k ) ( f-aux& n 1 k )) ( definovat ( f-aux& n a k ) ( =& n 0 ( lambda ( b ) ( pokud b ; pokračování zachováno ( k a ) ; v rekurzivním volání ( -& n 1 ( lambda ( nm1 ) ( *& n a ( lambda ( nta ) ( f-aux& nm1 nta k )))))))))) |
V „čistém“ CPS vlastně žádná pokračování sama o sobě neexistují – každé volání se ukáže jako koncové volání . Pokud jazyk nezaručuje optimalizaci koncových hovorů ( TCO ), pak s každým vnořeným hovorem roste jak samotné pokračování, tak zásobník hovorů . To obvykle není žádoucí, ale někdy se to zajímavým způsobem používá (například v překladači Chicken Scheme ). Kombinované použití optimalizačních strategií TCO a CPS umožňuje zcela eliminovat dynamický zásobník ze spustitelného programu. Tímto způsobem pracuje řada kompilátorů funkčních jazyků , jako je kompilátor SML/NJ pro Standard ML . callcc
Existuje několik typů rozšíření. Nejběžnější z nich jsou neomezená pokračování , implementovaná pomocí funkce nebo jejích analogů. Taková pokračování skutečně představují stav celého programu (nebo jednoho z jeho vláken) v určitém okamžiku. Volání takového pokračování není jako volání funkce, protože odpovídá "skoku" do uloženého stavu programu a nevrací žádnou hodnotu; takové pokračování většinou nelze volat vícekrát. Oddělená pokračování abstrahují závislost výsledku nějakého programového bloku na výsledku nějakého podvýrazu tohoto bloku. V určitém smyslu odpovídají určitému segmentu zásobníku volání, nikoli celému zásobníku. Taková pokračování lze použít jako funkce, volat je vícekrát a tak dále. Jsou abstrahovány pomocí mechanismu : obalí vnější blok, chová se jako , ale jako argument dostává nikoli globální pokračování, ale omezené - závislost hodnoty resetovaného bloku na hodnotě v místě posuvného bloku. Existují i jiné odrůdy, např . call/ccshift/resetresetshiftcall/ccprompt/control
Mnoho programovacích jazyků poskytuje tuto schopnost pod různými názvy, jako například:
V jakémkoli jazyce, který podporuje uzávěry , můžete psát programy ve stylu předávání pokračování a ručně implementovat call/cc. Konkrétně se jedná o přijímanou praxi v Haskellu , kde se snadno sestavují „monády, které projdou pokračováním“ (například knihovna monáda Conta monádový transformátor ). ContTmtl