En informática , el problema de funarg ( problema de argumento de función) se refiere a la dificultad de implementar funciones de primera clase ( funciones como objetos de primera clase ) en implementaciones de lenguaje de programación para usar la asignación de memoria basada en pila de las funciones.
La dificultad solo surge si el cuerpo de una función anidada se refiere directamente (es decir, no mediante el paso de argumentos) a identificadores definidos en el entorno en el que se define la función, pero no en el entorno de la llamada a la función. [1] Una resolución estándar es prohibir tales referencias o crear cierres . [2]
Hay dos versiones sutilmente diferentes del problema del funarg. El problema de funarg ascendente surge de devolver (o transmitir "hacia arriba") una función desde una llamada a función. El problema de funarg descendente surge de pasar una función como parámetro a otra llamada de función.
Problema de funarg hacia arriba
Cuando una función llama a otra durante la ejecución de un programa típico, el estado local de la persona que llama (incluidos los parámetros y las variables locales ) debe conservarse para que la ejecución continúe después de que la persona que llama regrese. En la mayoría de los programas compilados, este estado local se almacena en la pila de llamadas en una estructura de datos llamada marco de pila o registro de activación . Este marco de pila se empuja o se asigna, como preludio a la llamada a otra función, y se abre o se desasigna, cuando la otra función vuelve a la función que hizo la llamada. El problema de funarg hacia arriba surge cuando la función que llama se refiere al estado de la función llamada / salida después de que esa función ha regresado. Por lo tanto, el marco de pila que contiene las variables de estado de la función llamada no debe ser desasignado cuando la función regresa, violando el paradigma de llamada de función basado en pila .
Una solución al problema del funarg ascendente es simplemente asignar todos los registros de activación del montón en lugar de la pila y confiar en alguna forma de recolección de basura o recuento de referencias para desasignarlos cuando ya no sean necesarios. La gestión de registros de activación en el montón se ha percibido históricamente como menos eficiente que en la pila (aunque esto se contradice parcialmente [3] ) y se ha percibido que impone una complejidad de implementación significativa. La mayoría de las funciones en los programas típicos (menos para los programas en lenguajes de programación funcionales ) no crean funargs ascendentes, lo que aumenta las preocupaciones sobre los posibles gastos generales asociados con su implementación. Además, este enfoque es realmente difícil en lenguajes que no admiten la recolección de basura.
Algunos compiladores orientados a la eficiencia emplean un enfoque híbrido en el que los registros de activación de una función se asignan de la pila si el compilador puede deducir, a través del análisis de programa estático , que la función no crea funargs ascendentes. De lo contrario, los registros de activación se asignan desde el montón.
Otra solución es simplemente copiar el valor de las variables en el cierre en el momento en que se crea el cierre. Esto provocará un comportamiento diferente en el caso de variables mutables, porque el estado ya no se compartirá entre cierres. Pero si se sabe que las variables son constantes, entonces este enfoque será equivalente. Los lenguajes ML adoptan este enfoque, ya que las variables en esos lenguajes están vinculadas a valores, es decir, las variables no se pueden cambiar. Java también adopta este enfoque con respecto a las clases anónimas, en el sentido de que solo permite que uno haga referencia a las variables en el ámbito adjunto que son final
(es decir, constantes).
Algunos lenguajes permiten al programador elegir explícitamente entre los dos comportamientos. Las funciones anónimas de PHP 5.3 requieren que uno especifique qué variables incluir en el cierre usando la use ()
cláusula; si la variable está listada por referencia, incluye una referencia a la variable original; de lo contrario, pasa el valor. En las funciones anónimas de Blocks de Apple , las variables locales capturadas se capturan por defecto por valor; si uno quiere compartir el estado entre cierres o entre el cierre y el alcance externo, la variable debe declararse con el __block
modificador, en cuyo caso esa variable se asigna en el montón.
Ejemplo
El siguiente pseudocódigo inspirado en Haskell define la composición de la función :
componer fg = λx → f (gx)
λ
es el operador para construir una nueva función, que en este caso tiene un argumento x
, y devuelve el resultado de aplicar primero g
y x
luego aplicar f
a eso. Esta función λ lleva las funciones f
y g
(o apunta a ellas) como estado interno.
El problema en este caso existe si la función de composición asigna las variables de parámetro f
y g
en la pila. Cuando compose
regresa, el marco de pila que contiene f
y g
se descarta. Cuando la función interna λx
intente acceder g
, accederá a un área de memoria descartada.
Problema de funarg hacia abajo
Un funarg hacia abajo también puede referirse al estado de una función cuando esa función no se está ejecutando. Sin embargo, debido a que, por definición, la existencia de un funarg hacia abajo está contenida en la ejecución de la función que lo crea, el marco de pila para la función normalmente todavía se puede almacenar en la pila. No obstante, la existencia de funargs descendentes implica una estructura de árbol de cierres y marcos de pila que pueden complicar el razonamiento humano y de la máquina sobre el estado del programa.
El problema de funarg hacia abajo complica la compilación eficiente de llamadas de cola y código escrito en estilo de paso de continuación . En estos casos especiales, la intención del programador es (normalmente) que la función se ejecute en un espacio de pila limitado, por lo que el comportamiento "más rápido" puede ser realmente indeseable.
Implicaciones prácticas
Históricamente, el problema del funarg ascendente ha demostrado ser el más difícil. Por ejemplo, el lenguaje de programación Pascal permite que las funciones se pasen como argumentos pero no se devuelvan como resultados; por lo tanto, se requieren implementaciones de Pascal para abordar el problema del funarg descendente pero no el ascendente. Los lenguajes de programación Modula-2 y Oberon (descendientes de Pascal) permiten funciones como parámetros y valores de retorno, pero la función asignada puede no ser una función anidada. El lenguaje de programación C históricamente evita la principal dificultad del problema de funarg al no permitir que se aniden las definiciones de funciones; Debido a que el entorno de cada función es el mismo, que contiene solo las variables y funciones globales asignadas estáticamente, un puntero al código de una función describe la función por completo. Apple ha propuesto e implementado una sintaxis de cierre para C que resuelve el problema de funarg ascendente moviendo dinámicamente los cierres de la pila al montón según sea necesario. [ cita requerida ] El lenguaje de programación Java se ocupa de ello al requerir que el contexto utilizado por las funciones anidadas en las clases internas y locales anónimas se declare final , y que el contexto utilizado por las expresiones lambda sea efectivamente final. C # y D tienen lambdas (cierres) que encapsulan un puntero de función y variables relacionadas.
En los lenguajes funcionales , las funciones son valores de primera clase que se pueden pasar a cualquier lugar. Por lo tanto, las implementaciones de Scheme o Standard ML deben abordar tanto los problemas de funarg ascendentes como descendentes. Por lo general, esto se logra representando los valores de la función como cierres asignados al montón , como se describió anteriormente. El compilador OCaml emplea una técnica híbrida (basada en el análisis del programa ) para maximizar la eficiencia. [ cita requerida ]
Ver también
- Cierre (informática)
- Programación funcional
- Cálculo lambda
- Prueba de hombre o niño
- Vinculación de nombre
- Transparencia referencial
- Alcance (programación)
- Pila de espaguetis
Referencias
- ↑ La función de FUNCTION en LISP o por qué el problema de FUNARG debería llamarse problema ambiental , por Joel Moses, MIT Project MAC memo AI-199, MAC-M-428, junio de 1970 (15 págs.).
- ^ Una solución propuesta al problema de FUNARG , por Erik Sandewall, en: ACM SIGSAM Bulletin 17 (enero de 1971), págs. 29–42.
- ^ Andrew W. Appel , Zhong Shao. Un estudio empírico y analítico del costo de la pila frente a la pila para idiomas con cierres. Informe técnico de Princeton CS TR-450-94 , 1994.
enlaces externos
- Joseph Weizenbaum . "Explicación del problema de FUNARG" , 1968.
- Joel Moisés . "La función de FUNCTION en LISP, o por qué el problema de FUNARG debería llamarse el problema del medio ambiente" . MIT AI Memo 199, 1970.
- Enlaces, procedimientos, funciones, programación funcional y cálculo Lambda