Machine Lisp

Une machine Lisp au Musée du MIT.

Les machines Lisp sont des ordinateurs conçus (grâce à leur matériel particulier) 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.

Histoire

Contexte

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.

Premiers développements

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 5 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 mot, 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 25 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.

La séparation

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 du business, un peu à la manière de Apple. Mais cette manière de penser était complètement différente de celle de Noftsker. Malgré leur 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 fondée sur les principes du business^[é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.

C'est à ce moment, Greenblatt étant contrarié et inactif alors que l'entreprise de Noftsker (appelée Symbolics) se formait petit à petit (bien qu'il payait les hackers, il 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), qu'un consultant de CDC vint à la rencontre de Greenblatt. Il était à la recherche d'une machine Lisp pour travailler sur un langage naturel de programmation, environ huit mois après la conférence désastreuse avec Noftsker sur la commercialisation des machines Lisp. Greenblat avait décidé de lancer sa propre entreprise concurrente, mais n'avait rien fait. Le consultant, Alexander Jacobson, décida que la seule façon pour Greenblatt de réellement lancer sa compagnie et construire les machines qu'attendait désespérément Jacobson était qu'il le pousse et l'aide à prendre son départ. Jacobson rassembla des Business plans, une direction, et un partenaire pour Greenblatt (un certain F. Stephen Wyle). La nouvelle entreprise fut nommée 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 commença à opérer (l'entreprise 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 de l'entreprise). Symbolics avait quand même le gros avantage d'avoir pris la part du lion : 14 des hackers du laboratoire d'IA ont signé pour y travailler contre seulement 3 ou 4 pour Greenblatt. Seules deux personnes du MIT ne furent pas engagées dans ces entreprises : Richard Stallman et Marvin Minsky.

Après une série de disputes internes, Symbolics sortit de l'ombre en 1980/1981, vendant le CADR sous le nom de LM-2, tandis que Lisp Machines, Inc. le 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 le 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 le 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 le CADR. Le LMI-LAMBDA, sorti un an avant la G-Machine (en 1983), était compatible avec le CADR (il 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 puisse ê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 rivalisaient même avec beaucoup de PC commerciaux, mais n'ont jamais été adaptées aux tâches conventionnelles de l'informatique. Cependant, elles ont aussi é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'exploitations é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).

Autres machines historiques

BBN développa aussi sa propre machine Lisp, appelée Jericho, qui utilisait une version de Interlisp. Elle n'a jamais été commercialisée. Frustrés, l'ensemble de l'équipe d'IA démissionna, et signa 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 de 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 systems.

Une machine Lisp a également été étudiée en France entre 1977 et 1982 à l'Université Paul-Sabatier de Toulouse (voir [1]) 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 (voir [2]), à 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'AI Winter (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 encore 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 ont cessé leurs activités au début des années 1990 ou sont devenus des éditeurs de logiciels. Avec Xerox, Symbolics est le seul constructeur de machines Lisp ayant 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.

Notes et références

• 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

Liens externes

Français

• Thèse sur les machines libres, Augustin Lux
• projet M3L, Jean-Paul Sansonnet

Anglais

• CADR documentation
• "The Lisp Machine manual"
• "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)
• "If It Works, It's Not AI: A Commercial Look at Artificial Intelligence startups"
• "Symbolics, Inc.: A failure of Heterogenous engineering" - (PDF)
• Symbolics Documentation
• Symbolics Original Patent Document with source
• CADR LISP Machine source code released by MIT (Oct 3 2005)
• The Explorer III Project - (A project to "develop a portable software emulator of the TI Explorer II Lisp machine.")
• Jaap Weel's Lisp Machine Webpage - (A collection of links and locally stored documents appertaining to all manner of Lisp machines)
• "A Few Things I Know About LISP Machines" - (Another collection of links, but mostly a discussion of purchasing Lisp machines)
• Ralf Möller's Symbolics Lisp Machine Museum
  • A page of screenshots of Genera
• Rainer Joswig's web page with Lisp Machine videos and screen shots
  • "Genera Concepts" - (Web copy of Symbolic's introduction to Genera)
• Medley
• LISPMACHINE.NET - Lisp Books and Information
• Generic Blackboard - (Example of an AI system developed for Lisp machines)

• Portail de la programmation informatique