Лисп-машина

Лисп-машина в музее MIT

Лисп-машина — универсальная вычислительная машина, архитектура которой оптимизирована для эффективного выполнения программ на языке Лисп.

Эквивалентна (абстрактной) машине Тьюринга (и обычному персональному компьютеру) по критерию полиноминальной сводимости.

Несмотря на то, что лисп-машины никогда не были широко распространены (около 7 тыс. штук во всём мире на 1988 год), многие распространённые ныне идеи и программные технологии были впервые разработаны с помощью лисп-машин, например на тех, что использовались в исследовательском центре Xerox PARC были реализованы:

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

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

История

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

Проверка типов впоследствии была улучшена и автоматизирована, когда традиционный размер машинного слова в 32 бита был увеличен до 36 бит у лисп-машин модели Symbolics 3600, и даже до 40 бит или больше (обычно избыточные биты использовались для кодов коррекции ошибок). В первом блоке добавочных битов хранился тип данных (что и делало архитектуру теговой), а оставшиеся использовались для CDR-кодирования (когда обычные элементы в связном списке сжимались примерно вдвое), упрощая сборку мусора на порядок. Дальнейшим усовершенствованием стали две инструкции, которые специальным образом поддерживали функции Лиспа, уменьшая стоимость вызова функций до 20 тактов (в некоторых реализациях Symbolics).

Первая машина в честь оператора конструирования списков в Лиспе была названа CONS. Часто её неправильно называют «машиной Найта», возможно из-за того, что Найт защитил по ней диссертацию. Её улучшенная версия — CADR — основана на примерно той же архитектуре. Было продано около 25 прототипов CADR по цене примерно $50 тыс. Она стала популярной в среде увлечённых разработчиков, и на неё были быстро портированы многие популярные программы (например, Emacs в 1975 году). На конференции по проблемам искусственного интеллекта, которую проводил Массачусетский технологический институт в 1978 году, она была так хорошо воспринята, что DARPA стала финансировать её разработку.

На определённом этапе экспоненциального роста вычислительной мощности (закон Мура) аппаратная поддержка лямбда-исчисления утратила экономический смысл для компьютеров широкого потребления, и производители лисп-машин ушли с рынка.

Ссылки

• Symbolics Lisp Machine Museum
• Newquist, Harvey. The Brain Makers. Sams Publishing, 1994. ISBN 0-672-30412-0