Лисповские машины: специализированные компьютеры для языка Lisp

Введение

Компьютер, специализирующийся на выполнении Lisp – тип компьютера.

Lisp-машины – это компьютеры общего назначения, разработанные для эффективного выполнения Lisp в качестве основного программного обеспечения и языка программирования, как правило, с аппаратной поддержкой. Они представляют собой пример компьютерной архитектуры, ориентированной на язык высокого уровня. В определенном смысле, они были первыми коммерческими однопользовательскими рабочими станциями. Несмотря на относительно небольшое количество выпущенных машин (возможно, около 7000 единиц к 1988 году), Lisp-машины стали коммерческими пионерами многих современных технологий, включая эффективную сборку мусора, лазерную печать, оконные системы, компьютерные мыши, высокоразрешающую растровую графику, компьютерную графическую визуализацию и сетевые инновации, такие как Chaosnet. В 1980-х годах несколько компаний разрабатывали и продавали Lisp-машины: Symbolics (3600, 3640, XL1200, MacIvory и другие модели), Lisp Machines Incorporated (LMI Lambda), Texas Instruments (Explorer, MicroExplorer) и Xerox (рабочие станции Interlisp D). Операционные системы были написаны на Lisp Machine Lisp, Interlisp (Xerox), а позднее частично на Common Lisp.

Исторический контекст

Компьютерные программы искусственного интеллекта (ИИ) 1960-х и 1970-х годов изначально требовали того, что в то время считалось огромным объемом вычислительных ресурсов, измеряемым в машинном времени и объеме памяти. Потребности в вычислительной мощности исследований ИИ усугублялись использованием символического языка программирования Lisp, в то время как коммерческое оборудование разрабатывалось и оптимизировалось для языков программирования, таких как ассемблер и Fortran. Поначалу высокая стоимость компьютерного оборудования означала, что им приходилось делиться между многими пользователями. По мере того как технология интегральных схем уменьшала размер и стоимость компьютеров в 1960-х и начале 1970-х годов, а потребности в памяти программ ИИ начали превышать адресное пространство наиболее распространенного исследовательского компьютера, Digital Equipment Corporation (DEC) PDP 10, исследователи стали рассматривать новый подход: компьютер, разработанный специально для разработки и запуска крупных программ искусственного интеллекта и адаптированный к семантике языка Lisp. Чтобы операционная система оставалась (относительно) простой, эти машины не предназначались для совместного использования, а должны были быть выделены для одного пользователя.

Первоначальная разработка

В 1973 году Ричард Гринблатт и Томас Найт, программисты из Лаборатории искусственного интеллекта Массачусетского технологического института (MIT), начали проект, который впоследствии стал известен как MIT Lisp Machine Project, когда они впервые приступили к созданию компьютера с аппаратной реализацией основных операций Lisp, вместо их выполнения программным путем, в 24-битной архитектуре с тегами. Машина также поддерживала инкрементный (или Arena) сбор мусора. В частности, поскольку типы переменных Lisp определяются во время выполнения, а не компиляции, простое сложение двух переменных могло занимать в пять раз больше времени на обычном оборудовании из-за инструкций проверки и ветвления. Lisp Machines выполняли проверки параллельно с обычным сложением, требующим одной инструкции. Если одновременные проверки не проходили, результат отбрасывался и пересчитывался, что во многих случаях приводило к увеличению скорости в несколько раз. Этот подход одновременной проверки также использовался при проверке границ массивов при обращении к ним и для других задач управления памятью (а не только для сбора мусора или работы с массивами). Проверка типов была дополнительно улучшена и автоматизирована, когда стандартное 32-битное байтовое слово было увеличено до 36 бит для Lisp-машин Symbolics 3600, а затем и до 40 бит или более (обычно, неиспользованные биты применялись для кодов коррекции ошибок). Первая группа дополнительных битов использовалась для хранения информации о типах, что делало машину помеченной архитектурой, а оставшиеся биты использовались для реализации CDR-кодирования (при котором обычные элементы связного списка сжимались, занимая примерно половину объема памяти), что, по сообщениям, увеличивало эффективность сбора мусора на порядок. Дальнейшим улучшением стали две микрокоманды, специально поддерживающие функции Lisp, что снижало стоимость вызова функции до 20 тактов в некоторых реализациях Symbolics. Первая машина получила название CONS machine (в честь оператора cons для построения списков в Lisp). Ее часто называли машиной Найта, возможно, потому, что Найт написал магистерскую диссертацию на эту тему; она была очень хорошо принята. Впоследствии она была улучшена и превратилась в версию под названием CADR (игра слов; в Lisp функция cadr, возвращающая второй элемент списка, произносится как или , как некоторые произносят слово "cadre"), которая была основана на той же архитектуре. Около 25 прототипов CADR были проданы внутри и за пределами MIT по цене около 50 000 долларов США; она быстро стала любимой машиной для хакинга, и многие популярные программные инструменты были быстро портированы на нее (например, Emacs был портирован из ITS в 1975 году). Она получила такой положительный отклик на конференции по ИИ, проходившей в MIT в 1978 году, что Агентство передовых исследовательских проектов Министерства обороны (DARPA) начало финансировать ее разработку.

In 1973, Richard Greenblatt and Thomas Knight, programmers at Massachusetts Institute of Technology (MIT) Artificial Intelligence Laboratory (AI Lab), began what would become the MIT Lisp Machine Project when they first began building a computer hardwired to run certain basic Lisp operations, rather than run them in software, in a 24 bit tagged architecture. The machine also did incremental (or Arena) garbage collection. More specifically, since Lisp variables are typed at runtime rather than compile time, a simple addition of two variables could take five times as long on conventional hardware, due to test and branch instructions. Lisp Machines ran the tests in parallel with the more conventional single instruction additions. If the simultaneous tests failed, then the result was discarded and recomputed; this meant in many cases a speed increase by several factors. This simultaneous checking approach was used as well in testing the bounds of arrays when referenced, and other memory management necessities (not merely garbage collection or arrays). Type checking was further improved and automated when the conventional byte word of 32 bits was lengthened to 36 bits for Symbolics 3600 model Lisp machines and eventually to 40 bits or more (usually, the excess bits not accounted for by the following were used for error correcting codes). The first group of extra bits were used to hold type data, making the machine a tagged architecture, and the remaining bits were used to implement CDR coding (wherein the usual linked list elements are compressed to occupy roughly half the space), aiding garbage collection by reportedly an order of magnitude. A further improvement was two microcode instructions which specifically supported Lisp functions, reducing the cost of calling a function to as little as 20 clock cycles, in some Symbolics implementations. The first machine was called the CONS machine (named after the list construction operator cons in Lisp). Often it was affectionately referred to as the Knight machine, perhaps since Knight wrote his master's thesis on the subject; it was extremely well received. It was subsequently improved into a version called CADR (a pun; in Lisp, the cadr function, which returns the second item of a list, is pronounced or , as some pronounce the word "cadre") which was based on essentially the same architecture. About 25 of what were essentially prototype CADRs were sold within and without MIT for ~$50,000; it quickly became the favorite machine for hacking many of the most favored software tools were quickly ported to it (e. g. Emacs was ported from ITS in 1975). It was so well received at an AI conference held at MIT in 1978 that Defense Advanced Research Projects Agency (DARPA) began funding its development.

Коммерциализация технологии машин MIT Lisp

В 1979 году Рассел Нофтскер, будучи убежденным в светлом коммерческом будущем машин Lisp благодаря силе языка Lisp и возможности аппаратного ускорения, предложил Гринблату коммерциализировать технологию. В контринтуитивный для хакера Лаборатории ИИ шаг, Гринблат согласился, надеясь воссоздать неформальную и продуктивную атмосферу Лаборатории в реальном бизнесе. Эти идеи и цели значительно отличались от замыслов Нофтскера. Они долго вели переговоры, но ни одна из сторон не желала идти на компромисс. Поскольку успех нового предприятия зависел от полной и безоговорочной поддержки хакеров Лаборатории ИИ как группы, Нофтскер и Гринблатт решили, что судьба компании должна быть в их руках, и предоставили выбор самим хакерам. Последовавшие дискуссии разделили лабораторию на два лагеря. В феврале 1979 года ситуация достигла критической точки. Хакеры поддержали Нофтскера, полагая, что коммерческое предприятие, финансируемое венчурным фондом, имеет больше шансов на выживание и коммерциализацию машин Lisp, чем предлагаемый Гринблатом самодостаточный стартап. Гринблатт потерпел поражение. В этот момент Symbolics, предприятие Нофтскера, начало обретать форму. Пока Нофтскер выплачивал сотрудникам зарплату, у него не было ни здания, ни оборудования для работы хакеров. Он договорился с Патриком Уинстоном, что в обмен на возможность для сотрудников Symbolics продолжать работать в MIT, Symbolics позволит MIT свободно использовать все разработанное программное обеспечение. Примерно через восемь месяцев после неудачной конференции с Нофтскером к Гринблату обратился консультант из CDC, пытавшийся создать приложение для обработки естественного языка с группой программистов с Западного побережья, и попросил предоставить машину Lisp для работы его команды. Гринблатт решил основать собственную конкурирующую фирму по производству машин Lisp, но не предпринял никаких действий. Консультант, Александр Джейкобсон, пришел к выводу, что Гринблатт начнет фирму и построит машины Lisp, которые Джейкобсону отчаянно нужны, только если Джейкобсон будет активно помогать ему в запуске предприятия. Джейкобсон подготовил бизнес-планы, сформировал совет директоров и нашел партнера для Гринблатта (Ф. Стивена Уайла). Новая фирма получила название LISP Machine, Inc. (LMI) и была профинансирована за счет заказов CDC, полученных через Джейкобсона. Примерно в это же время начала функционировать Symbolics (фирма Нофтскера). Ей мешало обещание Нофтскера дать Гринблату годовой запас времени, а также серьезные задержки с получением венчурного капитала. Symbolics все еще имела значительное преимущество: в то время как 3-4 хакера из Лаборатории ИИ перешли на работу к Гринблату, 14 других хакеров присоединились к Symbolics. Ни одна из фирм не наняла двоих сотрудников Лаборатории ИИ: Ричарда Столлмана и Марвина Минского. Однако Столлман обвинил Symbolics в упадке хакерского сообщества, существовавшего вокруг Лаборатории ИИ. В течение двух лет, с 1982 по конец 1983 года, Столлман самостоятельно клонировал разработки программистов Symbolics, стремясь не допустить их монополии на компьютеры Лаборатории. Тем не менее, после серии внутренних споров Symbolics все же начала работу в 1980/1981 годах, продавая CADR под названием LM 2, а Lisp Machines, Inc. – как LMI CADR. Symbolics не планировала производить много LM 2, поскольку семейство машин Lisp 3600 должно было выйти на рынок в ближайшее время, но выпуск 3600 постоянно откладывался, и в итоге Symbolics произвела около 100 LM 2, каждая из которых продавалась за 70 000 долларов. Обе компании разработали продукты второго поколения на базе CADR: Symbolics 3600 и LMI LAMBDA (LMI удалось продать около 200 экземпляров LAMBDA). 3600, выпущенная с задержкой в год, расширила возможности CADR, увеличив разрядность машинного слова до 36 бит, адресное пространство до 28 бит и добавив аппаратное обеспечение для ускорения общих функций, реализованных в микрокоде на CADR. LMI LAMBDA, вышедшая на год позже 3600, в 1983 году, была совместима с CADR (могла выполнять микрокод CADR), но имела аппаратные отличия. Texas Instruments (TI) присоединилась к конкуренции, лицензировав дизайн LMI LAMBDA и выпустив свой собственный вариант – TI Explorer. Некоторые из LMI LAMBDA и TI Explorer были двойными системами с процессорами Lisp и Unix. TI также разработала 32-битную версию микропроцессора Lisp CPU для TI Explorer. Этот чип Lisp также использовался в MicroExplorer – плате NuBus для Apple Macintosh II (NuBus изначально был разработан в MIT для использования в машинах Lisp). Symbolics продолжала разрабатывать семейство 3600 и свою операционную систему Genera, а также создала Ivory – аппаратную реализацию архитектуры Symbolics на основе интегральных схем. Начиная с 1987 года, было разработано несколько машин на базе процессора Ivory: платы для Suns и Macs, автономные рабочие станции и даже встраиваемые системы (I Machine Custom LSI, 32-битная адресация, Symbolics XL 400, UX 400, MacIvory II; в 1989 году доступны были платформы Symbolics XL 1200, MacIvory III, UX 1200, Zora, NXP1000 "pizza box"). Texas Instruments уменьшила Explorer до размеров кремниевого чипа и выпустила MicroExplorer в виде платы для Apple Mac II. LMI отказалась от архитектуры CADR и разработала собственную K Machine, но обанкротилась до того, как машина была выпущена на рынок. Перед банкротством LMI работала над распределенной системой для LAMBDA, использующей пространство Moby. Эти машины имели аппаратную поддержку различных примитивных операций Lisp (проверка типов данных, кодирование CDR), а также аппаратную поддержку инкрементной сборки мусора. Они очень эффективно выполняли большие программы на Lisp. Машина Symbolics была конкурентоспособна со многими коммерческими супермини-компьютерами, но так и не была адаптирована для обычных целей. Машины Lisp Symbolics также продавались на некоторые рынки, не связанные с ИИ, такие как компьютерная графика, моделирование и анимация. Машины Lisp, разработанные в MIT, работали на диалекте Lisp под названием Lisp Machine Lisp, происходящем от Maclisp MIT. Операционные системы были написаны с нуля на Lisp, часто с использованием объектно-ориентированных расширений. Позже эти машины Lisp также поддерживали различные версии Common Lisp (с Flavors, New Flavors и Common Lisp Object System (CLOS)).

In 1979, Russell Noftsker, being convinced that Lisp machines had a bright commercial future due to the strength of the Lisp language and the enabling factor of hardware acceleration, proposed to Greenblatt that they commercialize the technology. In a counter intuitive move for an AI Lab hacker, Greenblatt acquiesced, hoping perhaps that he could recreate the informal and productive atmosphere of the Lab in a real business. These ideas and goals were considerably different from those of Noftsker. The two negotiated at length, but neither would compromise. As the proposed firm could succeed only with the full and undivided assistance of the AI Lab hackers as a group, Noftsker and Greenblatt decided that the fate of the enterprise was up to them, and so the choice should be left to the hackers. The ensuing discussions of the choice divided the lab into two factions. In February 1979, matters came to a head. The hackers sided with Noftsker, believing that a commercial venture fund backed firm had a better chance of surviving and commercializing Lisp machines than Greenblatt's proposed self sustaining start up. Greenblatt lost the battle. It was at this juncture that Symbolics, Noftsker's enterprise, slowly came together. While Noftsker was paying his staff a salary, he had no building or any equipment for the hackers to work on. He bargained with Patrick Winston that, in exchange for allowing Symbolics' staff to keep working out of MIT, Symbolics would let MIT use internally and freely all the software Symbolics developed. A consultant from CDC, who was trying to put together a natural language computer application with a group of West coast programmers, came to Greenblatt, seeking a Lisp machine for his group to work with, about eight months after the disastrous conference with Noftsker. Greenblatt had decided to start his own rival Lisp machine firm, but he had done nothing. The consultant, Alexander Jacobson, decided that the only way Greenblatt was going to start the firm and build the Lisp machines that Jacobson desperately needed was if Jacobson pushed and otherwise helped Greenblatt launch the firm. Jacobson pulled together business plans, a board, a partner for Greenblatt (one F. Stephen Wyle). The newfound firm was named LISP Machine, Inc. (LMI), and was funded by CDC orders, via Jacobson. Around this time Symbolics (Noftsker's firm) began operating. It had been hindered by Noftsker's promise to give Greenblatt a year's head start, and by severe delays in procuring venture capital. Symbolics still had the major advantage that while 3 or 4 of the AI Lab hackers had gone to work for Greenblatt, a solid 14 other hackers had signed onto Symbolics. Two AI Lab people were not hired by either: Richard Stallman and Marvin Minsky. Stallman, however, blamed Symbolics for the decline of the hacker community that had centered around the AI lab. For two years, from 1982 to the end of 1983, Stallman worked by himself to clone the output of the Symbolics programmers, with the aim of preventing them from gaining a monopoly on the lab's computers. Regardless, after a series of internal battles, Symbolics did get off the ground in 1980/1981, selling the CADR as the LM 2, while Lisp Machines, Inc. sold it as the LMI CADR. Symbolics did not intend to produce many LM 2s, since the 3600 family of Lisp machines was supposed to ship quickly, but the 3600s were repeatedly delayed, and Symbolics ended up producing ~100 LM 2s, each of which sold for $70,000. Both firms developed second generation products based on the CADR: the Symbolics 3600 and the LMI LAMBDA (of which LMI managed to sell ~200). The 3600, which shipped a year late, expanded on the CADR by widening the machine word to 36 bits, expanding the address space to 28 bits, and adding hardware to accelerate certain common functions that were implemented in microcode on the CADR. The LMI LAMBDA, which came out a year after the 3600, in 1983, was compatible with the CADR (it could run CADR microcode), but hardware differences existed. Texas Instruments (TI) joined the fray when it licensed the LMI LAMBDA design and produced its own variant, the TI Explorer. Some of the LMI LAMBDAs and the TI Explorer were dual systems with both a Lisp and a Unix processor. TI also developed a 32 bit microprocessor version of its Lisp CPU for the TI Explorer. This Lisp chip also was used for the MicroExplorer – a NuBus board for the Apple Macintosh II (NuBus was initially developed at MIT for use in Lisp machines). Symbolics continued to develop the 3600 family and its operating system, Genera, and produced the Ivory, a VLSI implementation of the Symbolics architecture. Starting in 1987, several machines based on the Ivory processor were developed: boards for Suns and Macs, stand alone workstations and even embedded systems (I Machine Custom LSI, 32 bit address, Symbolics XL 400, UX 400, MacIvory II; in 1989 available platforms were Symbolics XL 1200, MacIvory III, UX 1200, Zora, NXP1000 "pizza box"). Texas Instruments shrank the Explorer into silicon as the MicroExplorer which was offered as a card for the Apple Mac II. LMI abandoned the CADR architecture and developed its own K Machine, but LMI went bankrupt before the machine could be brought to market. Before its demise, LMI was working on a distributed system for the LAMBDA using Moby space. These machines had hardware support for various primitive Lisp operations (data type testing, CDR coding) and also hardware support for incremental garbage collection. They ran large Lisp programs very efficiently. The Symbolics machine was competitive against many commercial super minicomputers, but was never adapted for conventional purposes. The Symbolics Lisp Machines were also sold to some non AI markets like computer graphics, modeling, and animation. The MIT derived Lisp machines ran a Lisp dialect named Lisp Machine Lisp, descended from MIT's Maclisp. The operating systems were written from the ground up in Lisp, often using object oriented extensions. Later, these Lisp machines also supported various versions of Common Lisp (with Flavors, New Flavors, and Common Lisp Object System (CLOS)).

Interlisp, BBN и Xerox

Bolt, Beranek and Newman (BBN) разработали собственную Lisp-машину под названием Jericho, работавшую под управлением версии Interlisp. Она так и не была выпущена в продажу. Разочарованные, все сотрудники группы искусственного интеллекта уволились и в основном были приняты на работу в Xerox. Таким образом, исследовательский центр Xerox Palo Alto, одновременно с разработкой Гринблатта в MIT, создал собственные Lisp-машины, предназначенные для работы с InterLisp (а позднее с Common Lisp). То же аппаратное обеспечение использовалось и с другим программным обеспечением, в частности, как машины для Smalltalk и как офисная система Xerox Star. К ним относились Xerox 1100, Dolphin (1979); Xerox 1132, Dorado; Xerox 1108, Dandelion (1981); Xerox 1109, Dandetiger; и Xerox 1186/6085, Daybreak. Операционная система Lisp-машин Xerox также была портирована на виртуальную машину и доступна для различных платформ в виде продукта под названием Medley. Машины Xerox были хорошо известны своей продвинутой средой разработки (InterLisp D), оконным менеджером ROOMS, ранним графическим пользовательским интерфейсом и инновационными приложениями, такими как NoteCards (одно из первых приложений гипертекста). Xerox также работала над Lisp-машиной, основанной на архитектуре с упрощенным набором команд (RISC), используя "Xerox Common Lisp Processor" и планировала выпустить ее на рынок к 1987 году, но этого не произошло.

Комплексные инференс-машины

В середине 1980-х годов компания Integrated Inference Machines (IIM) создала прототипы Lisp-машин под названием Inferstar.

Развитие машин Lisp за пределами США

В 1984–1985 годах британская фирма Racal Norsk, совместное предприятие Racal и Norsk Data, попыталась использовать супермини ND 500 от Norsk Data в качестве Lisp-машины с микропрограммированием, работающей под управлением программного обеспечения CADR – Система обработки знаний (KPS). Японские производители также предприняли несколько попыток выйти на рынок Lisp-машин: сопроцессор для мэйнфрейма Fujitsu Facom alpha, Elis от NTT, AI-процессор (AIP) от Toshiba и LIME от NEC. Несколько университетских исследовательских групп создали рабочие прототипы, в том числе TAKITAC 7 Университета Кобе, FLATS от RIKEN и EVLIS Университета Осаки. Во Франции возникло два проекта Lisp Machine: M3L в Университете Поля Сабатье в Тулузе и позднее MAIA. В Германии компания Siemens разработала сопроцессор Lisp COLIBRI на базе RISC.

Конец машин Lisp

С наступлением зимы искусственного интеллекта и началом революции микрокомпьютеров, которая смела с рынка производителей миникомпьютеров и рабочих станций, более дешевые настольные ПК вскоре стали запускать программы Lisp даже быстрее, чем специализированные Lisp-машины, без использования специального аппаратного обеспечения. Потеряв высокодоходный бизнес по продаже оборудования, большинство производителей Lisp-машин к началу 90-х годов прекратили свое существование, оставив лишь компании, специализирующиеся на программном обеспечении, такие как Lucid Inc., или производителей оборудования, перешедших на программное обеспечение и услуги, чтобы избежать краха. Помимо Xerox и TI, Symbolics – единственная компания, продолжающая работать с Lisp, продавая программную среду Open Genera Lisp и систему компьютерной алгебры Macsyma.

Наследие

Было предпринято несколько попыток создания эмуляторов с открытым исходным кодом для различных машин Lisp: CADR Emulation, Symbolics L Lisp Machine Emulation, проект E3 (эмуляция TI Explorer II), Meroko (TI Explorer I) и Nevermore (TI Explorer I). 3 октября 2005 года MIT опубликовал исходный код CADR Lisp Machine под открытой лицензией. В сентябре 2014 года Александр Бергер, разработчик PicoLisp, представил PilMCU – аппаратную реализацию PicoLisp. В PDF-архиве Bitsavers доступны PDF-версии обширной документации для машин Symbolics Lisp Machines, TI Explorer и MicroExplorer Lisp Machines, а также машин Xerox Interlisp D Lisp Machines.

Приложения

Домены, использовавшие Lisp-машины, охватывали преимущественно широкую область применения искусственного интеллекта, но также включали компьютерную графику, обработку медицинских изображений и многие другие сферы. Основные коммерческие экспертные системы 80-х годов, такие как Knowledge Engineering Environment (KEE) от Intellicorp, Knowledge Craft от The Carnegie Group Inc., и ART (Automated Reasoning Tool) от Inference Corporation, были доступны на рынке.