Vraag call / cc-implementatie?


Ik probeer te vinden hoe call / cc is geïmplementeerd. De beste die ik heb gevonden is dit Haskell-fragment:

callCC f = Cont $ \k -> runCont (f (\a -> Cont $ \_ -> k a)) k

Hoewel dit niet zo eenvoudig is als ik wil vanwege de Cont en runCont. Ik heb ook beschrijvingen gevonden van wat het doet, hoewel nooit zo duidelijk als de echte code.

Dus hoe wordt het geïmplementeerd in de eenvoudigste vorm? Ik tag dit met Scheme en Haskell, want dat zijn twee talen die ik het liefst heb.


25
2018-01-29 03:39


oorsprong


antwoorden:


"Implementing call/cc"is niet echt logisch in de laag waarin je werkt, als je kunt implementeren call/cc in een taal betekent dat alleen dat het een ingebouwd construct heeft dat minstens zo krachtig is als call/cc. Op het niveau van de taal zelf, call/cc is in feite een primitieve besturingsstroomoperator, net zoals een vorm van vertakking moet zijn.

Natuurlijk kunt u een taal gebruiken met call/cc in een taal zonder; dit komt omdat het op een lager niveau is. U vertaalt de constructies van de taal op een specifieke manier en u regelt deze vertaling zodat u deze kunt implementeren call/cc; d.w.z. in het algemeen, continuerende stijl (hoewel je voor niet-draagbare implementatie in C, de stapel ook rechtstreeks kunt kopiëren, zal ik de stijl van doorgaan met doorgeven verderop in meer detail bespreken). Dit geeft echt geen goed inzicht call/cc  zelf - het inzicht zit in het model waarmee u het mogelijk maakt. Daarbovenop, call/cc is gewoon een verpakking.

Haskell stelt nu geen begrip van een voortzetting; het zou referentiële transparantie schaden en mogelijke implementatiestrategieën beperken. Cont wordt geïmplementeerd in Haskell, net als elke andere monade, en je kunt het zien als een model van een taal met voortzettingen die gebruik maken van continuerende stijl, net als de lijstmonademodellen niet-determinisme.

Technisch gezien is die definitie van callCC typt als je gewoon de applicaties van verwijdert Cont en runCont. Maar dat zal je niet helpen begrijpen hoe het werkt in de context van de Cont monad, dus laten we eens naar de definitie kijken. (Deze definitie is niet de definitie die wordt gebruikt in de huidige Monad Transformer Library, omdat alle monaden erin zijn gebouwd bovenop hun transformatorversies, maar het komt overeen met het gebruik van het fragment Cont (die alleen werkt met de oudere versie), en dingen drastisch vereenvoudigt.)

newtype Cont r a = Cont { runCont :: (a -> r) -> r }

Oke dus Cont r a is gewoon (a -> r) -> r, en runCont laat ons deze functie uit een Cont r a waarde. Simpel genoeg. Maar wat betekent het?

Cont r a is een continuation-passing berekening met eindresultaat ren resultaat a. Wat betekent eindresultaat? Nou, laten we het type schrijven runCont explicieter:

runCont :: Cont r a -> (a -> r) -> r

Dus, zoals we kunnen zien, is het "eindresultaat" de waarde waar we uitkomen runCont aan het einde. Nu, hoe kunnen we berekeningen opbouwen met Cont? De monad-instantie is verhelderend:

instance Monad (Cont r) where
  return a = Cont (\k -> k a)
  m >>= f = Cont (\k -> runCont m (\result -> runCont (f result) k))

Wel, oke, het is verhelderend als je al weet wat het betekent. Het belangrijkste is dat wanneer je schrijft Cont (\k -> ...), k is de rest van de berekening- het verwacht van je dat je het een waarde geeft a, en geeft u vervolgens het eindresultaat van de berekening (van het type r, onthoud) terug, die u vervolgens kunt gebruiken als uw eigen retourwaarde, omdat uw retourtype dat is r te. Oef! En wanneer we een Cont berekening met runCont, we specificeren gewoon de finale k - het "hoogste niveau" van de berekening die het eindresultaat oplevert.

Wat wordt deze "rest van de berekening" genoemd? EEN voortzetting, omdat het de voortzetting van de berekening!

(>>=) is eigenlijk best simpel: we voeren de berekening aan de linkerkant uit en geven deze onze eigen Rest-van-berekening. Deze rest-van-berekening voedt de waarde gewoon in f, die zijn eigen berekening produceert. We voeren die berekening uit en voeren deze door naar de rest van de berekening die onze gecombineerde actie heeft gekregen. Op deze manier kunnen we berekeningen samenvoegen in Cont:

computeFirst >>= \a ->
computeSecond >>= \b ->
return (a + b)

of, in het meer bekende do notatie:

do a <- computeFirst
   b <- computeSecond
   return (a + b)

We kunnen deze berekeningen dan uitvoeren met runCont - meestal, zoiets runCont foo id werkt prima, draaien een foo met hetzelfde resultaat en resultaattype in het resultaat.

Tot nu toe, zo goed. Laten we nu dingen verwarrend maken.

wtf :: Cont String Int
wtf = Cont (\k -> "eek!")

aargh :: Cont String Int
aargh = do
  a <- return 1
  b <- wtf
  c <- return 2
  return (a + b + c)

Wat is hier aan de hand?! wtf is een Cont berekening met eindresultaat String en resultaat Int, maar er is geen Int in zicht.

Wat gebeurt er als we rennen aargh, zeg met runCont aargh show - d.w.z. voer de berekening uit, en show haar Int resultaat als een String om het eindresultaat te produceren?

We krijgen "eek!" terug.

Onthoud hoe k is de "rest van de berekening"? Wat we hebben gedaan in wtf is listig niet noem het maar, en lever in plaats daarvan ons eigen eindresultaat - wat dan, nou ja, definitief wordt!

Dit is het eerste wat vervolgingen kunnen doen. Zoiets als Cont (\k -> k 1 + k 2) voert de rest van de berekening uit alsof deze 1 is geretourneerd, en opnieuw alsof het 2 is teruggekeerd, en voegt de twee eindresultaten samen toe! Continueren staat in principe expressie toe willekeurig complexe niet-lokale controlestroom, ze zo krachtig maken als ze verwarrend zijn. Inderdaad, voortzettingen zijn zo algemeen dat, in zekere zin, elke monade is een speciaal geval van Cont. Je kunt inderdaad denken aan (>>=) in het algemeen als gebruik van een soort continuïteitsstijl:

(>>=) :: (Monad m) => m a -> (a -> m b) -> m b

Het tweede argument is een voortzetting van het resultaat van de eerste berekening en het retourneren van de rest van de berekening die moet worden uitgevoerd.

Maar ik heb nog steeds geen antwoord gegeven op de vraag: wat is daar aan de hand callCC? Wel, het noemt de functie die je geeft met de huidige voortzetting. Maar wacht even, is dat niet wat we deden? Cont nu al? Ja, maar vergelijk de typen:

Cont   :: ((a -> r)        -> r)        -> Cont r a
callCC :: ((a -> Cont r b) -> Cont r a) -> Cont r a

Huh. Zie je, het probleem met Cont is dat we acties niet kunnen achterhalen binnen van de functie die we passeren - we produceren gewoon een rresulteren in een pure manier. callCC laat de voortzetting worden benaderd, doorgegeven, en gewoon in het algemeen worden verknoeid met van binnen  Cont berekeningen. Wanneer we hebben

do a <- callCC (\cc -> ...)
   foo ...

Je kunt je voorstellen cc een functie zijn die we kunnen bellen met elke waarde binnen de functie om dat de geretourneerde waarde van te maken callCC (\cc -> ...) berekening zelf. Of we kunnen natuurlijk gewoon een waarde teruggeven, maar dan bellen callCC in de eerste plaats zou een beetje zinloos zijn :)

Wat betreft het mysterieuze b daar is het gewoon omdat je het kunt gebruiken cc foo om in te staan ​​voor een berekening van ieder typ je wilt, omdat het ontsnappingen de normale controlestroom en zoals ik al zei onmiddellijk gebruikt als resultaat van het geheel callCC (\cc -> ...). Dus omdat het nooit een waarde hoeft te produceren, kan het wegkomen met het retourneren van een waarde van elk type dat het wil. Stiekem!

Dat brengt ons bij de daadwerkelijke implementatie:

callCC f = Cont (\k -> runCont (f (\a -> Cont (\_ -> k a))) k)

Eerst krijgen we de volledige rest van de berekening en noemen we het k. Maar wat is dit f (\a -> Cont (\_ -> k a)) deel over? Welnu, dat weten we f neemt een waarde van het type (a -> Cont r b), en dat is wat de lambda is - een functie die een waarde heeft om te gebruiken als het resultaat van de callCC fen retourneert een Cont berekening die de voortzetting ervan negeert en die waarde gewoon doorgeeft k - de "rest van de berekening" vanuit het perspectief van callCC f. OK, dus het resultaat daarvan f bellen is een andere Cont berekening, waarvoor we een vervolg moeten geven om te kunnen uitvoeren. We geven gewoon opnieuw dezelfde voortzetting door, want als alles normaal verloopt, willen we dat de berekening terugkeert naar onze retourwaarde en normaal doorgaat. (Inderdaad, het doorgeven van een andere waarde zou niet maken zin - het is "call with actueel voortzetting ", niet" aanroepen met een andere voortzetting dan degene waarmee je me echt in het gareel houdt ")

Al met al hoop ik dat je dit even verhelderend vond als het lang is. Continuaties zijn erg krachtig, maar het kan veel tijd kosten om een ​​intuïtie te krijgen voor hoe ze werken. Ik stel voor om mee te spelen Cont (die je moet bellen cont om dingen te laten werken met de huidige mtl) en uit te werken hoe je de resultaten krijgt die je doet om een ​​gevoel te krijgen voor de controlestroom.

Aanbevolen verder lezen over voortzettingen:


78
2018-01-29 04:20



call/cc is triviaal om te implementeren. Het moeilijkste is het opzetten van de omgeving waar deze zich bevindt mogelijk implementeren.

We moeten eerst een uitvoeringsomgeving met een continu-passing style (CPS) definiëren. In deze omgeving retourneren je functies (of functie-achtige dingen) niet direct waarden; in plaats daarvan krijgen ze een functie doorgegeven die de 'volgende stap' in de berekening vertegenwoordigt - de 'voortzetting' - en ze geven hun resultaat daar door. In Haskell ziet dit er zo uit:

newtype Cont r a = Cont { runCont :: (a -> r) -> r }

Zoals je kunt zien, a Cont monade-actie is echt een functie die een voortzetting is (a -> r), geeft een resultaat door a naar de voortzetting, en krijgt een eindresultaat van r, die het eenvoudig doorgeeft aan de beller (dwz, a Cont monade actie zou moeten staartoproep in de voortzetting). runCont haalt het gewoon uit de nieuwewrapper - je zou het ook kunnen zien als het aanroepen van een actie met een bepaalde voortzetting, zoals in runCont someAction someContinuation.

We kunnen dit dan in een monade veranderen:

instance Monad (Cont r) where
    return x = Cont $ \cc -> cc x
    (Cont f) (>>=) g = Cont $ \cc -> f (\r -> runCont (g r) cc)

Zoals je kan zien, return krijgt gewoon een vervolg cc, en geeft de waarde ervan door aan de voortzetting. (>>=) is een beetje lastiger, het moet aanroepen f met een voortzetting die dan oproept g, haalt de actie terug en geeft de uiterlijke voortzetting door aan deze nieuwe actie.

Dus gezien dit kader is het eenvoudig om tot het vervolg te komen. We willen alleen een functie aanhalen met zijn voortzetting tweemaal. Het lastige is dat we deze voortzetting moeten hergroeperen in een nieuwe monadische actie die de bestaande voortzetting overboord gooit. Dus laten we het een beetje opsplitsen:

-- Invoke a raw continuation with a given argument, throwing away our normal 
-- continuation
gotoContinuation :: (a -> r) -> a -> Cont r x
gotoContinuation continuation argument = Cont $ \_ -> continuation argument

-- Duplicate the current continuation; wrap one up in an easy-to-use action, and
-- the other stays the normal continuation for f
callCC f = Cont $ \cc -> runCont (f (gotoContinuation cc)) cc

Eenvoudig, niet?

In andere talen, zoals Scheme, is het principe hetzelfde, hoewel het kan worden geïmplementeerd als een compilerprimitief; de reden dat we het in Haskell kunnen doen, is omdat het continueren van doorgaan iets was dat we in Haskell hebben gedefinieerd, niet op een lager niveau van de looptijd. Maar het principe is hetzelfde: u moet eerst CPS hebben en daarna call/cc is een triviale toepassing van dit uitvoeringsmodel.


10
2018-01-29 04:12



Je hebt de Haskell kant van de vergelijking gehoord; Ik geef je de Racket / Scheme één, en welke je het meest van dienst is, je kunt er mee aan de slag.

Mijn antwoord zal een stuk korter zijn, omdat ik denk dat de beste bron die ik je kan geven voor de implementatie van call / cc in een eenvoudige racket-evaluator afkomstig is van Shriram Krishnamurthi's PLAI, in het bijzonder paragraaf 20. Ik dacht erover om het relevante deel van de tolk op te nemen - het staat op pagina 205 - maar na een aantal keer geprobeerd te hebben het opnieuw te formatteren, besloot ik dat het logischer zou zijn op de juiste plaats op de pagina.

Nogmaals, ik probeer hier niet het idee achter call / cc uit te leggen, ik wijs u slechts op een werkende implementatie. Laat het me weten als je andere vragen hebt.


6
2018-01-29 04:20



Welnu, ik zal een veel korter, op Schema gebaseerd antwoord geven, omdat dit ook als 'schema' is getagd.

Begrijpen waarom je probeert te implementeren call/cc moet falen, je moet begrijpen wat doorlopende stijl is. Als je dat eenmaal begrijpt, is het vrij eenvoudig:

  • call/cc kan niet in directe stijl worden geïmplementeerd.
  • Het is echter triviaal om te implementeren in continuerende stijl.

Maar om een ​​beetje meer informatie te geven, is continuation-passing style een flow-control-discipline waarbij je het gebruik van een call-stack negeert ten gunste van een calling-conventie waarbij elke procedureaanroep een "extra" argument passeert: een afsluiting die de aangeroepen procedure veronderstelt om te bellen wanneer het "klaar" is (het doorgeven van de "geretourneerde waarde" als het argument). Deze extra redenatiesluitingen worden genoemd voortzettingen.

Elk programma kan mechanisch worden vertaald in een continuerende stijl, door middel van iets dat, toepasselijk genoeg, wordt genoemd CPS-transformatie. Veel Scheme-systemen werken in feite zo: het programma wordt geparseerd, de CPS-transformatie wordt erop toegepast en de abstracte syntaxisboom van CPS wordt ofwel geïnterpreteerd of vertaald naar objectcode.

Dit is hoe je zou implementeren call/cc in continuerende stijl (gebruiken continuation als de naam van het extra argument voor de voortzetting):

(define (call/cc-cps proc continuation)
  (proc continuation continuation))

Zoals je zou moeten kunnen zien, (a) kun je dit niet in directe stijl implementeren (het tegenovergestelde van CPS), en (b) het is triviaal in CPS. call/cc is slechts een procedure die een andere procedure als argumentatie en de (verplichte) voortzetting vereist, en noemt die procedure met de voortzetting zowel als argument als ook voor de voortzetting ervan.


3
2018-01-30 18:35



Risico's van zijn off-taal Ik denk dat in Smalltalk continuïteiten het gemakkelijkst kunnen worden geïmplementeerd en begrepen. De reden is dat in Smalltalk de uitvoeringsstapel wordt gevormd uit normale objecten die kunnen worden benaderd en gemanipuleerd zoals elk ander object.

Voor de implementatie van een eenvoudig continuatieobject zijn de volgende twee methoden nodig. In de eerste methode initialiseren we de voortzetting door itereren over de bovenliggende (afzender) frames (contexten) en het kopiëren van hun staat (programmateller, tijdelijke bestanden, argumenten):

Continuation>>initializeFromContext: aContext
    context := aContext.
    stream := WriteStream on: (Array new: 200).
    [ context notNil ] whileTrue: [
        stream nextPut: context.
        1 to: context class instSize do: [ :index |
            stream nextPut: (context instVarAt: index) ].
        1 to: context size do: [ :index |
            stream nextPut: (context at: index) ].
        context := context sender ].
    values := stream contents

De tweede methode is om de uitvoering te hervatten: eerst wikkelen we de huidige stapel (nogmaals, dat is slechts een simpele lus over de uitvoeringsstapel), dan herstellen we de genomen stapelframes, koppelen ze opnieuw aan het huidige stapelframe thisContext en hervat de uitvoering met het argument anObject:

Continuation>>value: anObject
    self terminate: thisContext.
    stream := values readStream.
    [ stream atEnd ] whileFalse: [
        context := stream next.
        1 to: context class instSize do: [ :index |
            context instVarAt: index put: stream next ].
        1 to: context size do: [ :index |
            context at: index put: stream next ] ]
    thisContext swapSender: values first.
    ^ anObject

Met deze twee methoden kunnen we eenvoudig bouwen callCC:

Continuation class>>callCC: aBlock
    ^ aBlock value: (self new initializeFromContext: thisContext sender)

Het mooie van deze aanpak is dat de gedrukte code alles toont wat nodig is om volledige voortzettingen (en ook andere soorten continuïteiten) te implementeren. Er is geen gedrag verborgen in het systeem (VM). Men kan een debugger gebruiken om door elk onderdeel te stappen en te observeren hoe de uitvoeringsstapel wordt gemanipuleerd.

De bovenstaande code is van de Kust web-framework. Om met de code te spelen wil je misschien een kant en klaar gebruik maken distributie en blader naar de klassen WAContinuation en WAContinuationTest.


3
2018-01-29 10:29