Función anidada

Una función anidada suele actuar como una función auxiliar o una función recursiva .

Las funciones anidadas se pueden usar para el control de flujo no estructurado , mediante la instrucción `return` para el control general no estructurado. Esto permite un control más preciso que el que ofrecen otras características integradas del lenguaje; por ejemplo, permite la terminación anticipada de un bucle `for` si breakno está disponible, o la terminación anticipada de un bucle `for` anidado si no se dispone de un bucle multinivel breako de excepciones.

En algunos lenguajes, es posible crear una función anidada que acceda a un conjunto de parámetros de la función externa (un cierre ) y que dicha función sea el valor de retorno de la función externa. De este modo, es posible devolver una función configurada para realizar una tarea determinada con pocos o ningún parámetro adicional, lo que puede aumentar el rendimiento de forma significativa. ^{[ 2 ]}

Un ejemplo sencillo en Pascal:

función E ( x : real ) : real ; función F ( y : real ) : real ; inicio F := x + y fin ; inicio E := F ( 3 ) + F ( 4 ) fin ;

La función Festá anidada dentro de E. Tenga en cuenta que Eel parámetro de xtambién es visible en F(ya que Fes parte de E) mientras que tanto xcomo yson invisibles fuera de Ey Frespectivamente.

De manera similar, en Standard ML :

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

En Haskell :

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

En PL/I :

e: procedimiento(x) devuelve(flotante); declarar x flotante; f: procedimiento(y) devuelve(flotante); declarar y flotante; devolver x + y fin; devolver f(3.0) + f(4.0); fin; 

En Python :

def e ( x : float ) -> float : def f ( y : float ) -> float : return x + y return f ( 3.0 ) + f ( 4.0 )

En GNU C ^{[ 3 ]} – que extiende el estándar C con funciones anidadas:

float e ( float x ) { float f ( float y ) { return x + y ; } return f ( 3.0f ) + f ( 4.0f ); }

La siguiente es una implementación de quicksort : ^{[ 4 ]}

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

A continuación se muestra una implementación del algoritmo de ordenación rápida basado en particiones de Hoare utilizando la sintaxis de expresiones lambda de C++11 , que es una tecnología alternativa que también permite ocultar una función dentro de otra:

// Iter representa una plantilla de iterador de acceso aleatorio < typename Iter > void sort ( Iter begin , Iter end ) { auto partition = [ & ]() -> Iter { // Esquema de partición de Hoare Iter & pivot = * begin ; Iter forwardCursor = begin ; Iter backwardCursor = end - 1 ; Iter partitionPositionFound = false ;auto locatePartitionPosition = [ & ]() -> void { while ( * forwardCursor < pivot ) { ++ forwardCursor ; } while ( pivot < * backwardCursor ) { -- backwardCursor ; } if ( forwardCursor >= backwardCursor ) { partitionPositionFound = true ; } else swap ( * forwardCursor , * backwardCursor ); } };// Función auxiliar trivial auto moveOnAndTryAgain = [ & ]() -> void { ++ forwardCursor ; -- backwardCursor ; };// Breve descripción del proceso de partición real while ( true ) { locatePartitionPosition (); if ( partitionPositionFound ) return backwardCursor + 1 ; else { moveOnAndTryAgain (); } } };// Breve descripción del algoritmo quicksort if ( begin < end - 1 ) { Iter partitionPosition = partition (); sort ( begin , partitionPosition ); sort ( partitionPosition , end ); } }

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

Una alternativa común es aprovechar la tecnología de modularidad del lenguaje. Algunas funciones están disponibles para su uso fuera del módulo, mientras que otras solo son visibles dentro del mismo.

En C, esto se puede implementar declarando funciones y variables como estáticas para ocultarlas del código fuera del archivo. ^{[ 10 ]} Esto permite ocultar, encapsular y descomponer datos, pero con un nivel de granularidad diferente al de las funciones anidadas. Esta modularidad no admite más de un nivel de anidamiento.

En los lenguajes orientados a objetos , una clase generalmente proporciona un ámbito en el que las funciones y el estado pueden permanecer ocultos para quienes usan la clase, pero ser accesibles dentro de ella. Algunos lenguajes permiten anidar clases.

Para implementar la ocultación de datos, las funciones pueden pasar datos compartidos como parámetros, pero esto aumenta la complejidad de las llamadas a funciones. ^{[ 1 ]}

En C, esto generalmente se implementa pasando un puntero a una estructura que contiene los datos compartidos. ^{[ 10 ]}

En PHP y otros lenguajes, la función lambda es una alternativa. Una función se define en una instrucción de código en lugar de declararse con la sintaxis de función habitual. No tiene nombre, pero se puede invocar mediante una referencia de función . Estas funciones se pueden definir dentro de una función, así como en otros ámbitos. Para usar variables locales en la función anónima, utilice un cierre .

Los siguientes lenguajes proporcionan características similares a las funciones anidadas:

• C++ – las clases permiten una ocultación y encapsulación de datos similar; definir una clase dentro de otra clase proporciona una estructura similar (véase el objeto Función en C++ ).

• C++11 y posteriores : mediante expresiones lambda (véase el ejemplo de quicksort anterior) ^{[ 11 ]}

• Eiffel prohíbe explícitamente el anidamiento de rutinas para mantener el lenguaje simple; permite la convención de usar una variable especial, Result , para denotar el resultado de una función (que devuelve un valor).

• C# y Visual Basic – mediante expresiones lambda

• Java – desde Java 8, a través de expresiones lambda ^{[ 12 ]} , y en versiones anteriores, a través de una clase anónima que contiene un único método

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

Cualquier objeto no local , X, se alcanza mediante enlaces de acceso en los marcos de activación de la pila de la máquina. El llamador, C, ayuda al procedimiento llamado, P, insertando un enlace directo a la última activación de la encapsulación léxica inmediata de P, (P), antes de la llamada. De esta forma, P puede encontrar rápidamente la activación correcta para un X determinado siguiendo un número fijo de enlaces (P.depth – X.depth), que normalmente es pequeño.

El emisor crea este enlace directo siguiendo (por sí mismo) los enlaces más antiguos C.depth – P.depth + 1, que conducen a la última activación de (P), y luego uniendo temporalmente estos con un enlace directo a esa activación; el enlace desaparece posteriormente junto con P, por lo que los enlaces más antiguos que se encuentran debajo pueden volver a utilizarse.

Tenga en cuenta que P es visible para C 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 aun así suele optimizarse en los compiladores modernos (mediante el uso de pantallas o técnicas similares).

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

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 contenedora, de modo que sea accesible incluso cuando la activación actual de la función contenedora ya no exista. ^{[ 14 ]} Esto significa que el entorno debe almacenarse en un área de memoria diferente a (las partes posteriormente recuperadas 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 . Muchos lenguajes antiguos basados ​​en Algol (o dialectos de los mismos) no permiten que las funciones locales que acceden a no locales se pasen como valores de retorno, o no permiten funciones como valores de retorno en absoluto, aunque pasar dichas funciones como argumentos aún puede ser posible.

La implementación de funciones anidadas de GCC en C provoca la pérdida de pilas de no ejecución (pilas NX). Por lo tanto, el software diseñado con Secure Development Lifecycle a menudo no permite el uso de las funciones anidadas de GCC. ^{[ 15 ]} Por defecto, GCC emitirá una breve notificación cuando un archivo objeto generado requiera una pila ejecutable. Para una advertencia clara al compilar código C, utilice la opción.‑Wtrampolines

El problema se produce porque GCC utiliza "trampolines" (código ejecutable en la pila) para saltar a funciones anidadas. ^{[ 16 ]} El proyecto GCC tiene un método alternativo que podría proporcionar funciones anidadas a través de descriptores no ejecutables; sin embargo, actualmente solo se utiliza en el compilador Ada de GCC .