Quels sont les super combinateurs et formes constantes applicatives?

Question

Je suis aux prises avec ce que super Combinators sont:

A supercombinator est soit une constante, ou un combinateur qui ne contient que des sous-expressions comme supercombinators.

Et aussi avec ce que Constant Forms Applicative sont:

Tout super-Combinator qui n'est pas une abstraction lambda. Cela comprend les expressions réellement constantes telles que 12, ((+) 1 2), [1,2,3] ainsi que partiellement appliquées des fonctions telles que ((+) 4). Notez que ce dernier exemple est équivalent sous eta abstraction à \ x -> (+) 4 x qui n'est pas CAF

.

Ceci est tout simplement ne fait aucun sens pour moi! Est-ce pas ((+) 4) comme « vraiment constant » que 12? CAFs sonnent comme des valeurs à mon esprit simple.

Answer 1

Ces pages wiki Haskell vous faites référence sont vieux, et je pense malheureusement écrit. Est particulièrement regrettable qu'ils se mélangent et CAFs supercombinators. Supercombinators sont intéressantes, mais sans rapport avec GHC. CAFs sont encore très bien une partie de GHC, et peuvent être compris sans référence à supercombinators.

---

Commençons par supercombinators . Combinators dérivent de logique combinatoire , et, dans l'utilisation ici se composent de fonctions qui concernent uniquement la les valeurs transmises dans un à l'autre dans une ou une autre forme - à-dire qu'ils combinent leurs arguments. Le plus célèbre jeu de combinateurs sont S, K, et je , qui pris ensemble sont Turing- Achevée. Supercombinators, dans ce contexte, sont des fonctions intégrées que des valeurs passées, combinateurs, et d'autres supercombinators. Par conséquent, tout supercombinator peut être étendu, par substitution, dans une ancienne plaine Combinator.

Certains compilateurs pour les langages fonctionnels (non GHC!) Utilisation combinateurs et supercombinators comme des étapes intermédiaires dans la compilation. Comme pour toute technologie de compilateur similaire, la raison de le faire est d'admettre l'analyse d'optimisation qui est plus facile à réaliser dans un tel simplifié, langage minimal. Un tel langage de base construit sur supercombinators est épique de Edwin Brady.

---

Constant Forms Applicative sont tout autre chose. Ils sont un peu plus subtile, et ont quelques gotchas. La façon de penser à eux est comme un aspect de la mise en œuvre du compilateur sans signification sémantique distincte, mais avec un effet potentiellement important sur les performances d'exécution. Ce qui suit peut ne pas être une description parfaite d'un CAF, mais il va essayer de transmettre mon intuition de ce que l'on est, puisque je ne l'ai pas vu vraiment bonne description nulle part ailleurs pour moi de crèche de . propre description "faisant autorité" dans le Commentaire GHC Wiki se lit comme suit:

Constant Forms applicatifs, ou CAF pour faire court, sont des valeurs de niveau supérieur définie dans un programme. , Ils sont essentiellement des objets qui ne sont pas alloué dynamiquement au moment de l'exécution, mais, au contraire, font partie de la statique les données du programme.

C'est un bon début. Pures, les langages fonctionnels, paresseux peuvent être considérés en quelque sorte comme une machine de réduction de graphique. La première fois que vous demande la valeur d'un nœud, que les forces de son évaluation, ce qui peut exiger les valeurs de sous-noeuds, etc. Un nœud est évalué, les bâtonnets de valeur résultante autour (bien qu'il ne Vous à coller autour - puisque c'est une langue pure, nous pourrions toujours garder les sous-noeuds vivent et recalculées sans effet sémantique). Un CAF est en effet juste une valeur. Mais, dans le contexte, un type particulier de valeur - celle que le compilateur peut déterminer a une signification entièrement dépendante de ses sous-noeuds. C'est-à-dire:

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

Alors, pourquoi nous demander si les choses sont CAFs? Fondamentalement, parce que parfois nous voulons vraiment ne pas vraiment à quelque chose recalcul (par exemple, un memotable!) Et donc voulons nous assurer qu'il est correctement partagé. D'autres fois, nous avons vraiment faire veulent quelque chose de recalcul (par exemple un énorme ennuyeux facile de générer la liste - comme les Naturals - que nous sommes en train de marcher sur) et ne pas avoir le coller autour de la mémoire pour toujours . Une combinaison de nommer les choses et les lier en laisse ou les écrire en ligne, etc. nous permet généralement spécifions ce genre de choses de façon naturelle et intuitive. De temps en temps, cependant, le compilateur est plus intelligent ou plus bête que nous attendons, et quelque chose que nous pensons que devrait être calculée une fois est toujours recalculé, ou something nous ne voulons pas accrocher à obtient levé comme un CAF. Ensuite, il faut penser les choses à travers plus d'attention. Voir cette discussion pour avoir une idée sur certains des rouerie impliqués: Une bonne façon d'éviter " partage "?

[Soit dit en passant, je ne me sens pas à la hauteur, mais toute personne qui veut devrait se sentir libre de prendre autant de cette réponse qu'ils veulent essayer de l'intégrer dans les pages existantes Haskell Wiki et améliorer / mise à jour les]

Answer 2

Matt est juste que la définition est source de confusion. Il est même contradictoire. Un CAF est défini comme suit:

Tout super-Combinator qui n'est pas une abstraction lambda. Ceci comprend expressions vraiment constantes telles que 12, ((+) 1 2), [1,2,3] comme ainsi que partiellement appliqué des fonctions telles que ((+) 4).

, ((+) 4) est donc considéré comme un CAF. Mais dans la phrase suivante, on nous dit qu'il est équivalent à quelque chose qui est pas CAF:

ce dernier exemple est équivalent dans l'abstraction êta à \ x -> (+) 4 x qui n'est pas CAF.

Il serait plus propre à écarter les fonctions partiellement appliquées au motif qu'elles sont équivalentes à des abstractions lambda.