[Перевод] LISP — исследование оригинального языка ИИ
Откройте для себя один из первых языков программирования, который, по мнению Майка Бедфорда, не мог быть более непохожим на своих ранних собратьев.
В предыдущей части нашей серии, посвященной классическим языкам программирования, мы рассмотрели ALGOL, а теперь мы углубимся в изучение другого архаичного языка — LISP. Однако то, что оба они появились в 1950-х годах — это практически единственное, что их объединяет; в большинстве других аспектов они не могут быть более разными. Скорее всего, практически все языки, которыми вы когда-либо пользовались, относятся к типу императивных. LISP же является декларативным языком. Проще говоря, программирование на императивном языке предполагает определение набора операций, которые при последовательном выполнении обеспечивают требуемую функциональность. Тот факт, что существует альтернатива, может вызвать удивление, но в декларативном языке конечный результат определен, а система сама решает, как достичь поставленной цели.
Язык LISP был разработан Джоном Маккарти, который одним из первых начал изучать искусственный интеллект, и появился в 1959 году. Это делает его вторым по возрасту языком высокого уровня, используемым до сих пор. Джон также внес большой вклад в создание классического языка ALGOL, появившегося в 1960 году, хотя эти два языка не могли быть более разными.
Становится уже традицией показывать компьютеры, на которых были запущены наши классические языки, поэтому представляем вашему вниманию фотографию мэйнфрейма IBM 704, который был первой платформой LISP.
Эти два подхода можно сравнить с инструкциями, прилагаемыми к мебели для самостоятельной сборки. При императивном подходе инструкция представляет собой подробный перечень указаний, а при декларативном методе вам просто показывают картинку собранной мебели. На самом деле, это не первое знакомство с декларативным программированием. Чуть ранее мы познакомились с языком Prolog, который практически канул в Лету в 1980-х годах, а затем вновь стал популярным благодаря революции ИИ.
Мы не можем проследить его судьбу по годам, но, согласно индексу TIOBE, в 1988 г. LISP был третьим по распространенности языком. В 1988 г. он занимал третье место. Сегодня он находится на 29-й позиции, и, хотя это существенный спад с момента его расцвета, мы считаем, что для 64-летнего языка это не так уж плохо.
Декларативный язык LISP
Мы должны дать более точное определение LISP, сказав, что он не лишен императивных свойств, и хотя это, вероятно, справедливо для большинства декларативных языков, LISP более императивен, чем, например, Prolog. Таким образом, вы можете использовать LISP для написания программ, с которыми знакомы, но это будет не самое лучшее его использование, и он не будет подходящим языком для написания императивного кода.
По формальному определению, он в основном состоит из выражений и функций, а не из операторов и подпрограмм, но это уводит нас в пучину семантики. В чистых функциональных языках данные проходят через функции, но не имеют самостоятельного существования. Но стоит заметить, что LISP не является чистым языком в этом отношении.
Чтобы не увязнуть в попытках определить нишу, которую занимает LISP, эта статья носит в основном практический характер, поэтому мы оставим вам возможность сделать собственные выводы. Однако несколько других вводных замечаний все же уместны и, надеемся, более понятны. Прежде всего, как и Prolog, LISP был разработан для приложений, связанных с ИИ. В частности, он имеет сильные стороны в обработке естественного языка. Во-вторых, часто говорят, что LISP основан на выражениях, то есть все в программе является выражением и, следовательно, дает значение. Далее, название LISP расшифровывается как LISt Processing, и, в отличие от аббревиатур многих языков, оно достаточно информативно.
Если вы не проявляете особого интереса к теории вычислений, то, скорее всего, никогда не слышали о лямбда-исчислении. Однако язык LISP основан на нем, отсюда и его логотип.
Выражения в LISP имеют вид списков, а точнее, это так называемые символьные выражения (s-выражения), окруженные круглыми скобками. Ниже приводится одно из таких выражений: (defun po (ch) (list (elt ch (random(length ch))))) . Вы сразу узнаете ключевую характеристику кода LISP и поймете, почему в качестве возможного альтернативной расшифровки аббревиатуры было предложено Lots of Irritating Superfluous Parentheses (Много раздражающих лишних круглых скобок), хотя, признаемся, мы выбрали это выражение специально для того, чтобы пояснить суть, и было бы понятнее, если показать его в нескольких строках.
Начальный список
Мы предполагаем, что вы, скорее всего, захотите не только прочитать о LISP, но и попробовать его на практике, поэтому здесь представлены некоторые реализации, которые Вы сможете использовать. Все они относятся к диалекту Common LISP, который, как мы предполагаем, является наиболее распространенным в настоящее время.
Существует несколько FOSS-реализаций Common LISP для Linux — мы использовали интерпретатор GNU под названием Clisp (http://clisp.org). Он доступен в основных репозиториях и, по нашему опыту, не вызывает затруднений при установке.
В качестве альтернативы существуют онлайн-реализации, однако они являются компиляторами и работают не так, как локально установленная версия Clisp. Последняя запускается как диалог в окне терминала, и каждый раз, когда вы вводите выражение, она отвечает значением, а затем предлагает вам ввести другое выражение. Именно так работали первоначальные реализации LISP. Однако онлайн-реализации позволяют вводить полный исходный код, после чего нажать кнопку Run и увидеть результаты в области вывода. Один из вариантов, доступный для большинства языков, — Try It Online, но если вы хотите просмотреть изменения — загляните на OneCompiler, где также предусмотрена подсветка синтаксиса. Мы нашли интерпретатор Common LISP, в отличие от компилятора, на сайте https://jscl-project.github.io/, хотя это не полная реализация, и даже были замечены несколько явных ошибок.
Всегда полезно иметь примеры программ, которые можно опробовать на одном из этих интерпретаторов или компиляторов, для ознакомления или в качестве отправной точки для собственных упражнений по кодированию. Rosetta Code не испытывает недостатка в программах на Common LISP.
Первые шаги
Вам, вероятно, хорошо знакома идея о том, что программа Hello World является вводной в тот или иной язык, хотя вовсе не уверены, что вы многому научитесь на ней. Поэтому вместо этого начнем с простой арифметики. Конечно, LISP не является языком для арифметических приложений, но он может выполнять вычисления — в конце концов, это универсальный язык программирования, и многие нетехнические приложения нуждаются в выполнении тех или иных арифметических манипуляций. В частности, мы собираемся сложить 1 и 2, и вот код для этого: (+ 1 2). Если ввести это в интерпретатор LISP (но не в один из онлайн-компиляторов), то он сразу же выдаст 3. Следует отметить несколько моментов. Если вы знакомы с интерпретаторами BASIC, то знаете, что можно вводить операторы без номера строки, тогда они выполняются немедленно, но только операторы PRINT приводят к выводу чего-либо на экран. С другой стороны, интерпретатор LISP выводит на экран значение любого выражения сразу после его ввода. Это означает, что если вы напечатаете что-то вроде (print (+ 1 2)), то он дважды выведет на экран 3, что, вероятно, неожиданно. Первый раз — потому что это значение выражения, а второй раз — потому что таково назначение функции print. Следует также отметить, что (+ 1 2) фактически вызывает выполнение функции +. В отличие от большинства языков, в которых вызов функции содержит только аргументы в скобках — в LISP вызов функции представляет собой список, в котором первый элемент — это имя функции, а остальные элементы — аргументы. И, наконец, раз уж мы упомянули выражение (print (+ 1 2)), то следует сказать несколько слов о списках. Поскольку все выражения являются списками, то очевидно, что (print (+ 1 2)) — это список. Списки состоят из нескольких элементов, которые могут быть либо атомами, либо другими списками. В данном примере список содержит один атом, а именно print, и один список, а именно (+ 1 2). В свою очередь, этот список состоит из трех атомов, а именно +, 1 и 2. Теперь можно попробовать использовать и другие базовые арифметические выражения, с соответствующими операторами -, / и *. Например, как насчет написания выражений для оценки (1 + 2) * 3 и (1 + 4) / (3 — 5)?
Впервые язык LISP был запущен на мэйнфрейме IBM, и с тех пор он появился на огромном количестве компьютеров, которые появлялись и исчезали за прошедшие десятилетия. Однако одной из самых интересных категорий, безусловно, является LISP-машина. Это словосочетание относится к архитектуре машины, а таких реализаций было несколько, разработанной специально для работы с LISP.
Большинство компьютеров были универсальными — на них можно было работать с любым языком, но на момент появления LISP это было не так. И хотя обычные машины и могли работать с LISP, они не очень хорошо справлялись с его эффективным выполнением. LISP-машины были нацелены на преодоление этой проблемы. Аппаратные средства, разработанные специально для использования LISP, позволяли получить значительное преимущество в производительности. От обычных компьютеров они также отличались тем, что не были огромными многопользовательскими машинами. Напротив, они предназначались для использования одним LISP-разработчиком. В то время это было практически невиданным явлением, и пионерская разработка, начавшаяся в 1973 году, предшествовала появлению однопользовательских компьютеров. В немалой степени это было связано с тем, что Intel 8080 — первый успешный 8-разрядный микропроцессор, был выпущен только через год.
Первый компьютер на языке LISP, который на самом деле назывался LISP Machine, был разработан в лаборатории искусственного интеллекта Массачусетского технологического института. Однако он не остался в академической среде. Сотрудники института основали две дочерние компании — Symbolics и LISP Machines, производившие LISP-машины на коммерческой основе. Еще несколько компаний также разрабатывали LISP-машины, но лишь немногие продукты дожили до 1980-х годов, когда микропроцессоры произвели революцию в компьютерной индустрии, и интерес к ИИ снизился.
Разработанная в Массачусетском технологическом институте машина LISP Machine предназначена для эффективной работы с LISP. Затем появились коммерческие версии.
Далее, несмотря на свою необычность во многих отношениях, LISP имеет переменные, и им можно присваивать значения с помощью функции setq — например, (setq x 10). Несмотря на то, что многие вещи в LISP заметно отличаются от того, что ожидает большинство из нас, к этим переменным теперь можно обращаться в арифметическом выражении. Так, если вы введете предыдущее выражение setq, а затем (setq y 8), то обнаружите, что (print (* x y)) выводит ожидаемое значение 80, за исключением того, что оно, конечно же, выводится дважды.
Учитывая, что функции являются важной частью языка LISP, ведь это функциональный язык программирования — это наша следующая тема. Прежде всего, мы покажем, как определить функцию на тривиально простом примере. Это функция, возвращающая значение удвоенного своего единственного аргумента, и вот необходимое определение функции: (defun square (x) (* x x)). Если ввести это выражение, задать числовое значение x, а затем ввести выражение (square x), то можно увидеть, что оно работает именно так, как и ожидалось. Далее в качестве способа введения еще одного важного выражения — if — мы определим функцию, принимающую числовой аргумент и выдающую значение T (это специальный символ для обозначения True), если аргумент однозначный, или nil (false) в противном случае. Вот выражение, на этот раз расположенное в нескольких строках, чтобы облегчить согласование скобок, и теперь вы должны знать, что нужно сделать, чтобы его опробовать:
(defun ddigit (x)
(if (> x 9)
t
nil
)
)Теперь мы можем определить функцию, использующую еще одну ключевую особенность LISP, которая отнюдь не была гарантирована в первые годы его существования, а именно поддержку рекурсии. И для того, чтобы закольцевать изменения мы выбрали не обычную функцию факториала, а функцию для вычисления n-го числа Фибоначчи. Первые два таких числа — 1 и 1, а каждое последующее число — это сумма двух предыдущих. А вот определение функции, которое вы можете опробовать:
(defun fib(n)
(if (= n 1)
1
(if (= n 2)
1
(+ (fib (- n 1)) (fib (- n 2))))
)
)Если вы копируете в интерпретатор LISP код из внешних документов, таких как PDF-файлы или файлы Word убедитесь, что одинарные и двойные кавычки не были преобразованы в соответствующие открывающие и закрывающие символы кавычек. Если этого не заметить, то возможно придется изрядно поломать голову — говорим по собственному опыту. Программы скопированные из Rosetta Code, не страдают от этой проблемы.
Но как быть со списками?
Мы видели, что программа на LISP состоит из выражений, каждое из которых является списком, но длинная форма аббревиатуры языка — LISt Processing говорит не только об этом. В частности, она сообщает о том, что работа со списками является ключевой особенностью языка LISP, и, в общем-то, считается одним из его главных достоинств.
Прежде всего, давайте посмотрим, как присвоить список имени переменной. Как и раньше, мы используем выражение setq, но теперь нам необходимо использовать и выражение list, как видно из следующего примера: (setq x (list 1 3 5 7 9)). Если ввести это выражение в интерпретатор LISP, то он выдаст ответ (1 3 5 7 9), так что видно, что с переменной x связан список. В LISP имеется множество функций для работы со списками, но несколько из них можно попробовать, для понимания что они делают — это first, rest, third и reverse. Так, примером первой может быть (setq y (first x)). Другой полезной функцией списка является append, создающая один список из двух более коротких — например, (1 2 3) и (4 5 6) чтобы получить (1 2 3 4 5 6).
Ни один из этих коротких фрагментов кода обработки списков и близко не подошел к реальному применению, но они заложили основу. Одним из важных применений списков является работа с языками — естественным языком или языком программирования, поскольку предложение в естественном языке или высказывание в языке программирования представляет собой строку слов и/или символов и/или чисел. Разбор языка — это классическое применение LISP, но оно слишком сложно для использования здесь в качестве примера. Поэтому вместо этого мы рассмотрим пример обработки естественного языка. Рассматриваемое приложение генерирует случайные простые предложения, соответствующие синтаксическим правилам английского языка, и можем представить это как синтаксический разбор в обратном направлении. Процесс состоит в построении предложения из субъектной фразы (например, «A small man»), глагола (например, «saw» или «liked») и объектной фразы (например, «The blue table»), расположенных в таком порядке. В свою очередь, и субъект, и объект фразы состоят из артикля (неопределенного артикля «a» или определенного «the»), прилагательного («small» или «large», например) и существительного (например, «woman» или «man»), хотя субъект и объект фразы редко совпадают в предложении, поскольку артикль, прилагательное и существительное выбираются произвольно. Наконец, артикли, прилагательные, существительные и глаголы выбираются случайным образом из списка. А вот код, позволяющий это сделать:
(setf *random-state* (make-random-state t))
(defun pick-one (words) (list (elt words (random(length words)))))
(defun sentence() (append (subject-phrase) (verb) (object-phrase)))
(defun subject-phrase() (append (article) (adjective) (noun)))
(defun object-phrase() (append (article) (adjective) (noun)))
(defun article() (pick-one '(the a)))
(defun adjective() (pick-one '(large small green blue)))
(defun noun() (pick-one '(man ball woman table)))
(defun verb() (pick-one '(hit took saw liked)))
(format t "~{~a~* ~}.” (sentence))Если честно — сам так и не смог запустить этот код.
Первое выражение инициализирует генератор случайных чисел при каждом запуске программы по-разному, при этом мы заметили, что оно не работает с онлайн-интерпретатором https://jscl-project.github.io/. И, переходя к последнему выражению, можно задаться вопросом, почему мы использовали именно его, а не функцию print, которую использовали ранее. Не будем вдаваться в подробные объяснения, но функция format предоставляет гораздо больше возможностей для определения того, как именно должен быть отформатирован вывод, и, хотя мы могли бы использовать (print (sentence)), и оно бы сработало, формат вывода не был бы идеальным, поскольку, например, «A GREEN MAN TOOK THE BLUE TABLE.» будет выглядеть как (A GREEN MAN TOOK THE BLUE TABLE), другими словами, будет отформатировано не так, как должно выглядеть предложение, а в виде списка. И, наконец, мы только убедились, что созданные предложения являются синтаксически корректными, но не обязательно семантически корректными. Так, например, вполне может быть сгенерировано бессмысленное предложение The small table took the green ball (Маленький столик взял зеленый шарик). Есть много возможностей для того, чтобы использовать этот код и расширить его для генерации более сложных предложений, хотя мы сомневаемся, что при этом вы узнаете о LISP гораздо больше.
LISP сегодня
Возможно, чтобы вдохновить вас на более глубокое освоение программирования на языке LISP, мы скажем несколько слов о том, как он используется сегодня. Конечно, он используется для обработки естественного языка в приложениях ИИ, но много говорится и о его применении в написании компиляторов для языков программирования. Мы также много слышим о применении LISP не для разбора языка, а для его генерации, в частности, для написания генераторов HTML.
NASA уже несколько лет как отошло от дел, но слава LISP связана с его использованием в нескольких программах космического агентства. На основе LISP была создана автономная система управления космическим аппаратом Remote Agent на борту Deep Space 1 — первой миссии в рамках программы New Millennium. Впоследствии Remote Agent был признан лучшим программным обеспечением NASA. По данным NASA, космический аппарат, запущенный с мыса Канаверал 24 октября 1998 года, испытывал в космосе несколько передовых технологий, связанных с повышенным риском. Кроме того, аппарат столкнулся с кометой Боррелли и вернул лучшие изображения и другие научные данные, когда-либо полученные с кометы.
Однако, пожалуй, наибольшего внимания заслуживает то, как он был использован с марсоходом Sojourner — первым марсоходом, который приземлился в 1997 году. Хорошо было бы сказать, что он доставил код LISP на Красную планету, но нет, бортовой код был написан на языке C. Программа планирования, которая использовалась на Земле перед загрузкой команд на марсоход, была написана на LISP. А это немалая задача. Если бы была замечена ошибка — возможно, могла быть выдана команда, приведшая к падению Sojourner в кратер, — отменять ее было бы уже поздно. Поскольку радиосигнал доходит до Земли за 40 минут, ровер уже превратился бы в хлам стоимостью 25 млн. долларов.
Язык LISP был важным элементом миссии NASA Mars Pathfinder, в рамках которой осуществлялось управление марсоходом Sojourner на поверхности планеты.
Чтобы отвлечься от общих тем и дать представление о непреходящей значимости языка, приведем несколько современных приложений, написанных на LISP. Начнем с популярного и расширяемого текстового редактора Emacs, который был написан на собственном диалекте LISP — Emacs Lisp. Если обратиться к обработке естественного языка, то LISP — это язык, используемый в основном грамматическом движке онлайн-помощника по написанию текстов Grammarly Al. Еще одной категорией языка можно считать музыку, и здесь также не обошлось без LISP — в виде программы для создания музыкальных композиций OpusModus. И в заключение мы приведем неожиданное утверждение, а именно, что языки Common Lisp написаны на Common Lisp.
