Función anidada - Nested function

En la programación de computadoras , una función anidada (o procedimiento anidado o subrutina ) es una función que se define dentro de otra función, la función envolvente . Debido a las reglas de alcance recursivas simples , una función anidada es en sí misma invisible fuera de su función que la encierra inmediatamente, pero puede ver (acceder) a todos los objetos locales (datos, funciones, tipos, etc.) de su función que lo encierra inmediatamente, así como de cualquier función (s) que, a su vez, encierra esa función. El anidamiento es teóricamente posible a una profundidad ilimitada, aunque normalmente solo se utilizan unos pocos niveles en los programas prácticos.

Las funciones anidadas se utilizan en muchos enfoques de la programación estructurada , incluidos los primeros, como ALGOL , Simula 67 y Pascal , y también en muchos lenguajes dinámicos modernos y lenguajes funcionales . Sin embargo, tradicionalmente no se admiten en la familia de idiomas C (originalmente simple).

Efectos

Las funciones anidadas asumen el alcance de la función o el alcance del bloque . El alcance de una función anidada se encuentra dentro de la función envolvente, es decir, dentro de uno de los bloques constituyentes de esa función, lo que significa que es invisible fuera de ese bloque y también fuera de la función envolvente. Una función anidada puede acceder a otras funciones locales, variables, constantes, tipos, clases, etc.que están en el mismo ámbito, o en cualquier ámbito adjunto, sin pasar parámetros explícitos, lo que simplifica enormemente pasar datos dentro y fuera de la función anidada. Por lo general, esto se permite tanto para la lectura como para la escritura.

Las funciones anidadas pueden en determinadas situaciones (y lenguajes) conducir a la creación de un cierre . Si es posible que la función anidada escape de la función adjunta, por ejemplo, si las funciones son objetos de primera clase y una función anidada se pasa a otra función o se devuelve desde la función adjunta, entonces se crea un cierre y las llamadas a esta función pueden acceder el entorno de la función original. El marco de la función que encierra inmediatamente debe continuar vivo hasta que muere el último cierre de referencia y, por lo tanto, las variables automáticas no locales referenciadas en los cierres no se pueden asignar a la pila . Esto se conoce como el problema de funarg y es una razón clave por la que las funciones anidadas no se implementaron en algunos lenguajes más simples, ya que complica significativamente la generación y el análisis de código, especialmente cuando las funciones están anidadas en varios niveles, compartiendo diferentes partes de su entorno.

Ejemplos de

Un ejemplo usando la sintaxis de Pascal (con ALGOL , Modula 2 , Oberon , Ada , etc. similar): 

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

La función Festá anidada dentro E. Tenga en cuenta que Eel parámetro de xes también visible en F(como Fes parte de E) mientras que ambos xy yson invisibles en el exterior Ey Frespectivamente.

De manera similar, en ML estándar: 

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

Una forma de escribir el mismo ejemplo en la sintaxis de Haskell : 

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

El mismo ejemplo en la sintaxis GNU C (C extendido con funciones anidadas): 

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

Ordenación rápida

Un ejemplo más realista es esta implementación de 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);
}

Otro ejemplo es la siguiente implementación de la ordenación rápida basada en la partición Hoare utilizando la sintaxis de expresión lambda de 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);
	}
}

Propósito

Las definiciones de funciones anidadas léxicamente son una forma de ocultar información y son útiles para dividir las tareas de procedimiento en subtareas que solo son significativas a nivel local. Esto evita saturar otras partes del programa con funciones y variables que no están relacionadas con esas partes.

Por lo general, se usan como funciones auxiliares o como funciones recursivas dentro de otra función (como en el ejemplo de ordenación rápida anterior). Esto tiene el beneficio estructural de organizar el código, evita contaminar el alcance y también permite que las funciones compartan el estado fácilmente. Como la función anidada puede acceder a las variables locales de la función adjunta, es posible compartir el estado sin pasar parámetros a la función anidada o utilizar una variable global , simplificando el código.

En lenguajes con funciones anidadas, las funciones normalmente también pueden contener constantes y tipos locales (además de variables , parámetros y funciones locales ), encapsulados y ocultos de la misma manera anidada, en cualquier nivel de profundidad. Esto puede mejorar aún más las posibilidades de estructuración del código.

Otros usos

Flujo de control

Las funciones anidadas también se pueden utilizar para el flujo de control no estructurado , utilizando la declaración de retorno para el flujo de control no estructurado general. Esto se puede usar para un control más detallado del que es posible con otras características integradas del lenguaje; por ejemplo, puede permitir la terminación anticipada de un bucle for si breakno está disponible, o la terminación anticipada de un bucle for anidado si hay múltiples -nivel breako excepciones no están disponibles.

Funciones de orden superior

Artículo principal: Funciones de orden superior

Como en la mayoría de los lenguajes las funciones son tipos de retorno válidos, es posible crear una función anidada que acceda a un conjunto de parámetros desde la función externa y que esa función sea el valor de retorno de la función externa. Por lo tanto, es posible devolver una función que está configurada para cumplir una determinada tarea con pocos o ningún parámetro adicional, lo que puede aumentar el rendimiento de manera significativa.

Alternativas

La principal alternativa a las funciones anidadas en lenguajes que carecen de soporte para ellas es colocar todas las funciones y variables relevantes en un módulo (archivo) separado y exponer públicamente solo la función contenedora de nivel superior . En C, esto generalmente se hará usando funciones estáticas para encapsulación y variables estáticas para comunicación. Esto logra la encapsulación y el intercambio de estado, aunque no la organización lógica dada por el anidamiento léxico de funciones, y tiene el costo de tener un archivo separado. Tampoco es posible en más de un nivel.

Otra alternativa es compartir el estado entre las funciones a través de los parámetros de la función, la mayoría de las veces pasando referencias como argumentos para evitar el costo de copiar. En C, esto generalmente se implementa mediante un puntero a una estructura que contiene el contexto. Esto aumenta significativamente la complejidad de las llamadas a funciones.

En PHP y otros lenguajes, la función anónima es la única alternativa: la función anidada se declara no como una función habitual, sino por referencia, como una variable local. Para usar variables locales en la función anónima, use cierre .

Idiomas

Los lenguajes bien conocidos que admiten funciones léxicamente anidadas incluyen:

Lenguajes funcionales

En la mayoría de los lenguajes de programación funcionales , como Scheme, las funciones anidadas son una forma común de implementar algoritmos con bucles en ellos. Se crea una función interna recursiva simple ( cola ) , que se comporta como el bucle principal del algoritmo, mientras que la función externa realiza acciones de inicio que solo deben realizarse una vez. En casos más complejos, se pueden crear varias funciones recursivas entre sí como funciones internas.

Algunos idiomas sin soporte directo

Ciertos lenguajes no tienen soporte sintáctico y semántico sencillo para implementar funciones anidadas. Sin embargo, para algunos de ellos, la idea de funciones anidadas puede simularse con cierto grado de dificultad mediante el uso de otras construcciones del lenguaje. Los siguientes lenguajes pueden aproximar funciones anidadas a través de las estrategias respectivas:

  • C ++
    • antes de C ++ 11: permite la definición de clases dentro de clases, lo que brinda la capacidad de usar métodos de clase de una manera similar a las funciones anidadas en un nivel (ver Objeto de función en C ++ ).
    • desde C ++ 11: utilizando expresiones lambda como el ejemplo de ordenación rápida anterior.
  • Eiffel prohíbe explícitamente el anidamiento de rutinas. Esto es para mantener el lenguaje simple y también permite la convención de usar una variable especial, Resultado , para denotar el resultado de una función (de retorno de valor).
  • Visual Basic , mediante el uso de métodos anónimos o expresiones lambda.
  • Java , mediante el uso de expresiones lambda (consulte Funciones anónimas en Java ) (desde Java 8) o mediante una solución alternativa que consiste en una clase anónima que contiene un único método. También se puede usar una clase con nombre declarada local a un método.

Implementación

Ver también: prueba de hombre o niño

La implementación de funciones anidadas puede ser más complicada de lo que parece, ya que una referencia a una función anidada que hace referencia a variables no locales crea un cierre . Por esta razón, las funciones anidadas no son compatibles con algunos lenguajes como C, C ++ o Java, ya que esto dificulta la implementación de los compiladores. Sin embargo, algunos compiladores los admiten como una extensión específica del compilador. Un ejemplo bien conocido de esto es la implementación GNU C de C, que comparte código con compiladores para lenguajes como Pascal, Ada y Modula.

Acceso de objetos no locales

Hay varias formas de implementar procedimientos anidados en un lenguaje de ámbito léxico, pero la forma clásica es la siguiente:

Se llega a cualquier objeto no local , X, a través de enlaces de acceso en los marcos de activación en la pila de la máquina. La persona que llama, C, ayuda al procedimiento llamado, P, presionando un enlace directo a la última activación de la encapsulación léxica inmediata de P, (P), antes de la llamada en sí. Entonces, P puede encontrar rápidamente la activación correcta para un cierto X siguiendo un número fijo (P.depth - X.depth) de enlaces (normalmente un número pequeño).
La persona que llama crea este enlace directo (por sí mismo) siguiendo C.depth - P.depth + 1 enlaces más antiguos, lo que lleva a la última activación de (P), y luego los une temporalmente con un enlace directo a esa activación; el enlace desaparece más tarde junto con P, por lo que los enlaces más antiguos debajo de él pueden volver a utilizarse.
Tenga en cuenta que P es visible para, y por lo tanto, puede ser llamado por, C si (P) = C / (C) / ((C)) / etc.

Este método original es más rápido de lo que parece, pero, sin embargo, a menudo se optimiza en compiladores modernos prácticos (utilizando pantallas o técnicas similares).

Otra forma de implementar funciones anidadas que utilizan algunos compiladores es convertir ("levantar") funciones anidadas en funciones no anidadas (donde los parámetros extra, ocultos, reemplazan los enlaces de acceso) mediante un proceso conocido como elevación lambda durante una etapa intermedia en la compilación.

Funciones como valores

Para que las funciones locales con no locales de ámbito léxico se pasen como resultados, el código de tiempo de ejecución del lenguaje también debe pasar implícitamente el entorno (datos) que la función ve dentro de su función de encapsulación, de modo que sea accesible también cuando la activación actual de la la función ya no existe. Esto significa que el entorno debe almacenarse en otra área de memoria que (las partes recuperadas posteriormente de) una pila de ejecución basada en cronología, lo que, a su vez, implica algún tipo de asignación de memoria libremente dinámica . Por lo tanto, muchos lenguajes antiguos basados ​​en Algol (o sus dialectos) no permiten que las funciones locales que acceden a los no locales se pasen como valores de retorno, o no permiten en absoluto funciones como valores de retorno, aunque el paso de tales funciones como argumentos aún puede ser posible.

Pilas sin ejecución

Al menos una implementación de funciones anidadas provoca una pérdida de pilas sin ejecución (pila NX) . La implementación de funciones anidadas de GCC llama a funciones anidadas a través de una instrucción de salto colocada en la pila de la máquina en tiempo de ejecución. Esto requiere que la pila sea ejecutable.

No hay pilas de ejecución y las funciones anidadas se excluyen mutuamente en GCC. Si se utiliza una función anidada en el desarrollo de un programa, NX Stack se pierde silenciosamente. GCC ofrece la advertencia -Wtrampoline para alertar de la condición.

El software diseñado con el ciclo de vida de desarrollo seguro a menudo no permite el uso de funciones anidadas en este compilador en particular (GCC) debido a la pérdida de NX Stacks.

Ver también

Notas

Referencias

enlaces externos