Problema de Funarg

En informática , el problema de los argumentos de función (funarg problem) se refiere a la dificultad de implementar funciones de primera clase ( funciones como objetos de primera clase ) en implementaciones de lenguajes de programación de manera que se utilice la asignación de memoria basada en pila para las funciones.

La dificultad surge únicamente si el cuerpo de una función anidada hace referencia 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 solución estándar consiste en prohibir dichas referencias o crear cierres . ^{[ 2 ]}

Existen dos versiones sutilmente diferentes del problema de los argumentos de función. El problema de los argumentos de función ascendentes surge al devolver (o transmitir de alguna otra forma "hacia arriba") una función desde una llamada a otra función. El problema de los argumentos de función descendentes surge al pasar una función como parámetro a otra llamada a otra función.

Cuando una función A llama a otra función B durante la ejecución de un programa típico, el estado local de B (incluidos los parámetros y las variables locales ) debe almacenarse en algún lugar. En una función hoja , esto puede almacenarse en registros, pero si B llama a otra función C que a su vez utiliza esos registros, estos deben conservarse en algún lugar de la memoria para que B pueda continuar después de que C finalice su ejecución.

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 inserta, o asigna, antes de que B llame a C, y se extrae, o libera, justo antes de que B regrese. El problema del argumento de función ascendente surge cuando el valor de retorno de B es en sí mismo una función F que hace referencia al estado de B (por ejemplo, alguna variable local V) después de que B haya regresado. A puede llamar a F, que necesita que V todavía esté asignada. Por lo tanto, el marco de pila que contiene las variables de estado de B no debe liberarse cuando B regresa, violando el paradigma de llamada a función basado en la pila .

Una solución al problema de los argumentos de función ascendentes consiste simplemente en asignar todos los registros de activación desde el montón en lugar de la pila y confiar en algún tipo de recolección de basura o conteo de referencias para liberarlos cuando ya no sean necesarios. Históricamente, se ha percibido que la gestión de los registros de activación en el montón es menos eficiente que en la pila (aunque esto se contradice parcialmente ^{[ 3 ]} ) y se ha considerado que impone una complejidad de implementación significativa. La mayoría de las funciones en los programas típicos (menos en los programas en lenguajes de programación funcional ) no crean argumentos de función ascendentes, lo que aumenta las preocupaciones sobre la posible sobrecarga asociada con su implementación. Además, este enfoque es realmente difícil en lenguajes que no admiten la recolección de basura.

Algunos compiladores que priorizan la eficiencia emplean un enfoque híbrido en el que los registros de activación de una función se asignan desde la pila si el compilador puede deducir, mediante análisis estático del programa , que la función no crea argumentos de función ascendentes. En caso contrario, los registros de activación se asignan desde el montón.

Otra solución consiste simplemente en copiar el valor de las variables en el cierre al momento de su creación. Esto provocará un comportamiento diferente en el caso de variables mutables, ya que el estado ya no se compartirá entre cierres. Sin embargo, si se sabe que las variables son constantes, este enfoque será equivalente. Los lenguajes ML adoptan este enfoque, dado que las variables en dichos lenguajes están vinculadas a valores, es decir, no se pueden modificar. Java también adopta este enfoque con respecto a las clases anónimas (y las expresiones lambda desde Java 8), ya que solo permite hacer referencia a variables dentro del ámbito que son efectivamente finalconstantes.

Algunos lenguajes permiten al programador elegir explícitamente entre ambos comportamientos. Las funciones anónimas de PHP 5.3 requieren especificar qué variables incluir en el cierre mediante la use ()cláusula; si la variable se lista por referencia, incluye una referencia a la variable original; de lo contrario, pasa el valor. En las funciones anónimas de Apple Blocks , las variables locales capturadas se capturan por valor de forma predeterminada; si se desea compartir el estado entre cierres o entre el cierre y el ámbito externo, la variable debe declararse con el __blockmodificador, en cuyo caso se asigna en el montón.

componer f g = λx → f ( g x )

Un argumento de función descendente también puede referirse al estado de una función cuando esta no se está ejecutando. Sin embargo, dado que, por definición, la existencia de un argumento de función descendente está contenida en la ejecución de la función que lo crea, el marco de pila de la función generalmente se puede almacenar en la pila. No obstante, la existencia de argumentos de función descendentes implica una estructura de árbol de cierres y marcos de pila que puede complicar el razonamiento humano y automático sobre el estado del programa.

Los argumentos de función descendentes también deben ser compatibles con la implementación de los argumentos de función ascendentes. Por ejemplo, consideremos que A llama a B, que calcula un valor de función F que hace referencia a una variable local V de B. B pasa F como parámetro a la función C, que llama a F (argumento de función descendente) antes de retornar. B utiliza la variable local V y, finalmente, devuelve F a A, que también llama a F (argumento de función ascendente). Tanto B como ambas llamadas a F deben compartir la misma variable local V.

El problema de los argumentos de función descendentes complica la compilación eficiente de las llamadas recursivas de cola . Normalmente, si la última acción de B antes de regresar a A es llamar a una función C (y devolver el valor de retorno de C a A, sin modificar), entonces B puede liberar su marco de pila antes de llamar a C, dejando la pila como si A hubiera llamado a C directamente. Algunos lenguajes prometen que las llamadas recursivas de cola se pueden realizar un número ilimitado de veces en una cantidad fija y limitada de espacio de pila. Sin embargo, si B pasa una función F a C, y F hace referencia a una variable local V de B, entonces el marco de pila de B (o al menos la variable V) debe conservarse hasta que C regrese.

El mismo problema se presenta con el código escrito en estilo de paso de continuaciones , donde las funciones no retornaban, sino que terminaban pasando sus valores de retorno a funciones de continuación (que no retornaban). Dichas llamadas deben implementarse como llamadas de cola para evitar una fuga de memoria ilimitada . Esto convierte una situación de argumentos de función ascendentes (B devuelve F) en una situación de argumentos de función descendentes (B pasa F a la función de continuación), y nuevamente el marco de pila de B debe conservarse mientras F pueda ser llamada.

Históricamente, el problema de los argumentos de funciones ascendentes ha demostrado ser más difícil. Por ejemplo, el lenguaje de programación Pascal permite pasar funciones como argumentos, pero no devolverlas como resultados; por lo tanto, las implementaciones de Pascal deben abordar el problema de los argumentos de funciones descendentes, pero no el ascendente. Los lenguajes de programación Modula-2 y Oberon (descendientes de Pascal) permiten funciones tanto como parámetros como valores de retorno, pero la función asignada no puede ser una función anidada. El lenguaje de programación C históricamente evita la principal dificultad del problema de los argumentos de funciones al no permitir definiciones de funciones anidadas; dado que el entorno de cada función es el mismo, conteniendo solo las variables y funciones globales asignadas estáticamente, un puntero al código de una función la describe completamente. Apple ha propuesto e implementado una sintaxis de cierre para C que resuelve el problema de los argumentos de funciones ascendentes moviendo dinámicamente los cierres de la pila al montón según sea necesario. El lenguaje de programación Java lo aborda exigiendo que el contexto utilizado por las funciones anidadas en clases internas y locales anónimas se declare como `<script>` , y que el contexto utilizado por las expresiones lambda sea efectivamente `<script>`. C# y D tienen expresiones lambda (cierres) que encapsulan un puntero a función y las variables relacionadas.final

En los lenguajes funcionales , las funciones son valores de primera clase que se pueden pasar a cualquier parte. Por lo tanto, las implementaciones de Scheme o Standard ML deben abordar los problemas de los argumentos de función ascendentes y descendentes. Esto se suele lograr representando los valores de las funciones como cierres asignados en el montón , como se describió anteriormente. El compilador de OCaml emplea una técnica híbrida (basada en el análisis estático del programa ) para maximizar la eficiencia.

• Cierre (informática)
• Programación funcional
• Cálculo lambda
• Prueba de hombre o niño
• Enlace de nombre
• Transparencia referencial
• Alcance (programación)
• pila de espaguetis

• José Weizenbaum . “Explicación del Problema del FUNARG” , 1968.
• Joel Moses . "La función de FUNCTION en LISP, o por qué el problema de FUNARG debería llamarse el problema del entorno" . MIT AI Memo 199, 1970.
• Enlaces, procedimientos, funciones, programación funcional y cálculo lambda.