Pokračování hovoru s proudem - Call-with-current-continuation
v programování s jazykem Systém, podprogram nebo funkce pokračování hovoru s proudem, zkráceně call / cc, se používá jako regulační tok operátor. Byl přijat několika dalšími programovacími jazyky.
Převzetí funkce F
jako jediný argument, (call / cc f)
ve výrazu se použije na aktuální pokračování například výrazu ((call / cc f) e2)
je ekvivalentní žádosti F
k aktuálnímu pokračování výrazu. Aktuální pokračování je dáno nahrazením (call / cc f)
proměnnou C
vázán lambda abstrakcí, takže aktuální pokračování je (lambda (c) (c e2))
. Použití funkce F
dává konečný výsledek (f (lambda (c) (c e2)))
.
Jako doplňkový příklad ve výrazu (e1 (call / cc f))
, pokračování sub-výrazu (call / cc f)
je (lambda (c) (e1 c))
, takže celý výraz je ekvivalentní (f (lambda (c) (e1 c)))
Jinými slovy, pořizuje „snímek“ aktuálního kontextu ovládání nebo stavu ovládání programu jako objekt a použije se F
k tomu. Objekt pokračování je a prvotřídní hodnota a je reprezentován jako funkce s funkční aplikace jako jeho jediná operace. Když se na argument použije objekt pokračování, stávající pokračování se eliminuje a aplikované pokračování se obnoví na jeho místo, takže tok programu bude pokračovat v bodě, ve kterém bylo zachyceno pokračování, a argument pokračování pak se stane „návratovou hodnotou“ volání volání / kopie. Pokračování vytvořená pomocí call / cc lze volat vícekrát, a to i mimo dynamický rozsah aplikace call / cc.
V informatice se zviditelnění tohoto typu implicitního stavu programu jako objektu nazývá reifikace. (Systém syntakticky nerozlišuje mezi použitím pokračování nebo funkcí.)
Pomocí call / cc lze implementovat celou řadu složitých řídicích operátorů z jiných jazyků pomocí několika řádků kódu, např. McCarthy je amb
operátor pro nedeterministická volba, Prolog -styl ustoupit, Simula 67 stylů coutiny a jejich zobecnění, Ikona -styl generátory nebo motory a vlákna nebo dokonce temný ODCHOD.
Příklady
Jak ukazuje následující příklad, call / cc lze použít k emulaci funkce návratové prohlášení známý z C -styl jazyky, které chybí Systém:
(definovat (F vrátit se) (vrátit se 2) 3)(Zobrazit (F (lambda (X) X))) ; zobrazí 3(Zobrazit (pokračování hovoru s proudem F)) ; zobrazí 2
Povolání F s argumentem pravidelné funkce nejprve použije tuto funkci na hodnotu 2, poté vrátí 3. Nicméně, když F je předán call / cc (jako v posledním řádku příkladu), použití parametru (pokračování) na 2 vynutí provedení programu tak, aby skočil do bodu, kde bylo voláno call / cc, a způsobí návrat call / cc hodnota 2. Tato je poté vytištěna funkcí displeje.
V dalším příkladu se call / cc používá dvakrát: jednou ke generování "návratového" pokračování jako v prvním příkladu a jednou k pozastavení iterace prostřednictvím seznamu položek:
;; [LISTOF X] -> (-> X u 'you-fall-off-the-end)(definovat (generovat-jeden-prvek-v-čase první) ;; Obě vnitřní funkce jsou uzávěry nad první ;; Interní proměnná / funkce, která předává aktuální prvek v seznamu ;; na jeho návratový argument (což je pokračování) nebo předá značku konce seznamu ;; pokud nezůstanou žádné další prvky. V každém kroku je název funkce ;; odskočit na pokračování, které ukazuje zpět do funkčního těla, ;; zatímco návrat se odskočí na jakékoli pokračování, které volající určí. (definovat (kontrolní stav vrátit se) (pro každého (lambda (živel) (soubor! vrátit se (pokračování hovoru s proudem (lambda (pokračovat zde) ;; Chyťte aktuální pokračování (soubor! kontrolní stav pokračovat zde) (vrátit se živel))))) ;; (návratový prvek) se vyhodnotí na další návrat první) (vrátit se „spadl jsi na konec)) ;; (-> X u 'you-fall-off-the-end) ;; Toto je skutečný generátor, který produkuje jednu položku ze seznamu najednou. (definovat (generátor) (pokračování hovoru s proudem kontrolní stav)) ;; Vraťte generátor generátor)(definovat generovat číslici (generovat-jeden-prvek-v-čase '(0 1 2)))(generovat číslici) ;; 0(generovat číslici) ;; 1(generovat číslici) ;; 2(generovat číslici) ;; ty jsi spadl-na-konec
Pokaždé, když smyčka chystá zpracovat další položku ze seznamu, funkce popadne aktuální pokračování a přiřadí ji proměnné 'control-state'. Tato proměnná je zpočátku uzavření který iteruje všemi prvky seznamu. Jak výpočet postupuje, stává se uzávěrkou, která iteruje příponou daného seznamu. Zatímco použití "call / cc" je pro lineární sběr zbytečné, jako např [LISTOF X]
, kód zobecňuje na žádný kolekce, kterou lze procházet.
Pokračování volání s proudem může také vyjádřit další sofistikovaná primitiva. Například další ukázka provádí kooperativní multitasking pomocí pokračování:
;; Kooperativní multitasking využívající pokračování hovoru s proudem;; ve 25 řádcích schématu;; Seznam vláken čekajících na spuštění. Toto je seznam jednoho;; funkce nevrácení argumentů (většinou pokračování);; Pokračování je nevracející se funkce, stejně jako (exit),;; v tom, že se nikdy nevzdává kontroly nad tím, čemu se to říká.(definovat připravený seznam '());; Funkce nevracející se. Pokud existuje nějaké jiné vlákno;; čeká na spuštění, způsobí spuštění dalšího vlákna, pokud existuje;; je ponecháno ke spuštění, jinak volá původní exit;; který opouští celé prostředí.(definovat výstup ;; Původní východ, který přepíšeme. (nechat ((výstup výstup)) ;; Prvořadá funkce. (lambda () (-li (ne (nula? připravený seznam)) ;; Na spuštění čeká další vlákno. ;; Takže to spustíme. (nechat ((pokr (auto připravený seznam))) (soubor! připravený seznam (cdr připravený seznam)) ;; Protože seznam připravených položek se nevrací ;; funkce se to nevrátí. (pokr #F)) ;; Nic nezbylo k běhu. ;; Originál (exit) je nevracející se funkce, ;; takže se jedná o nevracející se funkci. (výstup)))));; Vezme funkci jednoho argumentu s daným;; hádka a rozdvojuje to. Vidlicová funkce je nová;; podproces bude ukončen, pokud / kdy dojde k ukončení funkce.(definovat (Vidlička fn arg) (soubor! připravený seznam (připojit připravený seznam ;; Tato funkce byla přidána do ;; připravený seznam se nevrací, ;; protože východ se nevrací. (seznam (lambda (X) (fn arg) (výstup))))));; Poskytuje kontrolu nad dalším vláknem, které čeká na spuštění.;; Ačkoli se nakonec vrátí, vzdává se kontroly;; a znovu ji získá, až když bude vyvoláno pokračování.(definovat (výtěžek) (pokračování hovoru s proudem ;; Zachyťte pokračování představující TOTO volání (lambda (pokr) ;; Nalepte jej na seznam připravených položek (soubor! připravený seznam (připojit připravený seznam (seznam pokr))) ;; Získejte další vlákno a spusťte jej. (nechat ((pokr (auto připravený seznam))) (soubor! připravený seznam (cdr připravený seznam)) ;; Spusť to. (pokr #F)))))
V roce 1999 David Madore (vynálezce Unlambda Programovací jazyk) našel 12 znaků v termínu Unlambda s povoleným callcc, který má stejný účinek (zápis všech celých čísel v unární formě) více než 600 znaků v Unlambda bez volání / cc.[1] Při převodu tohoto výrazu na Schéma získal programový program známý jako puzzle jin-jang. Poté bylo zvykem ukázat se při diskusi o call / cc:[2]
(nechat* ((jin ((lambda (cc) (Zobrazit #\@) cc) (pokračování hovoru s proudem (lambda (C) C)))) (jang ((lambda (cc) (Zobrazit #\*) cc) (pokračování hovoru s proudem (lambda (C) C))))) (jin jang))
Ilustrace hádanky: Každé prohlášení mezi závorkami je stav jin a jang bezprostředně před ním (Yin Yang)
; Číslo znamená, zda 1. pokračování nebo 2. skok. Výrok za číslem představuje kontext.
;@*[(jin 1 ()) (jang 2 (jin 1 ()))];@*[(jin 2 (jin 1 ()))(jang 2 (jin 2 (jin 1 ())))];*[(jin 1 ())(jang 2 (jin 2 (jin 1 ())))];@*[(jin 2 (jin 2 (jin 1 ())))(jang 2 (jin 2 (jin 2 (jin 1 ()))))];*[(jin 2 (jin 1 ()))(jang 2 (jin 2 (jin 2 (jin 1 ()))))];*[(jin 1 ())(jang 2 (jin 2 (jin 2 (jin 1 ()))))];@*[(jin 2 (jin 2 (jin 2 (jin 1 ()))))(jang 2 (jin 2 (jin 2 (jin 2 (jin 1 ())))))];...;...
Kritika
Oleg Kiselyov, autor a ohraničené pokračování implementace pro OCaml a designér společnosti aplikační programovací rozhraní (API) pro manipulaci s oddělovanými zásobníky k implementaci řídicích operátorů, obhajuje použití ohraničená pokračování místo pokračování full-stacku, s nimiž manipuluje call / cc: "Nabídka call / cc jako základní funkce ovládání, ve smyslu které by měla být implementována všechna ostatní ovládací zařízení, se ukazuje jako špatný nápad. Únik výkonu, paměti a zdrojů, snadná implementace , snadné použití, snadné uvažování - to vše argumentuje proti call / cc. “[3]
Vztah k nekonstruktivní logice
The Curry – Howardova korespondence mezi důkazy a programy souvisí call / cc na Peirceův zákon, který se rozšiřuje intuicionistická logika na nekonstruktivní, klasická logika: ((α → β) → α) → α. Zde ((α → β) → α) je typ funkce F, který může buď přímo vrátit hodnotu typu α, nebo použít argument na pokračování typu (α → β). Vzhledem k tomu, že existující kontext je odstraněn při použití pokračování, typ β se nikdy nepoužívá a lze jej považovat za the, prázdný typ.
Princip eliminace dvojí negace ((α → ⊥) → ⊥) → α je srovnatelná s variantou call-cc, která očekává její argument F vždy vyhodnotit aktuální pokračování bez normálního vrácení hodnoty. Vložení klasické logiky do intuitivní logiky souvisí s pokračování procházející styl překlad.[4]
Jazyky implementující hovor / kopie
Viz také
Reference
- ^ David Madore, „call / cc mind-boggler“
- ^ Yin Wang, „Porozumění logice Yin-Yang“
- ^ "Argument proti volání / kopie".
- ^ Sørensen, Morten Heine; Urzyczyn, Paweł (2007). "Klasické logické a řídicí operátory". Přednášky o izomorfismu Curry-Howarda (1. vyd.). Boston, MA: Elsevier. ISBN 0444520775.
- ^ „Podpis CONT“. Standardní ML z New Jersey. Bell Labs, Lucent Technologies. 1997-10-28. Citováno 2019-05-15.
- ^ „Třída: Pokračování“. Ruby-doc.org. Neurogami, James Britt. Citováno 2019-05-15.
- ^ Kowalke, Oliver (2014). "Přepínání kontextu s hovorem / kopie". Boost.org. Citováno 2019-05-15.
- ^ https://stat.ethz.ch/R-manual/R-devel/library/base/html/callCC.html
externí odkazy
- Krátký úvod do
pokračování hovoru s proudem
- Definice
pokračování hovoru s proudem
ve schématu spec - Vtipné vysvětlení pokračování hovoru s proudem od Roba Warnocka v Usenetu comp.lang.lisp
- Kooperativní multitasking ve schématu pomocí Call-CC
Tento článek je založen na materiálu převzatém z Zdarma on-line slovník výpočetní techniky před 1. listopadem 2008 a začleněno pod "licencování" podmínek GFDL, verze 1.3 nebo novější.