Язык Лисп и его реализации

Решил вспомнить Лисп, знакомый еще с институтских лаб по реализации мю-лисп на персоналках в 1990-х с его бесчисленными CAAADDDR и скобками.

Книга 1978 года издания, с упоминанием БЭСМ-6, что не делает её устаревшей, так как авторы озаботились изложением общих принципов и подходов, включая реализацию транслятора. В целом изложение нравится.

Изящные примеры рекурсивных функций, позволяющие обходиться без циклов.

Интересно, что конструкция PROG, превращающая Лисп по сути в подобие императивного языка, мало того что признана авторами более простой для понимания "алголщиками", но и более эффективной в реализации на уровне транслятора.

Лисп очень похож на Форт, из которого изъяли операции управления стеком.

Кажется, что все языки с пре- и постфиксной записью типа (PLUS A B) в Лиспе или A B + в Форте и калькуляторных языках с обратной польской записью, созданы с одной целью: облегчить работу транслятору и уменьшить требуемые ресурсы при этом столь же затруднить восприятие текста человеком, ориентирующимся на стандартную инфиксную математическую запись.

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

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

Интересный факт: авторы описывают логическую реализацию на алголоподобном языке. Из этого прямо следует:

  • Алгол и его паскалеподобные наследники остаются одними из лучших в классе выразительных средств;
  • Лисп, как язык, является более высокоуровневым и специализированным.

Иными словами, если реализацию Паскаль-транслятора можно описать псевдокодом на самом Паскале, а первый транслятор Паскаля написан на самом Паскале, то с Лиспом такое не получится.

В том же разделе упоминается сборщик мусора, как один из ключевых компонентов реализации. Если вспомнить, что первые реализации Лиспа появились в 1962 году, то уверенных в новизне концепции программистов на Java или .NET ждет разочарование. Впрочем, .NET тоже является как минимум третьей попыткой реализации одной и той же архитектуры 1960-х годов.

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

В конце главы рассматривается вопрос перехода от интерпретатора к компилятору, связанные с этим особенности и ограничения.

В целом Лисп представляется хорошо переносимым и легко реализуемым языком. Однако, из книги становятся понятны и его недостатки:

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

Прогон примеров

Современной свободно распространяемой реализацией языка является Common LISP. Под ОС Ubuntu для работы с программами достаточно установить сам транслятор и среду разработки Geany.

sudo apt-get install geany
sudo apt-get install clisp

Запускаем Geany, в новом документе пишем

(WRITE "Hello, world")

Сохраняем как файл hello.lisp и запускаем по F5 (меню Build -- Execute).

"Hello, world"
 
 
------------------
(program exited with code: 0)
Press return to continue

Комментарии

Компилятор Лиспа

"Иными словами, если реализацию Паскаль-транслятора можно описать псевдокодом на самом Паскале, а первый транслятор Паскаля написан на самом Паскале, то с Лиспом такое не получится."
А вот и нет. Цитата из книги «Функциональное программирование. Применение и реализация» Хендерсона, переведённой в 1983 году: "Существенной чертой Лиспа является та лёгкость, с которой он применяется для записи своего собственного интерпретатора. В действительности, это является одним из главных его предназначений."
Что же до именно компилятора, то он полностью приведён на стр.334 той же книги, занял 70 строк на Лиспе. Объектный код уложился в половину следующей страницы... Ну, а дальше уже вступает в действие понятие раскрутки (в программном смысле слова, конечно :)

Изображение пользователя Serguei_Tarassov.

Хорошее дополнение

Однако, надо различать реальную компиляцию для исполняющих устройств от meta-circular evaluation (метациклическое воспроизведение). В этом смысле, нельзя написать meta-circular evaluator Паскаля на самом Паскале, но на Лиспе это возможно, что и сделано в книге Хендерсона.

Приведенная на стр.334 программа порождает саму себя в "объектном" коде. На самом деле это не объектный код, а промежуточное представление (то, что выдает синтаксический анализатор). Если присмотреться, то "объектный код" - это тот же Лисп, только с идентификаторами операций вместо некоторых имен, за исключением базовых, записанный в одну строку без переносов и прочей структуризации. Для выполнения такого "объектного" кода нужен некий абстрактный Лисп-процессор или соответствующая виртуальная среда, которая займется, например, вводом-выводом, управлением памятью и сборкой мусора.

В книге "Язык Лисп и его реализации" транслятор делается для совершенно конкретной БЭСМ-6, где необходимо реализовать, пусть и по минимуму, но все механизмы трансляции. Разница целей определяет средства.