Machine Lisp

Les machines Lisp sont des ordinateurs conçus pour interpréter Lisp efficacement et nativement. D'une certaine manière, elles furent les premières stations de travail mono-utilisateur commercialisées.

Malgré le faible nombre de machines Lisp (environ 7 000 unités en 1988^[1]), beaucoup de technologies communes de nos jours (telles qu'un ramasse-miettes efficace, l'impression laser, les interfaces fenêtrées, la souris, les images bitmap haute résolution, les moteurs de rendu et plusieurs innovations dans le domaine des réseaux) ont été développées en premier lieu sur des machines Lisp comme celles utilisées par le centre de recherche Xerox PARC.

Les programmes d'intelligence artificielle (IA) des années 1960 et 1970 nécessitaient des ordinateurs considérés à l'époque comme d'une très grande puissance (c'est-à-dire possédant un processeur rapide et beaucoup de mémoire). Ces besoins de puissance étaient accentués par le fait que les recherches américaines en IA étaient implémentées quasiment exclusivement avec le langage de programmation Lisp, alors que tout le matériel du commerce était conçu et optimisé pour les langages de type assembleur ou Fortran. Au début, le coût de telles machines était tel qu'elles devaient être partagées par plusieurs utilisateurs. Mais lorsque la technologie des circuits intégrés commença à réduire la taille et les coûts des ordinateurs (fin des années 1960), et lorsque les besoins de mémoire des programmes d'IA commencèrent à excéder l'espace d'adressage des ordinateurs les plus courants des centres de recherche (les DEC PDP-10), les chercheurs considérèrent une nouvelle approche : un ordinateur conçu spécialement pour écrire et exécuter des programmes d'IA imposants, et adapté à la sémantique du langage de programmation Lisp. Afin de garder un système d'exploitation (relativement) simple, ces machines ne devaient pas être partagées, mais dédiées à un unique utilisateur.

En 1973, Richard Greenblatt et Thomas Knight, programmeurs au laboratoire d'intelligence artificielle du Massachusetts Institute of Technology (MIT) ont initié le MIT Lisp Machine Project en construisant pour la première fois un ordinateur capable d'exécuter au niveau matériel, plutôt qu'au niveau logiciel, certaines opérations basiques de Lisp, dans une architecture 24 bits. La machine disposait aussi d'un ramasse-miettes incrémental (dit « Arena »). Par ailleurs, comme les variables Lisp sont typées à l'exécution et non à la compilation, une simple addition de deux variables pouvait prendre cinq fois plus de temps sur une machine conventionnelle, à cause des instructions de test et de branchement. Les machines Lisp effectuent ces tests parallèlement au calcul de l'addition car auparavant si les tests échouaient, le résultat de l'addition était abandonné et recalculé, ce qui pouvait multiplier le temps de calcul dans de nombreux cas. Cette approche de vérification simultanée est aussi utilisée pour tester les dépassements de tableaux et d'autres problèmes de gestion de la mémoire. La vérification des types a été par la suite encore améliorée lorsque le mot conventionnel de 32 bits a été étendu à 36 bits pour la I-Machine^[2], puis à 40 bits et plus (généralement, les bits supplémentaires ne sont pas comptés car ils sont utilisés comme codes correcteurs). Le premier groupe de bits en plus contient des données sur le type, et les suivants sont utilisés pour implémenter la programmation CDR (qui consiste à compresser les éléments des listes chaînées), aidant de façon non négligeable le ramasse-miettes. Une dernière amélioration fut l'ajout de deux instructions machine spécifiques aux fonctions Lisp, réduisant le coût d'un appel de fonction à seulement 20 cycles d'horloge (pour certaines implémentations de Symbolics).

La première machine fut appelée la machine CONS (en référence à l'opérateur de construction de liste cons en Lisp. On l'appelle aussi quelquefois la « machine Knight », peut-être parce que c'était le sujet de thèse de Knight). Elle a été enrichie de façon notable dans une seconde version appelée CADR (un jeu de mots, cadr est l'instruction permettant d'accéder au deuxième élément d'une liste en Lisp, elle se prononce « kay'-deur » ou « kah'-deur ») essentiellement basée sur la même architecture. Environ vingt-cinq prototypes de ces machines ont été vendues (au MIT et hors MIT) pour environ 50 000 $ ; elles devinrent rapidement les machines préférées des hackers, la plupart des principaux outils logiciels ont rapidement été portés sur ces machines (par exemple, Emacs a été porté en 1975). Elles ont reçu un tel succès lors de la conférence sur l'intelligence artificielle tenue au MIT en 1978 que DARPA accepta de financer leur développement.

En 1979, Russel Noftsker, convaincu que les machines Lisp sont vouées à un succès commercial grâce à la puissance du langage Lisp et à son efficacité une fois accéléré matériellement, fit une proposition à Greenblatt : commercialiser cette technologie. Allant à l'encontre de la philosophie des hackers du laboratoire d'IA, Greenblatt accepta, pensant pouvoir recréer l'ambiance informelle et productive de son laboratoire dans le monde des affaires, un peu à la manière d'Apple. Mais cette manière de penser était complètement différente de celle de Noftsker. Malgré leurs longues négociations, aucun n'accepta de compromis. Comme l'entreprise ne pouvait être un succès qu'avec le soutien complet de tous les hackers du laboratoire, Noftsker et Greenblatt estimèrent que le choix du destin de cette entreprise revenait à ces personnes, et les laissèrent donc décider.

Les discussions qui s'ensuivirent divisèrent le laboratoire en deux camps. En février 1979, un consensus se dégagea : les hackers étaient du côté de Noftsker, estimant qu'une entreprise sur un modèle conventionnel, à but lucratif et financée par des investisseurs^[évasif] avait plus de chances de survivre et de vendre des machines Lisp que la start-up autogérée proposée par Greenblatt. Greenblatt avait perdu la bataille.

Greenblatt était contrarié et inactif tandis que l'entreprise de Noftsker (appelée Symbolics) se formait petit à petit et payait les hackers, mais n'avait aucun local ou équipement à leur proposer au MIT ; il négocia donc avec Patrick Winston (directeur du labo d'IA) l'autorisation de laisser le personnel de Symbolics travailler hors du MIT en échange de la libre utilisation en interne des programmes développés par Symbolics. C'est alors qu'un consultant de CDC, qui était à la recherche d'une machine Lisp pour travailler sur un langage naturel de programmation, vint à la rencontre de Greenblat environ huit mois après la négociation désastreuse avec Noftsker sur la commercialisation des machines Lisp. Greenblatt qui avait décidé de lancer sa propre entreprise concurrente n'avait rien fait. Le consultant, Alexander Jacobson, fut convaincu que la seule façon pour Greenblatt de réellement lancer sa compagnie et de construire les machines qu'attendait désespérément Jacobson était qu'il le pousse et l'aide à prendre son départ. Jacobson mis en place un plan d'affaires, une direction, et un partenaire pour Greenblatt, nommé F. Stephen Wyle. La nouvelle entreprise fut créée sous le nom de LISP Machine, Inc. (LMI), et financée avec des actions de CDC, par l'intermédiaire de Jacobson.

À peu près au même moment, Symbolics, qui avait été gênée par la promesse de Noftsker de laisser Greenblatt diriger pendant la première année et par plusieurs retards importants du financement devint opérationnelle. Symbolics avait quand même le gros avantage d'avoir pris la part du lion : 14 des hackers du laboratoire d'IA avaient été recrutés contre seulement 3 ou 4 par LMI. Seules deux personnalités du AI Lab du MIT étaient restés à l'écart de ces entreprises : Richard Stallman et Marvin Minsky.

Après une série de disputes internes, Symbolics sortit de l'ombre en 1980 et 1981, vendant la CADR sous le nom de LM-2, tandis que Lisp Machines, Inc. la vendait sous le nom de LMI Lisp Machine. Symbolics n'avait pas l'intention de produire beaucoup de LM-2, car une seconde génération^[3] devait arriver sur le marché sous peu, mais était constamment retardée, si bien que Symbolics finit par produire environ 100 LM-2, chacune vendue au prix de 70 000 USD. Les deux entreprises développèrent des machines de deuxième génération basées sur la CADR : la L-Machine et le LMI Lambda (que LMI parvint à vendre à environ 200 exemplaires). La G-Machine^[4], mise en production une année en retard, étendait la CADR en passant le mot standard à 28 bits, en agrandissant l'espace d'adressage, et en ajoutant du matériel destiné à accélérer certaines fonctions courantes implémentées en microcode dans la CADR. La LMI Lambda, sortie un an avant la G-Machine (en 1983), était compatible avec la CADR (elle pouvait exécuter du microcode CADR), mais différait matériellement. Texas Instruments (TI) rejoignit la course en achetant le brevet du LMI Lambda et produisit sa propre version, le TI Explorer.

Symbolics continua à développer sa G-Machine^[5] et son système d'exploitation (Genera), et conçut the Ivory^[6], une implémentation VLSI de l'architecture Symbolics. À partir de 1987, plusieurs machines basées sur le processeur Ivory ont été développées : des cartes mères pour des Sun et des Mac, des stations de travail et même des systèmes embarqués. Texas Instruments miniaturisa l'Explorer pour donner le MicroExplorer. LMI abandonna l'architecture CADR et développa sa propre technologie, mais l'entreprise fit faillite avant que la machine eût pu être mise sur le marché.

Ces machines possédaient le matériel pour exécuter diverses instructions primitives du langage Lisp (vérification des types, programmation CDR), ainsi que pour effectuer de la récupération de mémoire incrémentale. Elles pouvaient exécuter des programmes Lisp volumineux de manière très efficace. Les machines Symbolics qui rivalisaient avec beaucoup de PC commerciaux, n'ont jamais été adaptées aux tâches conventionnelles de l'informatique. Cependant, elles ont néanmoins été vendues sur d'autres marchés que l'IA, tels que le graphisme, la modélisation et l'animation.

Les machines Lisp dérivées de celles du MIT interprétaient un dialecte Lisp appelé ZetaLisp, hérité de MacLisp, originaire lui aussi du MIT. Les systèmes d'exploitation étaient écrits en Lisp à partir de rien, souvent en utilisant des extensions orientées objet. Plus tard, ces machines supportèrent aussi des variantes de Common Lisp (telles que Flavors, New Flavors, et CLOS).

BBN développa aussi sa propre machine Lisp, appelée Jericho, qui utilisait une version d'Interlisp, qui n'a jamais été commercialisée. Frustrés, l'ensemble de l'équipe d'IA démissionna, et s'engagea auprès de Xerox principalement. Le Xerox PARC développa donc à son tour ses machines pour Interlisp (et Common Lisp par la suite) ainsi que pour d'autres langages tels que Smalltalk, mais ils ne parvinrent pas à pénétrer le marché et se retrouvèrent loin derrière LMI et Symbolics. Parmi ces machines, il y avait la Xerox 1100 (alias Dolphin, 1979) ; Xerox 1132 (alias Dorado) ; Xerox 1108 (alias Dandelion, 1981) ; Xerox 1109 (alias Dandetiger) ; et Xerox 6085 (alias Daybreak). Même si les machines de Xerox furent un échec commercial, elle influencèrent la création du Macintosh d'Apple. Le système d'exploitation des machines Lisp Xerox a aussi été porté en une machine virtuelle disponible pour plusieurs plates-formes et appelée Medley. Ces mêmes machines étaient aussi renommées pour leur environnement de développement évolué, leur interface graphique pionnière, et pour leurs applications innovantes telles que NoteCards (l'une des premières applications hypertexte).

Une entreprise britannique, Racal-Norsk, tenta d'utiliser son supermini Norsk Data comme machine Lisp en microprogrammant un interpréteur du langage ZetaLisp de Symbolics.

Il y eut aussi plusieurs tentatives des Japonais de rentrer sur le marché des machines Lisp, parmi lesquelles le coprocesseur Facom-alpha de Fujitsu (sorti en fait dès 1978), et plusieurs efforts de recherche universitaires ayant conduit à des prototypes faisant partie du projet Fifth generation computer (en).

Une machine Lisp a également été conçue en France entre 1977 et 1982 à l'université Paul-Sabatier de Toulouse par une équipe dirigée par Jean-Paul Sansonnet puis industrialisée et construite entre 1982 et 1986 par les laboratoires de Marcoussis (aspects logiciels) et le CNET de Lannion (aspects matériels). Il s'agissait de la machine MAIA, à base d'un processeur 40 bits (8 bits pour le type, 32 bits pour la donnée) et d'un compilateur Common Lisp complètement redéveloppé à Marcoussis.

Lorsqu'arriva l'hiver de l'IA (période au cours de laquelle l'intérêt pour l'intelligence artificielle retomba) et la révolution des PC (qui précipita les constructeurs de stations de travail et de superminis dans la faillite), les ordinateurs de bureau devinrent capables d'exécuter des programmes Lisp à moindre coût et plus vite que les machines Lisp, sans utiliser de matériel spécifique. Ne pouvant plus appliquer de marges importantes sur leur matériel, la plupart des constructeurs de machines Lisp cessèrent leurs activités au début des années 1990 ou devinrent des éditeurs de logiciels. Avec Xerox, Symbolics est le seul constructeur de machines Lisp à avoir survécu jusqu'à aujourd'hui, en vendant le système d'exploitation Lisp Open Genera et le logiciel de calcul formel Macsyma.

À la fin des années 1990, Sun Microsystems et d'autres entreprises projetèrent de construire des machines Java, de concept similaire aux machines Lisp.

• CADR, Thomas Knight, David A. Moon, Jack Holloway, Guy L. Steele. AI Lab memos, AIM-528, 1979.
• Design of LISP-based Processors, Guy Lewis Steele, Gerald Jay Sussman, AI Lab memo, AIM-514, 1979
• Lisp Machine manual, 6th ed. Richard Stallman, Daniel Weinreb, David Moon. 1984.
• Anatomy of a LISP Machine, Paul Graham, AI Expert, December 1988
• Master's Thesis de Thomas Knight

• CADR documentation
• "Lisp Machine Inc. K-machine: The Deffenbaugh, Marshall, Powell, Willison architecture as remembered by Joe Marshall"
• "My Lisp Experiences and the Development of GNU Emacs" - (a transcript of a speech Richard Stallman gave about Emacs, Lisp, and Lisp machines)
• LISPMACHINE.NET - Lisp Books and Information

• Portail de la programmation informatique