Lisp-machine

Dit artikel gaat over het computertype. Voor het bedrijf, zie Lisp Machines.

Lisp-machines zijn computers die ontworpen zijn om zo efficiënt mogelijk Lisp uit te voeren als hun belangrijkste software en programmeertaal, meestal via hardware-ondersteuning. Ze zijn een voorbeeld van een computerarchitectuur op basis van een hogere programmeertaal en in zekere zin waren het de eerste commerciële werkstations.

Ondanks hun bescheiden aantal waren Lisp-machines pioniers op het gebied van technologieën die later wijdverspreid zouden zijn, waaronder efficiënte garbage collection, venstersystemen, rasterafbeeldingen in hoge resolutie, netwerkinnovaties zoals Chaosnet^[1] en het gebruik van computermuizen en laserprinters.

In de jaren 1980 bouwden en verkochten verschillende firma's Lisp-machines: Symbolics (3600, 3640, XL1200, MacIvory en andere modellen), Lisp Machines, Inc. (LMI Lambda), Texas Instruments (Explorer, MicroExplorer) en Xerox (Interlisp-D werkstations). De besturingssystemen waren geschreven in Lisp Machine Lisp, Interlisp en later ook deels in Common Lisp.

AI-computerprogramma's uit de jaren zestig en zeventig hadden nood aan wat toen beschouwd werd als een enorme hoeveelheid computerkracht in termen van processortijd en geheugenruimte. Dat werd nog verergerd door het gebruik van de symbolische programmeertaal Lisp, in een tijdperk waar commerciële hardware ontworpen en geoptimaliseerd werd om zo efficiënt mogelijk software geschreven in assembleertaal en Fortran-achtige programmeertalen uit te voeren. Aanvankelijk was de hardware zo duur dat deze door veel gebruikers moest gedeeld worden.

Toen de technologie van geïntegreerde schakelingen in de jaren zestig en begin jaren zeventig de omvang en kostprijs van computers deed afnemen en de geheugenvereisten van AI-programma's de geheugencapaciteit van de meest gangbare onderzoekscomputer, de DEC PDP-10, begonnen te overschrijden, kozen onderzoekers voor een nieuwe aanpak: een computer die speciaal ontworpen was om grote AI-computerprogramma's die in Lisp geschreven waren te ontwikkelen en uit te voeren. Om het besturingssysteem relatief eenvoudig te houden, zouden deze machines persoonlijke werkstations worden die niet gedeeld werden door meerdere gebruikers.

In 1973 begonnen Richard Greenblatt en Thomas Knight, programmeurs bij het Artificial Intelligence Laboratory (AI Lab) van het Massachusetts Institute of Technology (MIT), aan wat het MIT Lisp-machineproject zou worden: het bouwen van een computer met een 24-bits architectuur die speciaal ontworpen was om bepaalde Lisp-basisbewerkingen rechtstreeks door de hardware te laten uitvoeren, in plaats van ze in software uit te voeren. De machine deed ook incrementele garbage collection. Meer specifiek, aangezien Lisp-variabelen een type krijgen toegewezen tijdens de uitvoering van een programma in plaats van tijdens het compileren, kunnen bepaalde bewerkingen met variabelen vijf keer zo lang duren op conventionele hardware als gevolg van de extra testinstructies die nodig zijn om eerst na te gaan van welk type de variabelen zijn. Lisp-machines voerden de bewerking voor elk type variabele in parallel uit en de bewerkingen die faalden werden genegeerd. Dit betekende in veel gevallen een aanzienlijke snelheidswinst. Deze simultane aanpak werd ook toegepast bij het geheugenbeheer.

Typecontrole werd verder verbeterd en geautomatiseerd toen het conventionele bytewoord van 32 bits verlengd werd tot 36 bits in de Symbolics 3600-familie van Lisp-machines^[2] en uiteindelijk tot 40 bits of meer. De eerste groep extra bits werd gebruikt om het type aan te geven en de resterende bits werden gebruikt om CDR-codering te implementeren, waardoor de garbage collection veel efficiënter kon uitgevoerd worden.

De eerste Lisp-machine was klaar in 1975 en kreeg de naam CONS machine (genoemd naar de cons-functie in Lisp om lijsten te bouwen).^[3] Het ontwerp werd vervolgens verder verbeterd tot de CADR machine uit 1978 (een woordspeling: de cadr-functie in Lisp geeft het tweede element in een lijst) die gebaseerd was op dezelfde architectuur.^[4] Hiervan werden een vijfentwintigtal prototypes gebouwd voor gebruik door andere onderzoeksgroepen van het MIT. Dit ontwerp maakte zodanig veel indruk tijdens een AI-conferentie die in 1978 aan het MIT gehouden werd, dat het Defense Advanced Research Projects Agency (DARPA) de verdere ontwikkeling ervan begon te financieren.^[5]

Eind jaren zeventig stelde Russell Noftsker, voormalig hoofd van het AI Lab, aan Greenblatt voor om de technologie op de markt te brengen. De twee kwamen echter niet tot een akkoord, waarop Noftsker de firma Symbolics oprichtte en 14 ontwikkelaars van MIT in dienst nam. Het bedrijf had aanvankelijk geen gebouwen of apparatuur, maar Noftsker sloot een akkoord met het MIT waardoor Symbolics de gebouwen van het MIT mocht gebruiken. In ruil daarvoor kreeg het MIT gratis alle Symbolics-software ter beschikking voor intern gebruik. Greenblatt, op zijn beurt, richtte met de hulp van Alexander Jacobson de firma LISP Machines, Inc. (LMI) op en nam een viertal ontwikkelaars van MIT in dienst. Twee bekende werknemers van het MIT, Richard Stallman en Marvin Minsky gingen voor geen van beide firma's werken.

In 1980/1981 ging Symbolics van start met de verkoop van de CADR-machine onder de naam LM-2. LMI bracht op zijn beurt de machine op de markt als de LMI-CADR. Beide firma's ontwikkelden een nieuwe generatie Lisp-machines op basis van de CADR: de Symbolics 3600-familie en de LMI Lambda. Aangezien de ontwikkeling van de 3600 herhaaldelijk vertraging opliep produceerde Symbolics uiteindelijk eerst nog zo'n 100 LM-2's. LMI wist ongeveer 200 exemplaren van de LMI Lambda te verkopen.

De 3600, die een jaar later dan gepland op de markt kwam, breidde de CADR uit door het machinewoord te vergroten tot 36 bits en de adresruimte tot 28 bits,^[2] en door hardware toe te voegen om bepaalde algemene functies te versnellen die op de CADR in microcode geïmplementeerd waren. De LMI Lambda die 1983 uitkwam, een jaar na de 3600, was compatibel met de CADR (hij kon CADR-microcode uitvoeren) maar gebruikte andere hardware. Texas Instruments (TI) gooide zich ook in de strijd door een licentie te nemen op het LMI Lambda-ontwerp en zijn eigen variant, de TI Explorer te produceren. Sommige LMI Lambda's en de tweede generatie van de TI Explorer konden met een Lisp- en een Unix-processor geleverd worden.^[6]

Symbolics bleef de 3600-familie en het bijbehorende besturingssysteem, Genera, verder ontwikkelen en produceerde de Ivory, een VLSI-implementatie van de Symbolics-architectuur. Vanaf 1987 werden verschillende machines uitgebracht op basis van de Ivory-processor: werkstations, coprocessorkaarten voor Sun- en Macintosh-systemen en embedded systemen. Texas Intruments miniaturiseerde de Explorer tot een 32-bits microprocessorversie. Deze Lisp-chip werd gebruikt voor de MicroExplorer, een NuBus-coprocessorkaart voor de Apple Macintosh II. LMI verliet de CADR-architectuur en ontwikkelde zijn eigen K-Machine, maar ging failliet voordat de machine op de markt kon gebracht worden.

Al deze machines hadden hardware-ondersteuning voor verschillende Lisp-basisbewerkingen, zoals het testen van datatypes en CDR-codering. Daarnaast was er ook hardware-ondersteuning voor incrementele garbage collection. Hierdoor konden deze machines grote Lisp-computerprogramma's heel efficiënt uitvoeren. De Symbolics-machines concurreerden met veel commerciële minicomputers, maar werden nooit aangepast voor meer conventionele doeleinden. Symbolics Lisp Machines werden ook buiten de AI-wereld gebruikt, zoals voor computergraphics, modellering en animatie.

De van MIT afgeleide Lisp-machines gebruikten een Lisp-dialect genaamd Lisp Machine Lisp, een afstammeling van Maclisp. De besturingssystemen waren volledig in Lisp geschreven, vaak met behulp van objectgeoriënteerde uitbreidingen. Later ondersteunden deze Lisp-machines ook verschillende versies van Common Lisp.

De firma Bolt, Beranek and Newman ontwikkelde zijn eigen Lisp-machine, de Jericho,^[7] waarop een versie van Interlisp draaide. Deze machine is echter nooit op de markt gebracht. Uit onvrede nam de hele AI-groep ontslag en werd daarop grotendeels ingehuurd door Xerox. Daardoor kon het Xerox Palo Alto Research Center quasi gelijktijdig met Greenblatt een eigen Lisp-machine ontwikkelen die ontworpen was om Interlisp en later Common Lisp te draaien. Dezelfde hardware werd met andere software ook gebruikt als Smalltalk-machine en als Xerox Star werkstations. De Xerox-machine stond bekend om zijn geavanceerde ontwikkelomgeving InterLisp-D, zijn grafische gebruikersomgeving en zijn revolutionaire toepassingen zoals NoteCards, een van de eerste hypertext-toepassingen.

Xerox werkte ook aan een Lisp-machine op basis van een RISC-architectuur en was van plan om deze tegen 1987 op de markt te brengen.^[8] Dit is echter nooit gebeurd.

Halverwege de jaren tachtig bouwde Integrated Inference Machines (IIM) de Inferstar, een prototype van een Lisp-machine.^[9]

In 1984-85 probeerde de Britse firma Racal-Norsk om de ND-500 supermini van Norsk Data om te bouwen tot een Lisp-machine met microcode, waarop CADR-software draaide: Het Knowledge Processing System (KPS).^[10]

Er waren ook verschillende pogingen van Japanse fabrikanten om de markt van Lisp-machines te betreden, waaronder Fujitsu met de Facom-alpha^[11] mainframe coprocessor, NTT met de Elis,^[12][13] Toshiba met de AI processor^[14] en NEC met de LIME.^[15]

In Duitsland ontwikkelde Siemens de RISC-gebaseerde Lisp-coprocessorkaart COLIBRI.^[16][17]

Begin jaren negentig bleek dat de vroegste succesvolle AI-systemen, zoals het XCON expertsysteem van DEC, te duur waren om te onderhouden. Dergelijke systemen waren moeilijk aan te passen, konden niet bijleren en waren berucht om groteske fouten te maken wanneer ze ongebruikelijke input voorgeschoteld kregen. Het werd duidelijk dat expertsystemen alleen nuttig waren in heel specifieke contexten, waardoor de interesse vanuit de industrie sterk afnam.

Bovendien werden goedkope pc's steeds krachtiger, waardoor ze al snel Lisp-programma's sneller konden uitvoeren dan Lisp-machines, zonder gebruik van speciale hardware. De hoge winstmarges op de verkoop van Lisp-machines verdwenen als sneeuw voor de zon en de meeste fabrikanten van Lisp-machines gingen in het begin van de jaren negentig failliet. Alleen bedrijven die uitsluitend Lisp-software leverden, zoals Lucid Inc. of hardwareproducenten die overgestapt waren op software en services bleven over. Sinds januari 2015 is Symbolics, naast Xerox en Texas Instruments, het enige bedrijf dat nog actief is met de verkoop van de Open Genera Lisp-machine-omgeving en van het Macsyma computeralgebrasysteem.^[18][19]

Er zijn verschillende initiatieven geweest om open-source emulators te schrijven voor diverse Lisp-machines:

• CADR-emulatie^[20]
• Symbolics L Lisp Machine-emulatie^[21]
• E3-project^[22] (TI Explorer II-emulatie)
• Meroko^[23] en Nevermore^[24] (TI Explorer I-emulatie)
• LambdaDelta^[25] (LMI Lambda-emulatie)

Op 3 oktober 2005 heeft het MIT de broncode van de CADR-machine vrijgegeven als open-source.^[26]

In september 2014 kondigde Alexander Burger, de ontwikkelaar van PicoLisp, PilMCU aan: een implementatie van PicoLisp in hardware.^[27]

Het Bitsavers' PDF Document Archive bevat een uitgebreide documentatie in pdf-formaat voor de Symbolics Lisp-machines,^[28] de TI Explorer^[29] en MicroExplorer^[30] Lisp-machines, de Xerox Interlisp-D Lisp-machines^[31] en de LMI Lambda Lisp machine.^[32]

Aanvankelijk waren Lisp-machines ontworpen als persoonlijk werkstation voor softwareontwikkeling in Lisp. Ze werden door één persoon gebruikt en boden geen multiuser-ondersteuning. De machines waren voorzien van een groot zwart-wit grafisch beeldscherm, toetsenbord en muis, netwerkadapter, lokale harde schijven, meer dan 1 MB RAM, seriële interfaces en een lokale bus voor uitbreidingskaarten. Grafische kleurenkaarten, tapedrives en laserprinters waren optioneel.

De processor voerde niet rechtstreeks Lisp uit, maar was een stack-machine met instructies die geoptimaliseerd waren voor gecompileerde Lisp. De vroege Lisp-machines gebruikten microcode om de instructieset te leveren. Voor verschillende bewerkingen werd typecontrole in hardware gedaan tijdens de uitvoering van het programma. Er is bijvoorbeeld slechts één optelbewerking die gebruikt kan worden voor verschillende numerieke typen (integer, float, rationale en complexe getallen). Het resultaat was een zeer compacte gecompileerde weergave van Lisp-code.

In het volgende voorbeeld wordt een functie gebruikt die het aantal elementen van een lijst telt waarvoor een predicaat de waarde true oplevert.

(defun example-count (predicate list)
  (let ((count 0))
    (dolist (i list count)
      (when (funcall predicate i)
        (incf count)))))

De gedisassembleerde machinecode voor de bovenstaande functie (voor de Ivory-microprocessor van Symbolics) ziet er als volgt uit:

Command: (disassemble (compile #'example-count))

  0  ENTRY: 2 REQUIRED, 0 OPTIONAL      ;Creating PREDICATE and LIST
  2  PUSH 0                             ;Creating COUNT
  3  PUSH FP|3                          ;LIST
  4  PUSH NIL                           ;Creating I
  5  BRANCH 15
  6  SET-TO-CDR-PUSH-CAR FP|5
  7  SET-SP-TO-ADDRESS-SAVE-TOS SP|-1
 10  START-CALL FP|2                    ;PREDICATE
 11  PUSH FP|6                          ;I
 12  FINISH-CALL-1-VALUE
 13  BRANCH-FALSE 15
 14  INCREMENT FP|4                     ;COUNT
 15  ENDP FP|5
 16  BRANCH-FALSE 6
 17  SET-SP-TO-ADDRESS SP|-2
 20  RETURN-SINGLE-STACK

Het besturingssysteem gebruikte virtueel geheugen om een grote adresruimte te bieden. Geheugenbeheer gebeurde met garbage collection. Alle code deelde een enkele adresruimte. Alle data-objecten werden met een tag in het geheugen opgeslagen, zodat het datatype tijdens de uitvoering van het programma kon bepaald worden. Meerdere threads werden ondersteund en processen genoemd. Alle processen liepen in de ene adresruimte.

Alle besturingssysteemsoftware was geschreven in Lisp. Xerox gebruikte Interlisp. Symbolics, LMI en TI gebruikten Lisp Machine Lisp (afstammeling van MacLisp). Met het verschijnen van Common Lisp werd Common Lisp ondersteund op de Lisp-machines en werd sommige systeemsoftware geporteerd naar Common Lisp of later herschreven in Common Lisp.

Sommige latere Lisp-machines (zoals de TI MicroExplorer, de Symbolics MacIvory of de Symbolics UX400/1200) waren niet langer complete werkstations, maar coprocessorkaarten die ontworpen waren om te gebruiken in computers zoals de Apple Macintosh II en de Sun-3 of Sun-4 workstations.

Sommige Lisp-machines, zoals de Symbolics XL1200, hadden uitgebreide grafische mogelijkheden met behulp van speciale grafische kaarten. Deze machines werden ook gebruikt in domeinen zoals medische beeldverwerking, 3D-animatie en CAD.

Zie de categorie Lisp machine van Wikimedia Commons voor mediabestanden over dit onderwerp.