2.12. Язык Лисп

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

ИПЛ, с помощью которого можно было обрабатывать списки. ИПЛ является одним из предшественников языка программирования Лисп (LISP - List Programming), разработанного Дж. Маккарти в 1960 г.

Среди языков программирования Лисп занимает особое место. Наиболее популярным он стал в среде специалистов по искусственному интеллекту в США, где в качестве стандартного получил распространение его диалект COMMONLISP [G. L. Steel, 1984].

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

Следует однако отметить, что в настоящее время инструментарием для обработки списков обладают и такие развитые языки программирования, как Фортран, ПЛ/1, Паскаль, Ада и др.

2.12.1. Основные элементы языка Лисп

Синтаксис

Выражения языка Лисп называются также -выражениями. Такое -выражение представляет собой либо атом, либо список.

Атом представляется каким-либо алфавитно-цифровым именем (т. е. в сущности числом). Список представляет собой некоторую внутреннюю часть, заключенную в скобки.

Синтаксис языка Лисп в форме Бэкуса — Наура определяется следующим образом:

Таким образом, всякое -выражение представляет собой набор атомов и списков, например:

Элементарные функции

Как и во всех языках программирования, некоторые предварительно определенные атомы являются функциями, аргументы которых представляют собой следующие за ними -выражения. В свою очередь аргумент сам может быть функцией, которую нужно вычислить. При этом надо иметь возможность определить, что представляет собой данный элемент — значение выражения или же символьное имя какого-то -выражения. В первом случае перед выражением ставится апостроф, например или же пишут в развернутой форме: (QUOTE L). Апостроф запрещает вычисление следующего за ним -выражения, которое воспринимается программой в этом случае без изменений.

Для задания выражения используется функция SETQ:

где значение -выражения не вычисляется. Стрелка в данном случае означает “выдать в качестве величины”. В общем случае всякое -выражение, поступающее в машину, тут же вычисляется. Так, например, при использовании апострофа имеем

Кроме этого, функция связывает полученный при ее применении результат с атомом:

Две фундаментальные функции CAR и CDR позволяют осуществлять обработку списков, если последние не пусты. Функция CAR определяется следующим образом: непустой список первое подвыражение списка. Ниже приводятся примеры использования функции

(см. скан)

Функция CDR определяется следующим образом:

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

Примеры использования функции

Не совсем обычные обозначения функций CAR и CDR сложились исторически в процессе первой реализации языка Лисп на ЭВМ типа они являлись относительными адресами регистра и декремента регистра. Наличие в языке этих двух функций и разнообразных их сочетаний является очень удобным при программировании задач искусственного интеллекта. Для этого, в частности, используются следующие сокращенные формы записи:

В Лиспе имеется функция действие которой противоположно действию функций CAR и Она определяется следующим образом:

Пример действия функции

Второй аргумент функции может быть пустым списком который может также обозначаться как Например:

В общем случае, каково бы ни было выражение имеем

Ниже рассмотрено обычное машинное представление объектов и алгоритм вычисления (оценивания) значений выражений в Лиспе.