Avgränsad fortsättning

I programmeringsspråk är en avgränsad fortsättning , komponerbar fortsättning eller partiell fortsättning , en "del" av en fortsättningsram som har reifierats till en funktion . Till skillnad från vanliga fortsättningar returnerar avgränsade fortsättningar ett värde och kan därför återanvändas och sammansättas . Kontrollavgränsare, grunden för avgränsade fortsättningar, introducerades av Matthias Felleisen 1988, även om tidiga anspelningar på komponerbara och avgränsade fortsättningar finns i Carolyn Talcotts Stanford-avhandling 1984, Felleisen et al. , Felleisens avhandling från 1987, och algoritmer för funktionell bakåtspårning.

Historia

Avgränsade fortsättningar introducerades först av Felleisen 1988 med en operator som heter ${\displaystyle {\mathcal {F}}} , som$ först introducerades i en teknisk rapport 1987, tillsammans med en promptkonstruktion $\#$ . Operatören designades för att vara en generalisering av kontrolloperatörer som hade beskrivits i litteraturen , såsom call/cc från Scheme , ISWIMs J-operatör , John C. Reynolds escape - operatör och andra. Därefter uppfanns många konkurrerande avgränsade kontrolloperatörer av forskarsamhället för programmeringsspråk som prompt och kontroll , shift and reset , cupto , fcontrol och andra.

Exempel

Olika operatorer för avgränsade fortsättningar har föreslagits i forskningslitteraturen.

Ett oberoende förslag är baserat på fortsättningspasseringsstil (CPS) - dvs inte på fortsättningsramar - och erbjuder två kontrolloperatörer: skift och återställning . Återställningsoperatören ställer in gränsen för fortsättningen medan skiftoperatören fångar upp eller reifar den aktuella fortsättningen upp till den innersta omslutande återställningen . Tänk till exempel på följande kodavsnitt i Schema :

       (  *  2  (  återställ  (  +  1  (  skift  k  (  k  5  ))))))

Återställningen avgränsar fortsättningen som shift fångar (namngiven av k i detta exempel) . När detta utdrag exekveras kommer användningen av shift att binda k till fortsättningen (+ 1 []) där [] representerar den del av beräkningen som ska fyllas med ett värde. Denna fortsättning motsvarar direkt koden som omger skiftet fram till återställningen . Eftersom skiftkroppen (dvs (k 5) ) omedelbart anropar fortsättningen, är denna kod ekvivalent med följande:

   (  *  2  (  +  1  5  ))

I allmänhet kan dessa operatörer koda mer intressant beteende genom att till exempel returnera den fångade fortsättningen k som ett värde eller anropa k flera gånger. Skiftoperatören skickar den infångade fortsättningen k till koden i sin kropp, som antingen kan anropa den, producera den som ett resultat eller ignorera den helt . Vilket resultat som växlingen än ger ges till den innersta återställningen , vilket förkastar fortsättningen mellan återställning och växling . Men om fortsättningen anropas, installerar den i praktiken fortsättningen om efter att ha återgått till återställningen . När hela beräkningen inom återställningen är klar, returneras resultatet av den avgränsade fortsättningen. Till exempel, i denna schemakod :

      (  återställ  (  *  2  (  skift  k  CODE  )))

närhelst CODE anropar (k N) , (* 2 N) utvärderas och returneras.

Detta motsvarar följande:

       (  låt  ((  k  (  lambda  (  x  )  (  *  2  x  ))))  KOD  )

Dessutom, när hela beräkningen inom shift är klar, kasseras fortsättningen, och exekveringen startar om utanför reset . Därför,

        (  återställ  (  *  2  (  skift  k  (  k  (  k  4  ))))))

anropar (k 4) först (som returnerar 8), och sedan (k 8) (som returnerar 16). Vid denna tidpunkt skiftuttrycket avslutats och resten av återställningsuttrycket kasseras. Därför är slutresultatet 16.

Allt som händer utanför återställningsuttrycket är dolt, dvs inte påverkat av kontrollöverföringen. Till exempel returnerar detta 17:

         (  +  1  (  återställ  (  *  2  (  skift  k  (  k  (  k  4  )))))))

Avgränsade fortsättningar beskrevs först oberoende av Felleisen et al. och Johnson. De har sedan använts inom ett stort antal domäner, särskilt för att definiera nya kontrolloperatörer ; se Queinnec för en undersökning.

Låt oss ta en titt på ett mer komplicerat exempel. Låt null vara den tomma listan:

 
   
          
      (  återställ  (  börja  (  skift  k  (  nackdelar  1  (  k  (  ogiltig  ))))  ;; (1)  null  ))

Kontexten som fångas av shift är (begin [*] null) , där [*] är hålet där k :s parameter kommer att injiceras. Det första anropet av k inuti skift utvärderas till detta sammanhang med (void) = #<void> som ersätter hålet, så värdet av (k (void)) är (början #<void> null) = null . Skiftkroppen , nämligen (cons 1 null) = (1) , blir det totala värdet för återställningsuttrycket som slutresultat.

För att göra det här exemplet mer komplicerat, lägg till en rad:

 
   
         
         
      (  återställ  (  börja  (  skift  k  (  nackdelar  1  (  k  (  void  ))))  (  skift  k  (  nackdelar  2  (  k  (  void  ))))  null  ))

Om vi kommenterar det första skiftet vet vi redan resultatet, det är (2) ; så vi kan lika gärna skriva om uttrycket så här:

 
   
         
      (  återställ  (  börja  (  skift  k  (  nackdelar  1  (  k  (  ogiltig  ))))  (  lista  2  )))

Detta är ganska bekant och kan skrivas om som (nackdelar 1 (lista 2)), det vill säga (lista 1 2) .

Vi kan definiera avkastning med det här tricket:

(definiera (avkasta x) (skifta k (cons x (k (void)))))

och använd den i bygglistor:

  
           
           
           
               (  återställ  (  start  (  avkastning  1  )  (  avkastning  2  )  (  avkastning  3  )  null  ))  ;; (lista 1 2 3)

Om vi ersätter nackdelar med stream-cons kan vi bygga lata streams:

         

  
     
             
             
             
             (  definiera  (  stream-yield  x  )  (  shift  k  (  stream-cons  x  (  k  (  void  )))))  (  definiera  lazy-exempel  (  återställ  (  börja  (  stream-yield  1  ))  (  stream-yield  2  )  (  stream-yield  3  )  stream-null  )))

Vi kan generalisera detta och konvertera listor till stream, i ett svep:

  
    
             
             (  definiera  (  lista->ström  xs  )  (  återställ  (  börja  (  för varje  ström-avkastning  xs  )  stream-null  )))

I ett mer komplicerat exempel nedan kan fortsättningen säkert slås in i en lambdakropp och användas som sådan:

   
    
      
               
                            
                                
                         
               (  definiera  (  for-each->stream-maker  for-each  )  (  lambda  (  samling  )  (  återställ  (  börja  (  för-each  (  lambda  (  element  ) )  (  shift  k  (  stream-cons  element  (  k  'ignored  ))))  collection  )  stream-null  ))))

Delen mellan återställning och växling inkluderar kontrollfunktioner som lambda och for-each ; detta är omöjligt att omformulera med lambdas ^{[ varför? ]} .

Avgränsade fortsättningar är också användbara inom lingvistik : se Fortsättningar i lingvistik för detaljer.

externa länkar