¿Cuáles son super combinadores y constante aplicativo formas?

Question

Yo estoy luchando con lo que Super Combinadores son:

Un supercombinator es una constante, o un combinador que contiene sólo supercombinators como las subexpresiones.

Y también con lo que Constante Aplicativo Formas son:

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

Este es sólo que no tenía sentido para mí!No ((+) 4) así como "verdaderamente constante" como 12?Caf sonido como valores para mi simple opinión.

Answer 1

Estos Haskell páginas wiki hace referencia a viejo, y creo que por desgracia escrito.Especialmente lamentable es que se mezcla la Caf y supercombinators.Supercombinators son interesantes pero no relacionado con GHC.Caf son todavía una parte muy importante de GHC, y puede ser entendido sin referencia a supercombinators.

---

Así que vamos a empezar con supercombinators.Combinadores se derivan de lógica combinatoria, y, en el uso de aquí, constan de funciones que se aplican únicamente a los valores que se pasan de uno a otro en una u otra forma, es decir,ellos combinan sus argumentos.El más famoso conjunto de combinadores son S, K, y me, que , tomados juntos son Turing-completo.Supercombinators, en este contexto, son funciones sólo de los valores pasados, combinadores, y otros supercombinators.Por lo tanto, cualquier supercombinator puede ser ampliado, a través de la sustitución, en una llanura de edad combinador.

Algunos compiladores para los lenguajes funcionales (no GHC!) el uso de combinadores y supercombinators como pasos intermedios en la compilación.Como con cualquier otro compilador de la tecnología, la razón para hacer esto es la de admitir el análisis de optimización que es más fácil de realizar en un simplificado, lenguaje minimalista.Uno de esos núcleo del lenguaje construido sobre supercombinators es Edwin Brady epic.

---

Constante Aplicativo Formas son algo completamente distinto.Son un poco más sutiles, y tienen un par de errores.La forma de pensar de ellos es como un aspecto de la implementación del compilador con ningún significado semántico, pero con potencial de un profundo efecto sobre el rendimiento en tiempo de ejecución.El siguiente no puede ser una perfecta descripción de un CAF, pero voy a tratar de transmitir mi intuición de lo que uno es, ya que no he visto realmente buena descripción de cualquier otro lugar para mí para cuna de.El limpiar la "autoridad" de la descripción en el GHC Comentario Wiki se lee como sigue:

Constante Aplicativo Formas, o Caf corto, son de nivel superior de los valores de definidos en un programa.Esencialmente, son objetos que no son asigna de forma dinámica en tiempo de ejecución, pero, en cambio, son parte de la estática los datos del programa.

Ese es un buen comienzo.Puro, funcional, perezoso idiomas puede considerarse en cierto sentido como un gráfico de reducción de la máquina.La primera vez que demanda el valor de un nodo, que las fuerzas de su evaluación, que a su vez la demanda de los valores de los subnodos, etc.Uno de un nodo es evaluado, el valor resultante se pega alrededor (aunque no han a pegarse a su alrededor, ya que este es un lenguaje puro que siempre se puede mantener a los subnodos vivir y volver a calcular sin efecto semántico).Un CAF es de hecho sólo un valor.Pero, en el contexto, un tipo especial de valor, que el compilador puede determinar tiene un significado totalmente dependiente 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 Caf?Básicamente porque a veces nosotros realmente no quiero volver a calcular algo (por ejemplo, un memotable!) y así queremos asegurarnos de que no es compartido correctamente.Otras veces somos realmente ¿ quiero volver a calcular algo (por ejemplo,un enorme aburrido fácil generar lista -- tales como los naturales, donde estamos simplemente caminar más) y no tener que pegarse en la memoria para siempre.Una combinación de nombrar las cosas y la unión bajo permite o escribir de ellos en línea, etc.normalmente nos permite especificar este tipo de cosas en una forma natural, de manera intuitiva.Ocasionalmente, sin embargo, el compilador es más listo o mas tonto de lo que esperamos, y es algo que creo que sólo debe ser calculada una vez siempre se vuelve a calcular, o algo que no quiero estar en se levantó como un CAF.Entonces, tenemos que pensar las cosas con más cuidado.Ver esta discusión para obtener una idea de la dificultad que participan: Una buena manera de evitar el "compartir"?

[Por cierto, no me siento bien, pero cualquier persona que quiere debe sentirse libre de tomar como gran parte de esta respuesta como quieren probar e integrar con la existente Haskell las páginas de la Wiki y mejorar/actualizar]

Answer 2

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

Cualquier súper combinador 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 eso, ((+) 4) se ve como una cafetería. Pero en la siguiente oración nos dicen que es equivalente a algo que no es un café:

Este último ejemplo es equivalente bajo abstracción ETA a \ x -> (+) 4 x que no es una cafetería.

Sería más limpio descartar funciones parcialmente aplicadas por el terreno de que son equivalentes a las abstracciones lambda.