Aller au contenu

Haskell

Un article de Wikipédia, l'encyclopédie libre.
Page d’aide sur l’homonymie

Pour les articles homonymes, voirHaskell (homonymie).

Haskell
Logo.
Date de première version Voir et modifier les données sur Wikidata
Paradigmes fonctionnel
Auteur comité Haskell
Développeurs communauté Haskell
Dernière version Haskell 2010 ()[1]Voir et modifier les données sur Wikidata
Typage Fort,statique
Dialectes Helium, O'Haskell, Template Haskell, PolyP
Influencé par LispetScheme,ISWIM,FP,APL,Hope,SISAL,Miranda,ML,Lazy ML,Orwell,Alfl,Id,Ponder
Implémentations GHC,Hugs,Yhc
Système d'exploitation Multiplateforme
Site web https://www.haskell.org
Extension de fichier hs et lhsVoir et modifier les données sur Wikidata
modifier

Haskellest unlangage de programmationfonctionnelfondé sur lelambda-calculet lalogique combinatoire.Son nom vient du mathématicien et logicienHaskell Curry.Il a été créé en 1990 par un comité de chercheurs en théorie des langages intéressés par les langages fonctionnels et l'évaluation paresseuse.Le dernier standard estHaskell 2010:c'est une version minimale et portable du langage conçue à des fins pédagogiques et pratiques, dans un souci d'interopérabilité entre les implémentations du langage et comme base de futures extensions. Le langage continue d'évoluer en 2020, principalement avecGHC,constituant ainsi un standardde factocomprenant de nombreuses extensions.

Historique

[modifier|modifier le code]

La sortie deMirandaen 1985 provoqua un regain d'intérêt pour leslangages fonctionnelsàévaluation paresseuseet entraîna une explosion du nombre de tels langages expérimentaux, de sorte qu'en 1987 plus d'une douzaine d'entre eux étaient disponibles. Miranda était de loin le plus populaire mais son modèle propriétaire fermé n'encourageait pas les contributions et à la conférence FPCA '87 (Functional Programming Languages and Computer Architecture, se traduisant par langages de programmation fonctionnels et architecture des ordinateurs) àPortlandenOregon,une réunion de chercheurs éminents du domaine aboutit à la conclusion qu'il serait souhaitable d'établir un standard ouvert qui pourrait servir de base commune à de futures recherches sur leslangages fonctionnels.Dans ce but ils formèrent un comité dont la tâche serait de mettre en commun les points forts des prototypes de l'époque.

Versions

[modifier|modifier le code]
Haskell 1.0 à 1.4

Le travail du comité se poursuivit de réunion en réunion et aboutit en 1990 à la définition de Haskell 1.0, suivi par diverses révisions pour les versions 1.1, 1.2, 1.3 et 1.4.

Haskell 98

Le rapportHaskell 98établit un standard durable sur lequel toutes les implémentations subséquentes se basent. Une version révisée parait en.

Haskell 2010

Le procédé de révision du standard Haskell, nommé Haskell' (prononcé «Haskell Prime») commença en 2006. Originellement entrepris dans l'optique de publier une nouvelle version du standard Haskell, l'effort peina à se mettre en place de façon durable et s'est maintenant fixé un objectif plus restreint: publier régulièrement (théoriquement une fois par an) une révision du rapport de 1998 intégrant quelques nouveautés introduites depuis par GHC et incontestablement acceptées et utilisées par la communauté.Haskell 2010a ainsi ajouté une définition du mécanisme d'interface de Haskell avec d'autres langages (FFI:foreign functions interface) et supprimé les motifs « n+k » du langage (qui permettaient d'écrire:decrement (n+1) = n). Il a également officialisé un mécanisme pour spécifier quel standard on souhaite respecter dans un fichier source donné, ainsi que les extensions éventuelles, entérinant la nature plutôt modulaire du Haskell utilisée en pratique.

Versions de recherche

En 2012, Haskell est probablement le langage fonctionnel sur lequel le plus de recherches ont été entreprises. Plusieurs variantes ont été développées. Des versions parallélisées faites au Laboratory for Computer Science duMassachusetts Institute of Technology(MIT) et à l'université de Glasgowont toutes deux été appelées Parallel Haskell. Des versions plus parallélisées et plus distribuées sont appelées Distributed Haskell (anciennement Goffin) et Eden, il existe également une tentative d'utiliser Haskell dans lecloud computingappelée Cloud Haskell. Une version d'exécution spéculative,Eager Haskell et plusieurs versions orientées objet, Haskell++, O'Haskell et Mondrian ont vu le jour. Ces diverses versions de recherche étaient assez souvent basées surGHCet ont fréquemment laissé leurs traces dans ce compilateur lorsque l'expérimentation s'est révélée fructueuse, inspirant ainsi le support actuel pour lesfils d'exécutionset les diverses formes de parallélisation du code.

Fonctionnalités

[modifier|modifier le code]

Les fonctionnalités les plus intéressantes de Haskell sont le support desfonctions récursives,l'inférence de types,leslistes en compréhension,l'évaluation paresseuseet les structures de données infinies dont l'exemple phare est le type de donnéestream.Ces fonctionnalités, surtout si elles sont combinées, facilitent l'écriture et l'utilisation de fonctions et la manipulation des données. Le système de types, objet de nombreuses recherches, est également l'un des plus expressifs et l'un des plus aptes à mettre en œuvre, de façonstatique,de nombreuses contraintes ordinairement vérifiées à l'exécution. Haskell se distingue également par l'utilisation demonadespour les entrées/sorties et pour la gestion des exceptions, rendue nécessaire par l'une des plus importantes spécificités du langage, à savoir que Haskell est un langage fonctionnel pur, ce qui signifie que, de façon inhérente, aucun effet de bord n'est autorisé, ni les entrées/sorties, ni les affectations de variables, ni les exceptions. La plupart des langages fonctionnels encouragent ce style, mais Haskell l'impose dans tout code qui ne signale pas explicitement par son type qu'il admet des effets de bord et qui grâce à ce mécanisme en prévient et en circonscrit les dangers.

Exemples de code

[modifier|modifier le code]

Fonction factorielle (récursive)

[modifier|modifier le code]

La définition classique de la fonctionfactorielle: 

facn|n<2=1
|otherwise=n*fac(n-1)

Fonction factorielle (avec product)

[modifier|modifier le code]

La définition élégante de la fonction factorielle (qui utilise la fonction Haskellproductet la notation sur les listes): 

facn=product[1..n]

Fonction factorielle (liste infinie)

[modifier|modifier le code]

Il est également possible de définir une liste de toutes les factorielles: 

facs=1:zipWith(*)facs[1..]

La valeur précédente est une liste infinie, ce qui est tout à fait possible grâce à l'évaluation paresseuse.Grâce à cette liste, on peut implémenterfacde cette manière: 

facn=facs!!n

(!!est unopérateurqui renvoie le n-ième élément d'une liste).

Commefacsest évaluée de manière paresseuse dansfac,un appel àfac nne provoque que l'évaluation des n premiers termes defacs.Notez que la valeur de chaque élément defacsn'est évaluée qu'une seule fois.

Fonction Fibonacci (naïve)

[modifier|modifier le code]

Une implémentation naïve de la fonction qui retourne le n-ième nombre de lasuite de Fibonacci: 

fib0=0
fib1=1
fibn=fib(n-2)+fib(n-1)

Fonction Fibonacci (liste infinie)

[modifier|modifier le code]

Une fonction qui retourne la liste infinie des nombres de Fibonacci, également grâce à l'évaluation paresseuse: 

fibs=0:1:(zipWith(+)fibs(tailfibs))
fibn=fibs!!n

Contrairement à la version naïve, la complexité d'un appel àfibest linéaire, et ceci grâce à lamémoïsation.

En effet, dans la précédente version les valeurs de fib étaient calculées à chaque demande. Ainsi, un appel àfib 4provoque un appel àfib 3et un appel àfib 2,qui eux-mêmes appellent une nouvelle foisfib 2,deuxfoisfib 1et une foisfib 0,etc.

En revanche, dans le cas de la liste infinie, chaque valeur defibn'est calculée qu'une seule fois puis stockée en mémoire.

Recherche de nombres premiers

[modifier|modifier le code]

Grâce au mécanisme de l'évaluation paresseuse, il est également possible de définir la liste entière (et infinie) desnombres premiers: 

primes=remDivs[2..]
whereremDivs(x:xs)=x:remDivs[n|n<-xs,(modnx)/=0]

Cet algorithme est cependant très inefficace, et une implémentation ducrible d'Ératosthènepermet de bien meilleures performances[2].

Pour rendre la recherche plus efficace, on peut vérifier que le nombre dont on teste la primalité n’est divisible par aucun des nombres premiers inférieurs à sa racine carrée. Une implémentation en Haskell peut être: 

prem=2:[a|a<-[3,5..],(all(/=0)(map(\x->modax)(takeWhile(<=truncate(sqrt(fromIntegrala::Float)))prem)))]

Tri rapide (quicksort)

[modifier|modifier le code]

L'algorithme dutri rapidepeut être écrit en Haskell en manipulant des listes: 

qsort[]=[]
qsort(x:xs)=
qsortelts_lt_x++[x]++qsortelts_greq_x
where
elts_lt_x=[y|y<-xs,y<x]
elts_greq_x=[y|y<-xs,y>=x]

Ou 

qsort[]=[]
qsort(x:xs)=qsort(filter(<x)xs)++[x]++qsort(filter(>=x)xs)

En raison des copies et des concaténations de listes, ce code peut être lent, en fonction du compilateur. Une amélioration consiste à effectuer le test de comparaison une seule fois: 

qSort::(Orda)=>[a]->[a]
qSort[]=[]
qSort(mid:xs)=qSortinf++eg++qSortsup
where(inf,eg,sup)=sepxs([],[mid],[])
where
sep[]tuple=tuple
sep(y:ys)(i,e,s)
|(y<mid)=sepys(y:i,e,s)
|(y==mid)=sepys(i,y:e,s)
|otherwise=sepys(i,e,y:s)

Ces implémentations naïves du tri rapide présentent cependant l'inconvénient d'être d'une complexité(O(N²))dans le cas d'une liste triée.

Implémentations

[modifier|modifier le code]

Les implémentations suivantes sont toutes compatibles (ou presque compatibles) avec le standard Haskell 98, et sont distribuées sous licences libres. Toutes les implémentations de Haskell sont à ce jour deslogiciels libres.

  • GHC.Le Compilateur Haskell de Glasgow (Glasgow Haskell Compiler) compile le code en natif sur nombre d'architectures, et compile aussi en C. GHC est probablement le plus populaire des compilateurs Haskell, et il contient des bibliothèques très utiles (par exemple des bindings pourOpenGL) qui ne marchent qu'avec GHC.
  • Hugsest un interpréteurbytecode.Il offre une compilation rapide et une vitesse d'exécution raisonnable. Il possède aussi unebibliothèque graphiquesimple. Hugs se prête bien à l'apprentissage de Haskell, mais il ne faut pas en déduire que Hugs est une implémentation simpliste. C'est la plus portable et la plus légère des implémentations de Haskell.
  • nhc98est un autre interpréteur de bytecode, mais le bytecode s'exécute plus vite qu'avec Hugs. Nhc98 se concentre sur un usage minimal de la mémoire, et c'est un choix recommandé pour les vieilles machines.
  • HBCest un autre compilateur natif. Il n'est plus développé depuis quelque temps, mais il reste encore utilisable.

Quelques utilisations d'Haskell

[modifier|modifier le code]

Parce que non-procédural, Haskell permet de limiter considérablement les besoins de débogage: les déclarations (un programme Haskell ne comportequedes déclarations) étant indépendantes les unes des autres, le programmeur n'a pas à s'occuper d'un quelconque flot de contrôle ni même de la séquence ou du contexte des déclarations; il arrive donc sans surprise que des projets soient réalisés en Haskell avant d'être disponibles dans d'autres langages. Les exemples les plus connus sont:

  • Réécriture du système anti-spam de Facebook, Sigma[3],avec Haskell, en remplacement du langage propriétaire précédemment utilisé, FXL. Sigma traite plus d'un million de requêtes par seconde.
  • Pandoc,logiciel de conversion de documents en ligne de commande.
  • Xmonad,gestionnaire de fenêtres.
  • Darcs,logiciel de gestion de versionsdécentralisé.
  • Pugs,implémentation dePerl 6rendue disponible bien avant la sortie officielle de la version du langage fondée sur lamachine virtuelleParrot.
  • le programmenget,permettant de récolter toutes les images d'unnewsgroup Usenet- par exemple d'astronomie -, dont la première version fut codée en Haskell (une version enlangage C++fut ensuite développée pour en faciliter le portage).
  • GarganText[4],outil collaboratif de cartographie de corpus textuels, via de l'analyse sémantique. Il a permis notamment d'élaborer la feuille de route européenne sur les liens entre média numérique etBien-être[5]

Langages similaires à Haskell

[modifier|modifier le code]
  • le Concurrent Clean, qui offre un support pour la création deGUIainsi que CAL (Quarks Framework) qui s'appuie sur VM Java et est prévu pour s'intégrer comme extension d'API Java.
  • une version éducative de Haskell, appelée Gofer, a été développée par Mark Jones, et a finalement été supplantée par HUGS, le Système Gofer de l'Utilisateur Haskell (Haskell User's Gofer System).
  • les langages du typeMLsont aussi assez proches de Haskell, par leur philosophie commune de programmation fonctionnelle et de typage statique.Ocamlest le plus populaire des représentants de cette famille de langages, connu en France pour son enseignement en classe préparatoire et à l'université.En France, il reste ainsi beaucoup plus pratiqué que Haskell[réf. nécessaire].
  • Bien quePureScriptsoit un langage strict, sa similarité syntaxique avec Haskell est évidente malgré quelques différences[6].
  • DAML, un langage decontrat intelligentbasé surGlasgow Haskell Compiler.

Principaux lieux d'échanges de la communauté Haskell au niveau international

[modifier|modifier le code]
  • EnEuropetous les ans àZurichse déroule le ZuriHac[7],unHackathoncollectif
  • Le forum de discussion[8]échange quotidiennement (en juin 2023) une dizaine de questions

Références

[modifier|modifier le code]
  1. ↑aetb«[Haskell] Announcing Haskell 2010»,(consulté le)
  2. ↑«Sieve of Eratosthenes (Haskell)»(Archive.org•Wikiwix•Archive.is•Google•Que faire?),surLiteratePrograms
  3. ↑(en-US)«Fighting spam with Haskell», surFacebook Engineering,(consulté le)
  4. ↑(en)«gargantext / main», surGitLab,(consulté le)
  5. ↑(en)ChavalariasDavid,Beatrice DeGelder,GuidoCaldarelliet Melanie Dulong deRosnay,«Toward a Research Agenda on Digital Media and Humanity Well-Being»,Rapport - road map - ponctuelle,CNRS,‎(lire en ligne,consulté le)
  6. ↑«Purescript/documentation», surGitHub(consulté le).
  7. ↑«Zürich Friends of Haskell», surzfoh.ch(consulté le)
  8. ↑(en)«Haskell Community», surHaskell Community(consulté le)

Voir aussi

[modifier|modifier le code]

Sur les autres projets Wikimedia:

Articles connexes

[modifier|modifier le code]

Liens externes

[modifier|modifier le code]

Bibliographie

[modifier|modifier le code]
  • Julien Dehos,La programmation fonctionnelle - Introduction et applications en Haskell à l'usage de l'étudiant et du développeur,Ellipses, 2019
  • Graham Hutton,Programming in Haskell,Cambridge University Press,2007
Ce document provient de «https://fr.wikipedia.org/w/index.php?title=Haskell&oldid=214922890».