Lisp

En 1956, le projet Lisp émerge dans le cadre des recherches estivales de Dartmouth sur l'intelligence artificielle. John McCarthy cherche alors un langage algébrique pour traiter des listes sur l'IBM 704. Il s'intéresse aux travaux de Newell, Shaw et Simon sur IPL 2, un langage conçu pour le JOHNNIAC de la RAND Corporation, mais refuse d'en reproduire la forme trop dépendante de son environnement d'origine. L'approche algébrique du Fortran l'attire davantage.

Deux circonstances favorisent ce développement : la création d'un centre de calcul IBM au MIT, accessible depuis Dartmouth, et le lancement par IBM d'un programme de démonstration de théorèmes géométriques basé sur une idée de Marvin Minsky, pour lequel McCarthy travaille en tant que consultant. IBM semble s'engager vers la recherche naissante en IA.

En 1958, McCarthy propose le concept d'Advice Taker, un système devant représenter les informations par des phrases dans un langage formel et prendre des décisions par déductions logiques. La représentation des phrases par structures de listes s'impose naturellement, tout comme l'usage d'un langage de traitement de listes pour programmer les opérations déductives.

Le premier défi technique concerne la mise en œuvre des structures de listes sur l'IBM 704. Cet ordinateur utilise des mots de 36 bits, avec deux sections de 15 bits nommées adresse et décrément. L'adressage limité à 15 bits rend nécessaire l'utilisation de pointeurs de taille identique pour les structures de listes. McCarthy établit initialement des fonctions dont cwr (Contents of Word in Register) et quatre fonctions d'extraction. Il note que l'extraction d'une sous-expression exige la composition de l'extraction de l'adresse avec cwr, tandis que la progression dans la liste demande la composition de l'extraction du décrément avec cwr. Ces observations donnent naissance aux fonctions car (Contents of Address Register) et cdr, qui deviendront emblématiques du langage.

Durant les années 1957 et 1958, McCarthy conçoit les expressions conditionnelles en programmant des routines d'échecs en Fortran. Les limites de l'instruction IF de Fortran le conduisent à créer une fonction XIF(M,N1,N2) retournant N1 ou N2 selon la nullité de M. Cette solution simplifie les programmes mais souffre de l'évaluation systématique des trois arguments. Il invente l'expression conditionnelle authentique, n'évaluant que les expressions nécessaires.

À l'été 1958, invité par Nathaniel Rochester chez IBM, McCarthy travaille sur la différentiation d'expressions algébriques. Ce travail introduit plusieurs avancées : l'écriture de fonctions récursives utilisant des expressions conditionnelles, la fonction maplist formant une liste d'applications d'un argument fonctionnel aux éléments d'une liste, et l'usage de la notation λ de Church pour nommer les fonctions. Sa définition récursive de la différentiation ne prévoit pas l'effacement des structures abandonnées, car il refuse d'altérer l'élégance de sa définition.

À l'automne 1958, McCarthy évolue en tant que professeur assistant en sciences de la communication au MIT et lance avec Minsky le projet d'intelligence artificielle du MIT. Le développement de Lisp démarre avec l'objectif initial de créer un compilateur. L'équipe commence par compiler manuellement diverses fonctions en assembleur et écrire des sous-programmes d'environnement Lisp pour lire et écrire les structures de listes.

Les programmes s'écrivent d'abord dans une notation informelle appelée M-expressions, conçue pour ressembler au Fortran. Cette notation utilise des crochets pour les arguments des fonctions, réservant les parenthèses aux constantes de structure de liste. La notation M ne sera jamais complètement formalisée, car la représentation des fonctions Lisp par des listes s'impose comme approche dominante après l'apparition de l'interpréteur.

Les fonctions READ et PRINT établissent une notation externe standard pour l'information symbolique. Par exemple, l'expression x + 3y + z devient PLUS X (TIMES 3 Y) Z. Cette notation sera nommée Cambridge Polish, en référence à la notation préfixée de Lukasiewicz et à son usage antérieur par Quine.

La gestion mémoire soulève un problème particulier. L'effacement explicite, utilisé dans IPL, manque d'élégance. Deux options se présentent : effacer l'ancien contenu d'une variable lors de sa mise à jour, ce qui nécessite des compteurs de références impossibles à intégrer dans les six bits disponibles, ou utiliser le ramasse-miettes, qui abandonne le stockage jusqu'à épuisement de la liste libre, marque le stockage accessible depuis les variables et la pile, puis transforme le stockage non marqué en nouvelle liste libre.

Les versions suivantes de Lisp apportent diverses fonctionnalités : listes de propriétés associées aux atomes, insertion et suppression d'éléments dans les listes (via rplaca et rplacd), application efficace des nombres comme atomes, et le program feature pour écrire des programmes séquentiels avec instructions d'affectation et sauts.

Deux raisons expliquent la longévité de Lisp. D'une part, son noyau occupe une forme d'optimum local dans l'espace des langages de programmation, avec l'utilisation récursive des expressions conditionnelles, la représentation de l'information symbolique par listes, et la représentation uniforme des programmes et données. D'autre part, Lisp offre des caractéristiques opérationnelles uniques qui en font un véhicule privilégié pour les systèmes de calcul symbolique et d'intelligence artificielle : son système d'exécution donnant accès aux fonctionnalités de la machine hôte, sa représentation interne facilitant la compilation depuis des langages de plus haut niveau, et la disponibilité de son interpréteur comme langage de commande.