Verschachtelte Funktion - Nested function

In der Computerprogrammierung ist eine verschachtelte Funktion (oder verschachtelte Prozedur oder Unterroutine ) eine Funktion, die innerhalb einer anderen Funktion, der einschließenden Funktion, definiert ist . Aufgrund einfacher rekursiver Gültigkeitsbereichsregeln ist eine verschachtelte Funktion selbst außerhalb ihrer unmittelbar umschließenden Funktion unsichtbar, kann jedoch alle lokalen Objekte (Daten, Funktionen, Typen usw.) ihrer unmittelbar umschließenden Funktion sowie jeder beliebigen Funktion sehen (zugreifen). (s), die wiederum diese Funktion umschließt. Die Verschachtelung ist theoretisch in unbegrenzter Tiefe möglich, obwohl in praktischen Programmen normalerweise nur wenige Ebenen verwendet werden.

Verschachtelte Funktionen werden in vielen Ansätzen der strukturierten Programmierung verwendet , auch in frühen Ansätzen wie ALGOL , Simula 67 und Pascal , aber auch in vielen modernen dynamischen Sprachen und funktionalen Sprachen . Sie werden jedoch in der (ursprünglich einfachen) C-Sprachfamilie traditionell nicht unterstützt.

Auswirkungen

Verschachtelte Funktionen nehmen den Funktionsbereich oder den Blockbereich an . Der Geltungsbereich einer verschachtelten Funktion liegt innerhalb der einschließenden Funktion, dh innerhalb eines der konstituierenden Blöcke dieser Funktion, was bedeutet, dass sie außerhalb dieses Blocks und auch außerhalb der einschließenden Funktion unsichtbar ist. Eine verschachtelte Funktion kann ohne explizite Parameterübergabe auf andere lokale Funktionen, Variablen, Konstanten, Typen, Klassen usw. zugreifen, die sich im gleichen Bereich oder in einem umschließenden Bereich befinden, was die Übergabe von Daten in die und aus der verschachtelten Funktion erheblich vereinfacht. Dies ist in der Regel sowohl beim Lesen als auch beim Schreiben zulässig.

Verschachtelte Funktionen können in bestimmten Situationen (und Sprachen) zur Bildung eines Abschlusses führen . Wenn es der verschachtelten Funktion möglich ist, der einschließenden Funktion zu entkommen , zum Beispiel wenn Funktionen erstklassige Objekte sind und eine verschachtelte Funktion an eine andere Funktion übergeben oder von der einschließenden Funktion zurückgegeben wird, dann wird eine Closure erstellt und Aufrufe dieser Funktion können darauf zugreifen die Umgebung der ursprünglichen Funktion. Der Frame der unmittelbar umschließenden Funktion muss solange aktiv sein, bis der letzte referenzierende Abschluss stirbt und nicht-lokale automatische Variablen, auf die in Abschlüssen verwiesen wird, können daher nicht im Stapel zugewiesen werden . Dies ist als Funarg-Problem bekannt und ist ein Hauptgrund, warum verschachtelte Funktionen in einigen einfacheren Sprachen nicht implementiert wurden, da es die Codegenerierung und -analyse erheblich erschwert, insbesondere wenn Funktionen auf verschiedenen Ebenen verschachtelt sind und verschiedene Teile ihrer Umgebung teilen.

Beispiele

Ein Beispiel mit Pascal-Syntax (mit ALGOL , Modula 2 , Oberon , Ada usw. ähnlich): 

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

Die Funktion Fist darin eingebettet E. Beachten Sie, dass E‚S - Parameter xsichtbar sind auch in F(als Fein Teil E) , während beide xund yunsichtbar außerhalb sind Eund Fjeweils.

Ähnlich in Standard-ML: 

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

Eine Möglichkeit, dasselbe Beispiel in Haskell- Syntax zu schreiben : 

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

Das gleiche Beispiel in GNU-C- Syntax (C erweitert mit verschachtelten Funktionen): 

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

Schnelle Sorte

Ein realistischeres Beispiel ist diese Implementierung von 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);
}

Ein weiteres Beispiel ist die folgende Implementierung des auf Hoare-Partitionen basierenden Quicksorts unter Verwendung der C++11- Lambda-Ausdruckssyntax : 

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

Zweck

Lexikalisch verschachtelte Funktionsdefinitionen sind eine Form des Information Hiding und sind nützlich, um prozedurale Aufgaben in Teilaufgaben zu unterteilen, die nur lokal sinnvoll sind. Dadurch wird vermieden, dass andere Teile des Programms mit Funktionen und Variablen überladen werden, die nichts mit diesen Teilen zu tun haben.

Sie werden normalerweise als Hilfsfunktionen oder als rekursive Funktionen innerhalb einer anderen Funktion verwendet (wie im obigen Quicksort-Beispiel). Dies hat den strukturellen Vorteil, den Code zu organisieren, den Umfang nicht zu verschmutzen und es den Funktionen auch zu ermöglichen, den Status einfach gemeinsam zu nutzen. Da die verschachtelte Funktion auf lokale Variablen der einschließenden Funktion zugreifen kann, ist die gemeinsame Nutzung des Zustands möglich, ohne Parameter an die verschachtelte Funktion zu übergeben oder eine globale Variable zu verwenden , was den Code vereinfacht.

In Sprachen mit verschachtelten Funktionen können Funktionen normalerweise auch lokale Konstanten und Typen (zusätzlich zu lokalen Variablen , Parametern und Funktionen) enthalten, die auf dieselbe verschachtelte Weise in beliebiger Tiefe gekapselt und versteckt sind. Dies kann die Möglichkeiten der Codestrukturierung weiter verbessern.

Andere Verwendungen

Kontrollfluss

Verschachtelte Funktionen können auch für die unstrukturierte Ablaufsteuerung verwendet werden , indem Sie die return-Anweisung für die allgemeine unstrukturierte Ablaufsteuerung verwenden. Dies kann für eine feinere Steuerung verwendet werden, als dies mit anderen integrierten Funktionen der Sprache möglich ist – zum Beispiel kann es das vorzeitige Beenden einer for-Schleife ermöglichen, wenn breakes nicht verfügbar ist, oder das vorzeitige Beenden einer verschachtelten for-Schleife, wenn ein multi -Ebene breakoder Ausnahmen sind nicht verfügbar.

Funktionen höherer Ordnung

Hauptartikel: Funktionen höherer Ordnung

Da Funktionen in den meisten Sprachen gültige Rückgabetypen sind, ist es möglich, eine verschachtelte Funktion zu erstellen, die auf einen Satz von Parametern der äußeren Funktion zugreift und diese Funktion als Rückgabewert der äußeren Funktion verwendet. So ist es möglich, eine Funktion, die eine bestimmte Aufgabe erfüllen soll, ohne oder mit wenigen weiteren Parametern zurückzugeben, was die Leistung erheblich steigern kann.

Alternativen

Die Hauptalternative zu verschachtelten Funktionen in Sprachen, die diese nicht unterstützen, besteht darin, alle relevanten Funktionen und Variablen in einem separaten Modul (Datei) zu platzieren und nur die Wrapper-Funktion der obersten Ebene öffentlich zugänglich zu machen. In C geschieht dies im Allgemeinen durch die Verwendung statischer Funktionen zur Kapselung und statischer Variablen zur Kommunikation. Dies erreicht eine Kapselung und gemeinsame Nutzung des Zustands, jedoch nicht die logische Organisation, die durch die lexikalische Verschachtelung von Funktionen gegeben ist, und geht mit dem Preis einer separaten Datei einher. Es ist auch nicht in mehr als einer Ebene möglich.

Eine andere Alternative besteht darin, den Zustand zwischen den Funktionen über Funktionsparameter zu teilen, wobei meistens Referenzen als Argumente übergeben werden, um die Kosten des Kopierens zu vermeiden. In C wird dies im Allgemeinen durch einen Zeiger auf eine Struktur implementiert, die den Kontext enthält. Dies erhöht die Komplexität der Funktionsaufrufe erheblich.

In PHP und anderen Sprachen ist die anonyme Funktion die einzige Alternative: Die verschachtelte Funktion wird nicht als normale Funktion, sondern per Referenz als lokale Variable deklariert. Um lokale Variablen in der anonymen Funktion zu verwenden, verwenden Sie Closure .

Sprachen

Zu den bekannten Sprachen, die lexikalisch verschachtelte Funktionen unterstützen, gehören:

Funktionale Sprachen

In den meisten funktionalen Programmiersprachen , wie z. B. Scheme, sind verschachtelte Funktionen eine gängige Methode zur Implementierung von Algorithmen mit Schleifen darin. Es wird eine einfache ( tail ) rekursive innere Funktion erstellt, die sich als Hauptschleife des Algorithmus verhält, während die äußere Funktion Startaktionen ausführt, die nur einmal ausgeführt werden müssen. In komplexeren Fällen können mehrere sich gegenseitig rekursive Funktionen als innere Funktionen erzeugt werden.

Einige Sprachen ohne direkte Unterstützung

Bestimmte Sprachen haben keine direkte syntaktische und semantische Unterstützung, um verschachtelte Funktionen zu implementieren. Dennoch lässt sich für einige von ihnen die Idee verschachtelter Funktionen mit einem gewissen Schwierigkeitsgrad durch die Verwendung anderer Sprachkonstrukte simulieren. Die folgenden Sprachen können verschachtelte Funktionen durch die jeweiligen Strategien annähern:

  • C++
    • vor C++11: ermöglicht die Definition von Klassen innerhalb von Klassen und bietet die Möglichkeit, Klassenmethoden ähnlich wie verschachtelte Funktionen auf einer Ebene zu verwenden (siehe Funktionsobjekt in C++ ).
    • seit C++11: unter Verwendung von Lambda-Ausdrücken als Quicksort-Beispiel oben.
  • Eiffel verbietet ausdrücklich das Verschachteln von Routinen. Dies dient dazu, die Sprache einfach zu halten und ermöglicht auch die Konvention, eine spezielle Variable, Result , zu verwenden, um das Ergebnis einer (wertrückgebenden) Funktion zu bezeichnen.
  • Visual Basic , indem Sie anonyme Methoden oder Lambda-Ausdrücke verwenden.
  • Java , durch Verwendung von Lambda-Ausdrücken (siehe Anonyme Funktionen in Java ) (seit Java 8) oder durch eine Problemumgehung, die in einer anonymen Klasse mit einer einzelnen Methode besteht. Eine für eine Methode lokal deklarierte benannte Klasse kann ebenfalls verwendet werden.

Implementierung

Siehe auch: Mann- oder Jungentest

Die Implementierung verschachtelter Funktionen kann komplizierter sein, als es den Anschein hat, da ein Verweis auf eine verschachtelte Funktion, die auf nicht-lokale Variablen verweist, eine Closure erzeugt . Aus diesem Grund werden verschachtelte Funktionen in einigen Sprachen wie C, C++ oder Java nicht unterstützt, da dies die Implementierung von Compilern erschwert. Einige Compiler unterstützen sie jedoch als Compiler-spezifische Erweiterung. Ein bekanntes Beispiel dafür ist die GNU-C- Implementierung von C, die Code mit Compilern für Sprachen wie Pascal, Ada und Modula teilt.

Zugriff auf nicht lokale Objekte

Es gibt mehrere Möglichkeiten, verschachtelte Prozeduren in einer Sprache mit lexikalischem Geltungsbereich zu implementieren, aber der klassische Weg ist wie folgt:

Jedes nicht-lokale Objekt X wird über Zugriffslinks in den Aktivierungsrahmen auf dem Maschinenstapel erreicht. Der Anrufer C unterstützt die aufgerufene Prozedur P, indem er vor dem Anruf selbst eine direkte Verbindung zur letzten Aktivierung der unmittelbaren lexikalischen Kapselung (P) von P drückt . P kann dann schnell die richtige Aktivierung für ein bestimmtes X finden, indem er einer festen Anzahl (P.Tiefe – X.Tiefe) von Links (normalerweise eine kleine Anzahl) folgt.
Der Anrufer erstellt diesen direkten Link, indem er (selbst) C.depth – P.depth + 1 älteren Links folgt, die bis zur letzten Aktivierung von (P) führen, und diese dann vorübergehend mit einem direkten Link zu dieser Aktivierung überbrückt; der Link verschwindet später zusammen mit P, wobei die darunter liegenden älteren Links wieder zum Einsatz kommen können.
Beachten Sie, dass P für C sichtbar ist und daher von C aufgerufen werden kann, wenn (P) = C / (C) / ((C)) / etc.

Diese ursprüngliche Methode ist schneller, als es den Anschein hat, aber sie wird dennoch oft in praktischen modernen Compilern (mit Hilfe von Displays oder ähnlichen Techniken) optimiert .

Eine weitere Möglichkeit , verschachtelte Funktionen zu implementieren , die von einigen Compilern verwendet wird , ist zu konvertieren ( „Lift“) verschachtelte Funktionen in nicht verschachtelte Funktionen (wobei zusätzliche, versteckt, Parameter , welche die Zugangsverbindungen zu ersetzen) , ein Verfahren , wie bekannt , unter Verwendung von Lambda - Hebe während einer Zwischenstufe in der Zusammenstellung.

Funktionen als Werte

Damit lokale Funktionen mit lexikalisch beschränkten nichtlokalen Werten als Ergebnisse übergeben werden, muss der Sprachlaufzeitcode auch implizit die Umgebung (Daten) übergeben, die die Funktion in ihrer Kapselungsfunktion sieht, damit sie auch bei der aktuellen Aktivierung der Kapselung erreichbar ist Funktion nicht mehr vorhanden. Dies bedeutet, dass die Umgebung in einem anderen Speicherbereich gespeichert werden muss als (die später zurückgewonnenen Teile davon) eines chronologisch basierten Ausführungsstapels, was wiederum eine Art frei dynamische Speicherzuweisung impliziert . Viele ältere Algol-basierte Sprachen (oder Dialekte davon) erlauben daher keine Übergabe von lokalen Funktionen, die auf Nicht-Lokale zugreifen, als Rückgabewerte oder überhaupt keine Funktionen als Rückgabewerte, obwohl die Übergabe solcher Funktionen als Argumente möglicherweise noch möglich ist.

Nicht auszuführende Stacks

Mindestens eine Implementierung verschachtelter Funktionen verursacht einen Verlust von No-Execute-Stacks (NX-Stack) . Die Implementierung verschachtelter Funktionen von GCC ruft verschachtelte Funktionen über eine Sprunganweisung auf, die zur Laufzeit in den Maschinenstapel eingefügt wird. Voraussetzung dafür ist, dass der Stack ausführbar ist.

Unter GCC schließen sich keine Ausführungsstapel und verschachtelte Funktionen gegenseitig aus. Wird bei der Entwicklung eines Programms eine verschachtelte Funktion verwendet, geht der NX-Stack stillschweigend verloren. GCC bietet die Warnung -Wtrampolin , um auf den Zustand aufmerksam zu machen.

Software, die mit Secure Development Lifecycle entwickelt wurde , lässt aufgrund des Verlusts von NX-Stacks häufig die Verwendung verschachtelter Funktionen in diesem speziellen Compiler (GCC) nicht zu.

Siehe auch

Anmerkungen

Verweise

Externe Links