Lisp-maszyna

Lisp-maszyny – komputery ogólnego przeznaczenia, zaprojektowane ze sprzętowym wsparciem dla Lispu jako głównego języka programowania. Stanowią przykład architektury komputerowej dla języka wysokiego poziomu. Były jednymi z pierwszych komercyjnych jednoużytkownikowych stacji roboczych. Pomimo niewielkiej liczby egzemplarzy (około 7000 według stanu na dzień 1988 roku^[1]), Lisp-maszyny były pionierem wielu popularnych technologii – w tym odśmiecania pamięci, drukowania laserowego, systemu okienkowego, komputerowej myszy, grafiki rastrowej o wysokiej rozdzielczości, renderowania grafiki komputerowej, sieci komputerowych (np. Chaosnet). Następujące firmy budowały i sprzedawały Lisp-maszyny w latach 80.: Symbolics (3600, 3640, XL1200, MacIvory, i inne modele), Lisp Machines Incorporated (LMI Lambda), Texas Instruments (Explorer i MicroExplorer), Xerox (stacje robocze Interlisp-D). Systemy operacyjne dla Lisp-maszyn zostały napisane w języku Lisp Machine Lisp, InterLisp (Xerox), a później częściowo w Common Lispie.

W latach 60. i 70. XX wieku, implementacje algorytmów sztucznej inteligencji wymagały olbrzymiej jak na tamte czasy mocy obliczeniowej. Programy sztucznej inteligencji zazwyczaj pisano w języku Lisp, co dodatkowo obniżało ich wydajność, ponieważ większość istniejącego sprzętu była zoptymalizowana pod kątem użycia asemblera lub języków typu Fortran. Z początku, ze względu na wysokie koszty, komputery były dzielone przez wielu użytkowników. Wraz z upowszechnieniem się układów scalonych w latach 60. i 70., ceny komputerów obniżyły się. W tym samym okresie, programy sztucznej inteligencji przestały mieścić się w przestrzeni adresowej najpopularniejszych komputerów, takich jak: DEC PDP-10. Rozważono wtedy nowe podejście: komputer zaprojektowany w celu uruchamiania na nim programów sztucznej inteligencji, zużywających dużo zasobów, dostosowany do semantyki języka programowania Lisp. Aby kod systemu operacyjnego tego komputera nie był zbyt skomplikowany, celowo pominięto możliwość współdzielenia przez wielu użytkowników.

W 1973 roku, programiści MIT AI Lab, Richard Greenblatt i Thomas Knight, rozpoczęli pracę nad budową sprzętu do uruchamiania wybranych podstawowych operacji języka Lisp na 24-bitowej architekturze tagowanej. Sprzęt ten miał wbudowane inkrementalne odśmiecanie pamięci. Te prace stanowiły bazę dla projektu budowy Lisp-maszyny, MIT Lisp Machine Project. Ponieważ typowanie zmiennych w języku Lisp odbywa się w trakcie działania programu, a nie podczas kompilacji, proste operacje, takie jak dodawanie dwóch zmiennych, mogły trwać do pięciu razy dłużej na typowym sprzęcie z powodu instrukcji testowania i skoku. Lisp-maszyna uruchamiała instrukcje testujące równocześnie z instrukcją dodawania. Jeśli instrukcje testujące zwróciły błąd, wynik dodawania był pomijany, a działanie obliczane ponownie. W ten sposób przyspieszono kilkukrotnie przeciętny czas wykonania operacji. Takie podejście zastosowano również w zarządzaniu pamięcią operacyjną.

Typowanie poprawiono i zautomatyzowano w Lisp-maszynie Symbolics, model 3600, kiedy zamiast 32-bitowych słów maszynowych^[2] użyto 36-bitowych, a później 40-bitowych lub dłuższych. Spośród dodatkowych bitów, początkowe oznaczały typ zmiennej, a pozostałe bity były użyte do kodowania CDR, wspomagającego odśmiecanie pamięci, co przyspieszało odśmiecanie o rząd wielkości. Kolejne poprawki dotyczyły wprowadzenia dwóch dodatkowych instrukcji mikrokodu, które wspomagały wywołanie funkcji Lispu, skracając czas ich wywołania (w niektórych implementacjach Symbolics) nawet do 20 cyklów zegara.

Pierwsza z Lisp-maszyn, CONS, swoją nazwę zawdzięcza operatorowi tworzenia listy w języku Lisp. Nazywa się ją również pieszczotliwie „Maszyną Knighta”, ponieważ była ona tematem jego dobrze przyjętej w środowisku pracy magisterskiej. Była ona stopniowo ulepszana, a następną jej wersję opartą na tej samej architekturze nazwano CADR (nazwa pochodzi od funkcji Lisp zwracającej drugi element z listy). Około 25 prototypowych komputerów CADR sprzedano zarówno na uczelni, jak i poza nią w cenie ok. 50 000 dolarów za sztukę. Bardzo szybko stała się ulubionym komputerem społeczności hakerskiej – wiele spośród najpopularniejszych narzędzi oprogramowania zostało przeniesionych na CADR (na przykład w 1975 zaadaptowano edytor tekstu Emacs). Na konferencji sztucznej inteligencji odbywającej się 1978 roku na MIT Lisp-maszyna została doceniona przez uczestniczących i w efekcie DARPA zaczęła sponsorować jej rozwój.

W 1979 roku Russel Noftsker, w przekonaniu że Lisp-maszyna ma szansę na sukces komercyjny, ze względu na moc języka Lisp oraz jego wsparcie sprzętowe, zaproponował Greenblattowi, żeby skomercjalizować tę technologię. Greenblatt zgodził się, prawdopodobnie mając nadzieję, że uda się odtworzyć w firmie nieformalną, produktywną atmosferę panującą w AI Lab. Ten cel był jednak obcy Noftskerowi. Pomimo długich i trudnych negocjacji, nie udało się dojść do kompromisu. Ponieważ sukces firmy zależał całkowicie od pełnego zaangażowania całej grupy hakerów z AI Lab, Notfsker i Greenblatt zdecydowali, że to właśnie im powierzona będzie decyzja, od której zależą losy przedsiębiorstwa.

Dyskusje nad wyborem podzieliły lab na dwie frakcje. W lutym 1979 spór zakończono. Hackerzy opowiedzieli się po stronie Noftskera, uznając, że ze wsparciem inwestorów komercjalizacja Lisp-maszyn ma większe szanse powodzenia niż zaproponowany przez Greenblatta samowystarczalny start up.

W ten sposób powoli powstawała firma Symbolics. Chociaż Noftsker wypłacał pensję programistom, nie miał ani biura, ani sprzętu do pracy. Umówił się z Patrickiem Winstonem, że w zamian za pozwolenie programistom z Symbolics na pracę w laboratorium MIT, laboratorium będzie mogło korzystać na własny użytek w sposób nieograniczony z oprogramowania Symbolics. W tym samym czasie w celu zamówienia egzemplarza Lisp-maszyny z Greenblattem skontaktował się konsultant firmy CDC, Alexander Jacobson, który wraz z grupą programistów z zachodniego wybrzeża pracował nad rozwojem aplikacji dla języka naturalnego. Greenblatt już wcześniej chciał założyć własną, konkurencyjną firmę produkująca Lisp-maszyny, ale nie wykonał żadnych kroków w celu urzeczywistnienia swoich planów. Żeby otrzymać Lisp-maszyny, których firma CDC potrzebowała, Jacobson zdecydował się pomóc Greenblattowi w stworzeniu własnej firmy. Przygotował kosztorys, plan, załogę i znalazł partnera dla Greenblatta. Nowo założona firma nazywała się LISP Machine, Inc (LMI).

W tym samym czasie firma Noftskera, Symbolics, zaczęła swoje działanie – było to utrudnione przez obietnicę daną Greenblattowi, że firma Noftskera wstrzyma się przez rok z udostępnianiem swoich produktów, oraz przez problemy z zebraniem kapitału od inwesotrów. Mimo to, Symbolics miała ciągle znaczącą przewagę w postaci 14 hakerów z AI Lab, którzy w niej pracowali, w przeciwieństwie do 3 lub 4 którzy dołączyli do firmy Greenblatta. Tylko dwoje hackerów z AI Lab nie dołączyło do żadnej z tych grup: Richard Stallman i Marvin Minski. Stallman oskarżał Symbolics za upadek kultury hakerskiej w AI Lab. Przez dwa lata, od 1982 roku aż do końca 1983, Stallman samodzielnie reimplementował programy Symbolics, żeby zapobiec monopolowi Symbolics na oprogramowanie komputerów w labie MIT^[3].

Po serii wewnętrznych tarć, w latach 1980/1981 Symbolics zaczęła sprzedaż CADR jako LM-2, podczas gdy Lisp Machines, Inc. sprzedawała ją jako LMI-CADR. Symbolics nie zamierzała produkować wielu egzemplarzy LM-2, ponieważ wkrótce zamierzano wprowadzić nowe modele Lisp-maszyn 3600. Jednak prace nad nimi wielokrotnie się opóźniały, w związku z czym Symbolics wyprodukowała około 100 sztuk LM-2, z czego każda sprzedała się po cenie ok. 70 000 USD. Obie firmy wyprodukowały produkty drugiej generacji w oparciu o CADR: Symbolics 3600 oraz LMI-LAMBDA (LMI sprzedała ich około 200). W model 3600, który pojawił się z rocznym opóźnieniem, dokonano następujących zmian: wprowadzono 36-bitowe słowo maszynowe oraz powiększono przestrzeń adresową do 28-bitów^[4], dodano wsparcie sprzętowe dla funkcji, które były zaimplementowane w mikrokodzie na maszynie CADR. LMI-LAMBDA, który pojawił się rok po 3600, w 1983, było wstecznie kompatybilne z CADR, ale różnił się sprzętowo. Texas Instruments dołączył do konkurencji, również produkując swój wariant LMI-LAMBDA, zwany TI Explorer. LMI-LAMBDA i TI Explorer były podwójnymi systemami posiadającymi zarówno procesor Lisp, jak i UNIX. TI również zaprojektował 32-bitową mikroprocesorową wersję TI Explorera. Ta 32-bitowa wersja była również używana w MicroExplorerze – płytce NuBus dla Apple Macintosh.

Symbolics kontynuowało rozwój rodziny 3600 i systemu operacyjnego dla nich, Genera, i wyprodukowało Ivory – implementację architektury Symbolics jako VLSI. Począwszy od 1987, wyprodukowano następujące komputery w oparciu o Ivory: płytki dla komputerów Sun i Mac, samodzielne stacje robocze i nawet systemy wbudowane (I-Machine Custom LSI, 32 bit address, Symbolics XL-400, UX-400, MacIvory II; w 1989 dostępnymi platformami były Symbolics XL-1200, MacIvory III, UX-1200, Zora, NXP1000 „pizza box”). Texas Instruments zmniejszył Explorera do MicroExplorera, który był dostępny do komputerów Apple Mac II jako karta rozszerzeń. LMI porzuciło architekturę CADR i zaczęło rozwijać własną K-Machine^[5], ale firma zbankrutowała zanim skończono pracę nad tym projektem. Zanim jednak to się stało, pracowano tam również nad systemem rozproszonym dla LAMDA przy użyciu Moby space^[6].

Wspomniane komputery miały wsparcie sprzętowe dla różnych pierwotnych operacji języka Lisp (testowanie typu danych, kodowanie CDR), a także miały wsparcie sprzętowe dla odśmiecania pamięci, co znacząco zwiększało wydajność wykonywanych programów. Lisp-maszyny marki Symbolics były konkurencyjne w stosunku do komercyjnych super mini komputerów, ale nigdy nie zaadaptowano ich do konwencjonalnych celów. Symbolics Lisp Machines sprzedawano także do innych zastosowań, takich jak grafika komputerowa, modelowanie lub animacje.

Lisp-maszyny z AI labu uruchamiały programy napisane w dialekcie języka Lisp – Lisp Machine Lisp, pochodzący od MIT Maclisp. System operacyjny był w całości napisany w Lispie, przy użyciu obiektowych rozszerzeń tego języka. Później te komputery także wspierały różne wersje języka Common Lisp.

BBN rozwijał własny typ Lisp-maszyn, zwany Jericho^[7], na którym uruchamiano jedną z wersji Interlispu. Ten projekt nigdy nie został wprowadzony na rynek. Sfrustrowana tym faktem grupa programistów AI odeszła z BBN. Zatrudniła ich firma Xerox. W ten sposób Xerox Palo Ato Research Center rozwijała, równolegle do projektu Greenblatta, Lisp-maszyny, które były zaprojektowane do uruchamiania InterLispu (a w późniejszym okresie Common Lispu). Na tym samym sprzędzie działały także maszyny Smalltalka i Xerox Star. Włączając Xerox 1100, „Dolphin” (1979); Xerox 1132, „Dorado”; Xerox 1108, „Dandelion” (1981); Xerox 1109, „Dandetiger”; i Xerox 1186/6085, „Daybreak”. Komputery Xerox okazały się fiaskiem, ale wpłynęły na stworzenie komputera Apple, Macintosha. System operacyjny maszyn Xerox Lisp został także przepisany na maszyny wirtualne i jest dostępny na kilka platform jako „Medley”. Xerox Lisp Machine była dobrze znana z jej zaawansowanego środowiska programowania (InterLisp-D), menadżera okien ROOMS i z ich wczesnego graficznego interfejsu użytkownika i aplikacji takich jak NoteCards (jedną z pierwszych aplikacji hipertekstowych).

Xerox także pracował nad Lisp-maszynach o architekturze RISC z użyciem „Xerox Common Lisp Processor” i planował także rozpocząć jego dystrybucję w 1987, co jednak nie nastąpiło^[8].

W połowie lat 80. Integrated Inference Machines (IIM) zbudowały prototyp Lisp-maszyny nazwanej Inferstar^[9].

W latach 1984–1985 brytyjska firma, Racal-Norsk, będąca wspólną własnością firm Racal i Norsk Data, podjęła się modyfikacji super mini komputera firmy Norsk Data, ND-500 w celu stworzenia Lisp-maszyny, na której działało oprogramowanie CADR: Knowledge Processing System (KPS)^[10].

Japońscy producenci również podjęli kilka prób wejścia na rynek Lisp-maszyn: ko-procesor NTT Elis^[11][12] do mainframe Fujitsu Facom-alpha^[13], procesor AI firmy Toshiba^[14] (AIP) i NEC LIME^[15]. Kilka uniwersyteckich grup badawczych wyprodukowało działające prototypy, wśród nich Uniwersytet Kobe (TAKITAC-7^[16]), RIKEN FLATS^[17], i ELVIS Uniwersytetu Osaka^[18].

We Francji prowadzono dwa projekty badawcze na temat Lisp-maszyn: M3L^[19] w Uniwersytecie Toulouse Paul Sabatier i późniejszy MAIA^[20].

W Niemczech, Siemens zaprojektował koprocesor COLIBRI Lisp na architekturze RISC^[21][22].

Z początkiem zmniejszania się zainteresowania sztuczną inteligencją, oraz z wczesnymi początkami rewolucji mikroprocesorowej, programy napisane w języku Lisp zaczęły działać szybciej na osobistych komputerach, bez konieczności specjalnego wsparcia sprzętowego. Ponieważ większość biznesu firm sprzedających Lisp-maszyny opierała się na sprzedaży kosztownego sprzętu, większość producentów Lisp-maszyn zakończyła działalność we wczesnych latach 90., pozostawiając jedynie firmy zajmujące się oprogramowaniem takie jak Lucid Inc. lub producentów sprzętu, którzy przebranżowili się do oprogramowania i serwisów, żeby uniknąć bankructwa. W styczniu 2015 roku, poza firmą Xerox, Symbolics jest jedyną firmą zajmującą się Lisp-maszynami, która sprzedaje środowisko oprogramowania Lisp-maszyn Open Genera oraz Macsyma – program komputerowy do obliczeń symbolicznych^[23][24].

Podjęto kilka prób napisania emulatorów dla różnych Lisp-maszyn: CADR Emulation^[25], Symbolics L Lisp Machine Emulation^[26], E3 Projekt (TI Explorer II Emulation)^[27], Meroko (TI Explorer I)^[28], oraz Nevermore (TI Explorer I)^[29]. 3 października 2005 roku, MIT opublikowało kod źródłowy Lisp-maszyny CADR jako otwarte oprogramowanie^[30].

We wrześniu 2014 roku, Alexander Burger, programista PicoLisp, ogłosił PilMCU, sprzętową implementację języka PicoLisp^[31].

Archiwum dokumentów Bitsavers^[32] jest w posiadaniu dokumentacji Lisp-maszyn: firmy Symbolics^[33], TI Explorera^[34], oraz MicroExplorera^[35], Lisp-maszyn, oraz komputera Xerox Interlisp-D Lisp Machines w formacie PDF.^[36]

Lisp-maszyny były używane głównie w dziedzinie sztucznej inteligencji. Poza tym używano ich także m.in. w grafice komputerowej i przetwarzaniu obrazów medycznych.

Główne komercyjne systemy eksperckie oparte na Lisp-maszynie to: Knowledge Engineering Environment (KEE), Knowledge Craft firmy The Carnegie Group Inc., oraz ART (Automated Reasoning Tool) firmy Inference Corporation^[37].

Początkowo Lisp-maszyny były zaprojektowane jako osobiste stacje robocze dla rozwoju oprogramowania w języku Lisp. Nie miały wsparcia dla wielu użytkowników. Lisp-maszyny oferowały wielki czarno-biały wyświetlacz, klawiaturę i myszkę, adapter sieciowy, lokalne dyski twarde, ponad 1 MB pamięci RAM, interfejs szeregowy i lokalną szynę dla kart rozszerzeń. Kolorowe karty graficzne, napędy taśmowe i drukarka laserowa były opcjonalne.

Programy w Lispie nie były uruchamiane na procesorze bezpośrednio. Lisp-maszyna była maszyną stosową z instrukcjami zoptymalizowanymi pod skompilowany język Lisp. Wczesne komputery tego typu dostarczały zbiór instrukcji procesora w postaci mikrokodu. Dla szczególnych operacji sprawdzanie typów oraz dispatching były obsługiwane sprzętowo w trakcie działania programu. Dla przykładu, dostępna była tylko jedna instrukcja dodawania, która mogła być używana z różnymi typami numerycznymi (całkowitym, zmiennoprzecinkowym, ułamkowym i zespolonym). Dzięki temu, skompilowana reprezentacja kodu w Lispie była bardzo zwarta.

Poniższy przykład prezentuje funkcję która zlicza liczbę elementów, dla których dany predykat zwraca prawdę:

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

Zdesasemblowany kod maszynowy powyższej funkcji (dla procesora Ivory firmy Symbolics):

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

System operacyjny używał pamięci wirtualnej, by zapewnić dużą przestrzeń adresową. Zarządzanie pamięcią było realizowane przy pomocy odśmiecacza pamięci. Cały kod współdzielił pojedynczą przestrzeń adresową. Wszystkie obiekty były trzymane w pamięci razem z oznaczeniem typu, by w ten sposób można było łatwo określić typ w trakcie działania. Wielowątkowość była wspierana, ale wszystkie procesy współdzieliły przestrzeń adresową.

Systemy operacyjne Lisp-maszyn były napisane w Lispie. Xerox używał do tego celu języka InterLisp, Symbolics, LMI oraz TI używali Lisp Machine Lisp. Wraz z pojawieniem się Common Lispu dodano do Lisp-maszyn jego wsparcie, a część oprogramowania została zaadaptowana do Common Lispu, lub całkowicie przepisana.

Niektóre z Lisp-maszyn (takie jak TI MicroExplorer, Symbolics MacIvory lub Symbolics UX400/1200) nie były już kompletnymi stacjami roboczymi, ale były płytkami zaprojektowanymi by uruchamiać je na innym komputerze, np. Apple Macintosh II lub SUN 3 lub 4.

Niektóre z Lisp-maszyn, takie jak Symbolics XL1200 miały rozległe możliwości graficzne przy użyciu specjalnych kart graficznych. Znalazły one zastosowanie w przetwarzaniu obrazów medycznych, animacji 3D oraz CAD.