Skip to content

Histoire et taxonomie des langages de programmation

Pour rédiger cette partie, nous nous sommes basés sur les supports :

Yves Roggeman, LANGAGES DE PROGRAMMATION, VOL. I (3ème édition) 2020

Yves Roggeman, LANGAGES DE PROGRAMMATION, VOL. II (4ème édition) 2020

voir aussi https://fr.wikipedia.org/wiki/Paradigme_(programmation) http://projet.eu.org/pedago/sin/ICN/1ere/4-langages.pdf

Nous invitons le lecteur à utiliser ces références pour compléter l'information résumée ici.

Premiers langages de programmation

La genèse des tout premiers langages (FORTRAN, COBOL, ALGOL, LISP...) a montré que leur évolution allait être très rapide : les versions, voire générations différentes, se succédaient rapidement. De plus, les dialectes se multipliant (au gré du développement de compilateurs, bibliothèques et runtimes associés), il était indispensable de fixer leur définition, que ce soit par des normes officielles ou des standards de fait.

Mais ce qui est remarquable également, c'est le foisonnement de nouveaux langages qui sont apparus rapidement, presque toujours comme héritiers manifestes d'un ou plusieurs prédécesseurs, que cette filiation soit annoncée et acceptée ou non. Ceci explique la grande similitude entre langages, pour autant qu'on ne s'attarde pas trop sur de petits détails, bien sûr, mais c'est une grande chance pour les candidats-programmeurs lors de l'étude d'un nouveau langage.

Il existe de nombreux auteurs qui proposent une généalogie des différents langages usuels ; elles sont heureusement très proches.

On peut citer Éric Lévénez (qui se limite à une cinquantaine de langages) ou la HOPL (History Of Programming Languages) de DiarmuidPigott. Voir aussi la liste des langages de RosettaCode.org.

Mais au-delà de cette visualisation historique des créations de langages, il est utile d'essayer de les regrouper par familles présentant un grand ensemble de caractéristiques communes. Celles-ci sont d'ailleurs fortement liées aux objectifs, à l'usage envisagé pour le langage par ses concepteurs.

Par exemple, FORTRAN (1956–57) visait à réaliser des calculs scientifiques. Sa syntaxe est très proche de l'écriture algébrique usuelle et sa bibliothèque de fonctions transcendantes (logarithmes, trigonométriques, etc.) est très riche, dès le début. Par contre, les structures de programmation originelles sont quasi absentes : une boucle à compteur et des sauts conditionnels, mais aucune instruction composée algorithmique de type « while » ou « if then else ».

Par contre, COBOL (1959–60) est essentiellement conçu pour faire des entrées-sorties. Ces instructions y sont riches et nombreuses, ainsi que les capacités de décrire et manipuler des fichiers. Par contre, il ne comporte toujours quasi aucune instruction de calcul proprement dit.

Et ALGOL (1958–60) a été imaginé par des algorithmiciens. Sa syntaxe est celle d'une programmation structurée mature, mais il n'a aucune instruction standard d'entrées-sorties ! Pour cela, il a fallu attendre ALGOL68 — un autre langage, mais un dérivé très proche d'ALGOL — qui est vraiment l'archétype presque parfait d'un langage algorithmique. Sa syntaxe ou des variantes très proches servent d'ailleurs généralement pour la description des algorithmes dans les ouvrages et publications scientifiques de ce domaine.

Quant à LISP (1958), il ne devait originellement servir qu'à décrire mathématiquement des programmes sous forme de formules logiques proches du λ-calcul. Un programme dans ce langage peut donc, par essence, décrire et produire (i.e. calculer) un autre programme, le programme lui-même étant une donnée de lui-même et tout code étant potentiellement automodifiant. Il n'est toujours pas standardisé comme tel et il existe donc une foison de dialectes différents et incompatibles, dont certains sont finalement devenus des normes (Common Lisp en 1994, par exemple). Ce langage reste très utilisé dans le domaine de l'intelligence artificielle. Et il en est de même de tous les autres. Bien sûr, il n'existe pas une seule façon de mettre de l'ordre dans cet univers, et la répartition que nous présentons ici est largement arbitraire... et bien sûr incomplète. De plus, les frontières ainsi introduites sont floues et poreuses.

Cette description des paradigmes est librement inspirée de l'ouvrage de vulgarisation (Torra I. Reventós, Vicenç, Del Ábaco A La Revolución Digital: Algoritmos y Computación, RBA Libros, 2011, 150p.) (traduit dans de nombreuses langues).

Langages impératifs

Cette première famille, de loin la plus répandue, est à l'origine une « humanisation », une formalisation plus lisible par un humain du code machine binaire (machine code) ou de sa version textuelle (i.e. sous forme de véritables caractères) en langage d'assemblage ou assembleur (assembly language).

Un programme dans un langage impératif (imperative langage) décrit donc une suite d'instructions qui modifient l'état de la machine.

Un tel langage respecte le modèle d'architecture de von Neumann, c'est-à-dire que la machine qui doit l'exécuter est constituée d'un processeur et d'une mémoire contenant le code lui-même, d'une part, et les données qu'il traite d'autre part.

Un programme impératif qui s'exécute n'est qu'une suite de modifications de l'état de la mémoire, soit en modifiant une donnée, une variable (c'est une assignation), soit en indiquant explicitement son instruction suivante (c'est un saut, un « go to » conditionné ou non par l'état d'une variable). Le nouvel état d'une variable est lié à une évaluation, une opération (arithmétique, logique ou booléenne) effectuée sur une ou plusieurs variables.

Le jeu d'instructions des langages impératifs, quoique formel et a priori universel, reste proche de celui d'un langage de bas niveau, mais les adresses et les registres disparaissent au profit de variables — y compris de pointeurs parfois — et d'expressions, donc de valeurs temporaires invisibles et anonymes. Le modèle d'exécution devient celui de l'architecture de Harvard : la séparation stricte du code et des données en mémoire. Cette propriété est même devenue un critère essentiel de distinction entre les langages impératifs et les langages déclaratifs.

Ils peuvent ainsi être très aisément compilés, très rarement interprétés. La genèse de cette famille de langage a été étroitement liée à celle de la conception de leurs compilateurs, ces derniers précédant et influençant même la définition réelle du langage.

Langages procéduraux

Il n'existe pratiquement plus de langages impératifs bruts, parce que le besoin d'une plus grande garantie dans l'écriture de programmes corrects — ou du moins s'en approchant — a incité l'évolution de la syntaxe et de la sémantique vers plus de contraintes et plus de structures.

Parmi les ajouts, on trouve : 1. L'introduction d'instructions composées (boucles et choix) pour remplacer les sauts (jumps) et les étiquettes (labels) ; 2. La définition de types statiques, non seulement pour les valeurs, mais également pour les variables, que ces types soient déclarés ou inférés ; le type d'une variable reste fixé pour toute sa durée de vie, ce qui induit un mécanisme souvent complexe de conversions implicites. 3. La division et paramétrisation du code en fonctions ou procédures, sous différentes formes, avec paramètres formels et permettant également la réutilisation d'un même code (code reuse) de nombreuses fois, par un mécanisme de CALL-RETURN.

Certains auteurs distinguent les langages en fonction de ces trois propriétés : la propriété 1 correspond aux langages de programmation structurée ou algorithmiques, ceux qui satisfont la deuxième sont les langages typés et la troisième est la catégorie des langages procéduraux au sens strict. Il est exact, par exemple, que dès ses origines réelles (l'existence du premier compilateur), FORTRAN avait des sous-routines et fonctions, donc bien avant l'apparition d'instructions composées (autres que le «DO» basique). A contrario, le COBOL classique (avant sa version de 2002) n'a pas de fonctions ou procédures avec paramètres, mais des structures de choix et des boucles évoluées. Mais généralement, ces trois propriétés coopèrent à la structure du langage et nous adopterons donc la définition suivante.

Un langage procédural (procedural language) est un langage de programmation impératif qui satisfait les trois propriétés ci-dessus : instructions composées de programmation structurée, système de typage statique et découpe du code en fonctions avec paramètres formels.

Cette famille est la plus grande parmi les langages fortement utilisés. Son modèle originel est ALGOL, puis ses nombreux descendants, parmi lesquels C (apparu en 1971 seulement) est sans doute le plus célèbre représentant, ne serait-ce que pour la foison d'autres langages qu'il a inspirés, directement ou indirectement. Leur syntaxe est donc largement commune. ALGOL est partiellement issu de FORTRAN ; il en emprunte par exemple la syntaxe algébrique des expressions, y compris les appels de fonctions ou les tableaux («abs(x)+v[i]»), ainsi que les déclarations de variables (« integer i, j »). Il introduit toutefois de très nombreuses nouveautés essentielles qui ont été reprises, et parfois tristement abandonnées plus tard, par les générations suivantes. Citons, par exemple, - Un séparateur d'instruction « ; ». Il remplace la marque de fin de ligne utilisée par FORTRAN, puisque son écriture est complètement insensible aux blancs et aux lignes. Ce concept est devenu dans toute la famille C un terminateur d'instruction. Un terminateur (le « ; » en C, le « . » en COBOL, etc.) est une marque de fin d'instruction obligatoire, souvent redondante, mais utile au compilateur pour se resynchroniser en cas d'erreur de syntaxe, tandis qu'un séparateur ne doit s'écrire qu'entre deux instructions au sein d'une séquence. - Une notation propre pour l'assignation «:=». Elle évite l'ambiguïté avec la notation mathématique traditionnelle d'égalité, le « = » étant utilisé naturellement pour tester cette égalité. On retrouve ce choix astucieux et pédagogique en Pascal, en Smalltalk ou en Go (pourtant récent, 2009), mais aussi en CPL et BCPL, les ancêtres du C. On se demande pourquoi les concepteurs du langage B sont revenus à la syntaxe malheureuse de FORTRAN en influençant directement celle de C et de ses successeurs, ce qui impose en plus d'adopter une notation différente pour la comparaison (« .EQ. » en FORTRAN, « == » en C, etc.). - Des blocs d'instructions formalisant le concept algorithmique de séquence d'opérations. Ainsi la séquence, les choix et les boucles sont trois structures de programmation qui peuvent s'imbriquer pour décrire un algorithme. - La localité des déclarations. Une variable est déclarée au début d'un bloc (ou d'une instruction) et a une portée limitée à ce bloc. - Des fonctions récursives (voir ci-dessous) avec, a priori, une pile d'exécution. On retrouve plus ou moins ces différents concepts dans les langages procéduraux modernes, mais leur syntaxe diffère très souvent sur la représentation syntaxique des séquences d'instructions.

Plusieurs critères peuvent être utilisés pour subdiviser cet immense ensemble de langages. Nous allons en donner cinq exemples, sur base de la forme syntaxique ou sur la richesse d'expressivité.

1° Avec ou sans blocs

La séquence d'instruction est, comme nous le savons, une des structures algorithmiques essentielles. Certains langages procéduraux en font une instruction composée en soi avec sa syntaxe propre, d'autres en font un usage implicite et plus limité : il n'existe de bloc qu'au sein d'une autre instruction composée ou comme le corps d'une fonction.

La définition d'un bloc comme instruction autonome se fait généralement par marques explicites de début et fin de bloc, avec plusieurs variantes toutes équivalentes. - Par mots-clés « begin...end ». C'est ALGOL qui a introduit historiquement ce couple de mots-clés ; on le retrouve en SIMULA, en Ada, en Pascal et tous ses descendants (Modula-2, Modula-3, Delphi, etc.), mais pas de manière générale en ALGOL 68, comme on le verra ci-dessous (même s'il maintient cette notation dans certaines circonstances, avec la notation «(...)» complètement synonyme à « begin...end », d'ailleurs). - Par parenthésage, généralement par accolades «{...}». C'est une simple variante du choix précédent, certes plus synthétique. C'est une création du langage B devenue presque une « marque de fabrique » du C et de ses descendants (C++, D, Java, JavaScript, C#, F#...), parfois lointains (Perl, Raku, Go...), mais il a existé d'autres formes tombées en désuétude (« \((...)\) » en BCPL ou « [...] » en Smalltalk, par exemple). - Par indentation par «INDENT...DEDENT» de Python ou Occam.

Pour les langages sans bloc autonome, une séquence est implicitement délimitée en son début, par l'instruction qui le contrôle (choix, boucle, fonction) et à sa fin, par une marque de fin d'instruction particulière. C'est donc la syntaxe de chaque instruction composée qui contient une indication de terminaison propre, ce qu'on appelle une syntaxe d'instructions gardées (guarded command syntax). Ici encore, plusieurs formes sont possibles. - Par mot-clé général, «end» le plus souvent. Les instructions composées se terminent toutes ainsi : « if...end » ou « if...else...end », « while...end », « function...end », etc. On trouve cette syntaxe en Ruby, Lua, etc. - Par mot-clé spécifique, selon l'instruction. Par exemple, « IF...ELSE...END IF » ou « DO WHILE... END DO » en FORTRAN 77, « IF...ENF-IF », « PERFORM...END-PERFORM » « READ...END-READ », etc. en COBOL-85, « If...End If », « While...End While », « For...Next » ou « Do...Loop » en Visual Basic, etc. Le plus bel exemple de tous est celui d'ALGOL68 : chaque instruction se termine par l'image miroir de son mot-clé caractéristique. On écrit ainsi «if...then...fi» (avec clauses «elif...then» et «else» facultatives), «case...esac», «do...od» (précédé de clauses « for » et « while » facultatives), etc.

2° Avec ou sans récursivité

S'il paraît évident pour un programmeur d'aujourd'hui qu'une fonction peut être appelée récursivement, il n'en a pas toujours été ainsi et on peut toujours complètement dérécursifier un algorithme, ce qui le rend souvent beaucoup plus efficace. .

Pour cette raison, certains langages font le choix délibéré de ne pas autoriser les appels récursifs, directs ou indirects, avec parfois une dérogation si cet usage est explicitement déclaré (avec un mot-clé « recursive », par exemple) pour chaque fonction individuellement.

ALGOL, PL/I (moyennant déclaration), C, etc. permettent des appels récursifs. Voilà sans doute pourquoi ce modèle s'est largement généralisé. La version FORTRAN 90 a également autorisé les procédures et fonctions récursives moyennant déclaration explicite.

Pascal, PL/I, Ada, et quelques autres seulement permettent également l'imbrication de fonctions. Mais ces exemples sont plus rares, même si l'implantation d'algorithmes est plus aisée lorsqu'on dispose de cette possibilité.

3° Avec ou sans types programmés

A priori, un langage même statiquement typé peut ne travailler qu'avec un ensemble restreint de types élémentaires et quelques constructions simples supplémentaires, comme celle de vecteurs (variables indicées) et pointeurs. Un tel contexte permet d'implanter tout algorithme et plusieurs générations de langages n'ont connu que ce modèle.

Mais il est plus simple et surtout plus lisible et plus robuste de pouvoir enrichir son ensemble de types disponibles par de véritables constructions de nouveaux types par combinaison d'autres types préalablement définis, ce qu'on appelle des types programmés. Ces combinaisons sont l'imbrication itérée de constructions : vecteur (bloc homogène indicé de taille fixe), structure (ou « enregistrement », bloc hétérogène de taille fixe) et pointeur (ou référence, adresse d'un objet d'un type donné).

ALGOL68 a été le premier à introduire une syntaxe complète de définition de véritables types programmés. Toutes les constructions du langage et leur sémantique — définie formellement à l'aide d'une grammaire de van Wijngaarden — sont fondées sur un concept général de « type » (appelé « MODE » dans ce contexte, car le mot-clé pour une définition de type est « mode ») qui peut être une combinaison quelconque d'autres types. Et surtout, il permet la définition d'opérateurs (en surcharge) agissant sur ces types nouveaux, en plus évidemment de fonctions (surchargeables) ayant des paramètres formels ou des valeurs de ces types.

L'évolution naturelle des langages impératifs à types programmés est celle de langages orientés objet.

4° Avec ou sans pointeurs

Qu'on le veuille ou non, tout langage impératif doit utiliser des références. En effet, un tel langage est fondé sur l'existence d'assignations et celles-ci font nécessairement intervenir une R-value qui doit être évaluée — c'est donc la valeur d'une donnée — et une L-value qui est l'adresse de la destination — c'est donc une référence.

Mais ces références peuvent n'être que constantes et implicitement définies par la déclaration (ou le premier usage) d'une variable à laquelle elle est ainsi à jamais liée. Tel est le cas d'une partie des langages procéduraux que nous qualifierons de « sans pointeurs ».

Certains permettent toutefois de modifier le lien d'une référence. On peut alors définir des variables dont la valeur est une référence, c'est-à-dire, puisqu'une variable non constante est une L-value, des « références vers une référence ». Dans ce cas, ces variables peuvent contenir une référence nulle (ce nom varie selon le langage) ou se voir assigner la valeur d'expressions particulières — notamment des constructions dynamiques de nouvelles variables — qui doivent s'évaluer comme une référence. Dans ce cas, on peut aussi transmettre des références comme paramètre effectif de fonction. Mais l'usage de ces références reste semblable : servir de L-value ou être automatiquement déréférencée dans une expression à évaluer. Java, JavaScript et Python sont des exemples de tels langages.

Cela ne permet de pas réellement utiliser dans son code le fait qu'il s'agit de données non constantes représentant une adresse et de leur appliquer des opérations de nature à modifier cette adresse (autrement qu'en l'écrasant par une autre adresse constante). Les langages qui le permettent sont ceux que nous qualifions de « avec pointeurs ». ALGOL68, Pascal, C et de nombreux successeurs sont dans ce cas.

Un pointeur n'est pas qu'une simple adresse : pour s'inscrire dans la structure d'un vrai langage procédural (voir définition ci-dessus), un pointeur doit être typé ; c'est donc un type composé qui ne peut référencer qu'un seul type de donnée. Cette contrainte permet notamment un contrôle statique du type après déréférencement et l'ajout de conversions implicites si nécessaire. C'est bien le cas de la plupart des langages « avec pointeurs ».

Ces langages sont très nombreux : FORTRAN (depuis la version FORTRAN 90), PL/I, ALGOL68, Pascal, Modula-2, Modula-3, Ada, BASIC, C, C++, D, Eiffel, Go, etc. et, de manière plus limitée, c'est-à-dire sans arithmétique de pointeurs possible, C#, Visual Basic, Perl, Raku... Les langages vraiment sans pointeurs, c'est-à-dire sans opérateur de prise d'adresse par exemple, comme Java, JavaScript ou Python font presque figure d'exceptions dans cet univers.

Ce que l'on peut regretter, c'est que le modèle le plus répandu de pointeur reste celui de langages conçus entre 1968 et 1971, ce qu'on appelle des « pointeurs bruts » (raw pointers) : une simple adresse, sans possibilité de vérifier à l'exécution si elle est correcte, c'est-à-dire qu'elle correspond effectivement à une donnée vivante. Il existe pourtant une solution simple : lui adjoindre un identifiant unique de la donnée référencée, un hachage (hash) de celle-ci. Ceci éliminerait le risque de pointeurs vers des zombies (dangling pointers) ou non initialisés (wild pointers), mais avec un surcoût en espace et en temps (le runtime doit systématiquement faire la vérification).

Les risques d'erreurs à l'exécution liés aux pointeurs sont sans doute ce qui a conduit quelques langages, pourtant issus directement de C, à abandonner les pointeurs, malgré la perte d'expressivité et d'efficacité du code produit.

Langages orientés-objet

Nous avons déjà présenté certains aspects en Python.

Les langages orienté-objet sont les plus utilisés aujourd'hui. Ils permettent d'utiliser le paradigme de programmation par objets, qui change la façon de concevoir les programmes informatiques via l'assemblage de briques logicielles appelées objets.

L'histoire des langages orientés objets commence en 1967. En
implantant les Record Class de Hoare, le langage Simula 67 pose les
constructions qui seront celles des langages orientés objet à classes
classe, polymorphisme, héritage, etc.

Mais c'est réellement par et avec Smalltalk 71 puis Smalltalk 80, résultat des travaux d'Alan Kay, inspiré en grande partie par Simula 67 et Lisp, que les principes de la programmation par objets sont pleinement définis : objet, encapsulation, messages, typage et polymorphisme via la sous-classification ;

les autres principes, comme l'héritage, sont dérivés de ceux-ci.

À partir des années 80, commence l'effervescence des langages à objets :

  • C++ (en 1983),
  • Objective-C (en 1984),
  • Eiffel (en 1986),
  • Common Lisp Object System (en 1988),
  • etc.

Les années quatre-vingt dix voient l'âge d'or de l'extension de la programmation par objets dans les différents secteurs du développement logiciel.

Essayons de résumer les principes des langages orienté-objet. Concrètement, un objet est une structure de données qui répond à un ensemble de messages.

Cette structure de données définit son état tandis que l'ensemble des messages qu'il comprend décrit son comportement :

  • les données, ou champs, qui décrivent sa structure interne sont appelées ses attributs ;
  • l'ensemble des messages forme ce que l'on appelle l'interface de l'objet ;

c'est seulement au travers de celle-ci que les objets interagissent entre eux.

Une méthode donne la réponse au message reçu.

Le principe d'encapsulation consiste à cacher certains attributs ou méthodes. Ainsi, le programme peut modifier la structure interne des objets ou leurs méthodes associées sans avoir d'impact sur les utilisateurs de l'objet.

Dans la programmation par objets, chaque objet est typé. Le polymorphisme permet d'utiliser des objets de types différents là où est attendu un objet d'un certain type. Une façon de réaliser le polymorphisme est le sous-typage appelé aussi héritage de type : on raffine un type-père en un autre type par des restrictions sur les valeurs possibles des attributs. Notons qu'il existe d'autres types de polymorphisme.

On distingue dans les langages objets deux mécanismes de sous-typage :

  • l'héritage simple (comme c'est le cas avec Smalltalk, Java, C#), et
  • l'héritage multiple (comme c'est le cas avec C++, Python, Common Lisp, Eiffel).

Notons également le principe de redéfinition des messages (ou overriding en anglais) qui permet à un objet de raffiner une méthode des objets d'un type parent.

Enfin, parmi les critères de classement des langages orientés-objet, on distingue les langages orientés-objets purs ou non.

Dans un langage orienté objet pur, toute la syntaxe et la sémantique sont construites autour de la notion d'objet, sans exception :

  • tous les types, même les primitifs, sont des classes,
  • toutes les opérations, même prédéfinies, sont des méthodes de classes,
  • toutes les classes sont des objets, instances de métaclasses,
  • et le code du programme lui-même est un objet ;

il y a donc réflexivité complète.

Des exemples sont Smalltalk, évidemment, mais aussi Ruby, Raku, Self, ou encore Eiffel.

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.

Langages logiques

Parallèlement au renouveau des langages fonctionnels est née une approche fondamentalement différente de la programmation déclarative. Plutôt que de décrire une « formule » exprimant le calcul à effectuer, i.e. une fonction au sens fonctionnel, l'idée est de laisser encore plus de travail implicite à l'interpréteur ou au runtime. Ceci a conduit à ce qu'on a appelé la « programmation logique ». Dans ce contexte, un programme est une simple question, à laquelle, conformément à la logique aristotélicienne, on attend une réponse « oui » ou « non ». On ne donne plus la formule qui y répond, ni le raisonnement qui y conduit, ni évidemment la séquence d'opérations qui permettrait de le trouver, puis d'évaluer la réponse.

Bien sûr, cette « question » est contextualisée : on doit fournir préalablement (dans le programme même, où cela joue le rôle de « déclarations », ou bien dans sa « bibliothèque ») une « base de connaissances » constituée de faits connus et acceptés pour « vrais » (des prédicats (facts), ce qu'on appelle les axiomes en logique formelle) et des règles de déduction (rules), de combinaison de ces prédicats pour établir de nouvelles vérités (c'est le « système formel » dans lequel on travaille). L'interpréteur utilise alors ces données pour essayer de construire au moins une séquence de règles menant des prédicats à la question posée ou à sa négation.

Un tel programme définit ainsi ce qu'on appelle un «système logique» (deductive system), ou simplement « une logique », au sens de la logique mathématique. Son interpréteur s'appelle un « moteur d'inférence ».

Pour que ce moteur puisse être conçu, pour qu'il existe un algorithme capable de déduire une réponse à la question à partir de la base de connaissances, il faut imposer une forme particulière aux règles permises. En plus, il est préférable de se limiter à des situations où ce moteur peut être efficace ! Voilà pourquoi les langages logiques imposent une logique du premier ordre (first-order logic) — cette logique admet des prédicats écrits avec des variables simples, des opérateurs booléens (∧,∨,¬) et des quantificateurs (∀,∃) sur ces variables, mais pas de variables quantifiées représentant d'autres prédicats ou fonctions — et même souvent exclusivement des « clauses de Horn ».

Une clause de Horn est une clause, c'est-à-dire une expression booléenne disjonctive (i.e. formée de disjonctions (∨) de littéraux) qui contient au plus un littéral positif, les autres littéraux étant des négations.

La motivation provient de ce qu'une telle clause « q∨¬p1∨⋯∨¬pn » peut s'écrire « q ⫤ p1∧⋯∧pn », ce qui signifie « si p1 ... et pn, alors q », condition sous une forme bien comprise de tout programmeur !

On peut montrer que la combinaison de deux clauses de Horn est encore une clause de Horn (c'est un système stable) et que vérifier si une telle clause est vraie et un problème polynomial, même linéaire, par rapport au nombre de littéraux. De plus, un système logique défini à l'aide de clauses de Horn est équivalent à une machine de Turing universelle ; c'est donc un modèle parfait pour définir un langage de programmation.

Un langage logique est un langage pour lequel un programme est décrit par des clauses de Horn.

Parmi elles, les clauses positives (celles formées du seul littéral positif) énoncent les faits (facts), les axiomes ; les clauses strictes (definite clauses) (celles avec un seul littéral positif et au moins un négatif) définissent les règles de déduction (deduction rules) et les clauses négatives (sans littéral positif) représentent les questions posées (query) ou le but à atteindre (goal clauses).

Cette dernière catégorie se justifie du fait que « ¬q∨¬p1∨⋯∨¬pn » peut s'écrire « ∅ ⫤ q∧p1∧⋯∧pn », une preuve par l'absurde, puisqu'une clause vide « ∅ » est fausse. C'est le principe de la négation par l'échec (NAF ou Negation As Failure) : dans un langage logique, pour prouver « q » (i.e. affirmer qu'il est vrai), on montre qu'on ne peut déduire « ¬q » à partir des faits « p1...pn » selon les règles définies.

Il existe plusieurs exemples de langages logiques, mais celui qui est de loin le plus utilisé et qui constitue véritablement l'archétype de cette famille de langages, c'est Prolog.

Ce langage est une création française. Il a été imaginé vers 1971–72 par Alain Colmerauer et Philippe Roussel, chercheurs dans le domaine de l'intelligence artificielle, plus précisément en traductique, à l'université d'Aix-Marseille (à Luminy). Pour sa définition et sa mise en œuvre, ils se fondaient directement sur les travaux préalables du logicien et informaticien Robert Kowalski, à l'époque de l'université d'Édimbourg (Edinburgh), sur l'interprétation procédurale (et automatique) des clauses de Horn. Pour le décrire correctement, ils ont également utilisé les grammaires de van Wijngaarden, celles qui avaient si bien servi à la définition d'ALGOL68.

Durant l'été 1972, ils ont implanté un premier système Prolog en FORTRAN (ce qu'on appelle le Prolog I) qui eut rapidement du succès, malgré sa syntaxe complètement francophone et son efficacité très limitée... S'en suivirent de longs travaux intensifs en collaboration entre les deux équipes qui conduisirent à la conception d'un tout nouveau modèle de moteur d'inférence. En 1977, David Warren développa ce qu'on a appelé « le Prolog d'Édimbourg », mais ce n'est qu'en 1983 qu'il dévoila son modèle de machine abstraite, la WAM (Warren Abstract Machine), correspondant au Prolog II, qui le rendait aussi performant que les meilleurs LISP de l'époque. Il y eut ensuite le Prolog III en 1987, puis le Prolog IV en 1995–96, qui correspond à l'adoption de la norme ISO (revue en 2000) qui est le Prolog couramment utilisé aujourd'hui et qui accepte la programmation par contraintes et quelques autres extensions.

Comme Java, Prolog est en effet un langage compilé dont le bytecode produit est ensuite exécuté par une machine virtuelle, mais un programme peut aussi être compilé directement en code binaire natif. Ainsi, un système Prolog fonctionne normalement en deux temps : il compile les clauses qui vont constituer sa base de connaissances, puis il passe en mode « réponse aux questions » par le moteur d'inférence, a priori en mode interactif (il affiche le prompt « :- », puisqu'une question est une règle sans membre de gauche).

La syntaxe de Prolog est très simple. Ses termes sont des atomes, variables foncteurs ou structures :

  • Un atome est un nom (un identificateur alphanumérique commençant par une lettre minuscule), un nombre (en notation littérale), une chaîne de caractères (entre apostrophes) une structure vide (« {} » ou « [] ») ou, dans certaines circonstances, un opérateur, (graphic token).
  • Une variable (un identificateur commençant par une lettre capitale ou par « _ »).
  • Un foncteur (functor) ou terme composé (compound terms). Il s'agit d'une construction syntaxique, semblable à celle d'une fonction, composée d'un atome (le nom du foncteur) suivi immédiatement (i.e. sans espace), entre parenthèses, d'une suite d'autres termes séparés par une virgule (les paramètres du foncteur). Parmi eux peuvent figurer d'autres foncteurs, ce qui permet la récursivité fonctionnelle. L'arité d'un foncteur est évidemment significative.
  • Une structure, une liste : entre crochets, une suite de premiers atomes, puis une liste de suite précédée de «|» («[a,b|L]»), la suite pouvant être omise si elle est vide («[a,b]» est synonyme de « [a, b | []] ») ; elle peut aussi être écrite en « dotted notation » à l'aide du foncteur «.» («.(a,b)» est synonyme de «[a|b]»).

Bien sûr, une « variable » de Prolog n'a rien à voir avec le sens donné en programmation impérative. Il s'agit ici d'une variable au sens de la logique mathématique, d'une inconnue. Dans une règle (voir ci-dessous), une variable correspond à une quantification universelle « ∀ », c'est une variable libre du λ-calcul ; dans une question, elle permettra de rechercher une valeur conduisant à une vérité, si elle existe « ∃? ».

Un programme en Prolog est une suite de clauses : prédicat, règle ou question. Chaque clause se termine par un point « . ». Un fait ou prédicat s'énonce en Prolog par un foncteur, suivi directement du point : « vert(herbe). », ce qui veut vraisemblablement dire que «l'herbe est verte», mais c'est une interprétation purement humaine : il n'y a aucun sens inné dans les atomes (c'est comme en physique).

Un prédicat peut contenir des variables, ce qui énonce une « vérité générale ». Par exemple, la propriété « est le second élément d'une liste » peut s'énoncer comme le fait « sec([_, X | _], X). ». Ce foncteur a deux paramètres : une liste et une simple variable. On note l'usage de la variable « _ » indiquant une valeur quelconque ; le premier argument est une liste dont le premier élément est quelconque, le deuxième « X » et la suite est une liste quelconque (elle peut être vide).

Une règle s'écrit à l'aide du symbole « :- », également terminée par un point. Son membre de gauche est un foncteur qui sera vrai si tous les termes figurant dans membre de droite le sont ; ils sont séparés par une virgule « , » signifiant « et ». L'usage de variables permet d'écrire des règles générales : «mortel(X):-humain(X).», ce qui veut vraisemblablement dire que «tout humain est mortel», toujours en lecture anthropocentrique. De même,

'Ferrari'(X) :- rouge(X), voiture(X).

pourrait signifier que toutes les voitures rouges sont des Ferrari (on peut rêver en programmant).

Tant le membre de gauche que le membre de droite peuvent être vides. Ce second cas revient à un fait et on omet le « :- » ; le premier cas est une question.

Pour aider le programmeur, de nombreuses règles sont prédéfinies par le langage et, parmi elles, quelques prédicats : «true», «fail», «is», «+», etc.

Ainsi le célèbre programme « Hello, World! » s'écrit, de manière interactive, à l'aide des prédicats prédéfinis «write» et «nl» :

write('Hello, World!'), nl.

Et « halt. » permet de quitter l'interpréteur ; c'est plus propre que « CTRL-D ».

Ainsi, en combinant intelligemment les faits et les règles, on peut tout programmer (Prolog est Turing complet). Par exemple, tester si « y est la valeur absolue de x » pourrait s'écrire, en première tentative :

abs(X, Y) :- X < 0, Y is -X.
abs(X, X) :- X >= 0.

Ce n'est qu'une première version, incomplète (voir ci-dessous) et incorrecte, car elle ne s'assure pas que « X » est numérique, ce qui est imposé par tous les termes du membre de droite. Le foncteur prédéfini « is » impose l'égalité de ses deux paramètres, mais il évalue le second avant l'unification avec le premier.

Le nom des variables n'a pour portée que la règle courante ; elle ne s'étend donc pas d'une règle à l'autre. Ainsi, à la seconde ligne ci-dessus, on aurait pu utiliser un autre nom que « X » sans changer le sens du programme.

Ensuite, si l'on interroge par exemple par «abs(-1,1).» ou «abs(5,5).», il répond «yes», mais il répond «no» si l'on demande «abs(2,3).» ou «abs(-1,-1).» ou même «abs(1,a).» (puisque «a» est un atome quelconque différent de «1»). Par contre, «abs(a,1).» produit une erreur (voir correction ci-dessous).

Mais l'intérêt est qu'on peut faire « calculer » une bonne réponse en utilisant le moteur d'inférence et son mécanisme d'unification des variables au sein d'une clause : Prolog cherche à résoudre le problème,

donc à attribuer des valeurs aux variables qui conduisent à une vérité, y compris sur base d'autres variables. Ainsi, à la question

abs(-5, A).

il répond «A = 5», puis par un prompt «?». Si l'on répond par « ↵ », il s'arrête là, puis affiche «yes», car il est content de lui et très fier d'avoir trouvé une solution à votre problème ; mais si l'on répond « ; », il en recherche une autre et répondra « no » s'il n'en trouve plus, ce qui est le cas ici. En Prolog, « , » signifie « et », tandis que « ; » signifie « ou » inclusif.

Une telle recherche impose au moteur d'inférence d'effectuer de nombreux backtrackings pour attribuer des valeurs aux variables. Voilà pourquoi il existe un prédicat prédéfini très important : « ! » baptisé « cut » dont le sens est « n'allez pas plus loin, il n'y a plus d'autre voie utile ». Il permet non seulement d'éviter la recherche d'une autre réponse si elle n'existe pas, mais aussi d'éviter des erreurs parasites qui apparaîtraient dans des voies nécessairement fausses (cela rappelle le principe du SFINAE).

Tenant compte de cela, on peut définir un foncteur « abs(X, Y) » représentant « y = |x| », qui - si les deux variables sont numériques, teste simplement la relation ; - si X est numérique et Y une variable, calcule la seule valeur possible en utilisant le foncteur unaire prédéfini « abs » ; un « cut » est nécessaire ; - si Y est numérique et X une variable, trouve les deux solutions, sauf si Y est nul ; - est faux, mais sans erreur, dans toute autre situation.

abs(X, Y) :- number(X), Y is abs(X), !.
abs(X, Y) :- number(Y), Y > 0, X is -Y.
abs(X, Y) :- number(Y), Y >= 0, X is Y.

On voit que les choses se conçoivent et s'écrivent de façon relativement différente que dans un langage impératif. Pour programmer en Prolog, il faut penser comme un mathématicien, à l'aide de théorèmes (i.e. de propriétés vraies), plutôt que comme un informaticien qui raisonne sur des algorithmes.

Toutefois, si l'on veut que le programme soit efficace, c'est comme dans tout langage : il faut réfléchir aux structures internes, aux codages binaires et finalement, aux instructions qui seront effectivement exécutées par le processeur (ouf ! on redevient informaticien).

Si l'on tient compte de cet aspect — qui est loin d'être un détail ou une option ! — il faut bien connaître l'algorithme suivi par le moteur d'inférence et programmer en conséquence. De ce point de vue, Prolog n'est pas un langage logique pur, puisque l'ordre d'écriture des règles, ainsi que celui des termes dans le membre de droite ont un impact sur l'exécution du programme : il produira les réponses dans un ordre différent ou mettra beaucoup beaucoup beaucoup plus de temps pour répondre.

Par définition du langage, le moteur d'inférence de Prolog parcourt les règles dans leur ordre de définition et, au sein de chaque règle, il évalue les termes de gauche à droite. Cela correspond à un parcours de recherche descendante, appelé « SLD-resolution », au départ de la question posée, pour trouver d'abord les règles dont le membre de gauche correspond (même nom de foncteur et même arité) et tenter d'y attribuer une valeur aux variables éventuelles par unification en parcourant les autres règles pour chacune d'elles, et ainsi de suite. En cas d'échec, il entre en backtracking et tente une autre valeur pour la dernière substitution effectuée.

Ainsi, pour être efficace, il faut veiller à ce que les chemins menant à un échec soient les plus courts possibles (i.e. les moins profonds dans l'arbre de recherche) ou apparaissent après les bons (si l'on recherche une seule réponse). Par exemple, dans le programme ci-dessus, la première règle et son « cut » permet de capturer immédiatement les simples tests, comme « abs(-42,42). », sans explorer les deux autres règles. De même, placer la ligne 3 en dernière position fait qu'il ne recherche pas inutilement une deuxième solution à la question « abs(A,0). ».

Les exemples précédents correspondent à une exécution interactive : les questions sont encodées à l'exécution comme une donnée d'un programme. On peut également concevoir des programmes complets en utilisant le prédicat unaire prédéfini «initialization». Voici, en guise d'exemple, la résolution du problème des tours de Hanoï.

hanoi(Disques) :- integer(Disques), Disques > 0, hanoi_(Disques, 1, 2).
hanoi_(0, _, _) :- !.
hanoi_(Disques, Debut, Fin) :-
  Dm1 is Disques-1, Autre is 6-(Debut+Fin),
  hanoi_(Dm1, Debut, Autre),
  write([Debut, Fin]),
  hanoi_(Dm1, Autre, Fin).

:- initialization(hanoi(4)).

Ce n'est pas vraiment différent des autres langages, impératifs ou déclaratifs. Il faut toutefois utiliser des variables intermédiaires (« Dm1 », « Autre ») pour représenter des « sous-expressions » auxquelles elles sont unifiées (voir ligne 4). En fait, ce concept n'existe pas vraiment en Prolog, mais il existe plutôt quelques « evaluable functors » prédéfinis, comme l'est « abs » utilisé plus haut. Ainsi, « + » et « - » sont des noms de foncteurs évaluables binaires qui, de plus, peuvent s'écrire en notation infixe habituelle.

Autres langages déclaratifs

La programmation par contraintes (constraint programming) est un autre paradigme déclaratif important. On exprime le problème sous forme de variables (ou inconnues) et on décrit les relations entre elles qui doivent être respectées, ce qui réduit l'ensemble de leurs valeurs admissibles. Ces relations sont ce qu'on appelle les contraintes. Un programme est un ensemble de contraintes qui est soumis à un compilateur ou interpréteur qu'on appelle un « résolveur » (solver).

Il existe quelques exemples de résolveurs, généralement conçus pour un domaine de variables particulier (pour des valeurs binaires, on parle de SAT-solver), mais le plus souvent, il s'agit d'extensions ou de bibliothèques particulières de langages traditionnels. Il existe de telles bibliothèques en C++, en Java, etc. Mais Prolog, depuis sa version III, contient un ensemble de foncteurs prédéfinis permettant de réaliser réellement une programmation par contraintes.

Par ailleurs, les langages de balisage (markup language) sont une autre forme de programmation déclarative. Parmi eux, HTML ou XML sont certainement les exemples les plus connus. Un programme y est constitué de balises qui guident le comportement d'un interpréteur dont le rôle est de structurer, de produire ou d'afficher un document, de le mettre en page.

De manière générale, les langages déclaratifs connaissent une évolution — certains diraient une dénaturation — vers « plus d'impératif ». Parfois, cela se fait au sein du langage même (LISP a ainsi une fonction prédéfinie « progn » qui correspond à une évaluation séquentielle de ses paramètres), mais aussi par la création d'un nouveau langage dérivé : ainsi, XSLT est une extension impérative Turing complète de XML. Un autre exemple très connu dans le monde des sciences formelles est le langage « LaTeX », dont moteur sous-jacent, celui du langage TeX originel, est purement impératif (c'est le langage d'assemblage d'une machine à pile virtuelle). Les langages de présentation (appelés « d'impression » à l'origine), tels PostScript ou PDF (Portable Document Format), appartiennent également à cette dernière catégorie.

Autres langages (programmation concurrente, événementielle, ...)

Bien sûr, sans parler des langages exotiques, il existe de nombreux autres langages qui n'entrent pas parfaitement dans l'une des catégories « impératif », « orienté-objet » ou « déclaratif », et qui pourtant sont Turing complets et permettent parfaitement de « programmer ».

L'entrée (Paradigme de programmation, section Autres_types de wikipedia](https://fr.wikipedia.org/wiki/Paradigme_(programmation)#Autres_types) donne des dizaines de paradigmes différents.

Citons en particulier

  • la programmation événementielle où un programme sera principalement défini par ses réactions aux différents événements qui peuvent se produire (Par exemple, TcL/Tk gère un tel paradigme)
  • la programmation concurrente où plusieurs processus (applelés également threads, ou tâches) s'éxécutent en concurrence, donnant lieu à de nombreux problèmes informatiques complexes dont les célèbres problèmes d'interblocage et de famines)

De nombreux langages dédiés (domain-specific languages ou DSL) sont conçus pour répondre aux contraintes d'un domaine d'application précis. On peut citer, comme simple exemple parmi beaucoup d'autres :

  • Les langages de requêtes (query languages) : ils sont a priori conçus pour interroger une base de données ou un système d'information. SQL en est l'archétype.
  • Les langages de script (scripting languages) : à l'origine, il s'agissait des langages associés à un système d'exploitation (un JCL, Job Control Language). De nombreux autres langages interprétés sont venus enrichir cette catégorie : Bourne shell (sh) et ses variantes (csh, ksh, bash, tcsh, zsh...), Perl, Raku, Ruby, Lua, Tcl/Tk...
  • Les langages d'analyse statistique (statistical computing languages) : ils offrent des outils de traitement, d'analyse et de présentation graphique de grands ensembles de données. Exemples : R, SAS, SPSS, Statistica...
  • Les langages de calcul numérique (numerical computing languages) : d'un certain point de vue, ils sont une généralisation des précédents ; ce sont des outils de calculs complexes sur des données générales et de présentation graphique des résultats obtenus. Exemples : Gnu Octave, MATLAB, Mathematica, Scilab... Le langage APL (1966) était un précurseur de cette famille.
  • Les langages de calcul formel (computer algebra languages) : ces langages manipulent des valeurs qui sont des formules mathématiques, pas des valeurs numériques. Des exemples très connus sont Maple, Maxima, Reduce, Derive, MATHLAB (ne pas confondre avec l'autre)...
  • etc.

Pour illustrer ce qu'est un calcul formel, voici un exemple en Maxima. Si l'on écrit :

factor(x^2-3*x+2);

il répond (i.e. il évalue) : « (x-2)(x-1) ». Si l'on veut la dérivée première :

diff(x^2-3*x+2,x,1);

il répond : «2x-3».

Langages multi-paradigmes

Souvent les langages sont multi-paradigmes: ainsi Python est un langage impéritif, orienté-objet et permet une certaine programmation fonctionnelle. Si l'on regarde l'ébauche d'article Comparaison_des_langages_de_programmation_multi-paradigmes sur wikipedia, 10 paradigmes sont cités pour Python (le langage Julia en a plus de 17 !).