Часть 10.

6. Напишите на PROLOG код программы, решающей задачу перевозки человека, волка,

козы и капусты.

Выполните этот код и постройте граф поиска.

Измените порядок следования правил для получения альтернативных путей решения.

Используйте оболочку, описанную в этой главе, для реализации поиска в ширину.

Опишите полезные для данной задачи эвристики.

Постройте решение на основе эвристического поиска.

7. Выполните задания 6.1-6.5 из упражнения 6 для следующей задачи.

Три миссионера и три каннибала стоят на берегу реки и хотят переправиться через нее. У берега находится лодка, в которую могут поместиться только два человека, и ни одна из групп не умеет плавать. Если на одном из берегов реки миссионеров окажется больше, чем каннибалов, то каннибалы превратятся в миссионеров. Требуется найти последовательность перемещений всех людей через реку, не влекущую за собой никаких превращений.

Воспользуйтесь своей программой для решения модифицированной задачи миссио

нера и каннибала. Например, решите эту же задачу для 4 миссионеров и 4 канниба

лов, если лодка может перевезти только двух человек. Решите эту же задачу для слу

чая, если в лодке помещается три человека. Постарайтесь обобщить решение на це

лый класс задач миссионера и каннибала.

Напишите программу на PROLOG для решения полной задачи хода конем 8x8. Ис

пользуйте при этом архитектуру продукционной системы, предложенную в этой гла

ве и главе 5. Выполните задания 6.1-6.5 из упражнения 6.

10. Выполните задания 6.1-6.5 из упражнения 6 для задачи о кувшинах с водой.

Есть два кувшина, содержащие 3 и 5 литров воды соответственно. Их можно заполнять, опорожнять и сливать воду из одного в другой до тех пор, пока один из них не окажется полным или пустым. Выработайте последовательность действий, при которой в большем кувшине окажется 4 литра воды. (Совет: используйте только целые числа.)

11. Воспользуйтесь алгоритмом path для решения задачи хода конем в этой главе. Пе

репишите его вызов в рекурсивной форме вида

path(X, Y) :- path(X, W), move(W, Y). Выполните трассировку и опишите результаты.

12. Напишите программу передачи значений на верхний уровень дерева или графа игры.

Используйте при этом:

а) минимаксный подход;

б) отсечение дерева альфа-бета;

в) оба подхода для игры в "крестики-нолики".

Напишите на PROLOG программу реализации процесса поиска для алгоритма финансо

вого консультанта, описанного в главах 2-5. Воспользуйтесь архитектурой продукцион

ной системы. Чтобы сделать программу интереснее, добавьте несколько правил.

Допишите код для системы планирования из раздела 14.5. Рассмотрите ситуацию,

требующую нового множества перемещений, добавив такие фигуры, как пирамида

или сфера.

Глава 14. Введение в PROLOG 681

Разработайте планировщик на основе поиска в ширину для примера из раздела 14.5.

Добавьте к этому алгоритму соответствующие эвристики. Можно ли определить до

пустимость эвристики?

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

зуйте ее для сохранения и обобщения успешных последовательностей перемещений.

Создайте полный набор предикатов АТД для приоритетной очереди из раздела 14.2.

Реализуйте проверку соответствия типов, позволяющую предотвратить аномалию

вида append(nil, б, 6).

Действительно ли процедура конкатенации разностных списков выполняется за ли

нейное время (раздел 14.6)? Поясните.

Создайте базу данных товаров из подраздела 14.6.2. Реализуйте проверку соответст

вия типов для набора из шести запросов на множестве этих кортежей данных.

Дополните определение языка PROLOG в PROLOG (раздел 14.7), включив в него

оператор отсечения и операции логического И и ИЛИ.

Добавьте новые правила к оболочке exshell. Добавьте новые подсистемы для вы

явления неисправностей коробки передач или тормозов.

Создайте базу знаний для новой предметной области оболочки exshell.

Работа оболочки exshell завершается неудачно, если предложенное целевое ут

верждение нельзя доказать с помощью существующей базы правил. Дополните обо

лочку exshell таким образом, чтобы при невозможности доказательства цели она

вызывала эту цель как запрос PROLOG. Добавление этой возможности потребует

изменения предикатов solve и build_proof.

Оболочка exshell позволяет пользователю отвечать на запросы, вводя степень до

верия или запросы why и how. Дополните эту оболочку таким образом, чтобы поль

зователь мог вводить ответы у для истинных запросов и п - для ложных. Эти отве

ты должны соответствовать степеням доверия 100 и -100.

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

деле 6.2. Опишите эти графы на PROLOG. Разработайте правила PROLOG для опе

раций restrict, join и simplify. Совет: создайте список предложений, конъ

юнкция которых составляет граф. Тогда операции на графах будут соответствовать

операциям управления списками.

Реализуйте систему на основе фреймов с наследованием, поддерживающую определение

трех видов ячеек: свойств класса, наследуемых подклассами, свойств, наследуемых эк

земплярами данного класса, но не его подклассами, и ненаследуемых свойств класса.

Опишите преимущества и проблемы, связанные с таким разграничением.

Реализуйте поиск от общего к частному в пространстве версий с использованием

векторов признаков (раздел 9.4.1). Специализация вектора признаков выполняется за

счет замены переменных константами. Поскольку для этого требуется указать алго

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

ходим дополнительный аргумент. Следующее определение цели верхнего уровня ил

люстрирует необходимость инициализации для рассмотренного примера. Объекты

могут быть маленькими, средними или большими, красными, синими или зелеными

и иметь форму шара, бруска или куба.

682 Часть VI. Языки и технологии программирования для искусственного интеллекта

run_general :-

general_to_specific([[_,_,_]], [],

[[small, medium, large], [red, blue, green], [ball, brick, cube]]).

Реализуйте теорию описания предметной области для примера из главы 9. Запустите

этот пример с помощью команды prolog_ebg.

Дополните определение предиката ebg таким образом, чтобы после построения но

вого правила оно добавлялось в логическую базу данных и могло использоваться в

последующих запросах. Проверьте производительность полученной системы с по

мощью теории достаточно богатой предметной области. Такую теорию можно по

строить самостоятельно либо дополнить теорию из примера с чашками, добавив

в нее описание различных типов чашек, например, чашек без ручки.

В главе 15 приводится реализация алгоритма ID3 из главы 12 на языке LISP. Создай

те с ее помощью реализацию этого алгоритма на языке PROLOG. He пытайтесь при

этом просто перевести код LISP на PROLOG. Эти языки различны и, подобно есте

ственным языкам, для описания одних и тех же объектов требуют различных идиом.

Придерживайтесь стиля PROLOG.

Постройте на PROLOG ATN-анализатор из подраздела 13.2.4. Добавьте вопросы

who и what.

33. Напишите на PROLOG код для подмножества правил грамматики английского языка

(раздел 14.9). Добавьте к рассмотренному примеру:

а) прилагательные и наречия для модификации глаголов и существительных;

б) вводные фразы (можно ли сделать это с помощью рекурсивного вызова?);

в) сложные предложения (два предложения, объединенные операцией конъюнкции).

Описанный в этой главе простой анализатор естественного языка допускает грамма

тически корректные предложения, которые могут иметь недопустимое значение,

в частности 'The man bites the dog" (Человек кусает собаку). Такие предложения

можно исключить из грамматики, добавив в нее данные о семантической допустимо

сти. Разработайте на PROLOG небольшую семантическую сеть, позволяющую рас

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

английского языка.

Переработайте анализатор на основе семантических сетей из подраздела 13.3.2,

обеспечив более богатое представление класса иерархий. Перепишите определение

предиката match_with_inheritance, чтобы вместо перечисления общих спе

циализаций двух элементов он вычислял такие специализации с помощью поиска по

иерархии типов.

Глава 14. Введение в PROLOG 683

Введение в LISP

-...Заглавие этой песни называется "Пуговки для сюртуков" - Вы хотите сказать - песня так называется? - спросила Алиса,

стараясь заинтересоваться песней.

- Нет, ты не понимаешь, - ответил нетерпеливо Рыцарь. - Это заглавие так называется. А песня называется "Древний старичок ".

- Мне надо было спросить: это у песни такое заглавие? - поправилась Аписа.

-Да нет, заглавие совсем другое. "С горем пополам "! Но это она только так называется!

- А песня эта какая ? - спросила Алиса в полной растерянности.

- Я как раз собирался тебе об этом сказать.

- Льюис Кэррол (Lewis Carroll), Алиса в Зазеркалье

Старайтесь в сложном видеть простоту. - Лао Тзу (Lao Tzu)

15.0. Введение

За более чем сорокалетнюю историю своего существования LISP зарекомендовал себя в качестве хорошего языка программирования задач искусственного интеллекта. Изначально разработанный для символьных вычислений, за время своего развития LISP был расширен и модифицирован в соответствии с новыми потребностями приложений искусственного интеллекта. LISP - это императивный язык (imperative language). Его программы описывают, как выполнить алгоритм. Этим он отличается от декларативных языков (declarative language), программы которых представляют собой определения отношений и ограничений в предметной области задачи. Однако, в отличие от таких традиционных императивных языков, как FORTRAN или C++, LISP - еще и функциональный язык (functional language): его синтаксис и семантика продиктованы математической теорией рекурсивных функций. Мощь функционального программирования в сочетании с богатым набором таких высокоуровневых средств построения символьных структур данных, как предикаты, фреймы, сети и объекты, обеспечили популярность LISP в сообществе ИИ. LISP широко используется как язык реализации средств и моделей искусственного интеллекта, особенно среди исследователей. Высокоуровневая функциональность и богатая среда разработки сделали его идеальным языком для построения и тестирования прототипов систем.

В этой главе кратко описаны синтаксис и семантика диалекта Common LISP. При этом особое внимание уделено средствам языка, используемым для программирования задач искусственного интеллекта; рассказано о применении списков для создания сим-

вольных структур данных, а также реализации интерпретаторов и алгоритмов поиска для управления этими структурами. Приводятся примеры программ на языке LISP, включающие реализацию механизмов поиска, систем проверки соответствия шаблонам; системы доказательства теорем; оболочки экспертных систем, основанные на правилах; алгоритмы для обучения и объектно-ориентированного моделирования. Мы, конечно, не сможем дать исчерпывающее описание LISP. Этой тематике посвящено много замечательных книг, ссылки на которые помещены в конце данной главы. В этой книге мы сфокусируемся лишь на использовании LISP для реализации языков представления и алгоритмов для программирования задач искусственного интеллекта.

15.1. LISP: краткий обзор

15.1.1. Символьные выражения как синтаксическая основа LISP

Синтаксическими элементами языка программирования LISP являются символьные выражения (symbolic expression), которые также называют s-выражениями (s-expression). В виде s-выражений представляются и программы, и данные, s-выражение представляет собой либо атом (atom), либо список (list). Атомы LISP - это базовые синтаксические единицы языка, включающие числа и символы. Символьные атомы состоят из букв, цифр и следующих неалфавитно-цифровых символов.

*-+/@$%^&_<>~

Приведем несколько примеров атомов LISP.

3.1416

100

х

hyphenated-name

*some-global*

nil

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

(12 3 4)

(torn тагу John Joyce) (a (b с) (d (e f) )) ( )

Заметим, что элементами списков могут быть другие списки. При этом глубина вложенности может быть произвольной, что позволяет создавать символьные структуры любой формы и сложности. Пустой список () играет особую роль при построении структур данных и управлении ими. У него даже есть специальное имя - nil; nil - это единственное s-выражение, которое одновременно является и атомом, и списком. Список - чрезвычайно гибкое средство построения структур представления. Например, его можно использовать для представления выражений из теории предикатов.

(on block-1 table)

(likes bill X)

(and (likes george kate) (likes bill merry))

686 Часть VI. Языки и технологии программирования для искусственного интеллекта

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

((2467 (lovelace ada) programmer) (3592 (babbage charles)

computer-designer)) ((key-1 value-1) (key-2 value-2) (key-3 value-3))

Важным свойством LISP является использование одинакового синтаксиса для представления не только данных, но и программ. Например, списки

(* 7 9)

(- (+ 3 4) 7)

можно интерпретировать как арифметические выражения в префиксной форме записи. LISP обрабатывает эти выражения именно так: (*7 9) означает произведение 7 на 9. Если на компьютере установлен LISP, то пользователь может вести интерактивный диалог с его интерпретатором. Интерпретатор выводит приглашение (в качестве примера в этой книге используется символ >), считывает введенные пользователем данные, пытается оценить их и в случае успеха выводит результат. Например,

> (* 7 9)

63

>

Здесь пользователь ввел выражение (* 7 9), а интерпретатор выдал результат 63 - значение, связанное с этим выражением. После этого LISP выводит следующее приглашение и ожидает ввода пользователя. Такой цикл называется циклом чтения-оценки-печати (read-eval-print loop) и составляет основу интерпретатора LISP.

Получив список, интерпретатор LISP пытается проанализировать его первый элемент как имя функции, а остальные элементы - как ее аргументы. Так, s-выражение (f x у) эквивалентно более традиционной математической записи f(x, у). Выводимое LISP значение является результатом применения этой функции к ее аргументам. Выражения LISP, которые могут быть осмысленно оценены, называются формами (form). Если пользователь вводит выражение, которое нельзя корректно оценить, то LISP выводит сообщение об ошибке и позволяет пользователю выполнить трассировку и внести исправления. Вот пример сеанса работы с интерпретатором LISP.

(+ 14 5)

19

(+ 1 2 3 4)

10

(- (+ 3 4) 7)

0

(* (+ 2 5) (- 7 (/ 21 7)))

28

(= (+ 2 3) 5)

t

(> (* 5 6) (+ 4 5))

t

(a b с)

Error: invalid function: a

Глава 15. Введение в LISP 687

В нескольких из этих примеров аргументы сами являются списками, например (- (+ 3 4) 7). Это выражение представляет композицию функций и в данном случае читается так: "вычесть 7 из результата сложения 3 и 4". Слово "результат" выделено для того, чтобы подчеркнуть, что функции - в качестве аргумента передается не s-выражение (+ 3 4), а результат его оценивания.

Оценивая функцию, LISP сначала оценивает ее аргументы, а затем применяет функцию, задаваемую первым элементом выражения, к оценке аргументов. Если аргументы сами являются функциями, то LISP рекурсивно применяет это правило для их оценивания. Таким образом, LISP допускает вложенность вызовов функций произвольной глубины. Важно помнить, что по умолчанию LISP оценивает все объекты. При этом используется соглашение, что числа соответствуют сами себе. Например, если интерпретатору передать значение 5, то LISP вернет результат 5. С символами, например х, могут быть связаны выражения. При оценивании связанных символов возвращается результат связывания. Связанные символы могут появляться в результате вызова функций (подраздел 15.1.2). Если символ не связан, то при его оценке выдается сообщение об ошибке.

Например, оценивая выражение (+(*2 3)(*3 5)), LISP сначала оценивает аргументы (*2 3)и(*3 5). Для первого аргумента LISP оценивает его параметры 2 и 3, возвращая соответствующие им арифметические значения. Эти значения перемножаются и в результате дают число 6. Аналогично результатом оценки выражения (*3 5) является 15. Затем эти результаты передаются функции сложения более высокого уровня, при оценивании которой возвращается 21. Диаграмма выполнения этих операций показана на рис. 15.1.

Рис. 15.1. Древовидная диаграмма оценивания простой функции LISP

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

(list 1 2 3 4 5)

(1 2 3 4 5)

(nth 0 '(abed))

a

(nth 2 (list 1 2 3 4 5))

3

(nth 2 ' ((a 1) (b 2) (c 3) (d 4)))

(c 3)

(length '(a b c d))

4

(member 7 '(1 2 3 4 5))

nil

(null ( ))

t

Функции работы со списками более подробно будут описаны в подразделе 15.1.5. Основные идеи этого раздела можно изложить в виде следующего определения.

688 Часть VI. Языки и технологии программирования для искусственного интеллекта

ОПРЕДЕЛЕНИЕ S-ВЫРАЖЕНИЕ s-выражение можно рекурсивно определить следующим образом.

Атом - это s-выражение.

Если Si, s2,..., sn - s-выражения, то s-выражением является и список (sb s2,..., sn).

Список - это неатомарное s-выражение.

Форма- это подлежащее оцениванию s-выражение. Если это список, то первый элемент обрабатывается как имя функции, а последующие оцениваются для получения ее аргументов.

Оценивание выражений выполняется следующим образом. Если s-выражение - число, то возвращается значение этого числа. Если s-выражение - атомарный символ, возвращается связанное с ним значение. Если этот символ не связан, возвращается сообщение об ошибке.

Если s-выражение - это список, оцениваются все его аргументы, кроме первого, а к полученному результату применяется функция, определяемая первым аргументом.

В LISP в виде s-выражений представляются и программы, и данные. Это не только упрощает синтаксис языка, но и в сочетании с возможностью управления оценкой s-выражений упрощает написание программ, обрабатывающих в качестве данных другие программы. Это облегчает реализацию интерпретаторов на LISP.

15.1.2. Управление оцениванием в LISP: функции quote и eval

В нескольких примерах из предыдущего раздела перед списками аргументов располагался символ одинарных кавычек '. Этот символ, который также может быть представлен функцией quote, представляет собой специальную функцию, которая не оценивает свои аргументы, а предотвращает их оценивание. Зачастую это делается для того, чтобы аргументы обрабатывались как данные, а не как оцениваемая форма.

Оценивая s-выражения, LISP сначала старается оценить все аргументы. Если интерпретатору передается выражение (nth 0 (a b с d) ), то он сначала пытается оценить аргумент (a b с d). Эта попытка приведет к ошибке, поскольку а- первый элемент этого s-выражения - не является функцией LISP. Чтобы предотвратить это, следует воспользоваться встроенной функцией quote. Она зависит от одного аргумента и возвращает этот аргумент без его оценки. Например,

(quote (a b с))

(a b с)

(quote (+ 1 3))

(+ 1 3)

Поскольку функция quote используется довольно часто, то в LISP допускается ее сокращенное обозначение в виде символа '. Поэтому предыдущие примеры можно переписать в следующем виде.

' (a b с)

(a b с)

' (+ 1 3)

(+ 1 3)

Глава 15. Введение в LISP 689

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

(list (+ 12) (+3 4))

(3 7)

(list '(+12) '(+34))

((+ 12) (+3 4))

В первом примере аргументы не квотированы, поэтому они оцениваются и передаются в функцию list согласно используемой по умолчанию схеме. Во втором примере функция quote предотвращает оценку, и в качестве аргументов функции list передаются сами s-выражения. И хотя (+1 2) - это осмысленная форма LISP, функция quote предотвращает ее оценивание. Возможность предотвратить оценивание программ и обращаться с ними как с данными - важное свойство LISP.

В дополнение к функции quote LISP также предоставляет в распоряжение пользователя функцию eval, позволяющую оценить s-выражение. Она зависит от одного аргумента, представляющего собой s-выражение. Этот аргумент оценивается как обычный аргумент функции. Однако результат снова оценивается, и в качестве значения выражения eval возвращается окончательный результат. Вот примеры применения функций eval и quote.

(quote (+ 2 3))

(+ 2 3)

(eval (quote (+ 2 3))) ;функция eval отменяет результат выполнения

5

;функции quote

?> (list '* 2 5) ,-строится оцениваемое s-выражение

(* 2 5)

> (eval (list '* 2 5)) /строится и оценивается выражение

10

Функция eval, по существу, обеспечивает обычное оценивание s-выражений. Благодаря функциям quote и eval существенно упрощается разработка метаинтерпретаторов (meta-interpreter)- вариаций стандартного интерпретатора LISP, определяющих альтернативные или дополнительные возможности этого языка программирования. Эта важная методология программирования иллюстрируется на примере "инфиксного интерпретатора" в разделе 15.7 и разработки оболочки экспертной системы в разделе 15.10.

15.1.3. Программирование на LISP: создание новых функций

Диалект Common LISP включает большое количество встроенных функций, в том числе следующие.

Полный спектр арифметических функций поддержки целочисленной, веществен

ной, комплексной арифметики и работы с рациональными числами.

Разнообразные функции организации циклов и управления программой.

Функции работы со списками и другими структурами данных.

Функции ввода-вывода.

690 Часть VI. Языки и технологии программирования для искусственного интеллекта

Формы для контроля оценивания функций.

Функции управления средой и операционной системой.

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

Программирование в LISP сводится к определению новых функций и построению программ на основе богатого спектра встроенных и пользовательских функций. Новые функции определяются с помощью функции defun, имя которой представляет собой сокращение фразы "define function". После определения функции ее можно использовать так же, как и любую другую встроенную функцию языка.

Предположим, что требуется определить функцию square, зависящую от одного аргумента и возводящую его в квадрат. Эту функцию в LISP можно определить следующим образом.

(defun square (x) (* хх))

Первым аргументом функции defun является имя определяемой функции, вторым - список ее формальных параметров, которые должны быть символьными атомами. Остальные аргументы - это нуль или s-выражения, составляющие тело новой функции, т.е. код LISP, определяющий ее поведение. Как и все функции LISP, defun возвращает значение, представляющее собой просто имя новой функции.

Важным результатом работы функции defun является побочный эффект, состоящий в создании новой функции и добавлении ее в среду LISP. В рассмотренном примере определяется функция square, зависящая от одного аргумента и возвращающая результат умножения этого аргумента на себя. После определения функции ее необходимо вызывать с тем же числом аргументов или фактических параметров. При вызове функции фактические параметры связываются с формальными, и тело функции оценивается с учетом этого связывания. Например, при вызове (square 5) значение 5 связывается с формальным параметром х в теле определения. Оценивая тело (* х х), LISP сначала оценивает аргументы функции. Поскольку в этом вызове параметр х связан со значением 5, то оценивается выражение (* 5 5).

Более строго синтаксис выражения defun имеет вид.

(defun <имя функции> (<формальные параметрь>) <тело функции>)

В этом определении описания элементов формы заключены в угловые скобки <>. Это обозначение будет использовано и далее. Заметим, что формальные параметры функции defun представляются в виде списка.

Вновь определенную функцию можно использовать так же, как и любую другую встроенную функцию. Предположим, что необходимо вычислить длину гипотенузы прямоугольного треугольника, зная длины двух его других сторон. Эту функцию можно определить на основе теоремы Пифагора, используя определенную ранее функцию square, а также встроенную функцию sqrt. Следующий пример кода снабжен подробными комментариями. LISP поддерживает однострочные комментарии, т.е. игнорирует весь текст, начиная с первого символа ;, и до конца строки.

(defun hypotenuse (x у) ;длина гипотенузы равна

(sqrt (+ (square x) ;корню квадратному из суммы

(square у)))) /квадратов двух других сторон.

Глава 15. Введение в LISP 691

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

15.1.4. Управление программой в LISP: условия и предикаты

Реализация ветвления в LISP тоже основывается на оценивании функций. Управляющие функции выполняют проверку и в зависимости от результатов выборочно оценивают альтернативные формы. Например, рассмотрим следующее определение функции вычисления модуля (заметим, что в LISP имеется встроенная функция abs, вычисляющая абсолютное значение числа).

(defun absolute-value (x)

(cond ((< х 0) (- х)) ;если х меньше 0, вернуть -х

((>= х 0) х))) ;в противном случае возвращается х

В этом примере используется функция cond, реализующая ветвление. Аргументом этой функции является множество пар условие-действие (condition/action pair).

(cond (<условие1> <действие1>) {<условие2> <действие2>)

(<условиеп> <действиеп>) )

Условие и действие могут быть произвольными s-выражениями, при этом каждая пара заключается в скобки. Подобно функции defun cond не оценивает все свои аргументы. Она оценивает условия по порядку до тех пор, пока одно из них не возвратит значение, отличное от nil. В этом случае оценивается соответствующее действие, и полученный результат возвращается в качестве значения выражения cond. Ни одно из других действий и ни одно из последующих условий не оцениваются. Если все условия возвращают значение nil, то и функция cond возвращает nil.

Приведем альтернативное определение функции absolute-value.

(defun absolute-value (x)

(cond ((< х 0)(- х)) ;если х меньше 0, вернуть -х

(t х))) ;в противном случае возвращается х

В этой версии учитывается тот факт, что второе условие (>= х 0) - всегда истинно, если первое условие ложно. Атом t в последнем условии оператора cond - этом атом LISP, который соответствует значению "истина". Его оценка всегда совпадает с самим атомом. Следовательно, последнее действие выполняется только в том случае, если все предыдущие условия возвращают значение nil. Эта конструкция очень полезна, поскольку позволяет задать действие, выполняемое оператором cond по умолчанию в том случае, если все предыдущие условия не выполняются.

Несмотря на то что в качестве условий оператора cond можно использовать любые оцениваемые s-выражения, в LISP существуют специальные функции, получившие название предикатов (predicate). Предикат - это функция, возвращающая логическое значение ("истина" или "ложь") в зависимости от того, удовлетворяют ли ее параметры некоторому свойству. Наиболее очевидными примерами предикатов являются операторы сравнения вида =, > и >=. Вот некоторые примеры арифметических предикатов в LISP.

692 Часть VI. Языки и технологии программирования для искусственного интеллекта

> (= 9 (+ 4 5))

t

(>= 17 4)

t

(< 8 (+ 4 2))

nil

(oddp 3) ;проверка четности аргумента

t

(minusp 6) ;проверка неотрицательности аргумента

(numberp 17) ;проверка, является ли аргумент числом

t

(nuinberp nil)

nil

(zerop 0) ;проверка равенства аргумента нулю

t

(plusp 10) ;проверка строгой положительности аргумента

t

(plusp -2)

nil

Заметим, что в этих примерах предикаты возвращают значения t или nil, а не "истина" и "ложь". Вообще, в LISP значение предиката nil соответствует логическому значению "ложь", а любое отличное от него значение (не обязательно t) обозначает "истина". Примером функции, использующей это свойство, является предикат member. Он зависит от двух аргументов, причем второй аргумент обязательно должен быть списком. Первый аргумент - это элемент списка, определяемого вторым аргументом. Предикат member возвращает суффикс второго аргумента, начальным элементом которого является первый аргумент. Если первый аргумент не является элементом списка, предикат member возвращает результат nil. Например,

> (member 3 '(1 2 3 4 5))

(3 4 5)

Такое соглашение дает следующее преимущество. Предикат возвращает значение, которое в случае истинности условия может использоваться для дальнейшей обработки. Кроме того, при таком соглашении в качестве условия в форме cond можно выбирать любую функцию LISP.

Форму if, зависящую от трех аргументов, можно использовать как альтернативу функции cond. Первым параметром является само условие. Если результатом проверки условия является ненулевое значение, то оценивается второй аргумент функции if и возвращается результат этой оценки. В противном случае возвращается результат оценки третьего аргумента. При бинарном ветвлении конструкция i f в целом обеспечивает более прозрачный и изящный код, чем функция cond. Например, с помощью формы if функцию absolute-value можно определить следующим образом.

(defun absolute-value (x) (if (< х 0) (- х) х))

Помимо функций if и cond, в LISP содержится обширный набор управляющих конструкций, в том числе итеративных, таких как циклы do и while. Хотя эти функции очень полезны и обеспечивают программисту широкие возможности управления программой, они здесь не будут обсуждаться. Эту информацию читатель сможет найти в специализированной литературе по LISP.

Глава 15. Введение в LISP 693

Одно из наиболее интересных средств управления программой в LISP связано с использованием логических операций and, or и not. Функция not зависит от одного аргумента и возвращает значение t, если этот аргумент раве,н nil, и nil - в противном случае. Функции and и or могут зависеть от любого числа параметров. Они ведут себя точно так же, как и соответствующие логические операторы. Однако важно понимать, что функции and и or основываются на условной оценке (conditional evaluation).

При обработке формы and LISP оценивает ее аргументы слева направо. Процесс завершается, если один из аргументов принимает значение nil, или после оценки последнего аргумента. По завершении работы форма and возвращает значение последнего оцененного аргумента. Следовательно, ненулевое значение возвращается только в том случае, если все аргументы функции отличны от нуля. Аналогично аргументы формы or оцениваются только до появления ненулевого значения, которое и возвращается в качестве результата. Некоторые из аргументов этих функций могут оставаться неоцененными, что иллюстрируется на примере оператора print. Помимо вывода значения своего аргумента, в некоторых диалектах LISP функция print по завершении работы возвращает значение nil.

(and (oddp 2) (print "второй оператор был оценен"))

nil

(and (oddp 3) (print "второй оператор был оценен"))

второй оператор был оценен

(or (oddp 3) (print "второй оператор был оценен"))

t

(or (oddp 2) (print "второй оператор был оценен"))

второй оператор был оценен

Поскольку в первом выражении результатом оценки (oddp 2) является nil, функция and просто возвращает значение nil без оценивания формы print. Во втором выражении результатом оценки (oddp 3) является t, и форма and оценивает выражение print. Аналогично можно проанализировать работу функции or. Поведение этих функций очень важно понимать. Дело в том, что их аргументами могут быть формы, оценка которых связана с получением побочных эффектов, подобных функции print. Условный анализ логических функций позволяет управлять процессом выполнения программы LISP. Например, форму or можно использовать для получения альтернативных решений и проверки их до тех пор, пока одно из них не даст отличный от нуля результат.

15.1.5. Функции, списки и символьные вычисления

В предыдущих разделах был рассмотрен синтаксис LISP и введено несколько полезных функций. Все они применялись для решения простых арифметических задач, однако истинная сила LISP проявляется в символьных вычислениях. Они основываются на использовании списков для построения структур данных любой сложности, состоящих из символьных и числовых атомов, а также создании форм для управления ими. Простоту обработки символьных структур данных, а также естественность построения абстрактных типов данных в LISP продемонстрируем на простом примере управления базой данных. В нашем приложении будут выполняться операции над записями, содержащими информацию о сотрудниках. В полях записи заданы имя, зарплата и табельный номер сотрудника.

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

694 Часть VI. Языки и технологии программирования для искусственного интеллекта

(defun name-field (record) (nth 0 record))

Приведем пример ее использования.

> (name-field '((da Lovelace) 45000.00 338519))

(Ada Lovelace)

Аналогично можно определить функции получения доступа к полям зарплаты и табельного номера salary-field и number-field соответственно. Поскольку имя- это тоже список, состоящий из двух элементов (собственно имя и фамилия), целесообразно определить функцию, которая на основе параметра name вычисляет либо имя, либо фамилию.

(defun first-name (name) (nth 0 name))

Вот пример ее использования.

> (first-name (name-field '((Ada Lovelace) 45000.00 338519)))

Ada

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

(list 12 3 4)

(12 3 4)

(list '(Ada Lovelace) 45000.00 338519)

((Ada Lovelace) 45000.00 338519)

Как видно из второго примера, функцию list можно использовать для определения конструктора записей в базе данных.

(defun build-record (name salary emp-number) (list name salary emp-number))

Вот пример ее использования.

> (build-record '(Alan Turing) 50000.00 135772)

((Alan Turing) 50000.00 135772)

Теперь с помощью функций доступа и build-record можно создать функцию, возвращающую модифицированную копию записи. Например,

(defun replace-salary-field (record new-salary) (build-record (name-field record)

new-salary

(number-field record)))

> (replace-salary-field '((Ada Lovelace) 45000.00 338519) 50000.00)

((Ada Lovelace) 50000.00 338519)

Заметим, что эта функция на самом деле не обновляет саму запись, а создает ее модифицированную копию. Эту обновленную версию записи можно сохранить, связав ее с глобальной переменной с помощью функции setf (подраздел 15.1.8). Хотя в LISP существуют формы, позволяющие модифицировать конкретный элемент списка в исходной структуре (без создания копии), хороший стиль программирования не предполагает их использования, поэтому в этой книге они не упоминаются. Если в приложении ис-

Глава 15. Введение в LISP 695

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

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

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

15.1.6. Списки как рекурсивные структуры

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

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

(car ' (a b с) ) ; Заметим, что список квотирован

а

(cdr '(а Ь с))

(Ь с)

(саr '((а b) (с d))) ;первый элемент списка может быть списком

(а Ь)

(cdr '((а b) (с d)))

((с d))

(car (cdr '(a b c d)))

b

Функции car и cdr основаны на рекурсивном подходе к выполнению операций со списочными структурами. Операции над каждым элементом списка выполняются следующим образом.

Если список пуст, операция завершается.

В противном случае обрабатывается этот элемент и осуществляется переход к сле

дующему элементу списка.

696 Часть VI. Языки и технологии программирования для искусственного интеллекта

По этой схеме можно определить множество полезных функций работы со списками. Например, язык Common LISP включает предикат member, определяющий принадлежность некоторого s-выражения списку, и length, позволяющий найти длину списка. Определим свои собственные версии этих функций. Функция my-member будет зависеть от двух аргументов - произвольного s-выражения и списка my-list. Она должна возвращать nil, если s-выражение не является элементом списка my-list. В противном случае она будет возвращать список, содержащий это s-выражение в качестве первого элемента.

(defun my-member (element my-list)

(cond ((null my-list) nil) ;элемент не является членом списка

((equal element (car my-list)) my-list) ;элемент найден

(t (my-member element (cdr my-list))))) ;шаг рекурсии

Вот пример использования функции my-member.

(my-member 4 '(1 2 3 4 5 6))

(4 5 6)

(my-member 5 '(abed))

nil

Аналогично определим собственные версии функций length и nth.

(defun my-length (my-list) (cond ((null my-list) 0)

(t (+ (my-length (cdr my-list)) 1)))) (defun my-nth (n my-list)

(cond ((zerop n) (car my-list)) ;функция zerop проверяет

;равенство нулю

(t (my-nth (-n 1) (cdr my-list))))) ;своего аргумента

Интересно отметить, что приведенные примеры использования функций саг и cdr в то же время иллюстрируют историю развития LISP. Ранние версии языка содержали не так много встроенных функций, как диалект Common LISP. Программистам приходилось самим определять функции проверки принадлежности элемента списку, вычисления длины списка и т.д. Со временем наиболее общие из этих функций вошли в стандарт языка. Common LISP - легко расширяемый язык. Он позволяет легко создавать и использовать собственные библиотеки повторно используемых функций.

Помимо саг и cdr LISP содержит множество функций построения списков. Одна из них- list, зависящая от произвольного числа аргументов, представляющих собой s-выражения. Функция оценивает их и возвращает список результатов (подраздел 15.1.1). Более примитивным конструктором списков можно считать функцию cons, параметрами которой являются два s-выражения. Эти параметры оцениваются, и возвращается список, первым элементом которого является значение первого аргумента, а хвостом - значение второго.

(cons 1 '(2 3 4))

(12 3 4)

(cons ' (a b) ' (с d e) )

((a b) с d e)

Функцию cons можно считать обратным преобразованием для функций саг и cdr, поскольку результатом применения функции саг к значению, возвращаемому функцией cons,

Глава 15. Введение в LISP 697

всегда является первый аргумент cons. Аналогично результатом применения функции cdr к значению, возвращаемому формой cons, всегда является второй аргумент этой формы.

(car (cons 1 '(2 3 4)))

1

(cdr (cons 1 '(2 3 4)))

(2 3 4)

Приведем пример использования функции cons. Для этого определим функцию filter-negatives, параметром которой является числовой список. Эта функция должна удалять из списка все отрицательные значения. Функция filter-negatives рекурсивно проверяет элементы списка. Если первый элемент отрицателен, он исключается, и функция возвращает результат фильтрации отрицательных элементов хвоста списка, определяемого функцией cdr. Если первый элемент списка положителен, он включается в результат фильтрации отрицательных чисел хвоста.

((defun filter-negatives (number-list)

(cond ((null number-list) nil) ;условие останова

((plusp (car number-list)) (cons (car number-list)

(filter-negatives (cdr number-list)))) (t (filter-negatives (cdr number-list)))))

Вот пример вызова этой функции.

> (filter-negatives '(1-12-23 -4))

(1 2 3)

Это типичный пример использования функции cons в рекурсивных функциях над списками. Функции саг и cdr делят список на части и "управляют" рекурсией, a cons формирует результат по мере "развертывания" рекурсии. Еще один пример использования функции cons - переопределение встроенной функции append.

(defun my-append (listl Iist2) (cond ((null listl) Iist2)

(t (cons (car listl) (my-append (cdr listl) Iist2)))))

Проиллюстрируем вызов этой функции.

> (my-append '(12 3) '(456))

(12 3 4 5 6)

Заметим, что по такой же рекурсивной схеме строятся определения функций my-append, my-length и my-member. В каждом из этих определений для удаления элемента из списка используется функция cdr. Это обеспечивает возможность рекурсивного вызова укороченного списка. Рекурсия завершается, если список пуст. В процессе рекурсии функция cons перестраивает решение. Эта схема зачастую называется cdr-рекурсией (cdr-recursion) или хвостовой рекурсией (tail resursion), поскольку функция cdr используется для получения хвоста списка.

15.1.7. Вложенные списки, структуры и рекурсия car-cdr

Хотя обе функции cons и append предназначены для объединения небольших списков, важно понимать различие между ними. При вызове функции cons ее параметрами являются

698 Часть VI. Языки и технологии программирования для искусственного интеллекта

два списка. Первый из них становится первым элементом второго списка. Функция append возвращает список, членами которого являются элементы обоих аргументов.

(cons '(12) '(3 4))

((1 2) 3 4)

(append '(12) '(3 4))

(12 3 4)

Списки (1 2 3 4)и((1 2) 3 4) имеют принципиально разную структуру. Это различие можно отобразить графически, установив изоморфизм между списками и деревьями. Простейший способ построения соответствия между списками и деревьями - создание для каждого списка узла без метки, потомками которого являются элементы этого списка. Это правило рекурсивно применяется ко всем элементам списка, которые сами являются списками. Атомарные элементы становятся листовыми узлами дерева. При таком построении два указанных выше списка генерируют деревья различной структуры (рис. 15.2).

Рис. 15.2. Представление списков в виде деревьев для отображения различий в их структуре

Этот пример иллюстрирует широкие возможности списков по представлению данных. В частности, их можно использовать как средство представления любой древовидной структуры, в том числе дерева поиска или дерева грамматического разбора (рис. 15.1). Кроме того, вложенные списки обеспечивают возможность иерархического структурирования сложных данных. В примере с записями о сотрудниках из подраздела 15.1.4 поле имени само является списком, состоящим из собственно имени и фамилии. Этот список можно рассматривать как единую сущность, а можно получать доступ к каждому его компоненту.

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

> (length '((12) 3 (1 (4 (5)))))

3

Функция length возвращает значение 3, поскольку список состоит из 3 элементов: (1 2), 3 и (1 (4 (5))). Это, конечно, правильно, и такое поведение функции корректно.

С другой стороны, если требуется подсчитать количество атомов в списке, необходимо определить другую схему рекурсии, которая при сканировании элементов списка будет "вскрывать" неатомарные элементы списка и рекурсивно выполнять операции по подсчету атомов. Эту функцию можно определить так.

(defun count-atoms (my-list) (cond ((null my-list) 0) ((atom my-list) 1) (t (+ (count-atoms (car my-list)) ;вскрываем элемент

(count-atoms (cdr my-list)))))) ;сканируем список

> (count-atoms '((1 2) 3 (((4 5 (6))))))

6

Это определение- пример рекурсии car-cdr. Помимо рекурсивного прохода по списку с помощью формы cdr, функция count-atoms выполняет рекурсию по перво-

Глава 15. Введение в LISP 699

му элементу, получаемому с помощью формы саг. Затем функция + комбинирует оба результата при формировании ответа. Рекурсия завершается при достижении атома или конца списка. Такую схему можно рассматривать как добавление второго измерения к простой cdr-рекурсии, обеспечивающего "заглубление" в каждый из элементов списка. Сравните диаграммы вызовов функций length и count-atoms, представленные на рис. 15.3. Обратите внимание на сходство рекурсии car-cdr и рекурсивного определения s-выражений в подразделе 15.1.1.

Рис. 15.3. Диаграммы линейной и древовидной схемы рекурсии

700 Часть VI. Языки и технологии программирования для искусственного интеллекта

Еще одним примером использования рекурсии car-cdr является определение функции flatten. Она зависит от одного аргумента, представляющего собой список произвольных структур, и возвращает неиерархический список, состоящий из тех же атомов, расположенных в том же порядке. Обратите внимание на аналогию определений функций flatten и count-atoms. В обеих функциях для разбиения списков и управления рекурсией используется схема car-cdr, рекурсия прекращается при достижении нулевого или атомарного элемента, и для построения ответа по результатам рекурсивных вызовов в обоих случаях применяется вторая функция (append или +).

(defun flatten (1st)

(cond ((null 1st) nil)

((atom 1st) (list 1st))

(t (append (flatten (car 1st))(flatten (cdr 1st))))))

Вот пример вызова функции flatten.

(flatten '(a (b c) (((d) e f))))

(a b с d e f)

(flatten '(a b с) ) ,-этот список уже не содержит иерархии

(a b с)

(flatten '(1 (2 3) (4 (5 6) 7)))

(12 3 4 5 6 7)

Рекурсия car-cdr является основой реализации процедуры унификации в разделе 15.6.

15.1.8. Связывание переменных с помощью функции set

Язык LISP строится на теории рекурсивных функций. Ранние его версии могут служить примером функционального или прикладного языка программирования. Важным аспектом чисто функциональных языков является отсутствие побочных эффектов в результате выполнения функций. Это означает, что возвращаемое функцией значение зависит только от определения функции и фактических параметров при ее вызове. Хотя LISP основывается на математических функциях, можно определить формы, нарушающие это свойство. Рассмотрим следующие команды LISP.

(f 4)

5

(f 4)

б

(f 4)

7

Заметим, что f не является полноценной функцией, поскольку ее результат определяется не только фактическим параметром: различные вызовы с параметром 4 возвращают разные значения. Дело в том, что при выполнении этой функции создается побочный эффект, который сказывается на ее поведении при последующих вызовах. Функция f реализована с помощью встроенной в LISP функции set.

(defun f (x)

(set 'inc (+ inc 1)) (+ x inc))

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

Глава 15. Введение в LISP 701

ленному первым аргументом. Если в рассмотренном примере значение переменной inc инициализировать нулем с помощью вызова (set ' inc 0), то при последующих вызовах значение этого параметра будет увеличиваться на 1.

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

(set 'х 0)

0

(setq х 0)

0

Хотя использование функции set позволяет создавать в LISP объекты, не являющиеся чистыми функциями в строго математическом смысле, возможность связывания значения с переменной глобального окружения - очень полезное свойство. Многие задачи программирования наиболее естественно реализовать на основе определения объектов, состояние которых сохраняется между вызовами функции. Классическим примером таких объектов является начальное число, используемое генератором случайных чисел. Его значение изменяется и сохраняется при каждом вызове функции. Аналогично в системе управления базой данных (в частности, описанной в подразделе 15.1.3) естественно хранить базу данных, связав ее с переменной в глобальной среде.

Таким образом, существует два способа присваивания значения символу: явный - с помощью функции set или setq, и неявный, когда при вызове функции фактические параметры вызова связываются с формальными параметрами в определении функции. В рассмотренных выше примерах все переменные в теле функции были либо связанными (bound variable) либо свободными (free variable). Связанная переменная - это переменная, используемая в качестве формального параметра в определении функции, а свободная переменная встречается в теле функции, но не является формальным параметром. При вызове функции все связи переменной в глобальной среде сохраняются, а сама связанная переменная ассоциируется с фактическим параметром. После завершения выполнения функции исходные связи восстанавливаются. Поэтому присваивание значений связанной переменной в теле функции не влияет на глобальные связи этой переменной. Это видно из следующего примера.

> (defun foo (x)

(setq x (+ х 1)) ;инкрементирование связанной переменной х

х)

;возврат значения foo

(setq у 1)

1

(foo у)

2

у ;значение у не изменилось

1

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

702 Часть VI. Языки и технологии программирования для искусственного интеллекта

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

(setq x 0)

0

(setf x 0)

0

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

> (setf х '(a b с)) ;х связывается со списком

(а Ь с)

> х ;значение х - это список

(а Ъ с)

> (setf (car x) 1) .-результат вызова функции саг для х соответствует

1

;адресу в памяти

> х ;функция setf изменила значение первого элемента х

(1 Ь с)

> (setf (cdr x) '(2 3))

(2 3)

> х ;теперь у х изменился хвост

(1 2 3)

Функцию setf можно вызывать для большинства форм LISP, соответствующих адресу в памяти. В качестве первого параметра могут выступать символы и функции, в частности, car, cdr и nth. Таким образом, функция setf обеспечивает большую гибкость при создании структур данных LISP, управлении ими и даже замене их компонентов.

15.1.9. Определение локальных переменных с помощью функции let

Функция let - это еще одна полезная форма явного управления связыванием переменных. Она позволяет создавать локальные переменные. В качестве примера использования функции let рассмотрим функцию вычисления корней квадратного уравнения. Функция quad-roots зависит от трех параметров a, b и с уравнения ахг+Ьх+с=0 и возвращает список, состоящий из двух корней этого уравнения. Корни вычисляются по формуле

Например, так.

(quad-roots 12 1)

(-1,0 -1,0)

(quad-roots 16 8)

(-2,0 -4,0)

Глава 15. Введение в LISP 703

При вычислении значения функции quad-roots значение выражения

*\Ь2-Аас

используется дважды. Из соображений эффективности и элегантности это значение можно вычислить один раз и сохранить его в локальной переменной для вычисления обоих корней. Поэтому исходная реализация функции quad-roots может иметь такой вид.

(defun quad-roots-1 (a b с)

(setq temp (sqrt ( - (* b b) (* 4 a c)))) (list (/ (+ (- b) temp) (* 2 a)) (/ (- (- b) temp) (* 2 a))))

Заметим, что при такой реализации предполагается отсутствие мнимых корней уравнения. Попытка вычислить квадратный корень из отрицательного числа приведет к неудачному завершению функции sqrt с кодом ошибки. Модификация кода с целью обработки этой ситуации не имеет прямого отношения к рассматриваемому вопросу.

Хотя с учетом этого исключения код функции корректен, оценивание тела приведет к побочному эффекту установки значения переменной temp в глобальном окружении.

(quad-roots-1 12 1)

(-1,0 -1,0)

temp

0.0

Более предпочтительно сделать переменную temp локальной для функции quad-roots и исключить этот побочный эффект. Для этого можно использовать блок let. Вот синтаксис этого выражения.

(let (<локальные-переменные>) <выражения>)

Элементы списка (<локальные-переменные>) - это либо символьные атомы либо пары вида

(<символ> <выражение>)

При оценивании формы (или блока) let устанавливается локальное окружение, состоящее из всех символов списка (<локалъные-переменные>). Если некоторый символ является первым элементом пары, то второй элемент оценивается, и результат оценки связывается с этим символом. Символы, не включенные в пары, связываются со значением nil. Если некоторые из этих символов уже связаны в глобальном окружении, то глобальные связи сохраняются и восстанавливаются при выходе из блока let.

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

Поведение блока let можно проиллюстрировать на следующем примере.

(setq a 0)

0

(let ((а 3) Ь)

(setq b 4) (+ a b)) 7

а

0

b

ERROR - b is not bound at top level.

704 Часть VI. Языки и технологии программирования для искусственного интеллекта