En lenguajes de programación , la desfuncionalización es una transformación en tiempo de compilación que elimina funciones de orden superior , reemplazándolas por una única función de aplicación de primer orden . La técnica fue descrita por primera vez por John C. Reynolds en su artículo de 1972, "Intérpretes de definición para lenguajes de programación de orden superior". La observación de Reynolds fue que un programa dado contiene solo un número finito de abstracciones de funciones, de modo que cada una puede ser asignada y reemplazada por un identificador único. Cada aplicación de función dentro del programa es luego reemplazada por una llamada a la función de aplicación con el identificador de función como primer argumento. El único trabajo de la función de aplicación es despachar en este primer argumento y luego ejecutar las instrucciones denotadas por el identificador de función en los argumentos restantes.
Una complicación de esta idea básica es que las abstracciones de funciones pueden hacer referencia a variables libres . En tales situaciones, la desfuncionalización debe estar precedida por una conversión de cierre (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 estos enlaces capturados mediante la creación de estructuras de datos.
En lugar de tener una única función apply que se despache en todas las abstracciones de funciones de un programa, se pueden emplear varios tipos de análisis de flujo de control (incluidas distinciones simples basadas en aridad o firma de tipo ) para determinar qué función(es) se pueden llamar en cada sitio de aplicación de función, y se puede hacer referencia a una función apply especializada en su lugar. Como alternativa, el lenguaje de destino puede admitir llamadas indirectas a través de punteros de función , que pueden ser más eficientes y extensibles que un enfoque basado en el envío.
Además de su uso como técnica de compilación para lenguajes funcionales de orden superior , la desfuncionalización ha sido estudiada (particularmente por Olivier Danvy y colaboradores) como una forma de transformar mecánicamente los 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 una alternativa a los cierres).
Este es un ejemplo dado por Olivier Danvy , traducido a Haskell:
Dado el tipo de datos Árbol:
datos Árbol a = Hoja a | Nodo ( Árbol a ) ( Árbol a ) Desfuncionalizaremos el siguiente programa:
contras :: a -> [ a ] -> [ a ] contras x xs = x : xs o :: ( 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 ) Desfuncionalizamos reemplazando todas las funciones de orden superior (en este caso, oes la única función de orden superior) con un valor del Lamtipo de datos, y en lugar de llamarlas directamente, introducimos una applyfunción que interpreta el tipo de datos:
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 x o_def :: Lam a -> Lam a -> Lam a o_def f1 f2 = LamO f1 f2 flatten_def :: Árbol t -> [ t ] flatten_def t = aplicar ( walk_def t ) [] walk_def :: Árbol t -> Hoja t walk_def ( Hoja x ) = cons_def x walk_def ( Nodo t1 t2 ) = o_def ( walk_def t1 ) ( walk_def t2 )