Jatko ( englanniksi continuation ) on abstrakti esitys ohjelman tilasta tietyllä hetkellä, joka voidaan tallentaa ja käyttää siirtymiseen tähän tilaan. Jatkossa on kaikki tiedot ohjelman suorittamisen jatkamiseksi tietystä kohdasta alkaen; globaalien muuttujien tilaa ei yleensä säilytetä, mutta tämä ei ole välttämätöntä toiminnallisille kielille (esimerkiksi globaalien objektien arvojen valikoiva tallennus ja palauttaminen Schemissä saavutetaan erillisellä dynaamisella tuulimekanismilla). Jatkoot ovat samanlaisia kuin goto BASICsetjmp tai makrot Clongjmp : ssä , koska niiden avulla voit myös hypätä mihin tahansa paikkaan ohjelmassa. Mutta jatkot, toisin kuin , antavat sinun siirtyä vain ohjelman osaan, jossa on tietty tila, joka on tallennettava etukäteen, kun taas sen avulla voit siirtyä ohjelman osaan, jossa on alustamattomia muuttujia . gotogoto
Ensimmäinen kieli, joka toteutti jatkojen käsitteen, oli Scheme , ja myöhemmin sisäänrakennettu tuki jatkoille ilmestyi useilla muilla kielillä.
Muodollisesti callcc tämä on korkeamman asteen funktio , jonka avulla voit abstraktoida olemassa olevan funktion dynaamisen kontekstin toisen funktion muodossa, jota kutsutaan "jatkoksi".
Lyhyesti sanottuna jatko on "ohjelman loppuosa tietystä pisteestä" tai "funktio, joka ei koskaan palaa siihen pisteeseen, jota kutsuttiin" [1] . Funktionaalisen ohjelmoinnin kursseilla jatko-käsitteen selitys tiivistyy usein " korutiinin käsitteen laajentamiseen (monimutkaiseen) ", mutta didaktisessa mielessä tällaista selitystä pidetään hyödyttömänä [1] . Syy käsitteen selittämisen vaikeuteen piilee siinä, että jatkot ovat itse asiassa vaihtoehtoinen perustelu käsitteelle "käyttäytyminen" ("puhelu" laajimmassa merkityksessä), eli niillä on erilainen semanttinen malli, ja tässä Tässä mielessä alkusiirtymää "tavallisesta" toiminnallisesta ohjelmoinnista ohjelmointiin, jossa käytetään runsaasti jatkoja, voidaan verrata alkuperäiseen siirtymiseen pakollisesta ohjelmoinnista toiminnalliseen ohjelmointiin .
Jatkoot tarjoavat matemaattisen perustan koko ohjelman suoritusjärjestykseen silmukoista rekursioon ,goto poikkeuksiin , generaattoreihin , korutiineihin ja palautusmekanismiin [ 1 ] . Tämän seurauksena ne mahdollistavat kaikkien näiden elementtien toteuttamisen kielessä yhden rakenteen kautta.
Continuation -passing style ohjelmointi (CPS ) on ohjelmointityyli , jossa ohjaus siirretään jatkomekanismin kautta . CPS-tyylin esittelivät ensimmäisenä Gerald Jay Sussman ja Guy Steele, Jr. , samaan aikaan Scheme-kielen kanssa .
"Klassisen tyylin" ohjelma voidaan usein kirjoittaa uudelleen jatkosyötön tyyliin. Esimerkiksi ongelmalle laskea suorakulmaisen kolmion hypotenuusa "klassisella" Haskell -koodilla :
pow2 :: Float -> Float pow2 a = a ** 2 lisää :: Float -> Float -> Float lisää a b = a + b pyth :: Float -> Float -> Float pyth a b = sqrt ( add ( pow2 a ) ( pow2 b ))voit lisätä yhden tyypin argumentin F, jossa Ftarkoittaa funktiota alkuperäisen funktion palautusarvosta mielivaltaiseen tyyppiin xja tehdä tästä mielivaltaisesta tyypistä palautusarvo 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 ) -- tyypit a -> (b -> c) ja a -> b -> c ovat vastaavia, joten CPS-funktiota voidaan -- pitää yhden argumentin korkeamman asteen funktiona 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 )))Neliö pyth'lasketaan funktiossa, ja funktio ( lambda lausekea ) välitetään jatkona , jolloin neliö on ainoa argumentti. Lisäksi kaikki myöhemmät väliarvot lasketaan samalla tavalla. Laskelmien suorittamiseksi jatkona on välitettävä yhden argumentin funktio, esimerkiksi funktio , joka palauttaa minkä tahansa sille välitetyn arvon. Siten lauseke vastaa . aidpyth' 3 4 id5.0
Control.Monad.Cont-moduulin standardi haskell -kirjasto sisältää tyypin Cont, jonka avulla voit käyttää CPS-toimintoja monadissa. Toiminto pyth'näyttää tältä:
pow2_m :: Float -> Cont a Float pow2_m a = paluu ( a ** 2 ) -- cont-funktio nostaa normaalit CPS-funktiot arvoon 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 rTämä moduuli sisältää myös callCCtyypin funktion MonadCont m => ((a -> m b) -> m a) -> m a. Tyypistä voidaan nähdä, että se ottaa funktion ainoaksi argumentiksi, jolla puolestaan on myös funktio ainoa argumentti, joka keskeyttää jatkolaskutoimitukset. Voimme esimerkiksi keskeyttää lisälaskelmat, jos ainakin yksi argumenteista on negatiivinen:
pyth_m :: Float -> Float -> Cont a Float pyth_m a b = callCC $ \ exitF -> do when ( b < 0 || a < 0 ) ( exitF 0.0 ) -- when :: Applikatiivinen f => Bool -> f () -> f () a2 <- pow2_m a b2 <- pow2_m b anb <- cont ( add' a2 b2 ) r <- cont ( sqrt' anb ) return rEsimerkkejä CPS:stä kaaviossa:
| suora tyyli | Jatka passitustyyliä |
|---|---|
| ( 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 ( factorial n ) ( if ( = n 0 ) 1 ; EI häntärekursiivinen ( * n ( factorial ( - n 1 ))))) | ( define ( factorial& n k ) ( =& n 0 ( lambda ( b ) ( jos b ; jatkaa kasvuaan ( k 1 ) ; rekursiivisessa kutsussa ( -& 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-rekursiivinen ( 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 ) ( jos b ; jatko säilytetty ( k a ) ; rekursiivisessa kutsussa ) ( -& n 1 ( lambda ( nm1 ) ( *& n a ( lambda ( nta ) ( f-aux& nm1 nta k )))))))))) |
"Puhdassa" CPS:ssä ei itse asiassa ole jatkoa - jokainen puhelu osoittautuu tail calliksi . Jos kieli ei takaa tail call -optimointia ( TCO ), niin jokaisen sisäkkäisen kutsun yhteydessä sekä itse jatko että puhelupino kasvavat . Tämä ei yleensä ole toivottavaa, mutta sitä käytetään joskus mielenkiintoisella tavalla (esimerkiksi Chicken Scheme -kääntäjässä ). TCO- ja CPS-optimointistrategioiden yhdistetty käyttö mahdollistaa dynaamisen pinon poistamisen suoritettavasta ohjelmasta kokonaan. Useat toiminnalliset kielenkääntäjät toimivat tällä tavalla, kuten SML/NJ-kääntäjä Standard ML :lle . callcc
Laajennuksia on useita tyyppejä. Yleisimmät näistä ovat rajoittamattomat jatkot , jotka on toteutettu funktiolla tai sen analogeilla. Tällaiset jatkot todella edustavat koko ohjelman (tai yhden sen säikeen) tilaa tietyllä hetkellä. Tällaisen jatkon kutsuminen ei ole kuin funktion kutsumista, koska se vastaa "hyppäämistä" ohjelman tallennettuun tilaan eikä palauta mitään arvoa; tällaista jatkoa ei yleensä voida kutsua useaan kertaan. Erotetut jatkot abstraktioivat jonkin ohjelmalauseen tuloksen riippuvuuden tämän lauseen jonkin alilausekkeen tuloksesta . Tietyssä mielessä ne vastaavat jotakin puhelupinon segmenttiä, eivät koko pinoa. Tällaisia jatkoja voidaan käyttää funktioina, kutsua useita kertoja ja niin edelleen. Ne abstraktoidaan käyttämällä mekanismia : se kääri ulomman lohkon, toimii kuten , mutta vastaanottaa argumenttina ei globaalia jatkoa, vaan rajoitetun - nollauslohkon arvon riippuvuuden siirtolohkon sijasta. On muitakin lajikkeita, esim . call/ccshift/resetresetshiftcall/ccprompt/control
Monet ohjelmointikielet tarjoavat tämän ominaisuuden eri nimillä, kuten:
Millä tahansa kielellä, joka tukee sulkemisia , voit kirjoittaa jatko-pass-tyylisiä ohjelmia ja toteuttaa manuaalisesti call/cc. Erityisesti tämä on hyväksytty käytäntö Haskellissa , jossa "monadit, jotka ohittavat jatkot" rakennetaan helposti (esimerkiksi kirjaston monadi Contja monadimuuntaja ). ContTmtl