Desfuncionalización

En los lenguajes de programación , la defuncionalización es una transformación en tiempo de compilación que elimina las funciones de orden superior , reemplazándolas por una única función `apply` de primer orden . Esta técnica fue descrita por primera vez por John C. Reynolds en su artículo de 1972, "Intérpretes definicionales para lenguajes de programación de orden superior". Reynolds observó que un programa dado contiene solo un número finito de abstracciones de funciones, de modo que a cada una se le puede asignar y reemplazar por un identificador único. Cada aplicación de función dentro del programa se reemplaza entonces por una llamada a la función `apply` con el identificador de la función como primer argumento. La única tarea de la función `apply` es procesar este primer argumento y luego ejecutar las instrucciones indicadas por el identificador de la función en los argumentos restantes.

Una complicación a esta idea básica es que las abstracciones de funciones pueden hacer referencia a variables libres . En tales situaciones, la desfuncionalización debe ir precedida de la elevación de lambda , de modo que cualquier variable libre de una abstracción de función se pase como argumento adicional a apply . Además, si se admiten cierres como valores de primera clase , se hace necesario representar estas vinculaciones capturadas mediante la creación de estructuras de datos.

En lugar de utilizar una única función `apply` para todas las abstracciones de funciones en un programa, se pueden emplear diversos tipos de análisis de flujo de control (incluidas distinciones simples basadas en la aridad o la firma de tipo ) para determinar qué función(es) se pueden llamar en cada punto de aplicación de la función, y se puede hacer referencia a una función `apply` especializada . Como alternativa, el lenguaje de destino puede admitir llamadas indirectas mediante punteros a funciones , lo que puede ser más eficiente y extensible que un enfoque basado en la asignación de funciones.

Además de su uso como técnica de compilación para lenguajes funcionales de orden superior , la desfuncionalización se ha estudiado (en particular por Olivier Danvy y colaboradores) como una forma de transformar mecánicamente intérpretes en máquinas abstractas . La desfuncionalización también está relacionada con la técnica de la programación orientada a objetos de representar funciones mediante objetos de función (como alternativa a los cierres).

A continuación se presenta una traducción a Haskell de un ejemplo de Olivier Danvy . Considere el Treetipo de dato y el siguiente programa.

Datos Árbol a = Hoja a | Nodo ( Árbol a ) ( Árbol a )

cons :: a -> [ a ] ​​-> [ a ] ​​cons x xs = x : xso :: ( b -> c ) -> ( a -> b ) -> a -> c o f g x = f ( g x )aplanar :: Árbol t -> [ t ] aplanar t = caminar t []caminar :: Árbol t -> [ t ] -> [ t ] caminar ( Hoja x ) = cons x caminar ( Nodo t1 t2 ) = o ( caminar t1 ) ( caminar t2 )

La desfuncionalización reemplaza todas las funciones de orden superior (en este caso, oes la única función de orden superior) con un valor del Lamtipo de dato. En lugar de llamar directamente a las funciones de orden superior, introduce una applyfunción que interpreta el Lamtipo de dato.

datos Lam a = LamCons a | LamO ( Lam a ) ( Lam a )aplicar :: Lam a -> [ a ] ​​-> [ a ] ​​aplicar ( LamCons x ) xs = x : xs aplicar ( LamO f1 f2 ) xs = aplicar f1 ( aplicar f2 xs )cons_def :: a -> Lam a cons_def x = LamCons xo_def :: Lam a -> Lam a -> Lam a o_def f1 f2 = LamO f1 f2flatten_def :: Tree t -> [ t ] flatten_def t = apply ( walk_def t ) []walk_def :: Árbol t -> Lam t walk_def ( Hoja x ) = cons_def x walk_def ( Nodo t1 t2 ) = o_def ( walk_def t1 ) ( walk_def t2 )

• Conversión de cierre
• Evaluación parcial

• Reynolds, John (agosto de 1972). "Intérpretes definicionales para lenguajes de programación de orden superior". Actas de la Conferencia Anual de la ACM . Boston, Massachusetts. págs. 717–740 . doi : 10.1145/800194.805852 . 
• Danvy, Olivier ; Nielsen, Lasse R. (2001). "Desfuncionalización en el trabajo" (PDF) . Actas de la Conferencia ACM SIGPLAN sobre Principios y Práctica de la Programación Declarativa . págs. 162–174 . doi : 10.1145/773184.773202 . Archivado del original (PDF) el 27 de septiembre de 2011. Recuperado el 24 de agosto de 2011 . (Versión más completa: Informe técnico BRICS-RS-01-23 )
• Danvy, Olivier ; Millikin, Kevin R. (junio de 2009). "Refuncionalización en el trabajo". Science of Computer Programming . 74 (8): 534– 549. doi : 10.1016/j.scico.2007.10.007 .(También disponible como Informe Técnico BRICS-RS-07-7 )

• Desfuncionalización (Lenguajes de Programación) . Universidad de Oxford.