Les langages de programmation fonctionnels ont-ils plus de possibilités de faire l'optimisation du temps de compilation?

10

Je lisais le livre "Programmation fonctionnelle pour le monde réel". Cela a commencé par une comparaison entre les langages de programmation impératifs et fonctionnels. Et il a expliqué en quoi les «valeurs» et les «expressions» dans la programmation fonctionnelle sont différentes des «variables» et des «fonctions» de la programmation impérative. À partir de la discussion, j'ai en quelque sorte développé une idée qui -

Les langages de programmation fonctionnels ont plus de possibilités de faire l'optimisation du temps de compilation que leurs homologues impératifs.

Est-ce vrai?

functional-programming compilation Gulshan
la source

Réponses:

16

Les langages de programmation fonctionnels optimisent beaucoup plus le temps de compilation. L'une des raisons est la pureté - la concurrence est triviale car il n'y a pas d'État. Le compilateur peut donc prendre deux branches et les concurrencer facilement sans changer le comportement du programme.

En même temps, tout ce qui peut être calculé sans état (c'est-à-dire tout ce qui n'est pas monadique dans haskell) peut être calculé à l'avance par le compilateur, mais ces calculs peuvent être coûteux et ne sont donc probablement que partiellement effectués.

De plus, tout ce qui n'est pas nécessaire sur le plan informatique peut être complètement optimisé hors du programme.

alternative
la source
1
+1: La programmation gratuite des effets secondaires est très, très facile à optimiser.
S.Lott
@mathepic: en fait, la parallélisation (dans Haskell) se produit à la fois à la compilation et à l'exécution. La compilation décide s'il vaut la peine de créer un fragment (graine de thread) et le processus d'exécution traite les fragments comme il le peut, selon le nombre de threads que vous avez spécifié. Si vous ne spécifiez qu'un seul thread, les fragments sont créés, mais ils sont traités les uns après les autres.
Matthieu M.
2
@mathepic: une autre utilisation de la pureté -> la paresse et l'absence de calcul. Si vous pouvez prouver que la valeur n'est pas nécessaire, supprimez entièrement le calcul. Si cela peut être nécessaire, utilisez un thunk paresseux. Si vous savez que cela sera nécessaire, calculez-le directement (pour éviter les frais généraux paresseux). La pureté est (juste) incroyable :)
Matthieu M.
@Matthieu good point
alternative
1
@Masse Même la monade IO est pure. C'est juste que le résultat du "fonctionnement" de la monade IO ne l'est pas.
alternative
7

Le fait qu'il existe en principe plus de possibilités d'optimisation du temps de compilation pour les langages fonctionnels que pour leurs homologues impératifs est probablement vrai.

Plus intéressant cependant, s'ils sont réellement implémentés dans les compilateurs actuels et dans quelle mesure ces optimisations sont pertinentes dans la pratique (c'est-à-dire les performances finales du code idiomatique de la `` vraie vie '') dans un environnement de production, avec des paramètres de compilation a priori prévisibles).

Par exemple, les soumissions de Haskell pour le tristement célèbre Computer Language Benchmarks Game (aussi mauvais soit-il - mais ce n'est pas comme si il y avait - pour le moment - quoi que ce soit de bien mieux là-bas) donnent l'impression qu'un temps considérable a été consacré à Les optimisations manuelles, confrontées à l'affirmation concernant les "optimisations possibles du compilateur en raison de insert some property about FP languages here" laissent penser que les optimisations sont (actuellement au moins) plus une possibilité théorique qu'une réalité pertinente.

Je serais cependant heureux de me tromper sur ce point.

Alexander Battisti
la source
1
La raison des optimisations manuelles dans Haskell a plus à voir avec le fait que certaines opérations "simples" prennent un peu de temps (du point de vue de la complexité) dans Haskell. Par exemple, supposons que vous souhaitiez obtenir le dernier élément d'une liste. En Java, c'est une opération assez simple; dans Haskell, l'approche naïve exige que vous parcouriez la liste entière jusqu'à la fin (en raison de la nature paresseuse des listes), ce qui en fait une opération O (n). C'est (en partie) où les optimisations manuelles entrent en jeu.
mipadi
2
Je suis sûr qu'il existe des raisons valables pour les optimisations roulées à la main de Haskell, mais qu'elles sont nécessaires pour des opérations "simples" donne l'impression que les plus grandes opportunités d'optimisation de code ne sont (actuellement) pertinentes qu'en théorie.
Alexander Battisti
6
C'est plus la différence entre l'optimisation des algorithmes et l'optimisation du code généré. Prenons un exemple en C: si j'écris un algorithme de recherche, je peux écrire un algorithme naïf qui parcourt simplement une liste, ou je peux utiliser la recherche binaire. Dans les deux cas, le compilateur optimisera mon code, mais il ne transformera pas un algorithme de recherche naïf en recherche binaire. De nombreuses optimisations manuelles dans le code Haskell ont davantage à voir avec l'optimisation des algorithmes eux-mêmes, plutôt qu'avec l'optimisation du code généré.
mipadi
2
@mipadi, mais il semble que la version simple de l'algorithme Haskell n'est pas aussi bonne que la version simple des algorithmes d'autres langues. (Je soupçonne en raison de l'inadéquation entre le modèle fonctionnel et l'architecture informatique) Même si son bon à générer du code, ce n'est pas suffisant pour surmonter ce problème.
Winston Ewert
>> aussi mauvais soit-il << - Savez-vous si c'est mauvais ou pas? Que voulez-vous dire en suggérant que c'est "mauvais"? Soyez précis s'il vous plait.
igouy
2

Dans un style fonctionnel, le flux de valeurs à travers un programme est très, très visible (à la fois pour le compilateur et le programmeur). Cela donne au compilateur une grande latitude pour décider où stocker les valeurs, combien de temps pour les conserver, etc.

Dans un langage impératif, le compilateur promet au programmeur un modèle où la plupart des variables correspondent à des emplacements réels en mémoire qui restent autour pendant une durée de vie définie. Potentiellement, n'importe quelle instruction peut lire (ou écrire dans!) N'importe lequel de ces emplacements, de sorte que le compilateur ne peut remplacer les emplacements de mémoire par l'allocation de registres, fusionner deux variables en un seul emplacement de stockage ou effectuer des optimisations similaires après avoir effectué une analyse minutieuse de l'endroit où sinon dans le programme, cette variable peut être référencée.

Maintenant, il y a deux mises en garde:

  • La communauté des langages de programmation a consacré (gaspillé?) Beaucoup d'efforts au cours des cinquante dernières années pour développer des méthodes intelligentes pour effectuer cette analyse. Il existe des astuces bien connues comme la coloration des registres et ainsi de suite pour obtenir certains des cas les plus faciles la plupart du temps; mais cela fait de gros compilateurs lents et un compromis constant de complexité de compilation pour la qualité du code résultant
  • Dans le même temps, la plupart des langages de programmation fonctionnels ne sont pas non plus purement fonctionnels; beaucoup de choses que les programmes doivent réellement faire, comme répondre aux E / S sont intrinsèquement non fonctionnelles, donc aucun compilateur ne peut être complètement exempt de ces astuces, et aucun langage ne les évite complètement - même Haskell, qui est un peu trop pur à mon goût (Your Mileage May Vary) ne peut que contrôler et bloquer les parties non fonctionnelles de votre code, pas les éviter complètement.

Mais pour répondre à la question générale, oui, un paradigme fonctionnel donne au compilateur beaucoup de liberté pour l'optimiser qu'il n'a pas dans un cadre impératif.

Jimwise
la source
Tout dans Haskell est fonctionnel, c'est juste que vous mainêtes une fonction de transformation d'état plutôt que quelque chose qui utilise l'état lui-même.
alternative
Oui et non - conceptuellement, il est tout à fait correct de dire qu'un programme Haskell est une fonction pure sur les interactions de l'utilisateur avec ce programme (et l'état du générateur de nombres aléatoires du système, et la latence du réseau aujourd'hui, et tout autre intrinsèquement) entrées non fonctionnelles auxquelles le programme répond), mais dans la pratique, c'est une distinction sans différence.
jimwise
@jimwise La transparence référentielle est une très grande différence.
alternative le
Sauf que vous ne l'avez pas vraiment, du moins aux fins abordées ici. Le point des opérations comme IO, ou génération de nombres aléatoires, est qu'elles doivent retourner une valeur différente chaque fois qu'elles sont appelées avec les mêmes entrées, ce qui limite intrinsèquement le raisonnement à leur sujet fonctionnellement, pour le programmeur ou le compilateur.
jimwise
1
@mathepic Oui, bien sûr, vous pouvez visualiser conceptuellement le caractère aléatoire ou l'entrée utilisateur (ou la latence du réseau ou la charge du système) comme un flux infini ou une fonction d'état à état, mais ce n'est pas une vue qui se prête à un raisonnement utile sur le comportement du programme en vous ou votre compilateur - Bob Harper couvre bien ce sujet dans un récent article sur son blog sur le nouveau programme CS de la CMU.
jimwise