Programmation fonctionnelle et calcul scientifique

Je m'excuse s'il s'agit d'une question vague, mais voici:

Au cours des dernières années, la programmation fonctionnelle a retenu l'attention de la communauté du génie logiciel. Beaucoup ont commencé à utiliser des langages tels que Scala et Haskell et ont revendiqué le succès par rapport aux autres langages et paradigmes de programmation. Ma question est la suivante: en tant qu’experts en calcul haute performance / calcul scientifique, devrions-nous nous intéresser à la programmation fonctionnelle? Devrions-nous participer à cette mini-révolution?

Quels sont les avantages et les inconvénients de la programmation fonctionnelle dans le domaine de travail SciComp?

Je n'ai fait qu'un peu de programmation fonctionnelle, prenez donc cette réponse avec un grain de sel.

Avantages:

• La programmation fonctionnelle semble très mathématique; c'est un beau paradigme pour exprimer des concepts mathématiques
• Il existe de bonnes bibliothèques disponibles pour des tâches telles que la vérification formelle de programmes et la démonstration de théorèmes. Il est donc possible d'écrire des programmes qui raisonnent à propos de programmes - cet aspect est bon pour la reproductibilité.
• Vous pouvez effectuer une programmation fonctionnelle en Python et C ++ via des expressions lambda; vous pouvez également faire de la programmation fonctionnelle dans Julia et Mathematica
• Peu de gens l'utilisent, vous pouvez donc être un pionnier. Un peu comme il y avait des premiers utilisateurs de MATLAB, Python, R et maintenant Julia, il faut qu'il y ait des adopteurs précoces de la programmation fonctionnelle pour qu'il puisse prendre forme

Les inconvénients:

• Les langues généralement considérées comme des langages de programmation fonctionnels, tels que Haskell, OCaml (et d’autres dialectes ML) et Lisp, sont généralement considérées comme lentes par rapport aux langues utilisées pour le calcul scientifique de performances critiques. OCaml est, au mieux, environ deux fois moins rapide que C.
• Ces langages manquent d’infrastructures de bibliothèque par rapport aux langages couramment utilisés en informatique (Fortran, C, C ++, Python); Si vous voulez résoudre un PDE, il est beaucoup plus facile de le faire dans un langage plus couramment utilisé en science informatique que dans un autre.
• Il n’existe pas autant de communautés informatiques utilisant des langages de programmation fonctionnels que des langages de procédures, ce qui signifie que vous n’obtiendrez pas beaucoup d’aide pour l’apprendre ou le déboguer, et que les gens vont probablement vous faire chier. l'utiliser (que vous le méritiez ou non)
• Le style de programmation fonctionnelle est différent de celui utilisé dans la programmation procédurale, qui est généralement enseignée dans les cours d'initiation à l'informatique et dans les cours de type "MATLAB pour les scientifiques et les ingénieurs".

Je pense que bon nombre des objections de la section "Contre" pourraient être surmontées. Comme il est courant dans les discussions sur ce site Stack Exchange, le temps dont disposent les développeurs est plus important que le temps d’exécution. Même si les langages de programmation fonctionnels sont lents, si des parties critiques en termes de performances peuvent être déléguées à un langage procédural plus rapide et si des gains de productivité peuvent être démontrés grâce au développement rapide d'applications, ils peuvent valoir la peine d'être utilisés. Il convient de noter ici que les programmes implémentés en pur Python, pur MATLAB et pur R sont beaucoup plus lents que ceux de ces mêmes programmes en C, C ++ ou Fortran. Des langages comme Python, MATLAB et R sont populaires justement parce qu’ils négocient la vitesse d’exécution pour la productivité, et même alors, Python et MATLAB disposent tous les deux de fonctionnalités permettant d'implémenter des interfaces pour compiler du code en C ou C ++, de sorte que le code critique en termes de performances puisse être implémenté pour s'exécuter rapidement. La plupart des langages ont une interface de fonction étrangère avec C, ce qui serait suffisant pour s’interfacer avec la plupart des bibliothèques intéressantes pour les scientifiques en informatique.

Si vous êtes intéressé par la programmation fonctionnelle?

Tout dépend de ce que vous pensez être cool. Si vous êtes le genre de personne qui est disposée à renoncer à la convention et à évangéliser les gens sur les vertus de tout ce que vous voulez faire avec la programmation fonctionnelle, je vous prierais d'y aller. . J'adorerais voir les gens faire des choses sympas avec une programmation fonctionnelle en science informatique, ne serait-ce que pour prouver que tous les opposants ont tort (et il y en aura beaucoup). Si vous n'êtes pas le genre de personne qui veut faire face à un tas de gens qui vous demandent: « Pourquoi diable utilisez - vous un langage de programmation fonctionnelle au lieu de (insérer leur langage de programmation procédural préféré)? », Je n » pas la peine.

Des langages de programmation fonctionnels ont été utilisés pour les travaux intensifs en simulation. La société de commerce quantitatif Jane Street utilise OCaml pour la modélisation financière et l’exécution de ses stratégies de négociation. OCaml a également été utilisé dans FFTW pour générer du code C utilisé dans la bibliothèque. Liszt est un langage spécifique à un domaine développé à Stanford et implémenté dans Scala, qui est utilisé pour résoudre les PDE. La programmation fonctionnelle est définitivement utilisée dans l'industrie (pas nécessairement en informatique); il reste à voir si cela va décoller en science informatique.

J'ai peut-être une perspective unique à ce sujet parce que je suis un spécialiste du calcul intensif avec des connaissances en calcul scientifique et un utilisateur de langage de programmation fonctionnel. Je ne veux pas assimiler HPC à un calcul scientifique, mais il y a une intersection considérable, et c'est donc le point de vue que je défends pour répondre à cela.

Les langages fonctionnels ne seront probablement pas adoptés pour le moment dans le HPC, principalement parce que les utilisateurs et les clients du HPC tiennent réellement à atteindre des performances aussi optimales que possible. Il est vrai que lorsque le code est écrit de manière fonctionnelle, il expose naturellement un parallélisme exploitable, mais en HPC, cela ne suffit pas. Le parallélisme n’est qu’une pièce du puzzle pour atteindre de hautes performances, vous devez également prendre en compte un large éventail de détails micro-architecturaux. Pour ce faire, il faut généralement un contrôle très fin de l’exécution du code, ce contrôle n’existant en aucun cas. langages fonctionnels que je connais.

Cela dit, j'ai bon espoir que cela puisse changer. J'ai remarqué une tendance que les chercheurs commencent à comprendre que bon nombre de ces optimisations micro-architecturales peuvent être automatisées (dans une certaine mesure). Cela a engendré un zoo de technologie de compilateur source à source dans lequel un utilisateur saisit une "spécification" du calcul qu'il souhaite obtenir, et le compilateur fournit le code C ou Fortran qui réalise ce calcul avec les optimisations et le parallélisme nécessaires pour fonctionner efficacement. utiliser l'architecture cible. C'est d'ailleurs ce à quoi les langages fonctionnels sont bien adaptés: modéliser et analyser des langages de programmation. Ce n’est pas un hasard si les premiers grands adoptants de langages fonctionnels ont été les développeurs de compilateurs. À quelques exceptions notables, je ne l'ai pas encore vu se concrétiser, mais les idées sont là,

J'aimerais ajouter un aspect aux deux autres réponses. En dehors de l’écosystème, la programmation fonctionnelle offre une grande opportunité pour une exécution en parallèle telle que le multithreading ou l’informatique distribuée. Ses propriétés d’immutabilité inhérentes le rendent approprié au parallélisme, qui est généralement une vraie douleur dans le * bleep * quand il s’agit de langages impératifs.

Étant donné que l'amélioration des performances matérielles au cours des dernières années a été axée sur l'ajout de cœurs aux processeurs au lieu de pousser des fréquences plus hautes, le calcul parallèle devient de plus en plus populaire (je parie que vous le savez tous).

Geoff mentionne également que le temps passé par le développeur est souvent plus important que le temps d'exécution. Je travaille pour une société qui construit un SaaS gourmand en calcul et nous avons fait un test de performance initial lors du démarrage, en comparant C ++ et Java. Nous avons constaté que C ++ fournissait environ 50% de temps d'exécution sur Java (ceci concernait la géométrie informatique et que les chiffres varieraient très probablement selon l'application), mais nous avons quand même opté pour Java en raison de l'importance du temps de développement. Nous espérions que Les optimisations et les améliorations futures de la performance matérielle nous aideraient à réussir sur le marché. Je peux dire avec confiance que si nous avions choisi le contraire, nous ne serions toujours pas en affaires.

Ok, mais Java n’est pas un langage de programmation fonctionnel, vous vous demandez peut-être ce qu’il a à faire avec quoi que ce soit. Plus tard, alors que nous utilisions plus de partisans du paradigme fonctionnel et que nous sommes tombés sur le besoin de parallélisation, nous avons progressivement migré certaines parties de notre système vers Scala, qui combine les aspects positifs de la programmation fonctionnelle avec le pouvoir de l'impératif et se fond bien avec Java. Cela nous a énormément aidés lorsque nous avons augmenté les performances de notre système avec un minimum de maux de tête et que nous continuerons probablement à tirer parti des améliorations apportées aux performances du secteur du matériel quand de plus en plus de cœurs seront entassés dans les processeurs de demain.

Notez que je suis tout à fait d’accord avec les inconvénients mentionnés dans les autres réponses, mais j’ai pensé que la facilitation de l’exécution parallèle était un pro tellement puissant qu’elle ne pouvait pas passer inaperçue.

Geoff a déjà donné un bon aperçu des raisons pour lesquelles je n’ai rien à ajouter à part souligner un de ses points: l’écosystème. Que vous préconisiez la programmation fonctionnelle ou tout autre paradigme, l’une des questions importantes à laquelle vous devez répondre est qu’il existe une quantité incroyable de logiciels que tout le monde peut exploiter et que vous devez réécrire. Des exemples sont MPI, PETSc ou Trilinos pour l'algèbre linéaire, ou n'importe laquelle des bibliothèques d'éléments finis, toutes écrites en C ou C ++. Il y a une énorme inertie dans le système, peut-être pas parce que tout le monde pense que C / C ++ est en fait le meilleur langage pour écrire un logiciel de calcul, mais parce que beaucoup de gens ont passé des années à créer quelque chose qui soit utile à beaucoup de gens.

Je pense que la plupart des informaticiens seront d'accord pour dire qu'il est très utile d'essayer de nouveaux langages de programmation et d'évaluer leur pertinence pour ce problème. Mais ce sera une période difficile et solitaire, car vous ne serez pas en mesure de produire des résultats compétitifs par rapport à ceux de tout le monde. Cela peut également vous donner une réputation de personne qui a lancé la prochaine étape vers un paradigme de programmation différent. Hé, il a fallu environ 15 ans au C ++ pour remplacer Fortran!

Le résumé rapide est que

1. L'informatique numérique utilise la mutabilité / les effets secondaires pour réaliser la plupart de ses accélérations et réduire les allocations (de nombreuses structures de programmation fonctionnelles ont des données immuables)
2. L'évaluation paresseuse peut être difficile à utiliser avec des codes numériques.
3. Soit vous développez un paquetage où les performances sont primordiales (C / Fortran ou maintenant Julia) (vous pouvez également éditer le code assembleur si nécessaire), ou vous écrivez un script qui utilise ces bibliothèques rapides. vous avez donc généralement tendance à vous préoccuper du temps de développement (et vous avez donc choisi Julia / MATLAB / Python / R). Les langages fonctionnels ont tendance à se trouver dans un terrain d'entente étrange qui est utile dans d'autres disciplines, mais pas aussi utile ici.
4. $x_n$$x_{n+1}$

Ces faits réunis font que la programmation fonctionnelle ne semble pas nécessaire à la plupart des utilisateurs.

Je pense qu’il est intéressant de noter que l’utilisation de la programmation fonctionnelle en science informatique n’est pas nouvelle. Par exemple, cet article de 1990 montrait comment améliorer les performances des programmes numériques écrits en Lisp (probablement le premier langage de programmation fonctionnel) en utilisant une évaluation partielle. Ce travail faisait partie d'une chaîne d'outils utilisée dans un article de 1992 par GJ Sussman (de renommée SICP ) et J Wisdom qui fournissait une preuve numérique du comportement chaotique du système solaire . Plus de détails sur le matériel et les logiciels impliqués dans ce calcul peuvent être trouvés ici .

R est un langage fonctionnel et aussi un langage de statistiques (et maintenant de machine learning) et en fait le langage numéro 1 pour les statistiques. Ce n’est cependant pas un langage HPC: il n’est pas utilisé pour le "calcul automatique", comme les simulations physiques, etc. Mais il peut être configuré pour fonctionner en grappes massives (par exemple via MPI) pour des simulations statistiques massives (MCMC) de l’apprentissage automatique.

Mathematica est également un langage fonctionnel, mais son domaine de base est l’informatique symbolique plutôt que l’informatique numérique.

Dans Julia, vous pouvez aussi programmer dans un style fonctionnel (à côté de procédural et de leur saveur d’OO (multi-dispatch)) mais ce n’est pas pur (les structures de données de base sont modifiables (à l’exception des tuples)), bien qu’il existe certaines bibliothèques avec des fonctions immuables. structures de données fonctionnelles. Plus important encore, il est beaucoup plus lent que le style procédural, il est donc peu utilisé.

Je n'appellerais pas Scala un langage fonctionnel, mais plutôt un hybride objet-fonctionnel. Vous pouvez utiliser de nombreux concepts fonctionnels dans Scala. Scala est important pour le cloud computing en raison de Spark ( https://spark.apache.org/ ).

Notez que le Fortran moderne contient en fait des éléments de programmation fonctionnelle: il possède une sémantique de pointeur stricte (contrairement au C), vous pouvez avoir des fonctions pures (sans effet secondaire) (& le marquer comme tel) et vous pouvez avoir l’immuabilité. Il comporte même une indexation intelligente dans laquelle vous pouvez spécifier des conditions pour les index matriciels. Cette requête ressemble à une requête et ne se trouve normalement que dans un langage de haut niveau tel que R de LINQ en C # ou via des fonctions de filtrage d'ordre supérieur dans des langages fonctionnels. Donc, Fortran n’est pas si mauvais du tout, il possède même des fonctionnalités assez modernes (par exemple, les co-tableaux) que l’on ne retrouve pas dans de nombreuses langues. En fait, dans les futures versions de Fortran, je préférerais voir plus de fonctionnalités fonctionnelles ajoutées que de fonctionnalités OO (ce qui est généralement le cas actuellement), car OO en Fortran est vraiment maladroit et moche.

Les avantages sont les "outils" intégrés à chaque langage fonctionnel: il est si facile de filtrer les données, il est si facile de parcourir les données et il est beaucoup plus facile de proposer une solution claire et concise à vos problèmes.

Le seul inconvénient est que vous devez prendre conscience de ce nouveau type de réflexion: cela pourrait prendre du temps pour apprendre ce que vous devez savoir. D'autres dans le domaine SciComp n'utilisent pas vraiment ces langues, ce qui signifie que vous ne pouvez pas obtenir autant de support :(

Si vous êtes intéressé par les langages fonctionnels-scientifiques, j’en ai développé un https://ac1235.github.io

Voici mes arguments pour expliquer pourquoi la programmation fonctionnelle peut et doit être utilisée pour la science informatique. Les avantages sont vastes et les inconvénients disparaissent rapidement. Dans mon esprit, il n'y a qu'un seul problème:

Con : manque de prise en charge de la langue en C / C ++ / Fortran

Au moins en C ++, ce problème est en train de disparaître - car C ++ 14/17 a ajouté de puissantes fonctionnalités pour prendre en charge la programmation fonctionnelle. Vous devrez peut-être écrire vous-même un code de bibliothèque / support, mais le langage sera votre ami. A titre d'exemple, voici une bibliothèque (warning: plug) qui fait des tableaux multidimensionnels immuables en C ++: https://github.com/jzrake/ndarray-v2 .

En outre, voici un lien vers un bon livre sur la programmation fonctionnelle en C ++, bien qu’il ne soit pas axé sur les applications scientifiques.

Voici mon résumé de ce que je crois être les pros:

Avantages :

• La justesse
• Compréhensibilité
• Performance

En termes d' exactitude , les programmes fonctionnels sont manifestement bien posés : ils vous obligent à définir correctement l'état minimal de vos variables physiques et la fonction qui fait avancer cet état dans le temps:

int main()
{
    auto state = initial_condition();

    while (should_continue(state))
    {
        state = advance(state);
        side_effects(state);
    }
    return 0;
}

La résolution d'une équation aux dérivées partielles est idéale pour la programmation fonctionnelle. vous ne faites qu'appliquer une pure fonction ( advance) à la solution actuelle pour générer la suivante.

D'après mon expérience, les logiciels de simulation physique sont généralement grevés par une gestion médiocre de l' état . Habituellement, chaque étape de l'algorithme opère sur une partie d'un état partagé (globalement global). Cela rend difficile, voire impossible, d'assurer le bon ordre des opérations, laissant le logiciel vulnérable aux bugs pouvant se manifester par des erreurs de segmentation, ou pire, des termes d'erreur qui ne font pas planter votre code, mais compromettaient en silence l'intégrité de sa science. sortie. Tenter de gérer un état partagé dans une simulation physique inhibe également le multi-threading - un problème pour le futur, car les supercalculateurs évoluent vers un nombre de cœurs plus élevé et la mise à l'échelle avec MPI dépasse souvent les tâches d'environ 100 000 tâches. En revanche, la programmation fonctionnelle rend le parallélisme de la mémoire partagée trivial, du fait de son immuabilité.

Les performances sont également améliorées dans la programmation fonctionnelle grâce à l'évaluation paresseuse des algorithmes (en C ++, cela signifie générer plusieurs types au moment de la compilation - souvent un pour chaque application d'une fonction). Mais cela réduit la surcharge des accès et des allocations de mémoire, ainsi que l’élimination de la répartition virtuelle, ce qui permet au compilateur d’optimiser tout un algorithme en affichant immédiatement tous les objets fonction qui le composent. En pratique, vous allez expérimenter différents arrangements des points d'évaluation (où le résultat de l'algorithme est mis en cache dans une mémoire tampon) pour optimiser l'utilisation de la CPU par rapport aux allocations de mémoire. Ceci est plutôt facile en raison de la localité élevée (voir l'exemple ci-dessous) des étapes de l'algorithme par rapport à ce que vous verrez généralement dans un module ou un code basé sur une classe.

Les programmes fonctionnels sont plus faciles à comprendre dans la mesure où ils banalisent l’état physique. Cela ne veut pas dire que leur syntaxe est facilement compréhensible par tous vos collègues! Les auteurs doivent veiller à utiliser des fonctions bien nommées et les chercheurs en général doivent s'habituer à voir les algorithmes exprimés de manière fonctionnelle plutôt que procédurale. J'admets que l'absence de structures de contrôle peut déranger certaines personnes, mais je ne pense pas que cela devrait nous empêcher d'aller de l'avant, capables de faire de la science de meilleure qualité sur des ordinateurs.

Vous trouverez ci-dessous un exemple de advancefonction, adaptée d’un code de volume fini utilisant le ndarray-v2package. Notez les to_sharedopérateurs - ce sont les points d’évaluation auxquels je faisais allusion tout à l’heure.

auto advance(const solution_state_t& state)
{
    auto dt = determine_time_step_size(state);
    auto du = state.u
    | divide(state.vertices | volume_from_vertices)
    | nd::map(recover_primitive)
    | extrapolate_boundary_on_axis(0)
    | nd::to_shared()
    | compute_intercell_flux(0)
    | nd::to_shared()
    | nd::difference_on_axis(0)
    | nd::multiply(-dt * mara::make_area(1.0));

    return solution_state_t {
        state.time + dt,
        state.iteration + 1,
        state.vertices,
        state.u + du | nd::to_shared() };
}