Les sept ur-langages de la programmation (2022)

• Les différences entre syntaxes individuelles comptent moins que celles entre ensembles de motifs fondamentaux ; les langages de programmation se divisent en sept ur-langages selon leurs modes d’itération, de récursion et de composition
• ALGOL, Lisp, ML, Self, Forth, APL et Prolog constituent la classification centrale, et chaque famille utilise un langage représentatif comme échantillon de référence pour situer les autres langages
• Il est facile d’apprendre un nouveau langage qui partage un ur-langage déjà familier, mais passer vers un archétype inconnu demande de nouvelles voies de pensée et un temps d’apprentissage conséquent
• ALGOL se caractérise par une organisation des fonctions centrée sur l’affectation, les conditionnelles et les boucles ; Lisp par les macros et le code sous forme de listes ; ML par les fonctions de première classe et la récursion ; Self par les objets à passage de messages ; Forth par une syntaxe fondée sur la pile ; APL par les tableaux n-dimensionnels ; et Prolog par une structure de faits et de recherche
• Pour tous les programmeurs, la priorité est de bien maîtriser un langage de la famille ALGOL, puis d’apprendre SQL, avant de continuer ensuite à explorer régulièrement des ur-langages moins familiers, une approche plus avantageuse à long terme

---

Les sept ur-langages de la programmation

• Lorsqu’on choisit un langage de programmation, il est plus important d’acquérir les motifs fondamentaux que de s’attarder sur les différences de syntaxe individuelles ; entre langages d’une même famille, les structures de base comme le parcours de tableaux ou l’itération combinatoire ont presque la même forme
• Les différentes familles de langages diffèrent fortement par leurs modes d’itération, de récursion et d’organisation des programmes, et ces ensembles de motifs fondamentaux constituent des ur-langages distincts
• Apprendre un nouveau langage qui partage un ur-langage déjà connu est une transition relativement facile, mais passer vers un ur-langage inconnu demande beaucoup de temps et de nouvelles voies de pensée
• Dans l’ingénierie logicielle, on reconnaît sept ur-langages : ALGOL, Lisp, ML, Self, Forth, APL et Prolog
• Chaque ur-langage est classé à partir d’un langage représentatif servant d’échantillon de référence, et les autres langages sont situés en comparant leur lignée à cet étalon

• ALGOL

  • Un programme est organisé comme une suite d’affectations, de conditionnelles et de boucles, structurée en fonctions
  • De nombreux langages y ajoutent des systèmes de modules, des mécanismes de définition de nouveaux types de données, du polymorphisme, ou encore des structures de contrôle alternatives comme les exceptions ou les coroutines
  • La plupart des langages de programmation largement utilisés aujourd’hui appartiennent à la lignée de cet ur-langage
  • ALGOL lui-même comprend ALGOL 58, ALGOL 60, ALGOL W et ALGOL 68
  • Assembly language, Fortran, C, C++, Python, Java, C#, Ruby, Pascal, JavaScript et Ada se rattachent à cette lignée
  • C’est le plus ancien des ur-langages, avec une généalogie qui remonte jusqu’à la formalisation par Ada Lovelace de programmes pour la machine analytique de Babbage
  • Le langage machine et l’assembleur des ordinateurs de l’architecture Eckert-Mauchly, d’EDVAC aux premiers Univac, ainsi que les premières tentatives de langages de haut niveau, de l’A-0 de Grace Hopper à Fortran et COBOL, relèvent tous de cette forme
  • Dans les années 1960, le monde académique a fait progresser la programmation structurée pour rendre ces langages plus gérables ; le résultat en a été ALGOL 60, dont dérivent ensuite la plupart des membres de cette famille
  • Avec le temps, cette famille a eu tendance à absorber des fonctionnalités d’autres ur-langages
    • Dans les années 1980, des concepts de la famille Self ont été intégrés sous forme de classes, comme moyen de définir des types de données et d’implémenter le polymorphisme
    • Depuis 2010, des concepts de la famille ML ont également fait leur apparition

• Lisp

  • Une syntaxe combinant expressions préfixées parenthésées et représentation en listes
    • (+ 2 3)
    • (defun square (x) (* x x))
    • (* (square 3) 3)
  • La représentation en listes, où des éléments séparés par des espaces sont entourés de parenthèses, est intégrée au langage, si bien que le code lui-même prend la forme d’une liste
  • Les macros peuvent recevoir une liste, la modifier, puis transmettre le code modifié au compilateur, ce qui donne aux programmeurs une structure permettant de redéfinir la sémantique du langage
  • Dans la plupart des usages, le code tend à fonctionner comme dans d’autres ur-langages, généralement ALGOL ou ML, mais le système de macros est l’élément distinctif
  • La syntaxe loop de Common Lisp n’est pas une fonctionnalité intégrée au langage, mais une forme définie par macro
  • Il y a eu beaucoup de variantes de Lisp au début, mais la communauté a fini par converger vers Common Lisp
  • Sussman et Steele ont exploré jusqu’où l’on pouvait aller avec les fonctions, et ont créé Scheme
  • On trouve aussi des Lisp spécialisés comme Lush pour le calcul numérique, AutoLISP comme langage de script d’AutoCAD, ou Emacs Lisp pour implémenter le comportement de l’éditeur Emacs
  • Plus récemment, Clojure s’est imposé comme une troisième grande branche de la famille Lisp
  • Apparue environ un an après Fortran, c’est la deuxième plus ancienne famille de langages encore utilisée aujourd’hui
  • Son point de départ était une question mathématique : comment noter une structure mathématique capable d’évaluer ses propres expressions
  • John McCarthy a proposé une réponse en 1958, qui a ensuite été implémentée sur ordinateur
  • Les premières versions de Lisp, à cause de leur arrière-plan mathématique, s’accordaient mal avec les machines de l’époque ; les questions de mémoire et de cycles CPU n’existaient pas en mathématiques, ce qui a rendu nécessaires des techniques comme le garbage collection
  • À la fin des années 1970 et au début des années 1980, il existait des machines conçues de fond en comble uniquement pour exécuter Lisp
  • Une grande partie des éléments des environnements de développement intégrés actuels y ont été inventés
  • À la même époque, Lisp était l’outil principal de la recherche en intelligence artificielle, et lorsque l’emballement pour l’IA des années 1980 n’a pas produit les résultats attendus, Lisp a chuté avec le domaine lors de l’AI Winter
  • Il a néanmoins survécu, et l’augmentation des performances des ordinateurs ainsi que l’adoption de ses fonctionnalités par d’autres langages ont réduit les difficultés d’implémentation

• ML

  • Les fonctions y sont des valeurs de première classe, avec un système de types de la famille Hindley-Milner permettant d’exprimer des fonctions variées et des unions taguées
  • Toute itération y prend la forme de récursion
    • sum [] = 0
    • sum (x:xs) = x + sum xs
  • On utilise aussi des fonctions qui encapsulent des motifs d’itération et implémentent un comportement en recevant d’autres fonctions
    • map _ [] = []
    • map f (x:xs) = (f x) : (map f xs)
  • Certains langages, comme Miranda et Haskell, utilisent par défaut l’évaluation paresseuse
  • D’autres étendent le système de types dans plusieurs directions
    • OCaml tente une combinaison avec des concepts de l’ur-langage Self
    • Agda et Idris adoptent des systèmes de types dépendants mêlant valeurs et types
    • 1ML combine modules et types
  • ML a donné naissance à CaML, Standard ML et OCaml
  • Des familles apparentées comme Miranda, Haskell, Agda et Idris s’y rattachent également
  • ML était à l’origine le métalangage d’un programme de démonstration de théorèmes développé à Cambridge, au Royaume-Uni, et c’est de là que vient son nom
  • Il s’est ensuite diffusé comme langage autonome hors de ce contexte, gagnant en popularité en Europe, surtout au Royaume-Uni et en France

• Self

  • Un programme est composé d’un ensemble d’objets qui s’échangent des messages, et tout le comportement est implémenté de cette manière
  • Les nouveaux objets sont créés en envoyant des messages à des objets existants
  • Même les conditionnelles fonctionnent via une variable qui référence soit l’objet true, soit l’objet false
    • Ces deux objets reçoivent un message prenant comme paramètres une fonction à exécuter si c’est vrai et une fonction à exécuter si c’est faux
    • L’objet true exécute la première fonction, l’objet false exécute la seconde
    • Le code appelant ne sait pas de quel objet il s’agit ; il se contente d’envoyer un message
  • Les boucles fonctionnent de la même manière, et en fabriquant les bons objets puis en les insérant au bon endroit, il est possible de redéfinir entièrement la sémantique du langage
  • Dans ces langages, le code source est généralement stocké non pas dans des fichiers texte mais dans un environnement live
  • Le programmeur modifie le système live et en enregistre l’état, au lieu de compiler des fichiers pour construire un système
  • Les exemples importants sont Smalltalk et Self
  • De nombreux langages n’empruntent qu’une partie du modèle d’échange de messages de cette famille, et cette adoption partielle est généralement ce qu’on appelle la programmation orientée objet
  • La plupart d’entre eux dérivent de Smalltalk, à l’exception de JavaScript, qui vient du système d’objets sans classes de Self
  • Le système objet de Common Lisp généralise ce modèle : au lieu qu’un seul objet reçoive un message, le runtime choisit le code à exécuter en fonction de tous les paramètres
  • Erlang, lui, déplace l’idée vers des threads d’exécution parallèles qui écoutent et envoient explicitement des messages, plutôt que de faire circuler le flux d’exécution d’objet en objet
  • Le langage d’origine est Smalltalk, développé à Xerox Parc à la fin des années 1970 et dans les années 1980
  • Dans les années 1980, il existait plusieurs systèmes Smalltalk commerciaux, et IBM a utilisé Smalltalk pour développer la collection d’outils de programmation VisualAge pour d’autres langages
  • Aujourd’hui, Smalltalk survit principalement sous la forme open source de Pharo Smalltalk
  • Beaucoup de recherches ont été menées pour exécuter Smalltalk rapidement et efficacement, avec comme point culminant le projet Strongtalk
  • Les découvertes de Strongtalk ont une importance historique, car elles ont servi de base au compilateur JIT HotSpot de Java
  • Smalltalk a repris des concepts de valeur et de type issus de langages antérieurs pour implémenter les classes ; chaque objet possédait une classe qui lui attribuait son type, et la classe créait les objets de ce type
  • Self a supprimé la notion de classe pour ne conserver que les objets
  • C’est pourquoi Self est choisi comme échantillon représentatif de cet ur-langage, en raison de sa forme plus pure

• Forth

  • Les langages à pile sont en quelque sorte l’image miroir de Lisp, et partagent une syntaxe avec les calculatrices Hewlett Packard en notation polonaise inversée
  • Ils disposent d’une pile de données ; quand on écrit un littéral comme 42, il est empilé, et les noms de fonctions opèrent sur la pile sans paramètres explicites
  • Même l’arithmétique simple prend une forme inversée, comme 2 3 + 5 *
  • La définition de fonctions y est également très concise
    • Dans la plupart des variantes de Forth, : définit un nouveau mot
    • square signifie alors appeler dup puis *
    • dup duplique l’élément au sommet de la pile, * multiplie les deux éléments du sommet
  • Il est possible d’intercepter le parseur et de le remplacer par son propre code, ce qui permet de remplacer toute la syntaxe
  • Il est courant de voir des programmes Forth définir de petits langages, par exemple pour analyser directement un sous-ensemble de Fortran, une disposition de paquets, ou des diagrammes ASCII représentant les transitions d’une machine à états
  • On y trouve les différentes variantes de Forth, ainsi que PostScript, Factor et Joy
  • Joy est un langage purement fonctionnel qui utilise non pas une pile, mais une formalisation mathématique de la composition
  • Forth a été écrit pour la première fois en 1970 pour le contrôle de radiotélescopes
  • Il s’est ensuite largement diffusé dans l’univers des systèmes embarqués
  • Les systèmes Forth sont suffisamment faciles à amorcer qu’il existe des dizaines de variantes créées individuellement par des programmeurs pour leurs propres besoins
  • PostScript est apparu dans les années 1980 comme un moyen souple de décrire des documents sur les imprimantes
  • PostScript est à bien des égards plus contraint que Forth, mais définit dans le langage des opérations de base liées à la mise en page graphique

• APL

  • Tout dans ce langage est un tableau n-dimensionnel
  • Les opérateurs sont composés d’un ou deux symboles et effectuent des opérations de haut niveau sur des tableaux entiers
  • L’expression y est extrêmement compacte, au point qu’une suite de symboles elle-même sert de marqueur d’opération sans avoir besoin d’autres noms
  • Par exemple, le calcul de la moyenne de la variable x s’écrit (+⌿÷≢) x
  • APL, J et K en sont les principaux exemples
  • Les opérations d’ordre supérieur sur les tableaux ont été en partie exportées vers de nombreux environnements comme MATLAB, NumPy et R
  • APL est né dans les années 1960 comme une notation mathématique créée par Kenneth Iverson, puis a été implémenté sur ordinateur
  • Il a depuis conservé un soutien de niche parmi les personnes qui effectuent des calculs lourds
  • Son langage descendant K a été particulièrement populaire dans les environnements financiers

• Prolog

  • Un programme est constitué d’un ensemble de faits
    • father(bob, ed).
    • father(bob, jane).
  • Il utilise aussi des faits non ancrés qui permettent de déduire d’autres faits à l’aide de variables
    • grandfather(X, Y) :- father(X, Z), father(Z, Y).
  • Le runtime de Prolog prend ces faits et des requêtes, puis effectue une recherche pour trouver des résultats
  • Si l’on choisit correctement la structure des définitions de faits, on obtient la complétude de Turing
  • Dans Prolog, les termes qui composent les faits sont eux-mêmes un type de données distinct, que l’on peut construire puis transmettre au runtime
  • En cela, il occupe une place comparable aux macros de Lisp ou au remplacement du parseur en Forth
  • Un programme Prolog étant essentiellement une recherche, son optimisation se concentre sur l’ajustement de l’ordre de recherche et l’élimination précoce des chemins sans issue, comme dans les requêtes de base de données
  • Il comprend Prolog, Mercury et Kanren
  • Dans cette famille d’ur-langages, la majorité de la programmation réelle se fait directement en Prolog, et la communauté est très unifiée
  • Dans les années 1970, des logiciens français ont compris que l’on pouvait exprimer des programmes en logique du premier ordre, et ont commencé à essayer de les implémenter
  • Dans les années 1980, le projet japonais d’ordinateurs de cinquième génération a beaucoup misé sur Prolog, mais l’échec du projet a aussi terni sa réputation
  • Indépendamment de cela, les recherches se sont poursuivies pendant des décennies pour rendre le runtime Prolog efficace dans la plupart des cas et pour lui ajouter de nouvelles fonctionnalités
  • L’ajout de fonctions comme les contraintes numériques a conduit à la programmation logique par contraintes
  • Prolog continue d’apparaître dans des domaines de niche
    • La vérification de types de Java a été implémentée en Prolog pendant plusieurs années
    • Le premier outil de recherche dans le code source de Facebook reposait lui aussi sur Prolog

Comment l’utiliser

• Pour la plupart des programmeurs, une partie ou l’ensemble de ces familles peut paraître très étrangère, mais chacune mérite qu’on y consacre du temps pour les voies de pensée et les nouvelles possibilités qu’elle ouvre
• Il est très fréquent que deux choses paraissent totalement différentes depuis la perspective d’ALGOL, alors qu’elles ne sont qu’une comparaison triviale vues depuis une autre perspective

• Priorités

  • Tous les programmeurs devraient bien connaître un langage de la famille ALGOL
  • Ensuite, il est recommandé d’apprendre SQL, un langage de la famille Prolog
    • C’est probablement ce qui apporte, dans une carrière, le plus grand bénéfice après ALGOL

• Extension ensuite

  • Une fois ces deux familles maîtrisées, il est avantageux à long terme d’apprendre chaque année un nouveau langage appartenant à une famille d’ur-langages encore inconnue
  • Les langages proposés dans chaque famille, ainsi que leur ordre, sont les suivants
    • Lisp : PLT Racket
    • ML : Haskell
    • Self : Self
    • Prolog : Prolog
    • Forth : gForth
    • APL : K, via ok

• Ajuster l’ordre

  • Si vous faites beaucoup de calcul numérique, il peut être pertinent d’apprendre K plus tôt
  • Si vous faites beaucoup de programmation embarquée, il peut être pertinent d’apprendre gForth plus tôt
  • Cela dit, l’ordre lui-même, ou même le choix exact du langage, n’a pas tant d’importance
  • On peut tout aussi bien apprendre Standard ML ou OCaml à la place de Haskell, Common Lisp à la place de PLT Racket, ou Factor à la place de gForth

• Compléments inclus dans les notes

  • Même après avoir appris SQL, il reste nécessaire d’apprendre Prolog lui-même
    • Car son usage réel diffère considérablement de celui de SQL
  • Un avis de lecteur indique que, pour comprendre Forth en profondeur, une approche courante consiste à implémenter soi-même un interpréteur Forth
    • Forth est mentionné comme étant suffisamment petit pour qu’une seule personne puisse l’implémenter depuis zéro en relativement peu de temps
    • gForth est une bonne implémentation pour apprendre ANS Forth
    • Comme ressource d’apprentissage, le texte FORTH Fundamentals, Volume 1 de McCabe est mentionné
    • Parmi les autres Forth à examiner figurent PygmyForth, eForth et colorForth