Strategie hodnocení - Evaluation strategy

V programovacím jazyce je strategie hodnocení sada pravidel pro vyhodnocování výrazů. Termín se často používá k označení konkrétnějšího pojmu strategie předávání parametrů, který definuje, zda se mají vyhodnotit parametry volání funkce, a pokud ano, v jakém pořadí ( pořadí vyhodnocení ) a druh hodnoty, která je předána funkce pro každý parametr ( strategie vazby ). Pojem strategie redukce je odlišný, ačkoli někteří autoři tyto dva termíny spojují a definice každého termínu není široce dohodnuta.

Pro ilustraci, funkce aplikace může vyhodnotit argument před vyhodnocením těla funkce a předat adresu, což dává funkci možnost vyhledat aktuální hodnotu argumentu a upravit ji pomocí přiřazení .

Strategie hodnocení je určena definicí programovacího jazyka a není funkcí žádné konkrétní implementace. Konvence volání definuje podrobnosti předávání parametrů při provádění specifické.

Stůl

Toto je tabulka strategií hodnocení a reprezentativních jazyků podle roku zavedení. Reprezentativní jazyky jsou uvedeny v chronologickém pořadí, počínaje jazykem (jazyky), který představil strategii (pokud existuje), a následují prominentní jazyky, které tuto strategii používají.

Strategie hodnocení Reprezentativní jazyky Rok poprvé zaveden
Volejte podle doporučení FORTRAN II , PL/I 1958
Volejte podle hodnoty ALGOL , C , schéma 1960
Volejte jménem ALGOL 60 , Simula 1960
Volání kopírováním-obnovení Fortran IV , Ada 1962
Volejte podle potřeby Haskell , R. 1971
Volání podle referenčních parametrů C ++ , PHP , C# , Visual Basic .NET ?
Volání podle odkazu na konst C , C ++ ?
Volejte sdílením Java, Python, Ruby ?

Hodnocení zakázek

Zatímco pořadí operací definuje abstraktní strom syntaxe výrazu, pořadí vyhodnocení definuje pořadí, ve kterém jsou výrazy vyhodnocovány. Například program Python

def f(x):
    print(x)
    return x

f(1) + f(2)

výstupy 1 2kvůli vyhodnocovacímu pořadí Pythonu zleva doprava, ale podobný program v OCaml:

let f x =  print_string (string_of_int x); x ;;
f 1 + f 2

výstupy 2 1kvůli vyhodnocovacímu pořadí OCamla zprava doleva.

Pořadí vyhodnocení je viditelné hlavně v kódu s vedlejšími efekty , ale také ovlivňuje výkonnost kódu, protože rigidní pořadí brání plánování instrukcí . Z tohoto důvodu jazykové standardy, jako je C ++, tradičně nechávaly pořadí nedefinované, přestože jazyky jako Java a C# definují pořadí hodnocení jako zleva doprava a standard C ++ 17 přidal omezení na pořadí vyhodnocení.

Přísné hodnocení

Aplikační pořadí je rodina vyhodnocovacích řádů, ve kterých jsou argumenty funkce vyhodnoceny úplně před aplikací funkce. To má za následek, že je funkce přísná , tj. Výsledek funkce je nedefinovaný, pokud jsou některé z argumentů nedefinované, takže hodnocení aplikačního pořadí se běžně nazývá přísné hodnocení . Kromě toho se volání funkce provádí, jakmile se s ním setkáte v proceduře, takže se také nazývá dychtivé hodnocení nebo chamtivé hodnocení . Někteří autoři označují přísné hodnocení jako „volání podle hodnoty“ kvůli vazebné strategii volání podle hodnoty, která vyžaduje přísné hodnocení.

Společné Lisp, Eiffel a Java vyhodnocují argumenty funkcí zleva doprava. C ponechává objednávku nedefinovanou. Schéma vyžaduje, aby příkazem k provedení bylo sekvenční provedení neurčené permutace argumentů. OCaml podobně nechává pořadí neurčené, ale v praxi vyhodnocuje argumenty zprava doleva kvůli konstrukci svého abstraktního stroje . To vše je přísné hodnocení.

Nečekané hodnocení

Nestriktní vyhodnocení pořadí je zhodnocení příkaz, který není striktní, to znamená, že funkce může vrátit výsledek, než všechny jeho argumenty jsou plně vyhodnoceny. Prototypickým příkladem je normální hodnocení pořadí , které nevyhodnocuje žádný z argumentů, dokud nejsou v těle funkce potřeba. Normální vyhodnocení objednávky má tu vlastnost, že končí bez chyby vždy, když jakýkoli jiný vyhodnocovací příkaz skončí bez chyby. Poznamenáváme, že opožděné hodnocení je v tomto článku zařazeno spíše jako vazebná technika než jako vyhodnocovací pořadí. Toto rozlišení se však ne vždy dodržuje a někteří autoři definují líné hodnocení jako normální hodnocení pořadí nebo naopak, nebo si pletou ne-přísnost s líným hodnocením.

Booleovské výrazy v mnoha jazycích používají formu nestriktního hodnocení nazývanou zkratové hodnocení , kde se hodnocení vrací, jakmile je možné určit, že výsledkem bude jednoznačný booleovský výraz-například v disjunktivním výrazu (OR), kde truese vyskytne, nebo v konjunktivním výrazu (AND), kde falsese setkáváme atd. Podmíněné výrazy podobně využívají ne striktní hodnocení - vyhodnocena je pouze jedna z větví.

Porovnání aplikačního řádu a normálního vyhodnocení objednávky

Při normálním vyhodnocení objednávky budou výrazy obsahující drahý výpočet, chybu nebo nekonečnou smyčku ignorovány, pokud to není potřeba, což umožní specifikaci uživatelsky definovaných konstrukcí řídicích toků, zařízení, které není k dispozici s aplikačním vyhodnocením pořadí. Vyhodnocení normálního pořadí používá složité struktury, jako jsou například thunky pro nevyhodnocené výrazy, ve srovnání se zásobníkem hovorů používaným při hodnocení aplikačního pořadí. Normální hodnocení objednávek má historicky nedostatek použitelných nástrojů pro ladění kvůli své složitosti.

Přísné vazebné strategie

Volejte podle hodnoty

Při volání podle hodnoty je vyhodnocená hodnota výrazu argumentu vázána na odpovídající proměnnou ve funkci (často kopírováním hodnoty do nové oblasti paměti). Je-li funkce nebo postup je schopen přiřadit hodnoty jeho parametrů, pouze jeho lokální proměnná je přiřazena, to znamená, že všechno vede do volání funkce je v nezměněné formě volajícího rozsahu , když se vrací.

Implicitní omezení

V některých případech je termín „volání podle hodnoty“ problematický, protože hodnota, která je předávána, není hodnotou proměnné, jak ji chápe běžný význam hodnoty, ale odkazem na hodnotu specifickým pro implementaci . Výsledkem je, že to, co syntakticky vypadá jako volání podle hodnoty, se může nakonec chovat spíše jako volání podle odkazu nebo volání sdílením , často v závislosti na velmi jemných aspektech jazykové sémantiky.

Důvodem pro předání odkazu je často to, že jazyk technicky neposkytuje hodnotovou reprezentaci komplikovaných dat, ale místo toho je reprezentuje jako datovou strukturu při zachování určité podoby vzhledu hodnoty ve zdrojovém kódu. Přesně tam, kde je hranice mezi správnými hodnotami a datovými strukturami maskovanými jako takovými, je často těžké předvídat. V C je pole (jehož řetězce jsou speciální případy) datová struktura, ale název pole je považován za (má jako hodnotu) odkaz na první prvek pole, zatímco název proměnné struktury odkazuje na hodnotu i když má pole, která jsou vektory. V Maple je vektor zvláštním případem tabulky, a tedy datové struktury, ale seznam (který se vykreslí a lze jej indexovat přesně stejným způsobem) je hodnota. V Tcl jsou hodnoty „dvouportové“, takže reprezentace hodnot je použita na úrovni skriptu a jazyk sám spravuje odpovídající datovou strukturu, pokud je požadována. Úpravy provedené prostřednictvím datové struktury se promítnou zpět do reprezentace hodnot a naopak.

Popis „volání podle hodnoty, kde hodnota je referencí“ je běžný (ale neměl by být chápán jako volání podle odkazu); další termín je volání sdílením . Chování volání podle hodnoty Java nebo Visual Basic a volání podle hodnoty C nebo Pascal se tedy výrazně liší: v jazyce C nebo Pascal volání funkce s velkou strukturou jako argumentu způsobí zkopírování celé struktury (kromě případů, kdy je to ve skutečnosti odkaz na strukturu), potenciálně způsobující vážné snížení výkonu a mutace struktury jsou pro volající neviditelné. V jazyce Java nebo Visual Basic se však zkopíruje pouze odkaz na strukturu, který je rychlý, a pro volajícího jsou viditelné mutace struktury.

Volejte podle doporučení

Call by reference (nebo pass by reference) je strategie hodnocení, kde je parametr vázán na implicitní odkaz na proměnnou použitou jako argument, nikoli na kopii její hodnoty.

To obvykle znamená, že funkce může upravit (tj. Přiřadit ) proměnnou použitou jako argument - něco, co uvidí její volající. Volání odkazem lze tedy použít k poskytnutí dalšího komunikačního kanálu mezi volanou funkcí a volající funkcí. Jazyk call-by-reference ztěžuje programátorovi sledování účinků volání funkce a může zavádět jemné chyby. Jednoduchý lakmusový test, zda jazyk podporuje sémantiku call-by-reference, je, pokud je možné v jazyce napsat tradiční swap(a, b)funkci.

Volání podle odkazu lze simulovat v jazycích, které používají volání podle hodnoty a které nepodporují přesně volání podle odkazu, pomocí odkazů (objekty, které odkazují na jiné objekty), jako jsou ukazatele (objekty představující paměťové adresy jiných objektů) . Jazyky jako C , ML a Rust používají tuto techniku. Nejde o samostatnou strategii hodnocení - jazyk volá podle hodnoty -, ale někdy se mu říká „volání podle adresy“ nebo „předávání podle adresy“. V ML, odkazy jsou typově a paměť-safe , podobně jako Rust.

V čistě funkčních jazycích obvykle neexistuje žádný sémantický rozdíl mezi těmito dvěma strategiemi (protože jejich datové struktury jsou neměnné, takže neexistuje žádná možnost, aby funkce upravila jakýkoli ze svých argumentů), takže jsou obvykle popisovány jako volání podle hodnoty, přestože implementace často využívejte call by reference interně pro výhody efektivity.

Následuje příklad, který demonstruje volání odkazem v programovacím jazyce E :

def modify(var p, &q) {
    p := 27 # passed by value: only the local parameter is modified
    q := 27 # passed by reference: variable used in call is modified
}

? var a := 1
# value: 1
? var b := 2
# value: 2
? modify(a, &b)
? a
# value: 1
? b
# value: 27

Následuje příklad volání podle adresy, které simuluje volání podle odkazu v C :

void modify(int p, int* q, int* r) {
    p = 27; // passed by value: only the local parameter is modified
    *q = 27; // passed by value or reference, check call site to determine which
    *r = 27; // passed by value or reference, check call site to determine which
}

int main() {
    int a = 1;
    int b = 1;
    int x = 1;
    int* c = &x;
    modify(a, &b, c); // a is passed by value, b is passed by reference by creating a pointer (call by value),
                    // c is a pointer passed by value
                    // b and x are changed
    return 0;
}

Volejte sdílením

Call by sharing (také známý jako „call by object“ nebo „call by object-sharing“) je strategie hodnocení, kterou poprvé zaznamenala Barbara Liskov v roce 1974 pro jazyk CLU . Používají ho jazyky jako Python , Java (pro odkazy na objekty), Ruby , JavaScript , Scheme, OCaml, AppleScript a mnoho dalších. Pojem „volání sdílením“ však není běžně používán; terminologie je v různých zdrojích nekonzistentní. Například v komunitě Java se říká, že Java je voláním podle hodnoty. Volání sdílením znamená, že hodnoty v jazyce jsou založeny spíše na objektech než na primitivních typech , tj. Že všechny hodnoty jsou „ orámovány “. Vzhledem k tomu, že jsou zabaleny, lze o nich říci, že procházejí kopií odkazu (kde jsou primitiva zabalena před předáním a rozbalena na volanou funkci).

Sémantika volání sdílením se liší od volání odkazem: „Zejména to není volání podle hodnoty, protože pro volajícího budou viditelné mutace argumentů prováděné volanou rutinou. A není to volání podle odkazu, protože přístup není udělen proměnné volajícího, ale pouze k určitým objektům “. Pokud například byla předána proměnná, není možné simulovat přiřazení této proměnné v rozsahu volaného. Jelikož však funkce má přístup ke stejnému objektu jako volající (není provedena žádná kopie), jsou pro volajícího viditelné mutace těchto objektů, pokud jsou objekty měnitelné , v rámci funkce, což se může zdát odlišné od volání podle hodnoty sémantika. Mutace proměnného objektu v rámci funkce jsou volajícímu viditelné, protože objekt není kopírován ani klonován - je sdílen.

Například v Pythonu jsou seznamy měnitelné, takže:

def f(a_list):
    a_list.append(1)

m = []
f(m)
print(m)

výstupy, [1]protože appendmetoda upravuje objekt, na který je volána.

Přiřazení v rámci funkce není volajícímu patrné, protože v těchto jazycích předání proměnné znamená pouze předání (přístup k) skutečnému objektu, na který proměnná odkazuje, nikoli přístup k původní (volající) proměnné. Protože proměnná odrazu existuje pouze v rozsahu funkce, protějšek volajícího si zachová původní vazbu.

Porovnejte výše uvedenou mutaci Pythonu s níže uvedeným kódem, který váže formální argument na nový objekt:

def f(a_list):
    a_list = [1]

m = []
f(m)
print(m)

výstupy [], protože příkaz a_list = [1]znovu přiřadí nový seznam proměnné, nikoli umístění, na které odkazuje.

U neměnných objektů neexistuje skutečný rozdíl mezi voláním sdílením a voláním podle hodnoty, kromě případů, kdy je v jazyce viditelná identita objektu. Alternativou ke vstupním/výstupním parametrům je použití volání sdílením s měnitelnými objekty : parametr není přiřazen (argument není přepsán a identita objektu není změněna), ale objekt (argument) je mutován.

Volání kopírováním-obnovení

Call od kopie-restore-známý také jako „copy-in kopii-out“, „výzva podle výsledku hodnotou“, „volání obratem hodnoty“ (jak nazval v Fortran komunity) -je zvláštní případ volání odkazem, kde je poskytnutý odkaz je pro volající jedinečný. Tato varianta si získala pozornost v kontextech vícenásobného zpracování a vzdáleného volání procedury : pokud je parametrem volání funkce odkaz, který může být přístupný jinému vláknu provádění, jeho obsah může být zkopírován do nového odkazu, který není; když se vrátí volání funkce, zkopíruje se aktualizovaný obsah této nové reference zpět do původní reference („obnoveno“).

Sémantika volání pomocí kopírování-obnovení se také liší od sémantiky volání podle odkazu, kde se dva nebo více funkčních argumentů navzájem spojují (tj. Ukazují na stejnou proměnnou v prostředí volajícího). Při volání odkazem bude psaní jednomu ovlivňovat druhé; call by copy-restore se tomu vyhne tím, že funkci poskytne zřetelné kopie, ale ponechá výsledek v prostředí volajícího nedefinovaný podle toho, který z aliased argumentů je zkopírován zpět jako první-budou kopie vytvořeny v pořadí zleva doprava jak při vstupu a na oplátku?

Když je odkaz předán volanému neinicializovaný, může být tato strategie hodnocení nazývána „volání podle výsledku“.

Nestresové závazné strategie

Volejte jménem

Volání podle jména je strategie hodnocení, kde argumenty funkce nejsou vyhodnoceny dříve, než je funkce volána-spíše jsou nahrazeny přímo do těla funkce (pomocí substituce zabraňující zachycení ) a poté ponechány k vyhodnocení, kdykoli se objeví v funkce. Pokud v těle funkce není použit argument, argument není nikdy vyhodnocen; pokud je použit několikrát, je přehodnocen pokaždé, když se objeví. (Viz Jensenovo zařízení .)

Vyhodnocení podle jména je občas vhodnější než vyhodnocení podle hodnoty. Pokud ve funkci není použit argument funkce, volání podle jména ušetří čas tím, že argument nebude vyhodnocen, zatímco volání podle hodnoty jej vyhodnotí bez ohledu na to. Pokud je argumentem nekončící výpočet, je výhoda obrovská. Když je však použit argument funkce, volání podle jména je často pomalejší a vyžaduje mechanismus, jako je například thunk .

Dnešní jazyky .NET mohou simulovat volání podle jména pomocí delegátů nebo Expression<T>parametrů. Ten má za následek, že je funkci dán abstraktní strom syntaxe . Eiffel poskytuje agenty, kteří představují operaci, která má být v případě potřeby vyhodnocena. Seed7 poskytuje volání podle jména s funkčními parametry. Programy Java mohou provádět podobné líné hodnocení pomocí výrazů lambda a java.util.function.Supplier<T>rozhraní.

Volejte podle potřeby

Call by need je zapamatovaná varianta volání podle jména, kde pokud je vyhodnocen argument funkce, je tato hodnota uložena pro následné použití. Pokud je argument čistý (tj. Bez vedlejších účinků), vytvoří se stejné výsledky jako volání podle jména, což ušetří náklady na přepočítání argumentu.

Haskell je známý jazyk, který využívá vyhodnocení podle potřeby. Protože vyhodnocení výrazů se může stát libovolně daleko do výpočtu, Haskell podporuje pouze vedlejší efekty (jako je mutace ) pomocí monad . To eliminuje jakékoli neočekávané chování z proměnných, jejichž hodnoty se mění před jejich zpožděným vyhodnocením.

V R implementaci volání podle potřeby jsou předány všechny argumenty, což znamená, že R umožňuje libovolné vedlejší efekty.

Líné hodnocení je nejběžnější implementací sémantiky volání podle potřeby, ale existují varianty jako optimistické hodnocení . Jazyky .NET implementují volání podle potřeby pomocí typu Lazy<T>.

Redukce grafu je efektivní implementací líného hodnocení.

Volání pomocí rozšíření makra

Rozšíření volání podle makra je podobné volání podle jména, ale používá spíše nahrazení textu než zachycení, čímž se vyhýbá nahrazování. Substituce makra však může způsobit chyby, což vede k zachycení proměnných , což vede k nežádoucímu chování. Hygienická makra se tomuto problému vyhnou kontrolou a nahrazením stínovaných proměnných, které nejsou parametry.

Volejte do budoucna

„Call by future“, také známý jako „paralelní volání podle jména“, je souběžná strategie hodnocení, ve které je hodnota budoucího výrazu vypočítávána souběžně s tokem zbytku programu se sliby, známými také jako futures. Když je potřeba hodnota slibu, hlavní program blokuje, dokud slib nemá hodnotu (slib nebo některý ze slibů dokončí výpočet, pokud do té doby již nebyl splněn).

Tato strategie není deterministická, protože k hodnocení může dojít kdykoli mezi vytvořením budoucnosti (tj. Když je vyjádřen výraz) a použitím hodnoty budoucnosti. Je to podobné volání podle potřeby v tom, že hodnota je vypočítána pouze jednou a výpočet může být odložen, dokud není hodnota potřebná, ale může být spuštěna dříve. Dále, pokud není potřeba hodnota budoucnosti, například pokud se jedná o lokální proměnnou ve funkci, která se vrací, může být výpočet částečně ukončen.

Pokud je implementováno s procesy nebo vlákny, vytvoření budoucnosti vytvoří jeden nebo více nových procesů nebo vláken (pro sliby), přístup k hodnotě je synchronizuje s hlavním vláknem a ukončení výpočtu budoucnosti odpovídá zabití slibů, které počítají jeho hodnota.

Pokud je implementováno s coroutine , jako v .NET async/await , vytvoření budoucnosti volá coroutine (asynchronní funkce), což může dát volajícímu a následně se vrátit zpět při použití hodnoty, kooperativně multitasking.

Optimistické hodnocení

Optimistické vyhodnocení je další variantou volání podle potřeby, kde je argument funkce částečně vyhodnocen po určitou dobu (kterou lze upravit za běhu ). Po uplynutí této doby se vyhodnocení přeruší a funkce se použije pomocí volání podle potřeby. Tento přístup eliminuje některé náklady na běh strategie call-by-need při zachování požadovaných charakteristik ukončení.

Viz také

Reference


Další čtení

externí odkazy