haskell - ¿Qué son los super combinadores y las formas aplicativas constantes?

functional-programming combinators

Question

Estoy luchando con lo que son los Super Combinadores :

Un supercombinador es una constante o un combinador que contiene solo supercombinadores como subexpresiones.

Y también con lo que son las formas de aplicación constante :

Cualquier super combinator que no sea una abstracción lambda. Esto incluye expresiones verdaderamente constantes como 12, ((+) 1 2), [1,2,3], así como funciones parcialmente aplicadas como ((+) 4). Tenga en cuenta que este último ejemplo es equivalente en eta abstracción a / x -> (+) 4 x que no es un CAF.

¡Esto no tiene ningún sentido para mí! ¿No es ((+) 4) tan "verdaderamente constante" como 12? Los CAF suenan como valores para mi mente simple.

Answer 1

Estas páginas wiki de Haskell a las que hace referencia son antiguas, y creo que, lamentablemente, están escritas. Particularmente desafortunado es que mezclan CAF y supercombinadores. Los supercombinadores son interesantes pero no están relacionados con el GHC. Los CAF son todavía una parte importante de GHC, y pueden entenderse sin hacer referencia a supercombinadores.

Así que vamos a empezar con los supercombinadores . Los combinadores se derivan de la lógica combinatoria y, en el uso aquí, consisten en funciones que solo aplican los valores pasados ​​entre sí en una forma u otra, es decir, combinan sus argumentos. El conjunto más famoso de combinadores son S, K y I , que en conjunto son Turing-complete. Los supercombinadores, en este contexto, son funciones creadas solo con valores pasados, combinadores y otros supercombinadores. Por lo tanto, cualquier supercombinador se puede expandir, mediante sustitución, en un antiguo combinador simple.

Algunos compiladores para lenguajes funcionales (¡no GHC!) Utilizan combinadores y supercombinadores como pasos intermedios en la compilación. Al igual que con cualquier tecnología de compilación similar, la razón para hacer esto es admitir un análisis de optimización que se realiza más fácilmente en un lenguaje tan simple y simplificado. Uno de esos lenguajes centrales construidos sobre supercombinadores es la epic Edwin Brady.

Las formas de aplicación constante son algo completamente distinto. Son un poco más sutiles y tienen algunas trampas. La forma de pensar en ellos es como un aspecto de la implementación del compilador sin un significado semántico separado pero con un efecto potencialmente profundo en el rendimiento en tiempo de ejecución. Es posible que la siguiente no sea una descripción perfecta de un CAF, pero intentará transmitir mi intuición de lo que uno es, ya que no he visto una descripción realmente buena en ninguna otra parte de la que pueda contar. La descripción "autoritativa" limpia en el Wiki de comentarios de GHC dice lo siguiente:

Las formas de aplicación constante, o CAF, por sus siglas en inglés, son valores de nivel superior definidos en un programa. Esencialmente, son objetos que no se asignan dinámicamente en tiempo de ejecución sino que, en cambio, son parte de los datos estáticos del programa.

Ese es un buen comienzo. Los lenguajes puros, funcionales y perezosos pueden considerarse en cierto sentido como una máquina de reducción de gráficos. La primera vez que exige el valor de un nodo, que fuerza su evaluación, lo que a su vez puede exigir los valores de los subnodos, etc. Se evalúa un nodo, el valor resultante se mantiene (aunque no tiene que quedarse) ya que este es un lenguaje puro, siempre podríamos mantener los subnodos en vivo y recalcularlos sin ningún efecto semántico). Un CAF es de hecho solo un valor. Pero, en el contexto, un tipo especial de valor, uno que el compilador puede determinar tiene un significado que depende completamente de sus subnodos. Es decir:

foo x = ...
  where thisIsACaf = [1..10::Int]

        thisIsNotACaf = [1..x::Int]
        thisIsAlsoNotACaf :: Num a => [a]
        thisIsAlsoNotACaf = [1..10] -- oops, polymorphic! the "num" dictionary is implicitly a parameter.

        thisCouldBeACaf = const [1..10::Int] x -- requires a sufficiently smart compiler
        thisAlsoCouldBeACaf _ = [1..10::Int] -- also requires a sufficiently smart compiler

Entonces, ¿por qué nos importa si las cosas son CAFs? Básicamente, porque a veces realmente no queremos volver a calcular algo (por ejemplo, ¡un memotable!) Y queremos asegurarnos de que se comparte correctamente. Otras veces realmente queremos recompensar algo (p. Ej., Una enorme lista aburrida y fácil de generar, como las naturales, sobre las cuales solo estamos caminando) y no tenerla guardada en la memoria para siempre. Una combinación de nombrar cosas y unirlas bajo permite o escribirlas en línea, etc. normalmente nos permite especificar este tipo de cosas de una manera natural e intuitiva. De vez en cuando, sin embargo, el compilador es más inteligente o más tonto de lo que esperamos, y algo que pensamos que solo debe computarse una vez siempre se vuelve a calcular, o algo que no queremos que se retire como CAF. Entonces, tenemos que pensar las cosas con más cuidado. Vea esta discusión para tener una idea acerca de algunas de las trampas involucradas: ¿ Una buena manera de evitar "compartir"?

[Por cierto, no me siento capaz de hacerlo, pero cualquiera que lo desee debería sentirse libre de tomar la mayor parte de la respuesta que quiera e intentar integrarla con las páginas existentes de Haskell Wiki y mejorarlas / actualizarlas]

Answer 2

Matt tiene razón en que la definición es confusa. Incluso es contradictorio. Un CAF se define como:

Cualquier super combinator que no sea una abstracción lambda. Esto incluye expresiones verdaderamente constantes como 12 , ((+) 1 2) , [1,2,3] , así como funciones parcialmente aplicadas como ((+) 4) .

Por lo tanto, ((+) 4) se ve como un CAF. Pero en la siguiente oración se nos dice que es equivalente a algo que no es un CAF:

este último ejemplo es equivalente en eta abstracción a / x -> (+) 4 x que no es un CAF.

Sería más limpio descartar las funciones parcialmente aplicadas sobre la base de que son equivalentes a las abstracciones lambda.