Pour en savoir plus
Le modèle de calcul des langages fonctionnels est le l-calcul,
qui a été
inventé par Alonzo Church en 1932. Le but de Church était de définir
une notion de calculabilité effective au moyen de la
l-définissabilité. Plus tard, il apparut que la notion ainsi
introduite était équivalente aux notions de calculabilité au sens de
Turing (machine de Turing) et de Gödel-Herbrand (fonctions récursives).
Cette coïncidence
incite à penser qu'il existe une notion de calculabilité
universelle, indépendante des formalismes particuliers : c'est la thèse de
Church.
Dans ce calcul, les deux seules constructions sont l'abstraction et
l'application. Les structures de données (entiers, booléens, couples,
...) peuvent être codées par des l-termes.
Les langages fonctionnels, dont le premier représentant a été Lisp,
implantent ce modèle et l'étendent principalement par des structures
de données plus efficaces. Dans un souci d'efficacité, les premiers
langages fonctionnels implantaient des modifications physiques de
mémoire, ce qui entre autres forçaient la stratégie d'évaluation en
évaluation immédiate ou stricte. Dans cette stratégie, les arguments
des fonctions sont évalués avant d'être passés à la fonction. C'est en
fait plus tard, pour d'autres langages
comme Miranda, Haskell ou LML,
que la stratégie d'évaluation retardée (paresseuse ou par nécessité) a
été implantée pour les langages fonctionnels purs.
Le typage statique, avec inférence de types, a été promu par la famille ML
au début des années
80. La page
Lien
http://www.pps.jussieu.fr/~cousinea/Caml/caml_history.html
présente un historique du langage ML.
Son modèle de
calcul est alors le l-calcul typé, sous-ensemble du l-calcul.
Il garantit qu'aucune erreur de typage n'arrivera pendant le
déroulement du programme.
Néanmoins des programmes
<<tout-à-fait corrects>> peuvent être rejetés par le système de types
de ML. Ces cas arrivent rarement et ces programmes peuvent toujours être
réécrits de manière conforme au système de types.
Les deux langages fonctionnels les plus utilisés sont Lisp et ML,
représentants des langages fonctionnels impurs. Pour approfondir
l'approche fonctionnelle de la programmation, les
livres [AS89] et [CM95] présentent
chacun un cours général d'informatique utilisant respectivement
les langages Scheme (dialecte Lisp) et Caml-Light.