Introduction

Introduction

Le premier langage fonctionnel, Lisp, est apparu à la fin des années 1950. C'est-à-dire au même moment que Fortran, premier représentant des langages impératifs. Ces deux langages existent toujours, bien qu'ayant fortement évolués. Ils couvrent respectivement le domaine de la programmation d'applications numériques pour Fortran et d'applications symboliques pour Lisp. L'intérêt de la programmation fonctionnelle provient d'une grande facilité d'écriture des programmes et des valeurs qu'ils manipulent. Un programme est une fonction appliquée à ses arguments. Il calcule un résultat qui est retourné (quand le calcul termine) comme sortie du programme. Il devient alors facile de composer des programmes : la sortie d'un programme devient l'argument d'entrée d'un autre, au sens de la composition de fonctions.

La programmation fonctionnelle repose sur un modèle de calcul simple possédant trois constructions : les variables, la définition d'une fonction et son application à un argument. Ce modèle s'appelle le l-calcul et il a été introduit par Alonzo Church en 1932, donc avant le premier ordinateur. Il a été conçu pour offrir un modèle théorique général de la notion de calculabilité. En l-calcul, toutes les fonctions sont des valeurs manipulables. Elles peuvent être utilisées comme paramètres d'autres fonctions ou être retournées comme résultat de l'appel d'une autre fonction. La théorie du l-calcul affirme que tout ce qui est calculable (entendez programmable) peut être écrit dans ce formalisme. Cependant sa syntaxe est trop limitée pour être utilisable comme langage de programmation. En conséquence, il lui a été ajouté des valeurs de base (tels que les entiers ou les chaînes de caractères), des opérateurs sur ces valeurs de base, des structures de contrôle et les déclarations qui permettent de nommer des valeurs ou des fonctions et, en particulier, des fonctions récursives.

Il existe plusieurs classifications des langages fonctionnels. Pour notre part, nous les distinguons suivant deux caractéristiques qui nous paraissent prépondérantes :

Sans effets de bord (pur) ou avec effets de bord (impur) : un langage fonctionnel pur est un langage où l'affectation n'existe pas. Tout n'y est que calcul et l'on ne s'intéresse pas à son déroulement. Les langages fonctionnels impurs, comme Lisp ou ML, intègrent des traits impératifs comme l'affectation. Ils permettent d'écrire des algorithmes dans un style plus proche de langages comme Fortran où l'ordre d'évaluation des expressions est déterminant.
Typé dynamiquement ou typé statiquement : le typage permet de vérifier si un argument passé à une fonction est bien du type du paramètre formel de la fonction. On peut faire cette vérification à l'exécution du programme. On appellera alors cette vérification le typage dynamique. En cas d'erreur sur les types le programme s'arrêtera dans un état cohérent. C'est le cas du langage Lisp. Cette vérification peut aussi se faire avant l'exécution du programme, c'est-à-dire au moment de la compilation. On appelle cette vérification a priori le typage statique. Étant effectuée une fois pour toute, elle ne ralentira pas l'exécution du programme. C'est le cas du langage ML et de ses dialectes comme Objective CAML. Seuls les programmes correctement typés, c'est-à-dire ceux acceptés par le vérificateur de types, pourront être compilés puis exécutés.