Crochets et S-expressions : comment les limites des perforatrices IBM ont façonné Lisp

La perforatrice IBM 026 utilisée par les étudiants du Massachusetts Institute of Technology à la fin des années 1950 ne disposait pas de touches pour les crochets sur son clavier standard. À l'automne 1958, le chercheur en informatique John McCarthy a confié à une équipe d'étudiants du MIT la réalisation de son concept initial pour un nouveau langage de programmation axé sur l'intelligence artificielle. McCarthy avait prévu que les programmeurs écrivent leur code au moyen de M-expressions, une notation algébrique de haut niveau s'appuyant sur des crochets. Cependant, la perforation de ces caractères absents exigeait des manœuvres particulièrement fastidieuses sur leur matériel, poussant l'équipe d'étudiants à abandonner totalement les M-expressions pour rédiger leurs programmes directement sous la forme de S-expressions entourées de parenthèses.

De la logique de Dartmouth aux listes algébriques

Selon Two Bit History, McCarthy a commencé à mûrir la conception d'un langage de traitement de listes lors du projet de recherche d'été de Dartmouth sur l'intelligence artificielle en 1956. Lors de cette conférence, les chercheurs Allen Newell et Herbert Simon ont présenté leur langage IPL (Information Processing Language), spécialement conçu pour manipuler des listes d'expressions symboliques afin de générer des preuves logiques. Bien que McCarthy ait immédiatement reconnu que les listes symboliques constituaient un support idéal pour modéliser la déduction automatisée, le style macro-assembleur d'IPL lui déplaisait. Newell et Simon s'étaient concentrés sur des instructions machine de bas niveau au détriment d'une notation mathématique. McCarthy cherchait quant à lui une alternative algébrique capable d'associer le traitement symbolique de listes à la lisibilité de haut niveau offerte par Fortran.

Programmes d'échecs et dérivation symbolique

La vision de McCarthy a mûri à travers des expérimentations informatiques pratiques menées entre 1956 et 1958. En 1957, alors qu'il développait en Fortran des routines pour un programme de jeu d'échecs, les structures de contrôle limitées du langage l'ont frustré, le poussant à inventer les expressions conditionnelles dites « vraies ». Contrairement aux instructions d'aiguillage de Fortran, la conditionnelle de McCarthy renvoyait une sous-expression spécifique à la suite d'un test, en n'évaluant strictement que la branche validée. Durant l'été 1958, en travaillant sur la conception d'un système capable de réaliser de la dérivation symbolique, McCarthy s'est aperçu que ses expressions conditionnelles simplifiaient considérablement les opérations récursives. Afin de traiter la dérivation sur des sommes comportant un nombre arbitraire de termes, il a introduit la fonction maplist, capable d'appliquer une fonction donnée à l'ensemble des éléments d'une liste. Fort de ces avancées, McCarthy a demandé à ses étudiants du MIT, à l'automne 1958, de concevoir la première implémentation pratique de Lisp.

Contraintes de perforatrice et S-expressions

McCarthy avait initialement conçu les S-expressions — des expressions symboliques délimitées par des parenthèses — comme une simple représentation interne destinée à la machine. Le code source destiné aux humains devait quant à lui reposer sur des M-expressions encadrées par des crochets. Les limites physiques de la perforatrice IBM 026 ont toutefois profondément redéfini ce choix syntaxique. Faute de touches dédiées aux crochets sur le clavier, l'équipe a pris le parti d'exprimer aussi bien les listes de données que les appels de fonctions au moyen de S-expressions entre parenthèses. Ce qui n'était à l'origine qu'un compromis syntaxique temporaire de bas niveau est ainsi devenu le trait fondamental de Lisp : une notation préfixée, des structures arborescentes homogènes entre parenthèses et une équivalence stricte entre la représentation du code et celle des données.

Formaliser le calcul en 1960

En 1960, McCarthy a publié son article fondateur, « Recursive Functions of Symbolic Expressions and Their Computation by Machine ». Au fil du travail de simplification mené avec ses étudiants lors du développement, McCarthy a pris conscience que Lisp s'était métamorphosé, passant d'un utilitaire logiciel à un système mathématique d'une grande concision. En définissant Lisp à partir d'un noyau restreint de règles primitives et de fonctions récursives, McCarthy a posé un formalisme axiomatique pour l'étude du calcul qui s'avérait plus élégant et plus épuré que les machines de Turing ou la théorie classique des fonctions récursives.

La syntaxe minimale et les fondations axiomatiques définies par McCarthy ont permis à Lisp d'imposer sa longévité : il demeure aujourd'hui le deuxième plus ancien langage de haut niveau encore en usage, seulement devancé par Fortran. Les contraintes matérielles des perforatrices des années 1950 ont ainsi forgé une structure unifiée et sobre qui fait toujours de Lisp une référence incontournable dans la théorie des langages de programmation.

Illustration éditoriale générée par IA ; ce n’est pas une photographie documentaire.

Source: 0b10 0b10 How Lisp Became God's Own Programming Language