Skip to content

2 2 6 4 Histoire3 5

Langages déclaratifs

Par hypothèse générale en informatique, tout programme, quel que soit le langage dans lequel il est formulé (du moins, si ce langage est Turing complet), définit une exécution potentielle sur une machine de Turing. Celle-ci fonctionne pas à pas selon son état interne ; elle lit un caractère à sa position sur le ruban, puis elle fait trois choses : écrire un caractère (à sa position) sur le ruban, changer d’état et se déplacer sur le ruban d’une position (en avant ou en arrière). Cette action dépend de son état et de son programme : sa table de transition définissant son action pour tout état et tout caractère lu. Bien sûr, le nombre de caractères possibles et le nombre d’états internes sont finis. Si le programme est correct, après un nombre fini d’étapes, elle passe dans l’état « STOP » et s’arrête ; la réponse a été écrite sur le ruban.

Une machine de Turing universelle est une simple généralisation capable de simuler toute autre machine. Cette machine lit le programme à exécuter sur son ruban et sa table de transition (fixée) est donc un interpréteur de programmes (écrits dans son langage, celui correspondant à cette table). Les ordinateurs « réels » correspondent assez fidèlement à ce modèle ; leur code binaire est fait d’instructions qui modifient pas à pas son état (en fait, ses registres) ; le ruban est matérialisé par la mémoire et la table de transition, par le microcode.

Les langages d’assemblage suivent strictement cette logique, puisque leurs instructions correspondent aux instructions de la machine ciblée pour l’exécution. Et il en est de même pour tous les langages impératifs : ils décrivent les règles de modification de l’état de la machine à chaque étape de manière certes plus macroscopique et humainement intelligible, mais sous une forme directement traduisible en langage machine. C’est le rôle d’un compilateur.

Les langages impératifs décrivent donc COMMENT faire pour calculer un résultat ; par contre, les langages déclaratifs décrivent CE qu’il faut calculer.

Comment est-ce possible, puisque le modèle de machine n’a évidemment pas changé ? Ce qui change, c’est le rôle dévolu au programme de traduction. Pour ces langages, il s’agit généralement d’un interpréteur qui exécute le programme dans un environnement, un runtime riche et complexe. Cet interpréteur est une véritable machine virtuelle particulière qui analyse le programme fourni et fait appel, de manière automatique et implicite, à ses fonctions internes (en bibliothèque) pour exécuter finalement le code impératif correspondant (le langage machine natif dans lequel il s’exécute).

Un langage déclaratif (declarative language) décrit formellement un résultat à calculer, c’est-à-dire une « expression », indépendante de tout contexte (donc, évaluée sans effets de bord), sans aucun état interne et en étant référentiellement transparente (referentially transparent).

Cette propriété veut dire que si l’on y remplace une sous-expression (un morceau du programme) par sa valeur (son résultat), la valeur de l’expression (l’évaluation finale, le comportement et le sens du programme) reste inchangée.

La propriété de transparence référentielle a pour conséquence que l’ordre d’évaluation (en dehors de la préséance des opérations, bien sûr) est sans effet sur le résultat. Il n’y a donc pas de séquence d’exécution à définir ; elle reste complètement libre (et à la discrétion de l’interpréteur), contrairement au sens d’un programme impératif qui, précisément, s’emploie à la définir par des règles strictes et non ambiguës.

Les langages déclaratifs ont donc une syntaxe très différente de celle des langages impératifs. Fini les boucles, les tests, les « CALL-RETURN » et vive les fonctions « mathématiques », les variables formelles (i.e. comme en algèbre), etc. C’est un autre monde...

Cette grande et très ancienne famille (LISP date de 1958) peut également être divisée en sous-groupes selon les caractéristiques particulières des langages.

Langages fonctionnels

Les premiers langages déclaratifs, tant en nombre qu’historiquement, sont dits « fonctionnels ». Ils sont issus des travaux de John McCarthy qui, dès 1960, sur base des premiers développements de LISP, proposait une définition de langages fondés sur la notation du λ-calcul (λ-calculus), inventé vers 1930 par Alonzo Church.

La motivation initiale était de permettre d’utiliser des fonctions — pas des références ou pointeurs vers des fonctions — comme paramètres effectifs de fonctions, ce qui induit une forme de code automodifiant, si l’on reste dans l’univers des langages impératifs. Par contre, dans un langage fonctionnel, c’est la construction primitive, appelée « composition ».

Un langage fonctionnel est un langage dans lequel un programme est décrit par composition de fonctions.

Cette idée a été source de nombreux travaux durant les années 60, période de naissance des premiers langages (et des tâtonnements liés à l’exploration d’un nouveau domaine). Le langage LISP en a été le point de départ, un sujet d’étude propre et une inspiration riche et fertile pour d’autres. Puis, cette famille de langages est tombée partiellement en désuétude, sans doute parce que les programmes écrits ainsi étaient peu efficaces et trop drastiquement limités par les environnements matériels et logiciels disponibles à l’époque. Ceci explique sans doute pourquoi, à la même époque, les langages procéduraux se sont multipliés et ont prospéré, tant en recherche qu’en usage industriel (c’est du darwinisme).

Mais en 1978, John Backus, pourtant connu comme le cocréateur de FORTRAN et pour ses travaux précurseurs sur la définition et la compilation des langages impératifs, publie une longue communication (Backus, John, Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs, Comm. ACM 21(8), 613‒641 (Aug. 1978).) qui lui valut un Turing Award et relança véritablement l’intérêt pour cette famille de langages et le développement d’outils plus performants. Aujourd’hui, il existe effectivement de nombreux langages fonctionnels qui peuvent, dans certaines circonstances, rivaliser en efficacité avec les langages impératifs.

Comme signalé, LISP est le premier exemple et il reste très utilisé. Il a été développé dans les années 50, initialement comme un simple outil de manipulation de listes généralisées (ou récursives). Sa syntaxe y reste toujours attachée : tout y est une liste simple d’atomes ou de sous-listes. Les diverses tentatives de développement d’interpréteurs ont conduit à de nombreux dialectes, mais la forme appelée « Common LISP » est celle qui a largement émergé. C’est celle qui correspond à la norme ANSI depuis 1994 pour laquelle il existe de nombreux interpréteurs : GNU Common LISP (gcl), GNU CLISP, SBCL (Steel Bank Common LISP), etc. Nous allons donc présenter des éléments de LISP écrits en Common LISP.

Les « atomes » sont les données primitives : des nombres (entiers, flottants, rationnels, complexes), des caractères et des « symboles » (ce sont des identificateurs), parmi lesquels les booléens « t » et « nil » (que l’on peut noter en capitales, car LISP est insensible à la casse ; l’output est généralement affiché en capitales). Des dénotations littérales usuelles existent donc pour les représenter en LISP. En dehors de cela, LISP est un langage non typé : les notations n’y représentent qu’elles-mêmes.

Comme c’est un langage déclaratif, il n’existe pas d’instructions, mais des expressions appelées « S-expression » (pour « Symbolic expression ») : un programme est une telle S-expression composée d’autres sous-expressions (c’est la « composition », une construction syntaxique récursive). Une S-expression est une paire de sous-expressions ; sa notation habituelle, appelée « Dotted Pair Notation », les place entre parenthèses, séparées par un point : « ( s1 . s2 ) ». Une telle paire s’appelle une « cons », abréviation de « construction » (construct), parfois déclinée : une « cons », des « conses », du moins en anglais.

L’unique structure fondamentale est une liste : une liste simplement liée de telles « conses ». Chaque « cons » contient deux éléments : « car », sa donnée (abréviation de « Content of the Address Register »), et « cdr », sa suite (abréviation de « Content of the Decrement Register »). Une « cons » donc est parfaitement symétrique, mais a priori, la donnée est plutôt une référence vers un atome ou vers une sous-liste, tandis que la suite est une référence vers la liste des suivants. Une liste peut être vide ; sa valeur est représentée par le symbole « nil » (qui est aussi le codage de la valeur booléenne « faux »).

Toutes les autres structures prédéfinies sont construites à partir de là et, comme on le sait, les listes généralisées permettent de tout implanter : arbre, graphe, vecteur, matrice, etc.

La syntaxe habituelle pour noter une liste consiste en un couple de parenthèses contenant des éléments séparés par une espace qui représente la composition. Ainsi, « () » vaut « NIL » et « (1 2 3) » correspond à la S-expression « (1.(2.(3.NIL))) » qui est une liste de trois items.

Bien sûr, LISP peut noter des fonctions dites « de première classe » (first-class functions), c’est-à-dire des fonctions acceptant d’autres fonctions comme paramètres et comme résultat. Une fonction est représentée par une liste en syntaxe préfixée : le nom est le premier atome (un symbole) et les paramètres sont les éléments de la suite : « (fct x y) » (ce qui, en impératif, correspondrait à un appel « fct(x,y) »).

Il existe un grand ensemble de fonctions prédéfinies qui constituent les mots-clés du langage, y compris les opérateurs. Ainsi la somme « a+b » se programme « (+ a b) », mais par composition, « (+ a b c d) » représente une somme de quatre éléments. En particulier, pour construire une « cons », on ne peut utiliser la notation « dotted pair », mais la fonction « cons » : « (cons 1 2) » qui a pour valeur « (1.2) ». On remarque l’effet de substitution par évaluation, puisque le programme source est une liste de 3 éléments (l’atome du premier est le symbole « cons »), mais sa valeur est une seule « cons ».

Voici, par exemple, une fonction calculant le PGCD en LISP par l’algorithme d’Euclide (Εὐκλείδης), évidemment de façon récursive, puisqu’il s’agit d’un langage impératif. La fonction s’appelle « my_gcd », parce que « gcd » est déjà prédéfini en Common LISP.

(defun my_gcd (a b) (if (zerop b) (abs a) (my_gcd b (rem a b))))
(print (my_gcd 48 -30))

Le «print» permet à ce programme de produire un output s’il est compilé. Dans un interpréteur, introduire simplement « (my_gcd 48 -30) » affiche « 6 » directement.

Pour avoir un programme un peu plus long, examinons le célèbre problème des tours de Hanoï ci-dessus.

(defun Hanoi (Disques)
  (defun _Hanoi (Disques Debut Fin)
    (if (< 0 Disques)
      (append
        (_Hanoi (- Disques 1) Debut (- 6 Debut Fin))
    (list (cons Debut Fin))
        (_Hanoi (- Disques 1) (- 6 Debut Fin) Fin)
      ) 
    )
  )
  (_Hanoi Disques 1 2)
)
(print (Hanoi 4))

La valeur de ce programme — celle résultant de l’évaluation de la dernière ligne — est une liste, résultat de la concaténation (fonction « append ») des sous-listes construites finalement à la ligne 6 ; chacune est constituée chacune d’un seul élément dont la donnée (« car ») est une (référence vers une) « cons » indiquant le mouvement.

D’autres langages fonctionnels ont bien sûr été créés, notamment ML (pour « Meta-Language ») en 1973, un langage fortement et statiquement typé, surtout connu par son dialecte Caml et son lointain descendant orienté objet, OCaml (apparu en 1996). Mais également Scheme, Erlang, Haskell, F#...

Parmi cette véritable jungle, on peut distinguer deux sous-familles par leur stratégie d’évaluation des sous-expressions :

  • Évaluation stricte, gloutonne ou immédiate (eager evaluation) : tout est évalué (ou doit pouvoir l’être) en ordre quelconque en application (très) stricte du principe de transparence référentielle ; c’est le modèle de LISP.
  • Évaluation paresseuse (lazy evaluation) : les sous-expressions ne sont évaluées qu’à l’usage, c’est-à-dire qu’une notation autoréférentielle ou récursive est possible, car leur évaluation se fait en parallèle (en fait, par interfoliage) au fur et à mesure des besoins ; c’est le modèle de Haskell.

Haskell est même un langage fonctionnel pur, non seulement parce qu’il applique cette stratégie d’évaluation, mais aussi parce qu’il est fortement typé et dépourvu de toutes structures rappelant la programmation itérative : « tout y est fonction », et toujours en attente d’évaluation effective.

Cette propriété permet donc de définir facilement des ensembles infinis. Par exemple, en Haskell,

nat = 0 : map (+ 1) nat

définit l’ensemble infini des nombres naturels N, selon la méthode itérative de Peano. Le «:» est « l’équivalent » du « . » en LISP, et « map » est une fonction prédéfinie qui s’applique de manière vectorielle sur son second argument. La seconde occurrence de « nat » n’y est pas pré-évaluée, mais transformée en une itération à la demande. Haskell est un langage statiquement typé, mais avec inférence de type.

Grâce à sa stratégie d’évaluation paresseuse, on peut résoudre le problème des tours de Hanoï de manière purement impérative :

hanoi :: Int -> [(Int,Int)]
hanoi disques = _hanoi disques 1 2 []
  where
    _hanoi 0 _ _ suite = suite
    _hanoi disques debut fin suite
      = _hanoi (disques-1) debut (6-debut-fin) ((debut, fin)
      : _hanoi (disques-1) (6-debut-fin) fin suite)
main = print (hanoi 4)

La valeur affichée est la liste des mouvements successifs : des couples « (origine,destination) » (voyez la syntaxe de la valeur de la fonction déclarée en fin de ligne 1). Cette ligne 1 est, en effet, la déclaration obligatoire de la fonction (notation «::»); les lignes 2–7 la définissent (notation «=» qui est une définition, pas une assignation, évidemment !) à l’aide d’une valeur (une « fonction », puisque le langage est fonctionnel) intermédiaire locale. Cette substitution cyclique est possible, puisqu’elle n’aura lieu que si nécessaire et aboutira toujours in fine à une substitution non récursive de la ligne 4.