En los lenguajes de programación , la desfuncionalización es una transformación en tiempo de compilación que elimina las 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 reemplazada por una llamada a la función de aplicación con el identificador de función como primer argumento. El aplicar El único trabajo de la función es enviar en este primer argumento y luego ejecutar las instrucciones indicadas por el identificador de la 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 la conversión de cierre (elevación lambda) , de modo que cualquier variable libre de una abstracción de función se pase como argumentos adicionales para aplicar . Además, si los cierres se admiten como valores de primera clase , es necesario representar estos enlaces capturados mediante la creación de estructuras de datos.
En lugar de tener un único despacho de función de aplicación en todas las abstracciones de funciones en un programa, se pueden emplear varios tipos de análisis de flujo de control (incluidas distinciones simples basadas en arity o firma de tipo ) para determinar qué función (es) se pueden llamar en cada aplicación de función. site, y en su lugar se puede hacer referencia a una función de aplicación especializada . Alternativamente, el idioma 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 despacho.
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 a 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 por objetos de función (como una alternativa a los cierres).
Ejemplo
Este es un ejemplo dado por Olivier Danvy , traducido a Haskell:
Dado el tipo de datos Tree:
árbol de datos a = Hoja a | Nodo ( árbol a ) ( árbol a )
Desfuncionalizaremos el siguiente programa:
contras :: a -> [ a ] -> [ a ] contras 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 )
Desfuncionalizamos reemplazando todas las funciones de orden superior (en este caso, o
es la única función de orden superior) con un valor del Lam
tipo de datos, y en lugar de llamarlas directamente, introducimos una apply
funció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 xo_def :: Lam a -> Lam a -> Lam a o_def f1 f2 = LamO f1 f2flatten_def :: Árbol t -> [ t ] flatten_def t = aplicar ( walk_def t ) []walk_def :: Tree t -> Lam t walk_def ( Hoja x ) = cons_def x walk_def ( Nodo t1 t2 ) = o_def ( walk_def t1 ) ( walk_def t2 )
Ver también
Referencias
- Reynolds, John (agosto de 1972). "Intérpretes de definiciones para lenguajes de programación de orden superior". Actas de la Conferencia Anual de 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 .(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". Ciencia de la Programación de Computadores . 74 (8): 534–549. doi : 10.1016 / j.scico.2007.10.007 .(También disponible como Informe técnico BRICS-RS-07-7 )
enlaces externos
- Desfuncionalización (lenguajes de programación) . Universidad de Oxford.