Función anidada

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

En 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 < i>función envolvente. Debido a reglas simples de alcance recursivo, una función anidada es en sí misma invisible fuera de su función inmediatamente circundante, pero puede ver (acceder) a todos los objetos locales (datos, funciones, tipos, etc.) de su función inmediatamente circundante, así como de cualquier función. (s) que, a su vez, encierra esa función. En teoría, el anidamiento es posible hasta una profundidad ilimitada, aunque normalmente sólo se utilizan unos pocos niveles en los programas prácticos.

Las funciones anidadas se utilizan en muchos enfoques de programación estructurada, incluidos los primeros, como ALGOL, Simula 67 y Pascal, y también en muchos lenguajes dinámicos y funcionales modernos. Sin embargo, tradicionalmente no son compatibles con la familia de lenguajes 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 está 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 circundante, 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 lectura como para escritura.

Las funciones anidadas pueden, en determinadas situaciones (e idiomas), conducir a la creación de un cierre. Si es posible que la función anidada escape de la función envolvente, 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 envolvente, 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 muera el último cierre de referencia y, por lo tanto, las variables automáticas no locales a las que se hace referencia en los cierres no se pueden asignar en la pila. Esto se conoce como problema funarg y es una razón clave por la cual 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

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

función E()x: real): real; función F()Sí.: real): real; Comienzo F := x + Sí. final;Comienzo E := F()3) + F()4)final;

La función F está anidado dentro E. Note que EEs parámetro x es también visible en F (como F es una parte de EMientras ambos x y y son invisibles fuera E y F respectivamente.

Del mismo modo, en Standard ML:

diversión e ()x : real) = Deja diversión f Sí. = x+Sí. dentro f 3 + f 4 final;

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

e :: Float - No. Floate x = f 3 + f 4 Donde f Sí. = x + Sí.

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

flotador E()flotador x){} flotador F()flotador Sí.) {} Regreso x + Sí.; } Regreso F()3) + F()4);}

Quicksort

Un ejemplo más realista es esta implementación de clasificación rápida:

vacío especie()int *Temas, int tamaño) {} vacío rápido #()int primero, int último) {} vacío Swap()int p, int q) {} int tmp = Temas[p]; Temas[p] = Temas[q]; Temas[q] = tmp; }  int partición() {} int pivote = Temas[primero] índice = primero; Swap()índice, último); para ()int i = primero; i c) último; i++) si ()Temas[i] c) pivote) Swap()índice++, i); Swap()índice, último); Regreso índice; } si ()primero c) último) {} int pivoteIndex = partición(); rápido #()primero, pivoteIndex - 1); rápido #()pivoteIndex + 1, último); } } rápido #()0, tamaño - 1);}

Otro ejemplo es la siguiente implementación de la partición Hoare con base rápida usando C++11 sintaxis de expresión de lambda:

plantillac)nombre RandomAccessIterator■auto #()RandomAccessIterator Comienzo, RandomAccessIterator Final)- No.vacío {}auto Partición = ["]() {}/ Plan de partición Hoareauto "Pivot = *Comienzo;auto AdelanteCursor = Comienzo;auto BackwardCursor = Final - 1;auto PartitionPositionFound = falso;auto LocalizarPartitionPosition = ["]() {}mientras ()*AdelanteCursor c) Pivot)++AdelanteCursor;mientras ()Pivot c) *BackwardCursor)--BackwardCursor;si ()AdelanteCursor >= BackwardCursor)PartitionPositionFound = verdadero;másSwap()*AdelanteCursor, *BackwardCursor);};// Función de ayudante de vigilanciaauto MoveOnAndTryAgain = ["]() {}++AdelanteCursor;--BackwardCursor;};//Brief esquema del proceso de partición realmientras ()verdadero) {}LocalizarPartitionPosition();si ()PartitionPositionFound)Regreso BackwardCursor + 1;másMoveOnAndTryAgain();}};//Brief contorno del algoritmo de gama rápidasi ()Comienzo c) Final - 1) {}auto PartitionPosition = Partición();#()Comienzo, PartitionPosition);#()PartitionPosition, Final);}}

Propósito

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

Por lo general, se utilizan como funciones auxiliares o como funciones recursivas dentro de otra función (como en el ejemplo de clasificació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 ni utilizar una variable global, lo que simplifica 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

Control de flujo

Las funciones anidadas también se pueden utilizar para flujo de control no estructurado, utilizando la declaración return para flujo de control no estructurado general. Esto se puede utilizar para un control más detallado que el que es posible con otras funciones integradas del lenguaje; por ejemplo, puede permitir la terminación anticipada de un bucle for si break no está disponible, o la terminación anticipada. de un bucle for anidado si un break de varios niveles o excepciones no están disponibles.

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, es decir, un cierre, y hacer que esa función sea el retorno de la función externa. valor. 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 bastante significativa.

Alternativas

La principal alternativa a las funciones anidadas en idiomas que carecen de apoyo para ellos es colocar todas las funciones y variables pertinentes en un módulo separado (archivo) y exponer solamente la función de envoltura de alto nivel públicamente. En C esto se hará generalmente utilizando funciones estáticas para la encapsulación y variables estáticas para la comunicación. Esto consigue la encapsulación y el intercambio de estado, aunque no la organización lógica dada por el anidamiento lexical de funciones, y viene al costo de tener un archivo separado. Tampoco es posible en más de un solo nivel.

Otra alternativa es compartir el estado entre las funciones a través de parámetros de función, generalmente pasando referencias como argumentos para evitar el costo de la copia. 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 no se declara 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 conocidos que admiten funciones léxicas anidadas incluyen:

Lenguas basadas en ALGOL como ALGOL 68, Simula, Pascal, Modula-2, Modula-3, Oberon, Seed7 y Ada
Versiones modernas de Lisp (con alcance léxico) como Scheme, y Common Lisp
ECMAScript (JavaScript y ActionScript)
Dart
Kotlin ( Funciones locales)
Rust
Scala (funciones fijadas)
Varios grados de soporte en lenguajes de scripting como Ruby, Python, Lua, PHP y Perl
GCC admite funciones anidadas en C, como extensión de lenguaje.
C#, empezando por C# 7.0
El lenguaje D, un lenguaje relacionado con C con funciones anidadas.
Fortran, comenzando con Fortran-90, soporta un nivel único de anidado (CONTAINADO) subrutinas y funciones.
MATLAB (apoyo completo)
Wolfram Language

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. 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 mutuamente recursivas 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 aproximarse a funciones anidadas mediante las estrategias respectivas:

C++
- antes C++11: permite la definición de clases dentro de las clases, proporcionando la capacidad de utilizar métodos de clase de una manera similar a las funciones anidadas en uno nivel (ver objeto Función en C++).
- desde C++11: utilizando expresiones de lambda como en el ejemplo de la gama rápida anterior.
Eiffel explícitamente deja anidar 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 (retorno de valor)
Visual Basic, utilizando métodos anónimos o expresiones de lambda.
Java, utilizando expresiones de lambda (ver funciones anónimas en Java) (desde Java 8) o a través de una solución de trabajo que consiste en una clase anónima que contiene un solo método. También se puede utilizar una clase llamada local a un método.

Implementación

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 este motivo, 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 a objetos no locales

Hay 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 a través de enlaces de acceso en los marcos de activación en la pila de máquina. El callador, C, ayuda al procedimiento llamado, P, empujando un directa enlace con el más recientes activación de la encapsulación lexical inmediata de P, (P), antes de la llamada misma. P puede entonces encontrar rápidamente la activación correcta para un determinado X siguiendo un Número fijo (P. profundidad - X. profundidad) de los enlaces (normalmente un pequeño número).

El callador crea este enlace directo por (él mismo) después de C. profundidad – P. profundidad + 1 enlaces mayores, dando lugar a la última activación de (P), y luego temporalmente bridging over these with a direct link to that activation; the link later disappeareds together with P, whereby the older links under it may come into use again.

Tenga en cuenta que P es visible para, y 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 a menudo se optimiza en compiladores modernos y prácticos (mediante 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 parámetros adicionales ocultos reemplazan los enlaces de acceso) usando un proceso conocido como levantamiento lambda durante una etapa intermedia en la compilación.

Funciones como valores

Para que las funciones locales con elementos no locales de alcance léxico se pasen como resultados, el código de ejecución del lenguaje también debe pasar implícitamente el entorno (datos) que la función ve dentro de su función encapsuladora, de modo que sea accesible también cuando se active la activación actual. de la función envolvente ya no existe. Esto significa que el entorno debe almacenarse en otra área de memoria distinta a (las partes posteriormente recuperadas de) una pila de ejecución basada en cronológicamente, 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 dialectos de los mismos) no permiten que funciones locales que acceden a no locales se pasen como valores de retorno, o no permiten funciones como valores de retorno en absoluto, aunque aún es posible pasar tales funciones como argumentos.

Pilas sin ejecución

La implementación de funciones anidadas por parte de GCC provoca una pérdida de pilas no ejecutadas (pilas NX). Esta implementación llama a funciones anidadas mediante 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. Por lo tanto, las pilas que no se ejecutan y las funciones anidadas son mutuamente excluyentes en GCC. Si se utiliza una función anidada en el desarrollo de un programa, entonces la pila NX se pierde silenciosamente, a menos que se llame a GCC con la opción ‑Wtrampoline para alertar de la condición. El software diseñado utilizando Secure Development Lifecycle a menudo no permite el uso de funciones anidadas en este compilador en particular debido a la pérdida de pilas de NX.

Más resultados...