Referenční transparentnost - Referential transparency

Tento článek je o referenční transparentnosti v teorii programovacího jazyka. Pro jeho použití v lingvistice a filozofii viz neprůhledný kontext .

Referenční průhlednost a referenční neprůhlednost jsou vlastnosti částí počítačových programů . Výraz se nazývá referenčně transparentní, pokud může být nahrazen s odpovídající hodnoty (a naopak), aniž by se změnila chování programu. To vyžaduje, aby byl výraz čistý , to znamená, že hodnota výrazu musí být stejná pro stejné vstupy a jeho vyhodnocení nesmí mít žádné vedlejší účinky . Výraz, který není referenčním transparentním, se nazývá referenční neprůhledný.

V matematice jsou všechny funkční aplikace referenčně transparentní podle definice toho, co představuje matematickou funkci . To však není vždy případ programování, kde se používají pojmy postup a metoda, aby se zabránilo zavádějícím konotacím. Ve funkčním programování jsou brány v úvahu pouze referenčně transparentní funkce. Některé programovací jazyky poskytují prostředky k zajištění referenční transparentnosti. Některé funkční programovací jazyky vynucují referenční průhlednost pro všechny funkce.

Důležitost referenční transparentnosti spočívá v tom, že umožňuje programátorovi a kompilátoru uvažovat o chování programu jako přepisovacího systému . To může pomoci prokázat správnost , zjednodušit algoritmus , pomoci s úpravou kódu bez jeho porušení nebo optimalizovat kód pomocí memoizace , společné eliminace subexprese , líného vyhodnocení nebo paralelizace .

Dějiny

Koncept se zdá k vznikli v Alfred North Whitehead a Bertrand Russell ‚s Principia Mathematica (1910-13). To bylo přijato v analytické filosofii od Willard Van Orman Quine . V §30 Word and Object (1960) uvádí Quine tuto definici:

Způsob zadržování φ je referenční transparentní, pokud je výskyt singulárního výrazu t čistě referenční v termínu nebo větě ly (t), je čistě referenční také v obsahujícím termínu nebo větě φ (ψ (t)).

Tento termín se objevil v jeho současném využití v počítačové vědě, v diskusi o proměnných v programovacích jazycích , v klíčové sadě přednášek Christophera Stracheyho Základní pojmy v programovacích jazycích (1967). Poznámky k přednášce v bibliografii odkazovaly na Quinovo slovo a předmět .

Příklady a protiklady

Pokud jsou všechny funkce zahrnuté ve výrazu čisté funkce , pak je výraz referenčně transparentní.

Zvažte funkci, která vrací vstup z nějakého zdroje. V pseudokódu může být volání této funkce GetInput(Source)tam, kde Sourcemůže identifikovat konkrétní soubor na disku, klávesnici atd. I při stejných hodnotách Sourcese po sobě následující návratové hodnoty budou lišit. Funkce proto GetInput()není ani deterministická, ani referenční transparentní.

Subtilnějším příkladem je funkce, která má volnou proměnnou , tj. Závisí na nějakém vstupu, který není explicitně předán jako parametr. To se pak vyřeší podle pravidel vazby názvů na nelokální proměnnou , jako je globální proměnná , proměnná v aktuálním prostředí provádění (pro dynamickou vazbu ) nebo proměnná v uzavření (pro statickou vazbu). Protože tuto proměnnou lze změnit beze změny hodnot předaných jako parametr, výsledky následných volání funkce se mohou lišit, i když jsou parametry identické. V čistém funkčním programování však destruktivní přiřazení není povoleno, a proto je-li volná proměnná staticky vázána na hodnotu, funkce je stále referenčním způsobem transparentní, protože ani lokální proměnná, ani její hodnota se nemohou změnit kvůli statické vazbě a neměnnost .

Aritmetické operace jsou referenční transparentní: 5 * 5lze je například nahradit 25. Ve skutečnosti jsou všechny funkce v matematickém smyslu referenčně transparentní: sin(x)je transparentní, protože každému jednotlivému výsledku poskytne vždy stejný výsledek x.

Opětovné přiřazení není transparentní. Například výraz Cx = x + 1 změní hodnotu přiřazenou proměnné x. Za předpokladu, že xmá zpočátku hodnotu 10, dvě po sobě jdoucí vyhodnocení výtěžku výrazu 11a 12. Je zřejmé, že nahrazení x = x + 1buď 11nebo 12dává programu s jiným významem, a tak výraz není referenční transparentní. Volání funkce, jako je například, je transparentní, protože implicitně nezmění vstup, a proto nemá žádné takové vedlejší účinky . int plusone(int x) { return x + 1; } x

today()není transparentní, jako kdybyste jej vyhodnotili a nahradili jeho hodnotou (řekněme "Jan 1, 2001"), nedosáhnete stejného výsledku, jako kdybyste jej zítra spustili. Důvodem je, že to závisí na stavu (datum).

V jazycích bez vedlejších účinků, jako je Haskell , můžeme dosadit rovné za rovné: tj . x == yTehdy f(x) == f(y). Toto je vlastnost známá také jako nerozeznatelné identifikace . Takové vlastnosti nemusí obecně platit pro jazyky s vedlejšími účinky. I tak je důležité omezit taková tvrzení na takzvanou úsudkovou rovnost, tj. Rovnost podmínek testovaných systémem, bez zahrnutí uživatelem definované ekvivalence pro typy. Například pokud B f(A x)a typ Apřepsal pojem rovnosti, např. Vyrovnání všech výrazů, pak je možné mít x == ya přesto najít f(x) != f(y). Je to proto, že systémy jako Haskell neověřují, zda jsou funkce definované na typech s uživatelem definovanými relacemi ekvivalence dobře definované s ohledem na tuto ekvivalenci. Referenční transparentnost je tedy omezena na typy bez vztahů ekvivalence. Rozšíření referenční transparentnosti na relace ekvivalence definované uživatelem lze provést například s typem identity Martin-Lof, ale vyžaduje systém se závislým typem, například v Agda , Coq nebo Idris .

Kontrast s imperativním programováním

Pokud je substituce výrazu jeho hodnotou platná pouze v určitém bodě provádění programu, pak výraz není referenční transparentní. Definice a řazení těchto bodů posloupnosti jsou teoretickým základem imperativního programování a součástí sémantiky imperativního programovacího jazyka.

Protože však lze referenčně transparentní výraz kdykoli vyhodnotit, není nutné definovat posloupnost bodů ani vůbec žádnou záruku pořadí vyhodnocení. Programování provedené bez těchto úvah se nazývá čistě funkční programování .

Jednou z výhod psaní kódu v referenčním transparentním stylu je to, že vzhledem k inteligentnímu kompilátoru je statická analýza kódu jednodušší a lepší transformace zlepšující kód jsou možné automaticky. Například při programování v C bude výkonnostní trest za zahrnutí volání drahé funkce do smyčky, i když by bylo možné volání funkce přesunout mimo smyčku beze změny výsledků programu. Programátor by byl nucen provádět ruční pohyb kódu hovoru, pravděpodobně na úkor čitelnosti zdrojového kódu. Pokud je však kompilátor schopen určit, že volání funkce je referenční transparentní, může tuto transformaci provést automaticky.

Primární nevýhodou jazyků, které vynucují referenční průhlednost, je to, že činí výraz operací, které přirozeně zapadají do imperativního programovacího stylu postupnosti kroků, nepohodlnějším a méně výstižným. Takové jazyky často obsahují mechanismy, které usnadňují tyto úkoly při zachování čistě funkční kvality jazyka, jako jsou gramatiky s definitivní klauzí a monády .

Další příklad

Jako příklad pojďme použít dvě funkce, jednu, která je referenční transparentní a druhou, která je referenční neprůhledná: 

int g = 0;

int rt(int x) {
  return x + 1;
}

int ro(int x) {
  g++;
  return x + g;
}

Funkce rtje referenční transparentní, což znamená, že pokud x == yano rt(x) == rt(y). Například rt(6) = 7. Nemůžeme však nic takového říci, roprotože používá globální proměnnou, kterou modifikuje.

Díky referenční neprůhlednosti roje uvažování o programech obtížnější. Řekněme například, že si přejeme uvažovat o následujícím tvrzení: 

int i = ro(x) + ro(y) * (ro(x) - ro(x));

Lze být v pokušení zjednodušit toto tvrzení na: 

int i = ro(x) + ro(y) * 0;
int i = ro(x) + 0;
int i = ro(x);

To však nebude fungovat, roprotože každý výskyt ro(x)hodnotí jinou hodnotu. Nezapomeňte, že návratová hodnota roje založena na globální hodnotě, která není předána a která se při každém volání upraví ro. To znamená, že matematické identity jako x - x = 0 již neplatí.

Takové matematické identity budou platit pro referenční transparentní funkce, jako je rt.

Ke zjednodušení příkazu však lze použít sofistikovanější analýzu: 

int tmp = g; int i = x + tmp + 1 + (y + tmp + 2) * (x + tmp + 3 - (x + tmp + 4)); g = g + 4;
int tmp = g; int i = x + tmp + 1 + (y + tmp + 2) * (x + tmp + 3 - x - tmp - 4)); g = g + 4;
int tmp = g; int i = x + tmp + 1 + (y + tmp + 2) * (-1); g = g + 4;
int tmp = g; int i = x + tmp + 1 - y - tmp - 2; g = g + 4;
int i = x - y - 1; g = g + 4;

To vyžaduje více kroků a vyžaduje určitý stupeň přehledu o kódu, který je pro optimalizaci kompilátoru neproveditelný.

Referenční transparentnost nám proto umožňuje uvažovat o našem kódu, což povede k robustnějším programům, možnosti hledání chyb, které jsme nemohli doufat, že je najdeme testováním, a možnost vidět příležitosti k optimalizaci .

Viz také

Reference

externí odkazy