Лисп-машина

Программы в области искусственного интеллекта (ИИ) 1960-х и 1970-х годов требовали огромных по тем временам вычислительных ресурсов — процессорного времени и объёма памяти. Особые требования ИИ-комплексам предъявлял язык программирования Лисп, поскольку массовое оборудование разрабатывалось и оптимизировалось преимущественно под ассемблерные и Фортран-подобные языки. Высокая стоимость такой техники вынуждала делить ресурсы компьютера между многими пользователями. К концу 1960-х — началу 1970-х годов благодаря интегральным схемам размеры и цены компьютеров существенно снизились, а объёмы памяти, требуемые для ИИ-программ, стали превышать адресное пространство самой популярной исследовательской платформы — PDP-10 от Digital Equipment Corporation (DEC). В итоге родилась идея создания специализированной машины для разработки и запуска масштабных систем искусственного интеллекта, в архитектуре которой были бы реализованы семантические особенности языка Лисп. Для упрощения операционной системы такие машины предполагалось сделать индивидуальными, то есть предназначенными для использования одним пользователем одновременно.

В 1973 году Ричард Гринблатт и Том Найт, программисты лаборатории искусственного интеллекта MIT, инициировали проект Lisp Machine, построив компьютер с аппаратной реализацией базовых операций Лисп в 24-битной тегированной архитектуре. Эта машина поддерживала инкрементальный (аренный) сборщик мусора. Особенность Лисп заключается в определении типов переменных во время исполнения, а не на этапе компиляции, поэтому простое сложение двух переменных на обычном «железе» требовало нескольких разрядов — из-за инструкций проверки типа и переходов; лисп-машины выполняли проверки типов параллельно с собственно операциями вычисления, что в случае конвенциональных неудачных проверок приводило к аннулированию результата и пересчёту. Подобная параллельность использовалась и для контроля выхода за пределы массива при обращении к нему, а также для прочих операций управления памятью.

В более новых моделях (например, Symbolics 3600 c 36-битными машинными словами^[3]) и до 40 бит часть разрядов каждого слова выделялась под типовую информацию, что делало архитектуру полноценной тегированной; оставшиеся биты часто использовались для реализации компактного представления списков (CDR-кодирование), сокращая объём хранимых структур почти вдвое, что значительно ускоряло сборку мусора. Ещё одним усовершенствованием стали две микрокомандные инструкции, позволяющие вызывать функции Лисп всего за 20 тактов на некоторых реализациях Symbolics.

Первая машина называлась CONS (по имени базовой функции-конструктора cons в Лисп) и неофициально именовалась «машиной Knight» (по фамилии Knight, написавшего по ней магистерскую диссертацию). Эта разработка была очень тепло принята в научном сообществе. Позднее на её базе была создана усовершенствованная версия CADR (игра слов: cadr в Лисп возвращает второй элемент списка), архитектура которой унаследовала основные идеи CONS. Около 25 предсерийных экземпляров CADR было продано (в том числе за пределы MIT) по цене около 50 000 долларов; скоро на неё портировали основные инструменты разработки (например, Emacs был перенесён с ITS в 1975 году). После одобрения на конференции по ИИ в 1978 году проект получил финансирование DARPA.

В 1979 году Рассел Нофтскер, убеждённый в коммерческом потенциале лисп-машин, предложил Гринблатту вывести разработки MIT на рынок. После затяжных переговоров, приведших к разделению коллектива лаборатории на две группы, победил подход Нофтскера, и большинство программистов выбрали идею создания стартапа с венчурным финансированием. Так возникла фирма Symbolics, нанявшая большинство ведущих хакеров лаборатории и заключившая соглашение с лабораторией об обмене технологиями.

Вскоре после этого Гринблатт основал конкурирующую компанию Lisp Machine, Inc. (LMI), финансируемую CDC, но крупная часть коллектива уже ушла в Symbolics. Символикс начал продажи CADR (под названием LM-2), а LMI предлагала LMI-CADR; Symbolics позже перешла к более продвинутой серии 3600 с расширенным адресным пространством и аппаратным ускорением функций, тогда как LMI выпустила LMI-LAMBDA по лицензии. Texas Instruments приобрела лицензию на LMI-LAMBDA и создала свою линию TI Explorer, в том числе на основе 32-битного отдельного микропроцессора, применявшегося и для NuBus-карт (например, MicroExplorer для Apple Macintosh II).

Symbolics продолжала развивать серию 3600 и свою ОС Genera, реализовала архитектуру Ivory (VLSI), для которой выпускались как автономные станции, так и платы-ускорители для разных платформ (Macintosh и др.). LMI разрабатывала K-Machine^[4], но обанкротилась до вывода системы на рынок. Некоторые лисп-машины поддерживали двойную архитектуру — с отдельным процессором Лисп и Unix.

Эти компьютеры обладали аппаратной поддержкой множества низкоуровневых операций Лисп (определения типа, CDR-кодирования, инкрементального сбора мусора), что позволяло эффективно выполнять большие лисп-приложения. Машины Symbolics были конкурентоспособны по мощности с ведущими мини-компьютерами, но не использовались для массовых вычислительных задач. Лисп-машины также находили применение вне области искусственного интеллекта — например, в компьютерной графике, моделировании и анимации.

В MIT-разработках использовался диалект Lisp Machine Lisp, восходящий к Maclisp. Операционные системы были написаны на Лисп с введением объектно-ориентированных расширений. Поздние машины поддерживали и различные версии Common Lisp (с расширениями Flavors, New Flavors и Common Lisp Object System (CLOS)).

Bolt, Beranek and Newman (BBN) создала собственную лисп-машину Jericho^[5] под управлением Interlisp, но она не поступала в продажу. После неудач вся команда перешла на работу в Xerox. Одновременно с MIT лаборатория Xerox PARC разработала ряд лисп-машин для InterLisp (а затем и Common Lisp); на идентичном оборудовании запускались также Smalltalk и Xerox Star, офисная система. К числу моделей относятся Xerox 1100 («Dolphin», 1979), 1132 («Dorado»), 1108 («Dandelion», 1981), 1109 («Dandetiger»), 1186/6085 («Daybreak»)^[6]. Операционная система Xerox Lisp-машин портирована для современных платформ в проекте Medley. Машины Xerox были известны своим передовым окружением (InterLisp-D), оконным менеджером ROOMS, ранним графическим интерфейсом и приложениями вроде NoteCards (одна из первых гипертекстовых систем).

Xerox также работала над лисп-машиной на базе RISC-процессора (Xerox Common Lisp Processor), но вывести её на рынок не удалось^[7].

В середине 1980-х компания Integrated Inference Machines (IIM) разработала прототипы Inferstar^[8].

В 1984–85 годах британская компания Racal-Norsk попыталась адаптировать суперминикомпьютер ND-500 (Norsk Data) под лисп-машину на микропрограммном уровне с запуском ПО CADR («Knowledge Processing System», KPS)^[9].

В Японии рынок пытались освоить Fujitsu (Facom-alpha)^[10], NTT («Elis»)^[11][12], Toshiba (AIP)^[13], NEC (LIME)^[14]. В университетах также создавались рабочие образцы: TAKITAC-7 (Кобэ)^[15], FLATS (RIKEN)^[16], EVLIS (Осака)^[17].

Во Франции реализованы проекты M3L^[18] (Тулузский университет Поль Сабатье) и позднее MAIA^[19].

В Германии компанией Siemens разработан RISC-сопроцессор COLIBRI^[20].

С наступлением "зимы искусственного интеллекта" и началом массового распространения микрокомпьютеров (что привело к вытеснению мини-ЭВМ и рабочих станций), дешёвые персональные ПК быстро сравнялись по производительности с лисп-машинами, несмотря на отсутствие специального оборудования. Высокая рентабельность производства аппаратуры исчезла, и большая часть производителей лисп-машин к началу 1990-х прекратила работу, уступив место компаниям по разработке ПО (например, Lucid Inc.) и фирмам, перешедшим на сервисные модели. По состоянию на 2015 год среди компаний-производителей лисп-машин действуют лишь Symbolics (реализует программную среду Open Genera и систему компьютерной алгебры Macsyma) и отдельные сервисные подразделения Xerox и TI^[21].

Создано несколько эмуляторов лисп-машин с открытым исходным кодом: CADR Emulation^[22], Symbolics L Lisp Machine Emulation^[23], E3 Project (эмуляция TI Explorer II)^[24], Meroko (TI Explorer I)^[25], Nevermore (TI Explorer I)^[26]. В октябре 2005 года MIT опубликовал исходный код CADR Lisp Machine как открытое ПО^[27].

В сентябре 2014 года Александр Бургер, разработчик PicoLisp, объявил о реализации PicoLisp в аппаратуре (PilMCU)^[28].

Архив Bitsavers содержит оцифрованную документацию по лисп-машинам Symbolics^[29], TI Explorer^[30] и MicroExplorer^[31], а также Xerox Interlisp-D^[32].

Наиболее широко лисп-машины использовались в задачах искусственного интеллекта, а также в компьютерной графике, медицинской обработке изображений и других прикладных областях.

В 1980-х коммерческие экспертные системы для лисп-машин включали Knowledge Engineering Environment (KEE) от Intellicorp, Knowledge Craft (The Carnegie Group Inc.), ART (Automated Reasoning Tool) от Inference Corporation^[33].

Изначально лисп-машины проектировались как индивидуальные рабочие станции для разработки ПО на Лисп одним пользователем без многопользовательского режима. Комплектация включала большой монохромный дисплей с растровой графикой, клавиатуру, мышь, сетевой адаптер, жёсткие диски, оперативную память объёмом от 1 МБ, последовательные интерфейсы и локальную шину расширения. По опции поддерживались цветные видеокарты, стримеры и лазерные принтеры.

Процессор лисп-машины, как правило, не выполнял лисп-код непосредственно — архитектура строилась как стековая машина, оптимизированная для компилированного Лисп. Ранние модели реализовывали ряд инструкций на уровне микрокода; часть проверки типов и обработки данных происходила аппаратно в момент выполнения инструкций. Пример: одна операция сложения могла применяться к различным числовым типам (целые, вещественные, рациональные, комплексные), результатом была очень компактная компилируемая форма лисп-кода.

Пример функции, подсчитывающей элементы списка, для которых функция-предикат возвращает истину:

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

Дизассемблированный машинный код для данной функции (для микропроцессора Ivory от Symbolics):

Команда: (disassemble (compile #'example-count))

  0  ENTRY: 2 REQUIRED, 0 OPTIONAL      ;Создание PREDICATE и LIST
  2  PUSH 0                             ;Создание COUNT
  3  PUSH FP|3                          ;LIST
  4  PUSH NIL                           ;Создание 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

Операционная система применяла виртуальную память, что позволяло увеличить адресное пространство. Управление памятью реализовывалось через сборку мусора. Все процессы работали в общей адресной среде, все данные хранились в памяти с тегом типа для динамического определения типа во время выполнения. Поддерживалось несколько потоков выполнения («процессов»), работавших в едином адресном пространстве.

Всё программное обеспечение системы, в том числе ОС, писалось на Лисп. Xerox использовала Interlisp, Symbolics/LMI/TI — Lisp Machine Lisp (произошедший от MacLisp); позднее с появлением Common Lisp часть работы системы была переписана или портирована на этот язык.

Поздние лисп-машины, такие как TI MicroExplorer, Symbolics MacIvory и UX400/1200, уже не были самостоятельными рабочими станциями, а представляли собой платы-ускорители для встраивания в Apple Macintosh II, Sun-3 или Sun-4.

Ряд моделей, например Symbolics XL1200, благодаря специальным графическим платам активно применялись для мединцинской обработки изображений, 3D-анимации и CAD.