Vnořená funkce - Nested function

V počítačovém programování je vnořená funkce (nebo vnořená procedura nebo podprogram ) funkce, která je definována v rámci jiné funkce, uzavírací funkce . Díky jednoduchým rekurzivním pravidlům rozsahu je vnořená funkce sama neviditelná mimo svoji bezprostředně uzavírající funkci, ale může vidět (přistupovat) ke všem lokálním objektům (datům, funkcím, typům atd.) Své bezprostředně uzavírající funkce i jakékoli funkce s), což zase tuto funkci uzavírá. Vnořování je teoreticky možné do neomezené hloubky, i když se v praktických programech běžně používá jen několik úrovní.

Vnořené funkce se používají v mnoha přístupech ke strukturovanému programování , včetně těch raných, jako jsou ALGOL , Simula 67 a Pascal , a také v mnoha moderních dynamických jazycích a funkčních jazycích . V (původně jednoduché) C-rodině jazyků však tradičně nejsou podporovány.

Efekty

Vnořené funkce předpokládají rozsah funkcí nebo rozsah bloků . Rozsah vnořené funkce je uvnitř uzavírací funkce, tj. Uvnitř jednoho ze základních bloků této funkce, což znamená, že je neviditelná mimo tento blok a také mimo uzavírací funkci. Vnořená funkce může přistupovat k dalším místním funkcím, proměnným, konstantám, typům, třídám atd., Které jsou ve stejném rozsahu nebo v jakémkoli uzavřeném oboru, bez předávání explicitních parametrů, což výrazně zjednodušuje předávání dat do a ze vnořené funkce. To je obvykle povoleno pro čtení i psaní.

Vnořené funkce mohou v určitých situacích (a jazycích) vést k uzavření . Pokud je možné, aby vnořená funkce unikla uzavírací funkci, například pokud jsou funkce objekty první třídy a vnořená funkce je předána jiné funkci nebo vrácena z uzavírací funkce, vytvoří se uzávěr a volání této funkce bude mít přístup prostředí původní funkce. Rámec bezprostředně uzavírající funkce musí být nadále aktivní, dokud neumožní poslední referenční uzávěr a nelokální automatické proměnné odkazované v uzávěrech proto nelze přidělit zásobníku . Toto je známé jako problém funarg a je to klíčový důvod, proč vnořené funkce nebyly implementovány v některých jednodušších jazycích, protože to výrazně komplikuje generování kódu a analýzu, zvláště když jsou funkce vnořené na různé úrovně a sdílejí různé části svého prostředí.

Příklady

Příklad používající syntaxi Pascal (s ALGOL , Modula 2 , Oberon , Ada atd. Podobné): 

function E(x: real): real;
    function F(y: real): real;
    begin
        F := x + y
    end;
begin
    E := F(3) + F(4)
end;

Funkce Fje vnořena uvnitř E. Všimněte si, že Eparametr xje viditelný také v F(jak Fje součástí E), zatímco oba xa yjsou neviditelné venku Ea Fresp.

Podobně ve standardním ML: 

fun e (x : real) =
  let
    fun f y = x+y
  in
    f 3 + f 4
  end;

Jeden způsob, jak napsat stejný příklad v syntaxi Haskell : 

e :: Float -> Float
e x = f 3 + f 4 where f y = x + y

Stejný příklad v syntaxi GNU C (C rozšířený o vnořené funkce): 

float E(float x)
{
    float F(float y)
    {
        return x + y;
    }
    return F(3) + F(4);
}

Rychlé řazení

Realističtějším příkladem je tato implementace quicksortu : 

void sort(int *items, int size) {
    void quickSort(int first, int last) {
        void swap(int p, int q) {
            int tmp = items[p];
            items[p] = items[q];
            items[q] = tmp;
        }
        
        int partition() {
            int pivot = items[first], index = first;
            swap(index, last);
            for (int i = first; i < last; i++)
                if (items[i] < pivot)
                    swap(index++, i);
            swap(index, last);
            return index;
        }

        if (first < last) {
            int pivotIndex = partition();
            quickSort(first, pivotIndex - 1);
            quickSort(pivotIndex + 1, last);
        }
    }
    quickSort(0, size - 1);
}

Dalším příkladem je následující implementace rychlého řazení založeného na oddílech Hoare pomocí syntaxe lambda výrazu C ++ 11 : 

template<typename RandomAccessIterator>
auto Sort(RandomAccessIterator Begin, RandomAccessIterator End)->void {
	auto Partition = [&]() {
		//Hoare partition scheme
		auto &Pivot = *Begin;
		auto ForwardCursor = Begin;
		auto BackwardCursor = End - 1;
		auto PartitionPositionFound = false;
		auto LocatePartitionPosition = [&]() {
			while (*ForwardCursor < Pivot)
				++ForwardCursor;
			while (Pivot < *BackwardCursor)
				--BackwardCursor;
			if (ForwardCursor >= BackwardCursor)
				PartitionPositionFound = true;
			else
				Swap(*ForwardCursor, *BackwardCursor);
		};
		//Trivial helper function
		auto MoveOnAndTryAgain = [&]() {
			++ForwardCursor;
			--BackwardCursor;
		};
		//Brief outline of the actual partition process
		while (true) {
			LocatePartitionPosition();
			if (PartitionPositionFound)
				return BackwardCursor + 1;
			else
				MoveOnAndTryAgain();
		}
	};
	//Brief outline of the quicksort algorithm
	if (Begin < End - 1) {
		auto PartitionPosition = Partition();
		Sort(Begin, PartitionPosition);
		Sort(PartitionPosition, End);
	}
}

Účel

Lexikálně vnořené definice funkcí jsou formou skrývání informací a jsou užitečné pro rozdělení procedurálních úkolů na dílčí úkoly, které mají smysl pouze lokálně. Tím se zabrání zaplnění dalších částí programu funkcemi a proměnnými, které s těmito částmi nesouvisejí.

Obvykle se používají jako pomocné funkce nebo jako rekurzivní funkce uvnitř jiné funkce (jako v příkladu rychlého řazení výše). To má strukturální výhodu v organizaci kódu, vyhýbá se znečištění rozsahu a také umožňuje funkcím snadno sdílet stav. Protože vnořená funkce má přístup k lokálním proměnným uzavírající funkce, sdílení stavu je možné bez předávání parametrů vnořené funkci nebo použití globální proměnné , zjednodušující kód.

V jazycích s vnořenými funkcemi mohou funkce obvykle obsahovat také místní konstanty a typy (kromě místních proměnných , parametrů a funkcí), zapouzdřené a skryté stejným způsobem vnořené, na jakékoli úrovni hloubky. To může dále zlepšit možnosti strukturování kódu.

Jiné použití

Řídicí tok

Vnořené funkce lze také použít pro nestrukturovaný řídicí tok pomocí příkazu return pro obecný nestrukturovaný řídicí tok. Toho lze využít pro jemnější ovládání, než je možné u jiných vestavěných funkcí jazyka-například to může umožnit předčasné ukončení smyčky for, pokud breaknení k dispozici, nebo předčasné ukončení vnořené smyčky for, pokud je -úroveň breaknebo výjimky nejsou k dispozici.

Funkce vyššího řádu

Hlavní článek: Funkce vyššího řádu

Protože ve většině jazyků jsou funkce platnými návratovými typy, je možné vytvořit vnořenou funkci, která přistupuje k sadě parametrů z vnější funkce, a mít tuto funkci jako návratovou hodnotu vnější funkce. Je tedy možné vrátit funkci, která je nastavena tak, aby splňovala určitý úkol, s malými nebo žádnými dalšími parametry, které jí mohou výrazně zvýšit výkon.

Alternativy

Hlavní alternativou k vnořeným funkcím v jazycích, které pro ně nemají podporu, je umístit všechny relevantní funkce a proměnné do samostatného modulu (souboru) a veřejně vystavit pouze funkci obálky nejvyšší úrovně . V C to bude obecně provedeno pomocí statických funkcí pro zapouzdření a statických proměnných pro komunikaci. Tím se dosáhne zapouzdření a sdílení stavu, i když to není logická organizace daná lexikálním vnořením funkcí, a to za cenu mít samostatný soubor. Rovněž to není možné ve více než jedné úrovni.

Další alternativou je sdílení stavu mezi funkcemi prostřednictvím parametrů funkcí, nejčastěji předávání odkazů jako argumentů, aby se předešlo nákladům na kopírování. V C je to obecně implementováno ukazatelem na strukturu obsahující kontext. To výrazně zvyšuje složitost volání funkcí.

V PHP a dalších jazycích je anonymní funkce jedinou alternativou: vnořená funkce není deklarována jako obvyklá funkce, ale podle odkazu, jako lokální proměnná. Chcete -li použít místní proměnné v anonymní funkci, použijte uzavření .

Jazyky

Mezi dobře známé jazyky podporující lexikálně vnořené funkce patří:

Funkční jazyky

Ve většině funkčních programovacích jazyků, jako je Scheme, jsou vnořené funkce běžným způsobem implementace algoritmů se smyčkami v nich. Je vytvořena jednoduchá ( ocasní ) rekurzivní vnitřní funkce, která se chová jako hlavní smyčka algoritmu, zatímco vnější funkce provádí akce při spuštění, které je třeba provést pouze jednou. Ve složitějších případech může být jako vnitřní funkce vytvořena řada vzájemně rekurzivních funkcí.

Některé jazyky bez přímé podpory

Některé jazyky nemají přímou syntaktickou a sémantickou podporu pro implementaci vnořených funkcí. Nicméně u některých z nich lze představu vnořených funkcí s určitým stupněm obtížnosti simulovat pomocí jiných jazykových konstrukcí. Následující jazyky mohou aproximovat vnořené funkce prostřednictvím příslušných strategií:

  • C ++
    • before C ++ 11: umožňuje definici tříd v rámci tříd a poskytuje možnost používat metody třídy podobným způsobem jako vnořené funkce na jedné úrovni (viz objekt Function v C ++ ).
    • od C ++ 11: pomocí výrazů lambda jako příkladu rychlého řazení výše.
  • Eiffel výslovně zakazuje vnořování rutin. To má zachovat jednoduchost jazyka a také umožňuje konvenci použití speciální proměnné Result k označení výsledku funkce (vracející hodnotu).
  • Visual Basic pomocí anonymních metod nebo výrazů lambda.
  • Java pomocí výrazů lambda (viz Anonymní funkce v Javě ) (od Javy 8) nebo prostřednictvím řešení, které spočívá v anonymní třídě obsahující jedinou metodu. Lze také použít pojmenovanou třídu deklarovanou jako místní pro metodu.

Implementace

Viz také: Test muže nebo chlapce

Implementace vnořených funkcí může být více zapojena, než se může zdát, protože odkaz na vnořenou funkci, která odkazuje na nelokální proměnné, vytváří uzavření . Z tohoto důvodu nejsou vnořené funkce v některých jazycích, jako je C, C ++ nebo Java, podporovány, protože kompilátory se tím obtížněji implementují. Některé kompilátory je však podporují jako rozšíření specifické pro kompilátor. Dobře známým příkladem je implementace jazyka C GNU C, která sdílí kód s překladači pro jazyky jako Pascal, Ada a Modula.

Přístup k jiným než lokálním objektům

Existuje několik způsobů, jak implementovat vnořené procedury v lexikálně vymezeném jazyce, ale klasický způsob je následující:

Jakýkoli nelokální objekt , X, je dosažen prostřednictvím přístupových odkazů v aktivačních rámcích v zásobníku strojů. Volající, C, pomáhá volanému postupu, P, tím , že před samotným voláním tlačí přímý odkaz na nejnovější aktivaci okamžité lexikální enkapsulace P (P). P pak může rychle najít správnou aktivaci pro určité X sledováním pevného počtu (P.depth - X.depth) odkazů (obvykle malého počtu).
Volající vytvoří toto přímé spojení (sám) podle C.depth - P.depth + 1 starších odkazů, což vede k nejnovější aktivaci (P), a poté je dočasně přemostí přímým odkazem na tuto aktivaci; odkaz později zmizí společně s P, čímž se starší odkazy pod ním mohou znovu začít používat.
Všimněte si, že P je viditelné pro, a proto může být voláno C, pokud (P) = C / (C) / ((C)) / atd.

Tato originální metoda je rychlejší, než by se mohlo zdát, ale přesto je často optimalizována v praktických moderních kompilátorech (pomocí displejů nebo podobných technik).

Dalším způsobem, jak implementovat vnořené funkce, které používají některé překladače, je převést ("zvednout") vnořené funkce na vnořené funkce (kde navíc, skryté, parametry nahrazují přístupové odkazy) pomocí procesu známého jako zvedání lambda během mezistupně v kompilaci.

Funkce jako hodnoty

Aby mohly být lokální funkce s lexikálně vymezenými nonlocaly předávány jako výsledky, musí kód runtime jazyka také implicitně předávat prostředí (data), které funkce vidí uvnitř své zapouzdřovací funkce, aby bylo dosažitelné i při aktuální aktivaci uzavírající funkce již neexistuje. To znamená, že prostředí musí být uloženo v jiné paměťové oblasti než (následně regenerované části) chronologicky založeného prováděcího zásobníku, což zase znamená nějaký druh volně dynamické alokace paměti . Mnoho starších jazyků založených na Algolu (nebo jejich dialektech) proto neumožňuje předávat místní funkce, které přistupují k nelokálním, jako návratové hodnoty, nebo vůbec nepovolují funkce jako návratové hodnoty, přestože předávání takových funkcí jako argumentů může být stále možné.

No-execute stacks

Alespoň jedna implementace vnořených funkcí způsobí ztrátu zásobníků bez spouštění (zásobník NX) . Implementace vnořené funkce GCC volá vnořené funkce prostřednictvím instrukce skoku vložené do zásobníku počítače za běhu. To vyžaduje, aby byl zásobník spustitelný.

V GCC se vzájemně nevylučují žádné spouštěcí balíčky a vnořené funkce. Pokud je při vývoji programu použita vnořená funkce, pak se NX Stack tiše ztratí. GCC nabízí varování -Wtrampoline, které upozorní na stav.

Software navržený pomocí Secure Development Lifecycle často neumožňuje použití vnořených funkcí v tomto konkrétním kompilátoru (GCC) kvůli ztrátě NX Stacks.

Viz také

Poznámky

Reference

externí odkazy