Alternativas a la desfuncionalización

La desfuncionalización es una transformación descrita por primera vez en 1972 por John C. Reynolds para eliminar las funciones de orden superior. ¿Hay transformaciones alternativas (¿más eficientes?) Para eliminar las funciones de orden superior?

Hay tres enfoques principales (que yo sepa) para implementar funciones de orden superior. Desfuncionalización, conversión de cierre / levantamiento lambda y combinadores.

Vamos a escribir $A \Rightarrow B$ para el tipo de una función de orden superior de $A$ a $B$ y $A \to B$para el tipo de punteros de función de estilo C de$A$ a $B$. (Si quisiéramos formalizar esto, podríamos decir que la abstracción del puntero de función solo está permitida en el entorno vacío).

La conversión de cierre es la idea de que elegimos la representación

$$A \Rightarrow B \equiv \exists E.(E, (E, A) \to B)$$ los $E$normalmente será la tupla que contiene los valores de las variables libres en el sitio de abstracción lambda. Sin embargo, podría ser alguna otra representación.

El levantamiento de lambda adopta un enfoque algo diferente y más global en el que una abstracción de lambda se extrae hacia dentro para contener ámbitos que agregan variables libres como parámetros en el camino, hasta que alcanza el alcance de nivel superior. Si bien esto trata con la estructuración de bloques, para manejar los usos de funciones de orden superior se requiere una aplicación parcial. Luego puede pasar funciones aplicadas parcialmente, pero esta es básicamente la misma representación que la conversión de cierre.

Si desea eliminar los punteros de función, podemos utilizar la desfuncionalización, que, en este caso especial, simplemente produce una enumeración. Sin embargo, hay pocas razones para hacerlo, ya que los punteros de función son construcciones naturales en la mayoría de los lenguajes ensambladores.

El siguiente enfoque es usar combinadores. Esto es básicamente lo mismo que el levantamiento lambda y el uso de aplicaciones parciales, excepto que se utiliza un conjunto fijo de funciones de nivel superior, y todas las demás funciones se expresan como combinaciones de ellas. (Si no tienen un conjunto fijo predefinido de combinadores, entonces esto generalmente es solo un enfoque basado en levantamiento lambda como lo describí anteriormente). Una función de orden superior se representaría efectivamente por un valor en un tipo de datos usando la sintaxis de Haskell como el siguiente (usando SKcombinadores ):

data CA = S | K | App CA CA -- plus other things in reality, like primitive values

Una representación más parecida al cálculo de la columna vertebral probablemente tenga más sentido para la eficiencia. O podrías hacer algo como:

data CA = S0 | S1 CA | S2 CA CA | K0 | K1 CA  

La aplicación de una función de orden superior se divide en dos casos: un combinador se ha aplicado completamente y, por lo tanto, debe ejecutarse, o devolvemos un nuevo valor que representa la aplicación (parcial).

No he hecho una encuesta exhaustiva, pero estoy bastante seguro de que las variaciones en la conversión de cierre son, con mucho, la estrategia de implementación más común para funciones de orden superior (de ahí que a menudo se las llame "cierres"). Tiene las bonitas propiedades de ser modular, simple y razonablemente eficiente incluso en su forma más ingenua. Se necesita una buena selección de combinadores de base y cierta inteligencia para lograr que los enfoques basados ​​en combinador funcionen bien. La desfuncionalización simplemente no se usa ampliamente por lo que puedo decir, pero hay pocas razones para no aprovechar los punteros de función. En la medida en que lo haga, por ejemplo, en lugar de un análisis de caso grande, tiene una tabla de punteros de función en los que indexa, básicamente ha recreado la conversión de cierre.

Hay algunos otros enfoques. Una es la creación de instancias de plantilla, que básicamente es tomar$\beta$-reducción literalmente, y simplemente literalmente sustituye términos en otros términos. Por lo general, esto requiere tener y manipular una sintaxis abstracta con estructura de árbol. Las funciones de orden superior se representan por sus términos lambda (sintácticos) o "plantillas" de los mismos que pueden simplificar la realización de las sustituciones.