Funkcja zagnieżdżona - Nested function

W programowania , A zagnieżdżone funkcja (lub zagnieżdżonej procedury lub podprogram ) jest funkcją , który jest zdefiniowany w innej funkcji, funkcja otaczającego . Ze względu na proste reguły zakresu rekurencyjnego , funkcja zagnieżdżona sama w sobie jest niewidoczna poza swoją bezpośrednio otaczającą funkcją, ale może zobaczyć (dostęp) wszystkie lokalne obiekty (dane, funkcje, typy itp.) swojej bezpośrednio otaczającej funkcji, jak również dowolnej funkcji (s), co z kolei obejmuje tę funkcję. Zagnieżdżanie jest teoretycznie możliwe do nieograniczonej głębokości, chociaż w programach praktycznych zwykle stosuje się tylko kilka poziomów.

Funkcje zagnieżdżone są używane w wielu podejściach do programowania strukturalnego , w tym wczesnych, takich jak ALGOL , Simula 67 i Pascal , a także w wielu nowoczesnych językach dynamicznych i językach funkcjonalnych . Jednak tradycyjnie nie są one obsługiwane w (pierwotnie prostej) rodzinie języków C.

Efekty

Funkcje zagnieżdżone zakładają zakres funkcji lub zakres bloków . Zakres funkcji zagnieżdżonej znajduje się wewnątrz funkcji otaczającej, tj. wewnątrz jednego z bloków składowych tej funkcji, co oznacza, że ​​jest niewidoczna poza tym blokiem, a także poza funkcją otaczającą. Funkcja zagnieżdżona może uzyskać dostęp do innych funkcji lokalnych, zmiennych, stałych, typów, klas itp., które znajdują się w tym samym zakresie lub w dowolnym zakresie obejmującym, bez jawnego przekazywania parametrów, co znacznie upraszcza przekazywanie danych do i z funkcji zagnieżdżonej. Jest to zwykle dozwolone zarówno w przypadku czytania, jak i pisania.

Funkcje zagnieżdżone mogą w pewnych sytuacjach (i językach) prowadzić do powstania domknięcia . Jeśli zagnieżdżona funkcja może uciec od otaczającej funkcji, na przykład jeśli funkcje są obiektami pierwszej klasy, a zagnieżdżona funkcja jest przekazywana do innej funkcji lub zwracana z otaczającej funkcji, wówczas tworzone jest zamknięcie i wywołania tej funkcji mogą uzyskać dostęp środowisko pierwotnej funkcji. Ramka bezpośrednio otaczającej funkcji musi pozostać aktywna do momentu śmierci ostatniego odwołującego się zamknięcia i dlatego nielokalne zmienne automatyczne, do których odwołują się zamknięcia, nie mogą być przydzielone na stosie . Jest to znane jako problem funarg i jest kluczowym powodem, dla którego zagnieżdżone funkcje nie zostały zaimplementowane w niektórych prostszych językach, ponieważ znacznie komplikuje generowanie i analizę kodu, zwłaszcza gdy funkcje są zagnieżdżone na różnych poziomach, dzieląc różne części środowiska.

Przykłady

Przykład z użyciem składni Pascala (z podobnymi ALGOL , Modula 2 , Oberon , Ada , itp.): 

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

Funkcja Fjest zagnieżdżona w E. Zauważ, że Eparametr 's xjest widoczny również w F(jako Fczęść E), podczas gdy oba xi ysą niewidoczne na zewnątrz Ei Fodpowiednio.

Podobnie w Standard ML: 

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

Jeden sposób na napisanie tego samego przykładu w składni Haskella : 

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

Ten sam przykład w składni GNU C (C rozszerzony o zagnieżdżone funkcje): 

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

Szybkie sortowanie

Bardziej realistycznym przykładem jest ta implementacja quicksort : 

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);
}

Innym przykładem jest następująca implementacja szybkiego sortowania opartego na partycjach Hoare przy użyciu składni wyrażenia lambda 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);
	}
}

Cel, powód

Zagnieżdżone leksykalnie definicje funkcji są formą ukrywania informacji i są przydatne do dzielenia zadań proceduralnych na podzadania, które mają znaczenie tylko lokalnie. Pozwala to uniknąć zaśmiecania innych części programu funkcjami i zmiennymi, które nie są związane z tymi częściami.

Są one zwykle używane jako funkcje pomocnicze lub jako funkcje rekurencyjne wewnątrz innej funkcji (jak w powyższym przykładzie szybkiego sortowania). Ma to strukturalną korzyść w postaci uporządkowania kodu, pozwala uniknąć zanieczyszczenia zakresu, a także umożliwia funkcjom łatwe udostępnianie stanu. Ponieważ funkcja zagnieżdżona ma dostęp do zmiennych lokalnych funkcji otaczającej, udostępnianie stanu jest możliwe bez przekazywania parametrów do funkcji zagnieżdżonej lub używania zmiennej globalnej , upraszczając kod.

W językach z funkcjami zagnieżdżonymi funkcje mogą zwykle zawierać stałe lokalne i typy (oprócz zmiennych lokalnych , parametrów i funkcji), hermetyzowane i ukryte w ten sam sposób zagnieżdżony, na dowolnym poziomie głębokości. Może to dodatkowo zwiększyć możliwości strukturyzacji kodu.

Inne zastosowania

Kontrola przepływu

Funkcje zagnieżdżone mogą być również używane do nieustrukturyzowanego przepływu sterowania , używając instrukcji return dla ogólnego nieustrukturyzowanego przepływu sterowania. Może to służyć do bardziej szczegółowego sterowania niż jest to możliwe w przypadku innych wbudowanych funkcji języka — na przykład może umożliwić wcześniejsze zakończenie pętli for, jeśli breaknie jest dostępne, lub wcześniejsze zakończenie zagnieżdżonej pętli for, jeśli -poziom breaklub wyjątki nie są dostępne.

Funkcje wyższego rzędu

Główny artykuł: Funkcje wyższego rzędu

Ponieważ w większości języków funkcje są prawidłowymi typami zwracanymi, możliwe jest utworzenie funkcji zagnieżdżonej, która uzyskuje dostęp do zestawu parametrów z funkcji zewnętrznej i ma tę funkcję jako wartość zwracaną z funkcji zewnętrznej. W ten sposób możliwe jest zwrócenie funkcji, która jest ustawiona tak, aby spełniała określone zadanie, z niewielkimi lub żadnymi dodatkowymi parametrami, co może znacznie zwiększyć wydajność.

Alternatywy

Główną alternatywą dla funkcji zagnieżdżonych w językach, które ich nie obsługują, jest umieszczenie wszystkich odpowiednich funkcji i zmiennych w osobnym module (pliku) i publiczne udostępnienie tylko funkcji opakowującej najwyższego poziomu . W C będzie to generalnie wykonywane za pomocą funkcji statycznych do enkapsulacji i zmiennych statycznych do komunikacji. Osiąga to enkapsulację i współdzielenie stanu, choć nie jest to logiczna organizacja wynikająca z leksykalnego zagnieżdżania funkcji i odbywa się kosztem posiadania oddzielnego pliku. Nie jest to również możliwe na więcej niż jednym poziomie.

Inną alternatywą jest współdzielenie stanu między funkcjami poprzez parametry funkcji, najczęściej przekazując referencje jako argumenty, aby uniknąć kosztów kopiowania. W C jest to zazwyczaj realizowane przez wskaźnik do struktury zawierającej kontekst. To znacznie zwiększa złożoność wywołań funkcji.

W PHP i innych językach funkcja anonimowa jest jedyną alternatywą: funkcja zagnieżdżona jest deklarowana nie jako zwykła funkcja, ale przez referencję jako zmienna lokalna. Aby użyć zmiennych lokalnych w funkcji anonimowej, użyj closure .

Języki

Dobrze znane języki obsługujące funkcje zagnieżdżone leksykalnie to:

Języki funkcjonalne

W większości funkcjonalnych języków programowania , takich jak Scheme, funkcje zagnieżdżone są powszechnym sposobem implementacji algorytmów zawierających pętle. Tworzona jest prosta ( tail ) rekurencyjna funkcja wewnętrzna, która zachowuje się jak główna pętla algorytmu, podczas gdy funkcja zewnętrzna wykonuje czynności startowe, które trzeba wykonać tylko raz. W bardziej złożonych przypadkach, wiele funkcji wzajemnie rekurencyjnych może być tworzonych jako funkcje wewnętrzne.

Niektóre języki bez bezpośredniego wsparcia

Niektóre języki nie mają prostej obsługi składniowej i semantycznej do implementacji funkcji zagnieżdżonych. Niemniej jednak, dla niektórych z nich idea funkcji zagnieżdżonych może być symulowana z pewnym stopniem trudności poprzez użycie innych konstrukcji językowych. Następujące języki mogą aproksymować funkcje zagnieżdżone za pomocą odpowiednich strategii:

  • C++
    • przed C++11: umożliwia definicję klas wewnątrz klas, zapewniając możliwość używania metod klas w sposób podobny do funkcji zagnieżdżonych na jednym poziomie (patrz Obiekt funkcji w C++ ).
    • od C++11: używając wyrażeń lambda, jak w powyższym przykładzie szybkiego sortowania.
  • Eiffel wyraźnie zabrania zagnieżdżania procedur. Ma to na celu zachowanie prostoty języka, a także pozwala na konwencję używania specjalnej zmiennej Result , do oznaczania wyniku funkcji (zwracającej wartość).
  • Visual Basic przy użyciu metod anonimowych lub wyrażeń lambda.
  • Java , za pomocą wyrażeń lambda (zobacz Funkcje anonimowe w Javie ) (od Javy 8) lub poprzez obejście polegające na anonimowej klasie zawierającej pojedynczą metodę. Można również użyć nazwanej klasy zadeklarowanej lokalnie w metodzie.

Realizacja

Zobacz także: Test mężczyzny lub chłopca

Implementacja funkcji zagnieżdżonych może być bardziej skomplikowana niż się wydaje, ponieważ odwołanie do funkcji zagnieżdżonej, która odwołuje się do zmiennych nielokalnych, tworzy zamknięcie . Z tego powodu funkcje zagnieżdżone nie są obsługiwane w niektórych językach, takich jak C, C++ lub Java, ponieważ utrudnia to implementację kompilatorów. Jednak niektóre kompilatory obsługują je jako rozszerzenie specyficzne dla kompilatora. Dobrze znanym tego przykładem jest implementacja C GNU C, która współdzieli kod z kompilatorami dla języków takich jak Pascal, Ada i Modula.

Dostęp do nielokalnych obiektów

Istnieje kilka sposobów implementacji procedur zagnieżdżonych w języku o zasięgu leksykalnym, ale klasyczny sposób jest następujący:

Każdy nielokalny obiekt X jest osiągany przez łącza dostępu w ramkach aktywacji na stosie maszyny. Wywołujący, C, wspomaga wywoływaną procedurę, P, wpychając bezpośrednie łącze do ostatniej aktywacji bezpośredniej enkapsulacji leksykalnej P (P), przed samym wywołaniem. P może wtedy szybko znaleźć odpowiednią aktywację dla określonego X, podążając za ustaloną liczbą (P.depth – X.depth) linków (zwykle niewielka liczba).
Dzwoniący tworzy ten bezpośredni link, (sam) podążając za C.depth – P.depth + 1 starszymi linkami, prowadząc do ostatniej aktywacji (P), a następnie tymczasowo łącząc je z bezpośrednim linkiem do tej aktywacji; link później znika razem z P, dzięki czemu starsze linki znajdujące się pod nim mogą ponownie zostać użyte.
Zauważ, że P jest widoczne i dlatego może być wywoływane przez C, jeśli (P) = C / (C) / ((C)) / itd.

Ta oryginalna metoda jest szybsza niż mogłoby się wydawać, ale mimo to często jest optymalizowana w praktycznych nowoczesnych kompilatorach (przy użyciu wyświetlaczy lub podobnych technik).

Innym sposobem implementacji zagnieżdżonych funkcji, które są używane przez niektóre kompilatory, jest konwersja ("podnoszenie") funkcji zagnieżdżonych na funkcje niezagnieżdżone (gdzie dodatkowe, ukryte parametry zastępują łącza dostępu) przy użyciu procesu znanego jako podnoszenie lambda podczas etapu pośredniego w kompilacji.

Funkcje jako wartości

Aby funkcje lokalne z wartościami nielokalnymi o zasięgu leksykalnym były przekazywane jako wyniki, kod środowiska uruchomieniowego języka musi również niejawnie przekazywać środowisko (dane), które funkcja widzi w swojej funkcji enkapsulacji, tak aby była osiągalna również podczas bieżącej aktywacji otaczającej funkcja już nie istnieje. Oznacza to, że środowisko musi być przechowywane w innym obszarze pamięci niż (później odzyskane części) stosu wykonawczego opartego na chronologicznym, co z kolei implikuje pewien rodzaj swobodnie dynamicznej alokacji pamięci . Wiele starszych języków opartych na Algolu (lub ich dialektach) nie zezwala zatem na przekazywanie funkcji lokalnych, które uzyskują dostęp do wartości nielokalnych, jako wartości zwracanych lub w ogóle nie zezwala na funkcje jako wartości zwracane, chociaż przekazywanie takich funkcji jako argumentów może nadal być możliwe.

Stosy niewykonalne

Co najmniej jedna implementacja funkcji zagnieżdżonych powoduje utratę stosów No-execute (stos NX) . Implementacja funkcji zagnieżdżonych w GCC wywołuje funkcje zagnieżdżone poprzez instrukcję skoku umieszczoną na stosie maszyny w czasie wykonywania. Wymaga to, aby stos był wykonywalny.

Żadne stosy wykonywania i funkcje zagnieżdżone nie wykluczają się wzajemnie w GCC. Jeśli podczas tworzenia programu używana jest funkcja zagnieżdżona, stos NX jest po cichu tracony. GCC oferuje ostrzeżenie -Wtrampoline, aby ostrzec o stanie.

Oprogramowanie opracowane przy użyciu bezpiecznego cyklu życia rozwoju często nie pozwala na użycie zagnieżdżonych funkcji w tym konkretnym kompilatorze (GCC) z powodu utraty stosów NX.

Zobacz też

Uwagi

Bibliografia

Linki zewnętrzne