# Qu’est-ce que Lisp, et pourquoi John McCarthy l’a-t-il créé pour l’intelligence artificielle?

Date: 2019-03-11 · Author: Robert Scales · https://guidetoartificialintelligence.com/fr/apprendre/qu-est-ce-que-lisp/

**Answer:** Lisp, abréviation de « list processor » (processeur de listes), est un langage de programmation que John McCarthy a conçu en 1958 pour que les ordinateurs puissent manipuler des symboles, comme des mots et des énoncés logiques, et pas seulement des nombres. Créé au MIT pour l’IBM 704 et décrit dans un article de 1960, il a introduit des idées comme la récursivité avec expressions conditionnelles et le nettoyage automatique de la mémoire, et il est devenu le principal langage de la recherche en IA pendant des décennies.

Les premiers ordinateurs étaient construits pour calculer. Leurs langages, comme FORTRAN, étaient doués pour l’arithmétique sur des nombres rangés dans des tableaux bien ordonnés. Mais les premiers chercheurs en IA voulaient des machines capables de manier des idées : des énoncés logiques, des mots, des positions aux échecs, des formules algébriques. Ces choses ont toutes sortes de formes et de tailles, et elles s’emboîtent les unes dans les autres.

John McCarthy, le mathématicien qui avait forgé l’expression « intelligence artificielle », a décidé que l’IA avait besoin de son propre langage. Le résultat a été Lisp, qui s’est révélé l’un des langages de programmation les plus influents jamais conçus. C’est le deuxième plus ancien langage de haut niveau encore largement utilisé; seul FORTRAN est plus vieux, d’un an.

## Comment Lisp est né

McCarthy faisait remonter l’idée à l’été 1956, à l’atelier de Dartmouth sur l’intelligence artificielle. Allen Newell, Cliff Shaw et Herbert Simon y ont décrit l’IPL, le langage de traitement de listes qu’ils avaient créé pour leur Logic Theorist sur l’ordinateur JOHNNIAC de la RAND. McCarthy aimait l’idée de stocker l’information sous forme de listes, mais voulait quelque chose qui se lise davantage comme de l’algèbre, à la manière de FORTRAN.

Plusieurs morceaux se sont assemblés au cours des deux années suivantes. En travaillant sur des programmes d’échecs en FORTRAN au MIT en 1957-1958, McCarthy a inventé l’*expression conditionnelle*, une façon d’écrire « si ceci, alors cette valeur, sinon cette autre valeur » à l’intérieur d’une formule. À l’été 1958, au département Information Research d’IBM, il a choisi comme cas d’essai la dérivation d’expressions algébriques (l’opération de calcul différentiel qui consiste à trouver un taux de variation). Cet exercice l’a convaincu qu’il lui fallait des fonctions récursives, des fonctions auxquelles on peut passer d’autres fonctions, et la notation « lambda » pour nommer les fonctions, qu’il a empruntée au logicien Alonzo Church.

L’outil de traitement de listes qu’IBM avait déjà ne pouvait pas faire ces choses, et les ajouter à FORTRAN semblait peu pratique. Ainsi, à l’automne 1958, quand McCarthy est passé au MIT et a lancé l’Artificial Intelligence Project avec Marvin Minsky, l’équipe a commencé à construire un nouveau langage pour l’IBM 704.

## Comment fonctionne Lisp

Lisp n’a qu’un type de données de base, l’*expression symbolique*, ou S-expression. Une S-expression est soit un atome, un symbole unique comme `CAT` ou `X`, soit une liste d’autres S-expressions entre parenthèses. Comme les listes peuvent contenir des listes, Lisp peut représenter tout ce qui a une structure imbriquée. Les notes de McCarthy donnent la formule x + 3y + z ainsi :

```
(PLUS X (TIMES 3 Y) Z)
```

Une poignée d’opérations de base permettent de démonter les listes et de les construire. Leurs noms étranges viennent de parties d’un mot de la mémoire de l’IBM 704 :

| Opération | Ce qu’elle fait | Exemple | Résultat |
|---|---|---|---|
| `car` | Donne le premier élément d’une liste | `(car '(CAT DOG BIRD))` | `CAT` |
| `cdr` | Donne le reste de la liste | `(cdr '(CAT DOG BIRD))` | `(DOG BIRD)` |
| `cons` | Place un élément au début d’une liste | `(cons 'FISH '(DOG BIRD))` | `(FISH DOG BIRD)` |
| `atom` | Demande si quelque chose est un symbole unique | `(atom 'CAT)` | vrai |

Avec ces pièces et les expressions conditionnelles, on peut écrire des fonctions *récursives*, qui résolvent un problème en s’appelant elles-mêmes sur un plus petit morceau de celui-ci. Voici une fonction, dans un dialecte Lisp moderne, qui compte les éléments d’une liste :

```
(defun count-items (lst)
  (cond ((null lst) 0)
        (t (+ 1 (count-items (cdr lst))))))
```

Elle se lit ainsi : si la liste est vide, la réponse est 0; sinon, c’est 1 plus le nombre d’éléments du reste de la liste.

> **À essayer :** calculez `(count-items '(A B C))` à la main. Écrivez chaque appel sur sa propre ligne, `(A B C)`, puis `(B C)`, puis `(C)`, puis `()`, et additionnez les 1 en remontant. Vous venez de suivre la récursivité comme le fait Lisp.

## Des surprises en chemin

L’histoire de Lisp compte quelques heureux hasards. Pour montrer que Lisp pouvait décrire n’importe quel calcul aussi élégamment qu’une machine de Turing, McCarthy a écrit une fonction appelée `eval`, qui prend une expression Lisp et calcule sa valeur. Il la voyait comme un élément de théorie. Un programmeur du projet, Steve Russell, a compris qu’`eval` pouvait servir d’interpréteur fonctionnel, l’a codée à la main pour l’IBM 704, et du jour au lendemain, Lisp a pu exécuter des programmes directement.

Cette astuce reposait sur une autre idée : les programmes Lisp sont eux-mêmes écrits sous forme de listes, si bien qu’un programme Lisp peut lire, construire et modifier d’autres programmes Lisp. L’équipe a aussi décidé de ne pas obliger les programmeurs à libérer la mémoire à la main. Lisp allait plutôt repérer périodiquement les données qui ne servaient plus et récupérer leur espace, une technique appelée *ramasse-miettes* (*garbage collection*) sur laquelle s’appuient aujourd’hui la plupart des langages modernes.

McCarthy a publié la conception en avril 1960 dans *Communications of the ACM*, sous le titre « Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I ». Il y expliquait que Lisp était destiné à des expériences avec l’Advice Taker, un programme proposé qui pourrait accepter des énoncés sur le monde et en tirer des raisonnements avec du gros bon sens. Le premier compilateur Lisp complet écrit en Lisp a suivi en 1962; deux chercheurs du MIT, Tim Hart et Mike Levin, l’ont écrit.

## Pourquoi il a compté

Lisp est rapidement devenu le langage préféré de la recherche en IA. Ses listes convenaient à l’approche symbolique qui dominait le domaine : les démonstrateurs de théorèmes, les planificateurs et les programmes de traitement du langage manipulent tous des symboles structurés. Bien des idées dont il a été le pionnier, dont la récursivité, les fonctions traitées comme des valeurs, la gestion automatique de la mémoire et la boucle interactive où l’on tape une expression et voit aussitôt sa valeur, se sont répandues dans des langages bien au-delà de l’IA.

## Lisp sert-il encore en IA aujourd’hui?

Lisp n’est plus le principal langage de l’IA. Au début de 2019, la plupart des travaux en apprentissage automatique se font en Python, avec des bibliothèques comme TensorFlow et PyTorch qui confient les gros calculs numériques à du matériel rapide. L’apprentissage profond consiste surtout à multiplier de grands tableaux de nombres, le genre de tâche pour laquelle Lisp n’a jamais été conçu.

Lisp lui-même est toutefois bien vivant, sous plusieurs dialectes. Common Lisp a une norme ANSI officielle depuis 1994. Scheme reste un dialecte compact bien connu. Clojure, un Lisp pratique et polyvalent, tourne surtout sur la machine virtuelle Java. L’éditeur de texte Emacs se prolonge avec son propre dialecte, Emacs Lisp.

Son influence plus profonde est partout. Quand une personne qui programme en Python écrit une courte fonction anonyme avec `lambda`, passe une fonction à une autre ou ne pense jamais à libérer la mémoire, elle utilise des idées que Lisp a rendues pratiques. Si vous voulez comprendre comment les premiers chercheurs en IA concevaient les symboles et le raisonnement, écrire quelques petites fonctions Lisp reste l’une des meilleures façons d’apprendre.

## Sources

- Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I: http://www-formal.stanford.edu/jmc/recursive.pdf
- History of Lisp: http://www-formal.stanford.edu/jmc/history/lisp/lisp.html
- Lisp (programming language): https://web.archive.org/web/20190201171919/https://en.wikipedia.org/wiki/Lisp_(programming_language)