Ograniczona kontynuacja

W językach programowania rozdzielona kontynuacja , kontynuacja możliwa do złożenia lub kontynuacja częściowa jest „wycinkiem” ramki kontynuacji , która została zreifikowana w funkcję . W przeciwieństwie do zwykłych kontynuacji, kontynuacje z ogranicznikami zwracają wartość, dzięki czemu można je ponownie wykorzystać i skomponować . Ograniczniki kontrolne, podstawa kontynuacji z ogranicznikami, zostały wprowadzone przez Matthiasa Felleisena w 1988 r., Chociaż wczesne aluzje do kontynuacji możliwych do złożenia i z ogranicznikami można znaleźć w rozprawie Carolyn Talcott ze Stanford z 1984 r., Felleisen i in. , rozprawa Felleisena z 1987 r. i algorytmy funkcjonalnego cofania się.

Historia

$po$ w 1988 r. Wraz z operatorem o nazwie , raz pierwszy wprowadzonym w raporcie technicznym w 1987 r., Wraz z $konstruktem$ . Operator został zaprojektowany jako uogólnienie operatorów sterujących, które zostały opisane w literaturze, takich jak call/cc ze Scheme , operator J ISWIM , operator escape Johna C. Reynoldsa i inne. Następnie społeczność badaczy języków programowania wymyśliła wiele konkurujących ze sobą operatorów sterowania rozdzielanego, takich jak prompt and control , shift and reset , cupto , fcontrol i inne.

Przykłady

W literaturze naukowej zaproponowano różne operatory dla ograniczonych kontynuacji.

Jedna niezależna propozycja jest oparta na stylu przekazywania kontynuacji (CPS) — tj. nie na klatkach kontynuacji — i oferuje dwa operatory sterowania: shift i reset . Operator reset ustawia limit kontynuacji, podczas gdy operator shift przechwytuje lub reifikuje bieżącą kontynuację aż do najgłębszego otaczającego resetu . Rozważmy na przykład następujący fragment w Scheme :

       (  *  2  (  reset  (  +  1  (  przesunięcie  k  (  k  5  )))))

Reset ogranicza kontynuację przechwytywaną przez shift (nazwaną przez k w tym przykładzie). Gdy ten fragment zostanie wykonany, użycie shift spowoduje powiązanie k z kontynuacją (+ 1 []), gdzie [] reprezentuje część obliczeń, która ma zostać wypełniona wartością. Ta kontynuacja bezpośrednio odpowiada kodowi, który otacza przesunięcie w górę do resetu . Ponieważ treść przesunięcia (tj. (k 5) ) natychmiast wywołuje kontynuację, ten kod jest równoważny następującemu:

   (  *  2  (  +  1  5  ))

Ogólnie rzecz biorąc, operatorzy ci mogą zakodować bardziej interesujące zachowanie, na przykład zwracając przechwyconą kontynuację k jako wartość lub wielokrotnie wywołując k . Operator przesunięcia przekazuje przechwyconą kontynuację k do kodu w swoim ciele, który może ją wywołać, wygenerować jako wynik lub całkowicie ją zignorować. Jakikolwiek wynik przesunięcie , jest on przekazywany do najbardziej wewnętrznego resetu , odrzucając kontynuację pomiędzy resetem a przesunięciem . Jeśli jednak kontynuacja zostanie wywołana, to skutecznie ponownie instaluje kontynuację po powrocie do resetu . Gdy całe obliczenie w ramach resetowania zostanie zakończone, wynik jest zwracany przez kontynuację rozdzielaną. Na przykład w tym schematu :

      (  reset  (  *  2  (  shift  k  KOD  )))

ilekroć CODE wywołuje (k N) , (* 2 N) jest obliczane i zwracane.

Jest to równoważne następującemu:

       (  niech  ((  k  (  lambda  (  x  )  (  *  2  x  ))))  KOD  )

Ponadto, gdy całe obliczenie w ramach shift zostanie zakończone, kontynuacja jest odrzucana, a wykonywanie jest uruchamiane ponownie poza reset . Dlatego,

        (  reset  (  *  2  (  przesunięcie  k  (  k  (  k  4  )))))

wywołuje (k 4) najpierw (co zwraca 8), a następnie (k 8) (co zwraca 16). W tym momencie shift zostało zakończone, a reszta wyrażenia resetowania jest odrzucana. Dlatego ostateczny wynik to 16.

Wszystko, co dzieje się poza wyrażeniem resetowania , jest ukryte, tj. nie ma na nie wpływu przekazanie sterowania. Na przykład to zwraca 17:

         (  +  1  (  reset  (  *  2  (  przesunięcie  k  (  k  (  k  4  ))))))

Ograniczone kontynuacje zostały po raz pierwszy opisane niezależnie przez Felleisena i in. i Johnsona. Od tego czasu były używane w wielu dziedzinach, szczególnie w definiowaniu nowych operatorów sterujących ; zobacz Queinnec w celu uzyskania ankiety.

Spójrzmy na bardziej skomplikowany przykład. Niech null będzie pustą listą:

 
   
          
      (  zresetować  (  rozpocząć  (  shift  k  (  cons  1  (  k  (  void  ))))  ;; (1)  null  ))

Kontekst przechwycony przez shift to (begin [*] null) , gdzie [*] to dziura, do której zostanie wstrzyknięty parametr k . Pierwsze wywołanie k wewnątrz przesunięcia ocenia ten kontekst z (void) = #<void> zastępując dziurę, więc wartość (k (void)) to (begin #<void> null) = null . Ciało przesunięcia , a mianowicie (cons 1 null) = (1) , staje się ogólną wartością wyrażenia resetującego jako wynik końcowy.

Aby ten przykład był bardziej skomplikowany, dodaj linię:

 
   
         
         
      (  reset  (  start  (  shift  k  (  cons  1  (  k  (  void  ))))  (  shift  k  (  cons  2  (  k  (  void  ))))  null  ))

Jeśli zakomentujemy pierwszą zmianę , to już znamy wynik, to jest (2) ; więc równie dobrze możemy przepisać wyrażenie w ten sposób:

 
   
         
      (  reset  (  start  (  shift  k  (  cons  1  (  k  (  void  ))))  (  lista  2  )))

Jest to dość znajome i można je przepisać jako (cons 1 (list 2)) , czyli (list 1 2) .

Możemy zdefiniować yield za pomocą tej sztuczki:

(definiuj (wydajność x) (przesuń k (przeciw x (k (pusta)))))

i użyj go na listach budynków:

  
           
           
           
               (  zresetuj  (  początek  (  wydajność  1  )  (  wydajność  2  )  (  wydajność  3  )  null  ))  ;; (lista 1 2 3)

Jeśli zamienimy cons na stream-cons , możemy zbudować leniwe strumienie:

         

  
     
             
             
             
             (  zdefiniuj  (  wydajność strumienia  x  )  (  shift  k  (  wydajność strumienia  x  (  k  (  void  )))))  (  zdefiniuj  leniwy przykład  (  reset  (  początek  (  wydajność strumienia  1  )  (  wydajność strumienia  2  )  (  wydajność strumienia  3  )  strumień-null  )))

Możemy to uogólnić i za jednym zamachem przekonwertować listy na strumień:

  
    
             
             (  definiuj  (  lista->strumień  xs  )  (  resetuj  (  rozpocznij  (  dla-każdego  strumienia-wydajność  xs  )  strumień-null  )))

W bardziej skomplikowanym przykładzie poniżej kontynuacja może być bezpiecznie zawinięta w ciało lambda i używana jako taka:

   
    
      
               
                            
                                
                         
               (  zdefiniuj  (  for-each->stream-maker  for-each  )  (  lambda  (  kolekcja  )  (  reset  (  begin  (  for-each  (  lambda  (  element  )  (  shift  k  (  element  stream-cons  (  k  'ignorowane  ))))  kolekcja  )  strumień-null  ))))

Część między resetem a przesunięciem obejmuje funkcje kontrolne, takie jak lambda i for-each ; nie można tego przeformułować za pomocą lambda ^{[ dlaczego? ]} .

Ograniczone kontynuacje są również przydatne w językoznawstwie : zobacz Kontynuacje w językoznawstwie, aby uzyskać szczegółowe informacje.

Linki zewnętrzne