Лисп-машина

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

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

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

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

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

История

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

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

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

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

Ссылки

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

Отрывок, характеризующий Лисп-машина

– Дай бог только, чтобы князь Кутузов, – сказала Анпа Павловна, – взял действительную власть и не позволял бы никому вставлять себе палки в колеса – des batons dans les roues.
Князь Василий тотчас понял, кто был этот никому. Он шепотом сказал:
– Я верно знаю, что Кутузов, как непременное условие, выговорил, чтобы наследник цесаревич не был при армии: Vous savez ce qu'il a dit a l'Empereur? [Вы знаете, что он сказал государю?] – И князь Василий повторил слова, будто бы сказанные Кутузовым государю: «Я не могу наказать его, ежели он сделает дурно, и наградить, ежели он сделает хорошо». О! это умнейший человек, князь Кутузов, et quel caractere. Oh je le connais de longue date. [и какой характер. О, я его давно знаю.]
– Говорят даже, – сказал l'homme de beaucoup de merite, не имевший еще придворного такта, – что светлейший непременным условием поставил, чтобы сам государь не приезжал к армии.
Как только он сказал это, в одно мгновение князь Василий и Анна Павловна отвернулись от него и грустно, со вздохом о его наивности, посмотрели друг на друга.


В то время как это происходило в Петербурге, французы уже прошли Смоленск и все ближе и ближе подвигались к Москве. Историк Наполеона Тьер, так же, как и другие историки Наполеона, говорит, стараясь оправдать своего героя, что Наполеон был привлечен к стенам Москвы невольно. Он прав, как и правы все историки, ищущие объяснения событий исторических в воле одного человека; он прав так же, как и русские историки, утверждающие, что Наполеон был привлечен к Москве искусством русских полководцев. Здесь, кроме закона ретроспективности (возвратности), представляющего все прошедшее приготовлением к совершившемуся факту, есть еще взаимность, путающая все дело. Хороший игрок, проигравший в шахматы, искренно убежден, что его проигрыш произошел от его ошибки, и он отыскивает эту ошибку в начале своей игры, но забывает, что в каждом его шаге, в продолжение всей игры, были такие же ошибки, что ни один его ход не был совершенен. Ошибка, на которую он обращает внимание, заметна ему только потому, что противник воспользовался ею. Насколько же сложнее этого игра войны, происходящая в известных условиях времени, и где не одна воля руководит безжизненными машинами, а где все вытекает из бесчисленного столкновения различных произволов?
После Смоленска Наполеон искал сражения за Дорогобужем у Вязьмы, потом у Царева Займища; но выходило, что по бесчисленному столкновению обстоятельств до Бородина, в ста двадцати верстах от Москвы, русские не могли принять сражения. От Вязьмы было сделано распоряжение Наполеоном для движения прямо на Москву.
Moscou, la capitale asiatique de ce grand empire, la ville sacree des peuples d'Alexandre, Moscou avec ses innombrables eglises en forme de pagodes chinoises! [Москва, азиатская столица этой великой империи, священный город народов Александра, Москва с своими бесчисленными церквами, в форме китайских пагод!] Эта Moscou не давала покоя воображению Наполеона. На переходе из Вязьмы к Цареву Займищу Наполеон верхом ехал на своем соловом энглизированном иноходчике, сопутствуемый гвардией, караулом, пажами и адъютантами. Начальник штаба Бертье отстал для того, чтобы допросить взятого кавалерией русского пленного. Он галопом, сопутствуемый переводчиком Lelorgne d'Ideville, догнал Наполеона и с веселым лицом остановил лошадь.
– Eh bien? [Ну?] – сказал Наполеон.
– Un cosaque de Platow [Платовский казак.] говорит, что корпус Платова соединяется с большой армией, что Кутузов назначен главнокомандующим. Tres intelligent et bavard! [Очень умный и болтун!]
Наполеон улыбнулся, велел дать этому казаку лошадь и привести его к себе. Он сам желал поговорить с ним. Несколько адъютантов поскакало, и через час крепостной человек Денисова, уступленный им Ростову, Лаврушка, в денщицкой куртке на французском кавалерийском седле, с плутовским и пьяным, веселым лицом подъехал к Наполеону. Наполеон велел ему ехать рядом с собой и начал спрашивать:
– Вы казак?
– Казак с, ваше благородие.