Vymezené pokračování - Delimited continuation

v programovací jazyky, a ohraničené pokračování, skládatelné pokračování nebo částečné pokračování, je „plátek“ a pokračování rám to bylo reified do funkce. Na rozdíl od běžných pokračování, oddělovaná pokračování vrátit se hodnotu, a tak může být znovu použita a složen. Oddělovače řízení, základ oddělovaných pokračování, byly zavedeny Matthias Felleisen v roce 1988[1] ačkoli rané narážky na skládatelné a ohraničené pokračování lze nalézt v Carolyn Talcott disertační práce ve Stanfordu 1984, práce Felleisena a Friedmana PARL 1987,[2] a Felleisenova disertační práce z roku 1987.[3]

Dějiny

Vymezené pokračování poprvé představil Felleisen v roce 1988[1] s volaným operátorem , poprvé představen v technické zprávě v roce 1987,[2] spolu s rychlou konstrukcí . Operátor byl navržen jako zobecnění řídících operátorů, které byly popsány v literatuře, jako je call / cc z Systém, JÁ PLAVU je Operátor J., John C. Reynolds ' uniknout operátor a další. Následně bylo vynalezeno mnoho konkurenčních operátorů s odděleným řízením výzkumnou komunitou programovacích jazyků, jako např výzva a řízení,[4] posun a resetovat,[5] cupto,[6] fcontrol, a další.

Příklady

Ve vědecké literatuře byly navrženy různé operátory pro oddělené pokračování.[7]

Jeden návrh[5] nabízí dva ovládací operátory: posun a resetovat. The resetovat operátor stanoví limit pro pokračování, zatímco posun operátor zachycuje nebo reifikuje aktuální pokračování až do nejvnitřnějšího ohraničení resetovat. Zvažte například následující úryvek v Systém:

(* 2 (resetovat (+ 1 (posun k (k 5)))))

The resetovat vymezuje pokračování posun zachycuje (pojmenováno k v tomto příkladu). Když je tento fragment proveden, použití posun bude vázat k k pokračování (+ 1 []) kde [] představuje část výpočtu, která má být vyplněna hodnotou. Toto pokračování přímo odpovídá kódu, který obklopuje posun až po resetovat. Protože tělo směny (tj. (k 5)) okamžitě vyvolá pokračování, tento kód je ekvivalentní následujícímu:

(* 2 (+ 1 5))

Obecně mohou tito operátoři kódovat zajímavější chování, například vrácením zachyceného pokračování k jako hodnotu nebo vyvolání k několikrát. The posun operátor předá zachycené pokračování k na kód v jeho těle, který jej může buď vyvolat, vytvořit jako výsledek, nebo zcela ignorovat. Jakýkoli výsledek posun produkuje se poskytuje nejvnitřnějšímu resetovat, zahodit pokračování mezi resetovat a posun. Pokud je však vyvoláno pokračování, potom se efektivně znovu nainstaluje pokračování po návratu do resetovat. Když je celý výpočet uvnitř resetovat je dokončeno, výsledek je vrácen oddělovaným pokračováním.[8] Například v tomto Systém kód:

 (resetovat (* 2 (posun k KÓD)))

kdykoli KÓD vyvolává (k N), (* 2 s.) je vyhodnocen a vrácen.

To odpovídá následujícímu:

  (nechat ((k (lambda (X) (* 2 X)))) KÓD)

Kromě toho jednou celý výpočet uvnitř posun je dokončeno, pokračování je zahozeno a spuštění se restartuje venku resetovat. Proto,

 (resetovat (* 2 (posun k (k (k 4)))))

vyvolává (k 4) first (which returns 8), and then (k 8) (který vrátí 16). V tomto okamžiku posun výraz byl ukončen a zbytek souboru resetovat výraz je zahozen. Konečný výsledek je tedy 16.

Všechno, co se děje venku resetovat výraz je skrytý, tj. není ovlivněn přenosem řízení. Například vrátí 17:

 (+ 1 (resetovat (* 2 (posun k (k (k 4))))))

Vymezená pokračování byla poprvé popsána samostatně Felleisenem et al.[9] a Johnson.[10] Od té doby se používají ve velkém počtu domén, zejména při definování nových kontrolní operátoři; viz Queinnec[11] pro průzkum.

Podívejme se na složitější příklad. Nechat nula být prázdný seznam:

 (resetovat   (začít     (posun k (nevýhody 1 (k (prázdnota)))) ;; (1)     nula))

Kontext zachycený posun je (začátek [*] null), kde [*] je díra, kde kBude vložen parametr. První volání k uvnitř posun hodnotí v tomto kontextu s (neplatné) = # výměna díry, takže hodnota (k (neplatné)) je (začátek # null) = nula. Tělo posun, jmenovitě (nevýhody 1 null) = (1), se stává celkovou hodnotou resetovat výraz jako konečný výsledek.

Aby byl tento příklad komplikovanější, přidejte řádek:

 (resetovat   (začít     (posun k (nevýhody 1 (k (prázdnota))))     (posun k (nevýhody 2 (k (prázdnota))))     nula))

Pokud komentujeme první posun, výsledek už známe, je (2); takže můžeme také přepsat výraz takto:

 (resetovat   (začít     (posun k (nevýhody 1 (k (prázdnota))))     (seznam 2)))

To je docela dobře známé a lze to přepsat jako (nevýhody 1 (seznam 2)), to znamená, (seznam 1 2).

Můžeme definovat výtěžek pomocí tohoto triku:

(define (yield x) (shift k (cons x (k (void))))))

a použít jej v seznamech budov:

 (resetovat (začít          (výtěžek 1)          (výtěžek 2)          (výtěžek 3)          nula))    ;; (seznam 1 2 3)

Pokud vyměníme nevýhody s stream-cons, můžeme stavět líné streamy:

  (definovat (proudový výnos X) (posun k (stream-cons X (k (prázdnota)))))  (definovat líný příklad    (resetovat (začít            (proudový výnos 1)            (proudový výnos 2)            (proudový výnos 3)            stream-null)))

Můžeme to zobecnit a převést seznamy na stream, a to jedním tahem:

 (definovat (seznam-> stream xs)   (resetovat (začít            (pro každého proudový výnos xs)            stream-null)))

Ve složitějším příkladu níže může být pokračování bezpečně zabaleno do těla lambdy a použito jako takové:

 (definovat (for-each-> stream-maker pro každého)    (lambda (sbírka)      (resetovat (začít               (pro každého (lambda (živel)                           (posun k                             (stream-cons živel (k 'ignorováno))))                         sbírka)               stream-null))))

Část mezi resetovat a posun zahrnuje ovládací funkce jako lambda a pro každého; to není možné přeformulovat pomocí lambdas[proč? ].

Oddělovaná pokračování jsou také užitečná v lingvistika: viz Pokračování v lingvistice pro detaily.

Reference

  1. ^ A b Matthias Felleisen (1988). „Teorie a praxe prvotřídních výzev“. Principy programovacích jazyků: 180–190. doi:10.1145/73560.73576. ISBN  0-89791-252-7.
  2. ^ A b Felleisen; Friedman; Duba; Merrill (1987). Za pokračováním (Technická zpráva). Indiana University. 87-216.
  3. ^ Matthias Felleisen (1987). Kalkul konverze Lambda-v-CS: syntaktická teorie kontroly a stavu v imperativních programovacích jazycích vyšších řádů (PDF) (Teze).
  4. ^ Sitaram, Dorai; Felleisen, Matthias (1990). „Control Delimiters and their Hierarchies“ (PDF). Lisp a symbolický výpočet.
  5. ^ A b Olivier Danvy; Andrzej Filinski (1990). "Řízení abstrahování". LISP a funkční programování: 151–160. doi:10.1145/91556.91622. ISBN  0-89791-368-X.
  6. ^ Gunter; Rémy; Riecke (1995). "Zobecnění výjimek a ovládání v jazycích podobných ML". Funkční programovací jazyky a počítačová architektura.
  7. ^ Podívejte se například na operátory, které nabízí raketa / ovládání Raketa knihovna [1]; následující příklady lze spustit v Racket pomocí (vyžaduje raketu / ovládání)
  8. ^ Gasbichler, Martin; Sperber, Michael (2002). "Final Shift for Call / cc: Direct Implementation of Shift and Reset". CiteSeerX  10.1.1.11.3425. Citovat deník vyžaduje | deník = (Pomoc)
  9. ^ Felleisen, Matthias; Friedman, Daniel P .; Duba, Bruce; Marrill, John (únor 1987). „Nad rámec pokračování“ (PDF). Technická zpráva 216. Oddělení informatiky, Indiana University. Citovat deník vyžaduje | deník = (Pomoc)
  10. ^ Johnson, Gregory F. (červen 1987). "GL: denotační testbed s pokračováním a částečným pokračováním". Proc. SIGPLAN '87 Symposium on Interpreters and Interpretive Techniques. 218–225.
  11. ^ Queinnec, Christian (duben 1994). "Knihovna řídících operátorů na vysoké úrovni". École Polytechnique a INRIA -Rocquencourt. CiteSeerX  10.1.1.29.4790. Citovat deník vyžaduje | deník = (Pomoc)

externí odkazy