Budoucnost a sliby - Futures and promises

Nesmí být zaměňována s teorií slibů .

V počítačové vědě se budoucí , slibné , zpožděné a odložené odkazuje na konstrukce používané pro synchronizaci provádění programu v některých souběžných programovacích jazycích . Popisují objekt, který funguje jako proxy pro původně neznámý výsledek, obvykle proto, že výpočet jeho hodnoty ještě není dokončen.

Termín slib navrhli v roce 1976 Daniel P. Friedman a David Wise a Peter Hibbard jej označil za eventuální . Poněkud podobný koncept budoucnosti byl představen v roce 1977 v příspěvku Henryho Bakera a Carla Hewitta .

Pojmy budoucnost , příslib , zpoždění a odložený termín jsou často používány zaměnitelně, ačkoli některé rozdíly v používání mezi budoucností a příslibem jsou popsány níže. Konkrétně, když se rozlišuje použití, budoucnost je zástupný pohled proměnné pouze na čtení , zatímco příslib je zapisovatelný kontejner s jediným přiřazením, který nastavuje hodnotu budoucnosti. Je pozoruhodné, že budoucnost může být definována bez určení, který konkrétní příslib stanoví její hodnotu, a různé možné sliby mohou stanovit hodnotu dané budoucnosti, ačkoli to lze pro danou budoucnost provést pouze jednou. V ostatních případech se budoucnost a příslib vytvářejí společně a jsou navzájem spojeny: budoucnost je hodnota, příslib je funkce, která nastavuje hodnotu - v podstatě návratovou hodnotu (budoucnost) asynchronní funkce (příslib). Nastavení hodnoty budoucnosti se také nazývá její vyřešení , naplnění nebo svazování .

Aplikace

Futures a sliby vznikly ve funkčním programování a souvisejících paradigmatech (jako je logické programování ) za účelem oddělení hodnoty (budoucnosti) od toho, jak byla vypočítána (příslib), což umožňuje provádět výpočty flexibilněji, zejména jejich paralelizací. Později našel využití v distribuovaných počítačích , při snižování latence komunikačních okružních jízd. Později získal větší využití tím, že umožnil psaní asynchronních programů v přímém stylu , spíše než ve stylu předávání pokračování .

Implicitní vs. explicitní

Použití futures může být implicitní (jakékoli použití budoucnosti automaticky získá svou hodnotu, jako by to byla běžná reference ) nebo explicitní (uživatel musí pro získání hodnoty zavolat funkci, jako je getmetoda java.util.concurrent.Futurev Javě ). Získání hodnoty explicitní budoucnosti lze nazvat bodnutí nebo vynucení . Explicitní futures lze implementovat jako knihovnu, zatímco implicitní futures jsou obvykle implementovány jako součást jazyka.

Původní papír Baker a Hewitt popisoval implicitní futures, které jsou přirozeně podporovány herním modelem výpočtu a čistě objektově orientovanými programovacími jazyky, jako je Smalltalk . Dokument Friedmana a Wise popisoval pouze explicitní futures, pravděpodobně odrážející obtížnost efektivní implementace implicitních futures na akciový hardware. Potíž je v tom, že akciový hardware se nezabývá futures pro primitivní datové typy, jako jsou celá čísla. Například instrukce přidání neví, jak se vypořádat . V čistých herních nebo objektových jazycích lze tento problém vyřešit odesláním zprávy , která žádá budoucnost, aby se přidala k sobě a vrátila výsledek. Všimněte si toho, že přístup předávání zpráv funguje bez ohledu na to, kdy skončí výpočet a že není nutné žádné píchání/vynucování. 3 + future factorial(100000)future factorial(100000)+[3]3factorial(100000)

Slibujte potrubí

Použití futures může dramaticky snížit latenci v distribuovaných systémech . Například futures umožňují slibné propojení , jak je implementováno v jazycích E a Joule , kterému se také v jazyce Argus říkalo call-stream .

Zvažte výraz zahrnující konvenční vzdálená volání procedur , jako například: 

 t3 := ( x.a() ).c( y.b() )

které by bylo možné rozšířit na 

 t1 := x.a();
 t2 := y.b();
 t3 := t1.c(t2);

Každé prohlášení vyžaduje odeslání zprávy a přijetí odpovědi, než může pokračovat další prohlášení. Předpokládejme například, že x, y, t1a t2jsou umístěny na stejném vzdáleném stroji. V tomto případě musí proběhnout dvě kompletní síťové okružní jízdy na tento počítač, než se může spustit třetí příkaz. Třetí prohlášení pak způsobí další zpáteční cestu na stejný vzdálený počítač.

Pomocí futures by se dal napsat výše uvedený výraz 

 t3 := (x <- a()) <- c(y <- b())

které by bylo možné rozšířit na 

 t1 := x <- a();
 t2 := y <- b();
 t3 := t1 <- c(t2);

Zde je použita syntaxe jazyka E, kde x <- a()znamená odeslat zprávu a()asynchronně x. Všem třem proměnným jsou okamžitě přiřazeny futures pro jejich výsledky a provedení pokračuje v následujících výkazech. Pozdější pokusy o vyřešení hodnoty t3mohou způsobit zpoždění; potrubí však může snížit počet potřebných zpátečních letů. V případě, stejně jako v předchozím příkladu x, y, t1a t2jsou umístěny na stejném vzdáleném počítači, pipeline implementace může počítat t3s jednou zpáteční namísto tří. Protože všechny tři zprávy jsou určeny pro objekty, které jsou na stejném vzdáleném počítači, je třeba odeslat pouze jeden požadavek a přijmout pouze jednu odpověď obsahující výsledek. Odesílání t1 <- c(t2)by neblokovalo, i kdyby t1a t2byly na různých strojích navzájem, nebo na xnebo y.

Promise pipelining by mělo být odlišeno od paralelního asynchronního předávání zpráv. V systému podporujícím paralelní zasílání zpráv, ale ne zřetězení, zpráva vysílá x <- a()i y <- b()ve výše uvedeném příkladu by mohl probíhat souběžně, ale send ze t1 <- c(t2)bude muset počkat, dokud obě t1a t2byl přijat, i když x, y, t1a t2jsou na stejné dálkové ovládání stroj. Výhoda relativní latence pipeline je ještě větší v komplikovanějších situacích zahrnujících mnoho zpráv.

Promise pipelining by také nemělo být zaměňováno se zpracováním pipeline zpráv v herních systémech, kde je možné, aby herec určil a zahájil provádění chování pro další zprávu před dokončením zpracování aktuální zprávy.

Zobrazení pouze pro čtení

V některých programovacích jazycích, jako je Oz , E a AmbientTalk , je možné získat pohled budoucnosti pouze pro čtení, který umožňuje čtení jeho hodnoty při vyřešení, ale neumožňuje jeho vyřešení:

  • V Oz se !!operátor používá k získání zobrazení jen pro čtení.
  • V E a AmbientTalk je budoucnost reprezentována dvojicí hodnot nazývaných dvojice slib/resolver . Slib představuje pohled jen pro čtení a k nastavení hodnoty budoucnosti je potřeba překladač.
  • V C ++ 11 a std::futureposkytuje zobrazení jen pro čtení. Hodnota je nastavena přímo pomocí a std::promise, nebo je nastavena na výsledek volání funkce pomocí std::packaged_tasknebo std::async.
  • V Odloženém rozhraní API Dojo Toolkit od verze 1.5 objekt slib pouze pro spotřebitele představuje zobrazení jen pro čtení.
  • V Alice ML futures poskytují pohled jen pro čtení , zatímco slib obsahuje budoucnost i schopnost vyřešit budoucnost
  • V rozhraní .NET Framework 4.0 System.Threading.Tasks.Task<T> představuje zobrazení jen pro čtení. Vyřešení hodnoty lze provést pomocí System.Threading.Tasks.TaskCompletionSource<T>.

Podpora zobrazení jen pro čtení je v souladu se zásadou nejmenších oprávnění , protože umožňuje omezit možnost nastavení hodnoty na subjekty, které ji potřebují nastavit. V systému, který také podporuje pipelining, odesílatel asynchronní zprávy (s výsledkem) obdrží příslib jen pro čtení pro výsledek a cíl zprávy obdrží resolver.

Futures specifické pro vlákna

Některé jazyky, například Alice ML , definují futures, které jsou spojeny s konkrétním vláknem, které vypočítává hodnotu budoucnosti. Tento výpočet může začít buď dychtivě, když je vytvořena budoucnost, nebo líně, když je poprvé potřeba jeho hodnota. Líná budoucnost je podobná thunk , ve smyslu zpožděného výpočtu.

Alice ML také podporuje futures, které lze vyřešit jakýmkoli vláknem, a nazývá tyto sliby . Toto použití slibu se liší od jeho použití v E, jak je popsáno výše . V Alice není slib jen pro čtení a pipelining slibu není podporován. Místo toho se u futures přirozeně děje pipeline, včetně těch spojených se sliby.

Blokování vs neblokující sémantika

Pokud se k hodnotě budoucnosti přistupuje asynchronně, například odesláním zprávy do ní nebo výslovným čekáním na ni pomocí konstruktu, jako je například whenE, pak není problém oddálit, dokud se budoucnost nevyřeší, než bude možné zprávu zpracovat. přijato nebo se čekání dokončí. Toto je jediný případ, který je třeba vzít v úvahu v čistě asynchronních systémech, jako jsou čistě herecké jazyky.

V některých systémech je však také možné pokusit se o okamžitý nebo synchronní přístup k hodnotě budoucnosti. Pak je třeba zvolit design:

  • přístup by mohl blokovat aktuální vlákno nebo proces, dokud nebude vyřešena budoucnost (případně s časovým limitem). Toto je sémantika proměnných toku dat v jazyce Oz .
  • pokus o synchronní přístup může vždy signalizovat chybu, například vyvolání výjimky . Toto je sémantika vzdálených slibů v E.
  • potenciálně by přístup mohl uspět, pokud je budoucnost již vyřešena, ale signalizuje chybu, pokud není. To by mělo tu nevýhodu, že by se zavedl nedeterminismus a potenciál pro závodní podmínky , a zdá se, že jde o neobvyklou volbu designu.

Jako příklad první možnosti lze v C ++ 11 blokovat vlákno, které potřebuje hodnotu budoucnosti, dokud není k dispozici voláním funkce wait()nebo get(). Můžete také určit časový limit při čekání pomocí funkcí wait_for()nebo wait_until()členské funkce, abyste se vyhnuli blokování na neurčito. Pokud budoucnost vzešla z volání std::asyncblokování čekání (bez časového limitu), může způsobit synchronní vyvolání funkce pro výpočet výsledku v čekajícím vlákně.

Související konstrukce

Future je zvláštní případ události (synchronizační primitivum) , kterou lze dokončit pouze jednou. Obecně lze události resetovat do počátečního prázdného stavu, a proto je lze dokončit tolikrát, kolikrát chcete.

I-var (jako v jazyce Id ) je budoucí s blokací sémantiku, jak je definováno výše. I-struktura je struktura dat obsahující I-proměnnými. Související synchronizační konstrukt, který lze nastavit vícekrát s různými hodnotami, se nazývá M-var . M-vars podporují atomové operace k převzetí nebo vložení aktuální hodnoty, přičemž při převzetí hodnoty se také M-var vrátí do původního prázdného stavu.

Souběžné logická proměnná je podobný budoucnosti, ale je aktualizován sjednocení , stejně jako logické proměnné v logickém programování . Může být tedy vázán více než jednou na sjednocující hodnoty, ale nelze jej vrátit zpět do prázdného nebo nevyřešeného stavu. Proměnné toku dat Oz působí jako souběžné logické proměnné a mají také sémantiku blokování, jak je uvedeno výše.

Souběžné omezení proměnná je zobecněním souběžných logických proměnných, které mají podpořit Logické programování : Podmínka může být zúžen vícekrát, což znamená menší sady možných hodnot. Obvykle existuje způsob, jak určit thunk, který by měl běžet, kdykoli se omezení ještě zúží; je to nutné pro podporu šíření omezení .

Vztahy mezi expresivitou různých forem budoucnosti

Dychtivé futures specifické pro vlákna lze snadno implementovat do futures nespecifických pro vlákna, vytvořením vlákna pro výpočet hodnoty současně s vytvářením budoucnosti. V tomto případě je žádoucí vrátit pohled jen pro čtení klientovi, aby tuto budoucnost mohl vyřešit pouze nově vytvořený podproces.

Aby bylo možné implementovat implicitní líné futures specifické pro vlákna (jak je poskytována například Alice ML) v termínech pro futures nespecifické pro vlákna, potřebuje mechanismus k určení, kdy je hodnota budoucnosti poprvé potřeba (například WaitNeededkonstrukce v Oz). Pokud jsou všechny hodnoty objekty, pak je schopnost implementovat transparentní předávací objekty dostačující, protože první zpráva odeslaná do předávacího programu naznačuje, že je zapotřebí hodnota budoucnosti.

Futures nespecifické pro vlákna lze implementovat do futures specifických pro vlákna za předpokladu, že systém podporuje předávání zpráv, a to tak, že rozhodující vlákno odešle zprávu do vlastního vlákna budoucnosti. To lze však považovat za nepotřebnou složitost. V programovacích jazycích založených na vláknech se jeví jako nejexpresivnější přístup poskytnout kombinaci futures, které nejsou specifické pro vlákna, pohledy pouze pro čtení a buď konstrukci WaitNeeded , nebo podporu transparentního předávání.

Strategie hodnocení

Další informace: Volejte do budoucna

Strategie hodnocení futures, která může být nazývána voláním podle budoucnosti , je nedeterministická: hodnota budoucnosti bude hodnocena v určitém čase mezi vytvořením budoucnosti a použitím její hodnoty, ale přesný čas není určen. předem a může se změnit z běhu na běh. Výpočet může začít, jakmile je vytvořena budoucnost ( dychtivé hodnocení ) nebo pouze tehdy, když je hodnota skutečně potřebná ( opožděné hodnocení ), a může být pozastaveno na částečné cestě nebo provedeno v jednom běhu. Jakmile je hodnota budoucnosti přiřazena, není při budoucích přístupech přepočítávána; je to jako memoizace používaná při volání podle potřeby .

A líná budoucnost je budoucnost, která má deterministicky línou sémantiku hodnocení: výpočet hodnoty budoucnosti začíná, když je hodnota nejprve potřeba, jako při volání podle potřeby. Lazy futures se používají v jazycích, jejichž strategie hodnocení není ve výchozím nastavení líná. Například vC ++ 11 lzetakové líné futures vytvořit předáním zásadystd::launch::deferredspouštěnístd::async, spolu s funkcí pro výpočet hodnoty.

Sémantika budoucnosti v hereckém modelu

V hereckém modelu je výraz formuláře future <Expression>definován tím, jak reaguje na Evalzprávu s prostředím E a zákazníkem C následovně: Budoucí výraz reaguje na Evalzprávu odesláním zákazníkovi C nově vytvořeného herce F (proxy pro reakce vyhodnocení <Expression>) jako návratová hodnota souběžně s odesláním <Expression>k Evalzprávu se prostředí E a zákaznickou C . Výchozí chování F je následující:

  • Když F obdrží požadavek R , pak zkontroluje, zda již obdržel odpověď (to může být buď návratová hodnota nebo vyvolaná výjimka) z vyhodnocování, <Expression>jak postupuje takto:
    1. Pokud již má odpověď V , pak
      • Jestliže V je návratová hodnota, pak je poslal požadavek R .
      • Jestliže V je výjimka, pak je hozen k zákazníkovi na vyžádání R .
    2. Pokud to ještě nemá odpověď, pak R je uložen ve frontě žádostí uvnitř F .
  • Když F obdrží odpověď V z vyhodnocení <Expression>, pak je V uloženo do F a
    • Jestliže V je návratová hodnota, pak všichni ve frontě požadavků jsou odesílány do V. .
    • Pokud je V výjimkou, pak je zákazníkovi vyvolána u každého z požadavků ve frontě.

Některé futures však mohou řešit požadavky zvláštními způsoby, aby zajistily větší paralelismus. Výraz například 1 + future factorial(n)může vytvořit novou budoucnost, která se bude chovat jako číslo 1+factorial(n). Tento trik nefunguje vždy. Například následující podmíněný výraz:

if m>future factorial(n) then print("bigger") else print("smaller")

pozastaví, dokud budoucnost pro factorial(n)neodpověděla na žádost s dotazem, zda mje větší než ona sama.

Dějiny

Konstrukce budoucnosti a/nebo příslibu byly poprvé implementovány v programovacích jazycích, jako je MultiLisp a zákon 1 . Použití logických proměnných pro komunikaci v souběžných logických programovacích jazycích bylo docela podobné futures. Ty začaly v Prologu Freeze a IC Prolog a staly se skutečným souběžným primitivem s Relational Language, Concurrent Prolog , hlídanými klaksony Horn (GHC), Parlog , Strand , Vulcan , Janus , Oz-Mozart , Flow Java a Alice ML . Jednolodní přiřazení I-var od dataflow programovací jazyky, pocházející z Id a jsou zahrnuty v Reppy je souběžná ML , je podobně jako souběžné logické proměnné.

Slibovou techniku ​​pipeline (využívající futures k překonání latence) vynalezli Barbara Liskov a Liuba Shrira v roce 1988 a nezávisle Mark S. Miller , Dean Tribble a Rob Jellinghaus v kontextu projektu Xanadu kolem roku 1989.

Termín příslib vymysleli Liskov a Shrira, přestože na mechanismus pipeline odkazovali názvem call-stream , který se nyní používá jen zřídka.

Jak design popsaný v Liskovově a Shriřině dokumentu, tak implementace slibu v Xanadu měly limit, že slibné hodnoty nebyly prvotřídní : argument nebo hodnota vrácená hovorem nebo odesláním nemohla být přímo příslibem (takže příklad dřívějšího slibu, který používá příslib pro výsledek jednoho odeslání jako argument pro jiný, by nebyl přímo vyjádřen v návrhu toku volání nebo v implementaci Xanadu). Zdá se, že sliby a toky volání nebyly nikdy implementovány v žádném veřejném vydání Argusu, programovacího jazyka používaného v liscích Liskov a Shrira. Vývoj Argusu se zastavil kolem roku 1988. Xanaduská implementace slibu pipelining se stala veřejně dostupnou až po vydání zdrojového kódu pro Udanax Gold v roce 1999 a v žádném publikovaném dokumentu nebyla nikdy vysvětlena. Pozdější implementace v Joule a E plně podporují prvotřídní sliby a řešení.

Několik raných aktérských jazyků, včetně řady Act, podporovalo jak souběžné předávání zpráv, tak i zpracování zpráv přes pipeline, ale neslibovalo pipelining. (I když je technicky možné implementovat poslední z těchto funkcí do prvních dvou, neexistuje žádný důkaz, že by tak činily jazyky zákona.)

Po roce 2000, hlavní oživení zájmu o futures a slibů došlo v důsledku jejich použití v odezvy uživatelského rozhraní, a vývoj webových aplikací , vzhledem k požadavku odezvy modelu předávání zpráv. Několik hlavních jazyků má nyní jazykovou podporu pro futures a sliby, zejména popularizované FutureTaskv Javě 5 (oznámeno 2004) a asynchronní/čekající konstrukce v .NET 4.5 (oznámeno 2010, vydáno 2012) do značné míry inspirováno asynchronními pracovními toky F#, které se datuje do roku 2007. To bylo následně přijato jinými jazyky, zejména Dart (2014), Python (2015), Hack (HHVM) a koncepty ECMAScript 7 (JavaScript), Scala a C ++.

Seznam implementací

Některé programovací jazyky podporují futures, sliby, souběžné logické proměnné, proměnné toku dat nebo I-vary, a to buď pomocí přímé jazykové podpory, nebo ve standardní knihovně.

Seznam konceptů souvisejících s futures a sliby podle programovacího jazyka

Mezi jazyky podporující také slibné pipeline patří:

Seznam nestandardních implementací futures založených na knihovně

  • Pro Common Lisp :
    • Kos
    • Dychtivá budoucnost 2
    • paralelně
    • PCall
  • Pro C ++:
  • Pro C # a další .NET jazyky: The Parallel rozšíření knihovny
  • Pro Groovy : GPars
  • Pro JavaScript :
  • Pro Javu :
    • JDeferred, poskytuje API s odloženým slibem a chování podobné objektu JQuery .Deferred
    • ParSeq poskytuje API slibující úkoly, ideální pro asynchronní pipeline a větvení, spravované společností LinkedIn
  • Pro Lua :
    • Modul cqueues [1] obsahuje API Promise.
  • Pro Objective-C : MAFuture, RXPromise, ObjC-CollapsingFutures, PromiseKit, objc-slib, OAPromise,
  • Pro OCaml : Lazy modul implementuje líné explicitní futures
  • Pro Perl : Future, Promises, Reflex, Promise :: ES6 a Promise :: XS
  • Pro PHP : Reagovat/Slibovat
  • Pro Python :
    • Integrovaná implementace
    • pythonfutures
    • Twisted's Deferreds
  • Pro R :
    • budoucnost, implementuje rozšiřitelné budoucí API s línými a dychtivými synchronními a (vícejádrovými nebo distribuovanými) asynchronními futures
  • Pro Ruby :
    • Slib drahokam
    • libuv drahokam, plní sliby
    • Celluloidový drahokam, implementuje futures
    • budoucí zdroj
  • Pro Rust :
    • futures-rs
  • Pro Scala :
    • Knihovna nástrojů Twitter
  • Pro Swift :
    • Asynchronní framework implementuje styl C# async/neblokujícíawait
    • FutureKit, implementuje verzi pro Apple GCD
    • FutureLib, čistá knihovna Swift 2 implementující futures a sliby ve stylu Scala se zrušením ve stylu TPL
    • Odložená, čistá knihovna Swift inspirovaná OCaml's Deferred
    • BrightFutures
    • SwiftCoroutine
  • Pro Tcl : tcl-slib

Coroutines

Futures lze implementovat do coroutines nebo generátorů , což má za následek stejnou strategii hodnocení (např. Kooperativní multitasking nebo líné hodnocení).

Kanály

Hlavní článek: Channel (programování)

Futures lze snadno implementovat do kanálů : budoucnost je kanál s jedním prvkem a příslib je proces, který do kanálu odešle a naplní budoucnost. To umožňuje implementaci futures v souběžných programovacích jazycích s podporou kanálů, jako je CSP a Go . Výsledné futures jsou explicitní, protože k nim musí být přistupováno čtením z kanálu, nikoli pouze hodnocením.

Viz také

Reference

externí odkazy