Часть 11.

В этом примере до выполнения блока let переменная а связана со значением 0, a b - не связана на верхнем уровне окружения. При оценивании формы let а связывается со значением 3,ab - cnil. Функция setq присваивает переменной b значение 4, после чего оператор let возвращает значение суммы а и Ь. После завершения работы формы let восстанавливаются предыдущие значения переменных а и Ь, в том числе несвязанный статус переменной Ь.

С помощью оператора let функцию quad-roots можно реализовать без глобальных побочных эффектов.

(defun quad-roots-2 (a b с) (let (temp)

(setg temp (sqrt (- (*bb) (* 4 a c))))

(list (/ (+ (- b) temp) (* 2 a)) (/ (- (- b) temp) (* 2 a)))))

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

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

(let ((temp (sqrt (- (* b b) (* 4 a c) ) ) )

(denom (* 2 a)))

(list (/ (+ (- b) temp) denom)

(/ (- (- b) temp) denom))))

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

15.1.10. Типы данных в Common LISP

Язык LISP включает большое количество встроенных типов данных. К ним относятся целые числа, числа с плавающей точкой, строки и символы. В LISP также содержатся такие структурированные типы, как массивы, хэш-таблицы, множества и структуры. Со всеми этими типами связаны соответствующие операции и предикаты проверки принадлежности объектов данному типу. Например, для списков поддерживаются функции идентификации объекта как списка listp, определения пустоты списка null, а также конструкторы и функции доступа list, nth, car и cdr.

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

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

(setq x 'a)

a

(+ x 2)

> Error: a is not a valid argument to +.

> While executing: +

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

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

Естественная поддержка абстрактных типов данных.

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

Использование функции cond и рекурсии для управления программой.

Рекурсивная природа списочных структур и рекурсивные схемы управления ими.

Использование функций quote и eval для управления оцениванием форм.

Использование функций set и let для управления связыванием переменных и

побочными эффектами.

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

15.2. Поиск в LISP: функциональный подход к

решению задачи переправы человека, волка, козы и капусты

Чтобы продемонстрировать возможности программного решения задач искусственного интеллекта на языке LISP, вернемся к задаче перевозки человека, волка, козы и капусты.

Человеку требуется переправиться через реку и перевезти с собой волка, козу и капусту. На берегу реки находится лодка, которой должен управлять человек. Лодка одновременно может перевозить не более двух пассажиров (включая лодочника). Если волк останется на берегу с козой, то он ее съест. Если коза останется на берегу с капустой, то она уничтожит капусту. Требуется выработать последовательность переправки через реку таким образом, чтобы все четыре пассажира были доставлены в целости и сохранности на другой берег реки.

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

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

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

из четырех элементов, в которых каждый компонент обозначает местоположение человека, волка, козы и капусты соответственно. Так, список (е w e w) задает состояние, при котором человек (первый элемент) и коза (третий элемент) находятся на восточном берегу, а волк и капуста - на западном. Базовыми функциями, определяющими состояние данных этого типа, являются конструктор make-state и четыре функции, доступа farmer-side, wolf-side, goat-side и cabbage-side. Параметром конструктора является местоположение человека, волка, козы и капусты. Эта функция возвращает состояние. Параметрами функций доступа является состояние, а возвращаемым значением - местоположение объекта. Эти функции можно определить так.

(defun make-state (f w g с) (list f w g с)) (defun farmer-side (state)

(nth 0 state)) (defun wolf-side (state)

(nth 1 state)) (defun goat-side (state)

(nth 2 state)) (defun cabbage-side (state)

(nth 3 state))

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

При каждом переходе в новое состояние функции доступа используются для разделения состояния на его компоненты. Функция opposite (которая вскоре будет определена), задает новое местоположение объектов, пересекающих реку, а функция make-state - трансформирует его в новое состояние. Например, функцию farmer-takes-self можно определить так.

(defun farmer-takes-self (state)

(make-state (opposite (farmer-side state))

(wolf-side state) (goat-side state) (cabbage-side state)))

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

(safe ' (w w w w) ) /состояние безопасно, возвращается без изменений

(w w w w)

(safe '(е w w e)) ;волк съест козу, вернуть nil

nil

(safe '(w w e e)) ;коза съест капусту, вернуть nil

Функция safe используется в каждой функции перехода для фильтрации опасных состояний. Так, любой переход, приводящий к "небезопасному" состоянию, возвращает не это состояние, а значение nil. Рекурсивный алгоритм вычисления пути проверяет возвращаемое значение, и, если оно равно nil, отбрасывает это состояние. Таким образом функция safe обеспечивает реализацию проверки условия до определения возмож-

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

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

(defun farmer-takes-self (state)

(safe (make-state (opposite (farmer-side state))

(wolf-side state) (goat-side state) (cabbage-side state)))) (defun farmer-takes-wolf (state)

(cond ((equal (farmer-side state) (wolf-side state))

(safe (make-state (opposite (farmer-side state))

(opposite (wolf-side state)) (goat-side state) (cabbage-side state)))) (t nil))) (defun farmer-takes-goat (state)

(cond ((equal (farmer-side state) (goat-side state))

(safe (make-state (opposite (farmer-side state))

(wolf-side state) (opposite (goat-side state)) (cabbage-side state)))) (t nil))) (defun farmer-takes-cabbage (state)

(cond ((equal (farmer-side state) (cabbage-side state))

(safe (make-state (opposite (farmer-side state))

(wolf-side state) (goat-side state) (opposite (cabbage-side state))))) (t nil)))

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

defun opposite (side)

(cond ((equal side 'e) 'w)

((equal side 'w) 'e)))

В LISP существует множество различных предикатов для проверки равенства. Наиболее простой - eq - возвращает значение "истина" только в том случае, если его аргументы соответствуют одному и тому же объекту, т.е. указывают на одну и ту же область памяти. Более сложным является предикат equal, для истинности которого все его аргументы должны быть синтаксически идентичными.

(setq |1 '(1 2 3))

(1 2 3)

(setq |2 '(123))

(12 3)

(equal |1 |2)

t

(eq 11 |2)

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

nil

(setq |3 |1)

(1 2 3)

(eq |1 |3)

t

Функция safe определена на основе формы cond. Это позволяет проверить два "опасных" условия: человек расположен на противоположном берегу от волка и козы, и человек находится на противоположном берегу от козы и капусты. Если состояние безопасно, функция safe возвращает его неизменным, в противном случае она возвращает nil.

(defun safe (state)

(cond ((and (equal (goat-side state) (wolf-side state) ) ;волк съест козу

(not (equal (farmer-side state) (wolf-side state)))) nil) ((and (equal (goat-side state) (cabbage-side state))

;коза съест капусту

(not (equal (farmer-side state) (goat-side state)))) nil) (t state)))

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

(defun path (state goal)

(cond ((equal state goal) 'success)

(t (or (path (farmer-takes-self state) goal)

(path (farmer-takes-wolf state) goal) (path (farmer-takes-goat state) goal) (path (farmer-takes-cabbage state) goal)))))

Эта версия функции path представляет собой простой перевод рекурсивного алгоритма поиска пути с "человеческого" языка на LISP. Она содержит несколько ошибок, которые необходимо устранить. Однако эта версия отражает основную структуру алгоритма, поэтому до начала устранения ошибок ее следует проанализировать подробнее. Первый оператор cond служит для проверки успешного завершения алгоритма поиска. При соответствии исходного состояния целевому equal state goal рекурсия прекращается и возвращается атом success. В противном случае функция path генерирует 4 дочерних узла на графе поиска, а затем вызывает сама себя для каждого из этих узлов.

Обратите внимание на использование формы or для управления оцениванием аргументов. Напомним, что функция or оценивает свои аргументы до тех пор, пока один из них не возвращает значение, отличное от nil. В этом случае вызов функции or прекращается, остальные ее аргументы не оцениваются, а результатом считается это ненулевое значение. Таким образом, функция or не только используется как логический оператор, но и обеспечивает способ управления ветвлением в пространстве поиска. Здесь применяется форма or, а не cond, поскольку проверяемое и возвращаемое ненулевое значение совпадают.

Неудобство этого определения состоит в том, что функция перехода может возвращать значение nil, если переход невозможен или ведет к "опасному" состоянию. Чтобы предотвратить генерацию узла-потомка для состояния nil, необходимо сначала проверить, является ли текущее состояние нулевым. Если да, то функция path должна возвращать nil.

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

Еще одним вопросом, требующим решения при реализации функции path, является выявление потенциальных циклов в пространстве поиска. Через несколько шагов работы описанной выше функции path человек будет возить себя самого с одного берега на другой. Следовательно, алгоритм попадет в бесконечный цикл между идентичными состояниями, которые уже были посещены. Для предотвращения такой ситуации в функцию path нужно добавить третий параметр been-list, представляющий список уже посещенных состояний. При каждом рекурсивном вызове функции path для нового состояния мира родительское состояние будет добавляться в список been-list. Для проверки отсутствия в этом списке текущего состояния можно использовать предикат member. Вот новое определение функции path.

(defun path (state goal been-list) (cond ((null state) nil)

((equal state goal) (reverse (cons state been-list))) ((not (member state been-list :test #'equal)) (or (path (farmer-takes-self state) goal (cons state been-list))

(path (farmer-takes-wolf state) goal

(cons state been-list))

(path (farmer-takes-goat state) goal

(cons state been-list))

(path (farmer-takes-cabbage state) goal

(cons state been-list))))))

Здесь member - это встроенная функция Common LISP, которая ведет себя так же, как и пользовательская функция my-member, определенная выше в этой главе. Единственным различием между этими функциями является включение в список аргументов параметра : test #' equal. В отличие от "доморощенной" функции my-member, такая форма позволяет программисту указать функцию, которая будет использоваться для проверки принадлежности элемента списку. Это повышает гибкость функции, но не играет существенной роли в настоящем обсуждении.

Вместо того, чтобы возвращать атомарное значение success, лучше передавать из функции найденный путь решения. Поскольку последовательность состояний в пути решения уже содержится в списке been-list, список возвращается в новой версии функции. Поскольку этот список построен в обратном порядке (начальное состояние является его последним элементом), он сначала обращается (перестраивается в обратном порядке с использованием встроенной функции LISP reverse).

И, наконец, поскольку параметр been-lisp желательно скрыть от пользователя, целесообразно создать вызывающую функцию верхнего уровня, параметрами которой будут являться начальное и целевое состояние. Она будут вызывать функцию path со значением параметра been-list равным nil.

(defun solve-fwgc (state goal) (path state goal nil))

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

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

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

Состояния в версии PROLOG представляются с помощью предиката state (е, е, е, е), а в LISP задаются с помощью списка. Эти два представления не просто являются синтаксическими вариациями друг друга. Представление состояния в LISP определяется не только синтаксисом списков, но и функциями доступа и переходов, описывающими абстрактный тип данных "состояние". В версии PROLOG состояния являются шаблонами. Их значение определяется способом проверки соответствия другим шаблонам правил в PROLOG, которые тоже могут быть списками.

Версия LISP функции path несколько длиннее, чем ее реализация на PROLOG. Это связано с тем, что на LISP приходится реализовывать стратегию поиска, в то время как PROLOG использует встроенный алгоритм поиска. Алгоритм управления в LISP задается явно, а в PROLOG - неявно. Поскольку PROLOG строится на декларативном представлении и методах доказательства теорем, написанные на нем программы более лаконичны и напоминают описание предметной области задачи. В них алгоритмы поиска не нужно реализовывать напрямую. Обратной стороной медали является "сокрытие" поведения программы, определяемого встроенными стратегиями вывода PROLOG. Кроме того, над программистами "довлеют" формализм представления и стратегии поиска, заложенные в PROLOG. В свою очередь, LISP допускает большую гибкость в представлении и свободу действий программиста. Однако здесь программисту приходится явно реализовывать стратегию поиска.

15.3. Функции и абстракции высшего порядка

Одним из главных преимуществ LISP и других функциональных языков программирования является возможность определения функций, параметрами которых являются другие функции, а также функций, возвращающих функцию в качестве результата. Такие функции называются функциями высшего порядка (higher-order functions) и составляют важное средство реализации процедурной абстракции.

15.3.1. Отображения и фильтры

Фильтр (filter) - это функция, проверяющая элементы списка на предмет соответствия некоторому условию и удаляющая "отбракованные" элементы. Примером фильтра является описанная выше в этой главе функция filter-negatives. Отображения (тар) - выполняют некоторые действия над списком объектов данных и возвращают список результатов. Эту идею можно развить и ввести понятия обобщенных отображений и фильтров, получающих в качестве параметров списки и функции и проверяющих применимость функций к элементам списков.

В качестве примера рассмотрим упомянутую в подразделе 15.1.6 функцию filter-negatives. Ей в качестве параметра передается числовой список, а в результате ее выполнения возвращается этот же список, но без отрицательных элементов. Аналогично можно определить функцию-фильтр для удаления четных чисел из списка.

(defun filter-evens (number-list) ;условие останова

(cond ((null number-list) nil)

((oddp (car number-list))

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

(cons (car number-list) (filter-evens (cdr number-list)))) (t (filter-evens (cdr number-list)))))

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

Это можно сделать с помощью формы LISP f uncall, параметрами которой являются функция и последовательность аргументов, к которым эта функция и применяется.

((defun filter (list-of-elements test) (cond ((null list-of-elements) nil)

((funcall test (car list-of-elements)) (cons (car list-of-elements) (filter (cdr list-of-elements) test))) (t (filter (cdr list-of-elements) test))))

Функция filter проверяет условие test для первого элемента списка. Если результат проверки отличен от nil, он добавляется к результату фильтрации хвоста списка с помощью функции cons. В противном случае возвращается отфильтрованный хвост списка. При использовании этой функции ей можно передавать в качестве параметра различные предикаты. Тогда она будет решать разные задачи фильтрации.

> (filter '(13-95-2 -7 6) #'plusp) ;Фильтрация

/отрицательных чисел (13 5 6)

> (filter '(123456789) #'evenp) /Фильтрация всех

;нечетных чисел (2 4 6 8)

> (filter '(1 a b 3 с 4 7 d) #'numberp)

(1 3 4 7) /Фильтрация нечисловых

/элементов списка

При передаче функции в качестве параметра, как в приведенном примере, перед ее именем нужно указывать #', а не просто символ '. Это делается для того, чтобы интерпретатор LISP мог соответствующим образом обрабатывать этот аргумент. В частности, при передаче функции в качестве параметра в Common LISP сохраняются все связи ее свободных переменных (если таковые существуют). Такое сочетание определения функции со связыванием свободных переменных называется лексическим замыканием (lexical closure). Флаг #' уведомляет интерпретатор LISP о необходимости построения лексического замыкания и передачи его в функцию. Более строго funcall определяется следующим образом.

(funcall <функция> <аргг > < арг2 > . . . < аргп >)

В этом определении <функция> - это функция LISP, а <арг\>. . . <аргп> - нуль или более аргументов функции. Результат оценивания funcall совпадает с результатом вызова функции <функция>, если указанные аргументы передаются ей в качестве фактических параметров.

Функция apply выполняет ту же задачу, что и funcall, но ее аргументы должны передаваться в виде списка. Это единственное синтаксическое отличие между функциями apply и funcall. Программист может выбирать одну из функций по своему усмотрению. Эти функции аналогичны функции eval, поскольку все три позволяют пользователю управлять оцениванием функций. Различие между ними состоит в том, что параметрами функции eval

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

являются оцениваемые s-выражения, а функциям apply и f uncall передаются сама функция и ее параметры. Вот примеры использования этих функций.

(funcall #'plus2 3)

5

(apply #'plus'(2 3))

5

(eval '(plus 2 3))

5

(funcall fear ' (a b c) )

a

(apply #'car '((a b c)))

a

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

(defun map-simple (func list) (cond ((null list) nil)

((t (cons (funcall func (car list))

(map-simple func (cdr list))))))

(map-simple #'1+ '(123456))

(234567)

(map-simple #'listp (1 2 (3 4) 5 (6 7 8)))

(nil nil t nil t)

Это упрощенная версия встроенной в LISP функции mapcar, допускающая использование нескольких списков аргументов. Тогда к соответствующим элементам нескольких списков можно применять функции нескольких аргументов.

> (mapcar #'1+'(123456)) ;та же функция, что и map-simple

(234567)

>(mapcar #'+'(12 3 4) '(5 6 7 8)) (6 8 10 12)

> (mapcar #'max'(3 9 17) '(2 5 6 8))

(3 9 6 8)

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

15.3.2. Функциональные аргументы и лямбда-выражения

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

Выражение lambda позволяет отделить определение функции от ее имени. Истоки лямбда-выражений связаны с лямбда-исчислением (lambda-calculus) - математической моделью вычислений, обеспечивающей (среди всего прочего) особенно четкое разграничение между объектом и его именем. Синтаксис лямбда-выражения аналогичен определению функции de-fun, однако имя функции здесь заменяется ключевым словом lambda.

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

(lambda (<формальные-параметрь>) <тело>)

Лямбда-выражения можно использовать вместо имени функции в спецификации funcall или apply. Функция funcall выполнит тело лямбда-выражения, при этом аргументы будут связаны с параметрами funcall. Как и при использовании функции, количества формальных и фактических параметров должны совпадать. Например,

> (funcall #'(lambda (x) (* х х)) 4)

16

Здесь переменная х связывается со значением 4, а затем оценивается тело лямбда-выражения. Функция funcall возвращает квадрат числа 4. Приведем еще несколько примеров использования лямбда-выражений в функциях funcall и apply.

(apply #' (lambda (х у) (+ (* х х) у)) '(2 3))

7

(funcall #'(lambda (x) (append x x)) '(a b с))

(a b с a b с)

(funcall #'(lambda (xl x2) (append (reverse xl) x2)) '(a b c)

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

Лямбда-выражения можно использовать и в функциях высшего порядка наподобие mapcar вместо имени глобально определенной функции. Вот пример.

>(mapcar #'(lambda (x) (* х х)) '(12345)) (1 4 9 16 25)

(mapcar #'(lambda (x) (* х 2)) '(1234 5))

(2468 10)

(mapcar #'(lambda (x) (and (> x 0) (< х 10))) '(1 24 5 -9 8 23))

(t nil t nil t nil)

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

15.4. Стратегии поиска в LISP

Функции высшего порядка являются мощным средством процедурной абстракции. В этом разделе приемы абстрагирования будут применяться для реализации общих алгоритмов поиска в ширину, глубину и "жадного" алгоритма поиска, описанных в главах 3 и 4. Для управления поиском в пространстве состояний будут использованы списки open и closed.

15.4.1. Поиск в ширину и в глубину

Реализация алгоритма поиска в ширину базируется на использовании списка open в качестве структуры FIFO (очереди). Списки open и closed определяются как глобальные переменные. На то есть несколько причин. Во-первых, мы хотим продемонстрировать использование глобальных структур в LISP. Во-вторых, целесообразно сравнить

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

программное решение на LISP с программой на языке PROLOG. В-третьих, поскольку основная задача этой программы - решать проблему поиска, то пространство поиска следует определить глобально. И, наконец, списки open и closed разумно объявить глобальными переменными, поскольку они могут оказаться большими. В целом целесообразность использования локальных и глобальных переменных зависит от деталей реализации конкретного языка программирования. Глобальные переменные в Common LISP выделяются слева и справа символом *. Функции поиска в ширину можно определить следующим образом.

(defun breadth-first ( )

(cond ((null *open*) nil)

(t (let ((state (car *open*)))

( cond ((equal state *goal*) 'success)

(t (setq *closed* (cons state *closed*)) (setq *open* (append (cdr *open*) (generate-descendants state *moves*)))

(breadth-first))))))) (defun run-breadth (start goal) (setq *open* (list start)) (setq *closed* nil) (setq *goal* goal) (breadth-first))

В этой реализации проверяется наличие элементов в списке *ореп*. Если список пуст, то алгоритм возвращает значение nil, означающее неудачное завершение алгоритма. В противном случае проверяется первый элемент списка *ореп*. Если он соответствует целевому узлу, то алгоритм завершается и возвращает значение success. В противном случае для получения потомков текущего состояния вызывается функция generate-descendants, узлы-потомки добавляются в список *ореп*, и функция breadth-first рекурсивно вызывает сама себя. Функция run-breadth- это процедура инициализации, в которой задаются исходные значения переменных *ореп*, *closed* и *goal*. Функции generate-descendants в качестве параметров передаются состояние state и список функций *moves*, генерирующих переходы. В задаче перевозки человека, волка, козы и капусты с учетом определений переходов из раздела 15.2 список *moves* имеет вид.

(setq *moves*

'(farmer-takes-self farmer-takes-wolf farmer-takes-goat farmer-takes-cabbage))

Функция generate-descendants зависит от состояния и возвращает список его потомков. Помимо генерации списка потомков она предотвращает дублирование элементов в этом списке и исключает узлы, уже присутствующие в списке *ореп* или *closed*. Кроме состояния функции generate-descendants передается список переходов. Это могут быть имена уже определенных функций или лямбда-определения. Для сохранения результатов перехода в локальной переменной child используется блок let. Определение функции generate-descendants может иметь следующий вид.

(defun generate-descendants (state moves) (cond ((null moves) nil)

(t (let ((child (funcall (car moves) state))

(rest (generate-descendants state (cdr moves))))

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

(cond ((null child).rest)

((member child rest .-test #'equal) rest) ((member child *open* :test tt'equal) rest) ((member child *closed* :test f'equal) rest) (t (cons child rest)))))))

При вызове функции member используется дополнительный параметр : test #'equal, который впервые упоминался в разделе 15.2. Функция member позволяет пользователю задавать любую процедуру проверки наличия элемента в списке. Для этой цели можно использовать предикаты любой сложности и семантики. Однако LISP не требует обязательного задания такой функции: по умолчанию используется предикат eq. При использовании этого предиката два объекта считаются идентичными, если они занимают одно и то же местоположение в памяти. Мы используем более слабую функцию сравнения equal, в которой два объекта считаются равными, если они имеют одно и то же значение. Поскольку глобальная переменная *moves* связывается с соответствующим набором функций переходов, то описанный алгоритм поиска можно применять для поиска в ширину на любом графе состояний.

Единственной проблемой этой реализации является невозможность вывода списка состояний, расположенных вдоль пути решения от начала и до конца. Хотя при завершении алгоритма все ведущие к цели состояния содержатся в списке *closed*, в нем также находятся все остальные состояния, пройденные на предыдущих уровнях поиска. Чтобы решить эту проблему, для каждого состояния нужно записывать и его предка.

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

(defun build-record (state parent) (list state parent)) (defun get-state (state-tuple) (nth 0 state-tuple)) (defun get-parent (state-tuple) (nth 1 state-tuple)) (defun retrieve-by-state (state list) (cond ((null list) nil)

((equal state (get-state (car list))) (car list))

(t (retrieve-by-state state (cdr list) ) ) ) )

Функция build-record строит пару (<состояниехпредок>). Функции get-state и get-parent обеспечивают доступ к соответствующим полям записи. Функция retrieve-by-state получает в качестве параметров состояние и список записей состояния, а возвращает запись, поле состояния которой соответствует данному состоянию.

Функция build-solution использует форму retrieve-by-state для восстановления родительского состояния и построения списка состояний, ведущих к целевому. При инициализации списка *ореп* родительским состоянием для начального является nil. Функция build-solution прекращает свою работу после перехода к нулевому состоянию.

(defun build-solution (state) (cond ((null state) nil)

(t (cons state (build-solution (get-parent (retrieve-by-state state «closed*)))))))

Остальная часть алгоритма аналогична реализации поиска в ширину из раздела 3.2.

(defun run-breadth (start goal)

(setq *open* (list (build-record start nil)))

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

(setq *closed* nil) (setq *goal* goal) (breadth-first)) (defun breadth-first ( )

(cond ((null *open*) nil)

(t (let ((state (car *open*)'))

(setq *closed* (cons state *closed*))

(cond ((equal (get-state state) *goal*) (build-solution *goal*))

(t (setq *open* (append (cdr *open*)

(generate-descendants (get-state state) ?moves*)))

(breadth-first)))))))

(defun generate-descendants (state moves) (cond ((null moves) nil)

(t (let ((child (funcall (car moves) state))

(rest (generate-descendants state (cdr moves)))) (cond ((null child) rest)

((retrieve-by-state child rest) rest) ((retrieve-by-state child *open*) rest) ((retrieve-by-state child *closed*) rest) (t (cons (build-record child state) rest)))))))

Поиск в глубину можно обеспечить путем модификации процедуры поиска в ширину и реализации списка open в виде стека. Для этого нужно всего лишь изменить порядок следования аргументов функции append.

15.4.2. "Жадный" алгоритм поиска

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

(defun build-record (state parent depth weight)

(list state parent depth weight))

(defun get-state (state-tuple) (nth 0 state-tuple)) (defun get-parent (state-tuple) (nth 1 state-tuple)) (defun get-depth (state-tuple) (nth 2 state-tuple)) (defun get-weight (state-tuple) (nth 3 state-tuple)) (defun retrieve-by-state (state list)

(cond ((null list) nil)

((equal state (get-state (car list))) (car list)) (t (retrieve-by-state state (cdr list)))))

Функции best-first и generate-descendants определены следующим образом.

(defun best-first ( )

(cond ((null *open*) nil)

(t (let ((state (car *open*)))

(setq *closed* (cons state *closed*))

(cond ((equal (get-state state) *goal*) (build-solution

*goal*))

(t (setq *open*

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

(insert-by-weight

(generate-descendants (get-state state) (+ 1 (get-depth state)) *moves*) (cdr *open*))) (best-first)))))))

(defun generate-descendants (state depth moves) (cond ((null moves) nil)

(t (let ((child (funcall (car moves) state))

(rest (generate-descendants state depth (cdr moves)))) (cond ((null child) rest)

((retrieve-by-state child rest) rest) ((retrieve-by-state child *open*) rest) ((retrieve-by-state child *closed*) rest) (t (cons (build-record child state depth

(+ depth (heuristic child))) rest)))))))

Единственным отличием процедур поиска best-first от breadth-first является использование функции insert-by-weight для сортировки записей списка *ореп* по эвристическим весам и вычисление глубины поиска и этих весов с помощью функции generate-descendants.

Для завершения процедуры поиска best-first требуется определить функцию insert-by-weight. Она получает в качестве параметра не сортированный список записей состояний и вставляет их по одному в соответствующие позиции списка *ореп*. При этом также требуется с учетом специфики задачи определить функцию heuristic. Ее параметром является состояние, для которого вычисляется эвристический вес с помощью глобальной переменной *goal*. Определить эти функции читателю предлагается в качестве упражнения.

15.5. Проверка соответствия шаблонам LISP

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

Ядром системы восстановления информации служит функция match, параметрами которой являются два s-выражения, а возвращаемым значением - t, если эти выражения соответствуют друг другу. При этом оба выражения должны иметь одинаковую структуру, а также содержать идентичные атомы в соответствующих позициях. Функция match допускает использование в s-выражениях переменных, обозначенных символом ?. Переменные соответствуют любому s-выражению (списку или атому), но не сохраняют связывания, как при полной унификации. Ниже приводятся примеры требуемого поведения функции match. Эти примеры напоминают соответствующие примеры на языке PROLOG из главы 14, поскольку функция match на самом деле является упрощенной версией алгоритма унификации, положенного в основу языка PROLOG, а также многих других систем искусственного интеллекта, основанных на шаблонах. В разделе 15.6 функция match будет доведена до полноценной реализации алгоритма унификации за счет добавления возможности использования имен переменных и возвращения списка связей.

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

(match'(likes bill wine)'(likes bill wine))

t

(match'(likes bill wine)'(likes bill milk))

nil

(match'(likes bill ?)'(likes bill wine)) /пример с переменной

t

(match' (likes ? wine) ' (likes bill ?)) /переменные в обоих

;выражениях t

(match'(likes bill ?)'(likes bill (prolog lisp Smalltalk))

t

(match'(likes ?)'(likes bill wine))

nil

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

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

> (setq *database* '(((lovelace ada) 50000.00 1234)

((turing alan) 45000.00 3927) ((shelley тагу) 35000.00 2850) ((vonNeumann John) 40000.00 7955) ((simon herbert) 50000.00 1374) ((mccarthy John) 48000.00 2864) ((russell bertrand) 35000.00 2950)) ?database*

(get-matches '((turing alan) 45000.00 3927) *database*)

((turing alan) 45000.00 3927)

(get-matches '(? 50000.00 ?) *database*) ;все сотрудники

с зарплатой 50000 (((lovelace ada) 50000.00 1234) ((simon herbert) 50000.00 1374))

> (get-matches '((? John) ? ?) *database*) ;все сотрудники

с именем John (((vonNeumann John) 40000.00 7955) ((mccarthy John) 48000.00 2864))

Функция get-matches реализована рекурсивно. Это обеспечивает поиск элементов, соответствующих первому аргументу (шаблону). Все элементы базы данных, соответствующие этому шаблону, объединяются с помощью функции cons и передаются в качестве результата. Определение функции get-matches имеет следующий вид.

((defun get-matches (pattern database) (cond ((null database) ( ) )

/соответствие найдено,

((match pattern (car database)) /добавление к результату (cons (car database) (get-matches pattern (cdr database)))) (t (get-matches pattern (cdr database)))))

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

Основой данной системы является функция match. Она представляет собой предикат, определяющий, соответствуют ли друг другу два s-выражения с переменными. Работа функции match основана на утверждении, что два списка соответствуют друг другу в том и только том случае, если друг другу соответствуют их головы и хвосты. Поэтому для реализации данного алгоритма применена рекурсивная схема car-cdr. Рекурсия завершается, когда один из аргументов становится атомом (в том числе пустым списком nil, который является одновременно и атомом, и списком). Если оба аргумента представляют собой один и тот же атом, или один из шаблонов представляет собой атомарную переменную ? (соответствующую произвольному шаблону), то рекурсия завершается успешно. В противном случае проверка соответствия завершается с отрицательным результатом. Заметим, что если один из шаблонов является переменной, то второй необязательно должен быть атомарным, поскольку переменные могут соответствовать s-выражениям произвольной сложности.

Поскольку обработка условий завершения очень сложна, то в реализации функции match используется функция match-atom, зависящая от двух аргументов, хотя бы один из которых является атомом. Она и проверяет соответствие шаблонам. Поскольку сложность реализации процедуры скрыта в функции match-atom, структура рекурсии car-cdr в функции match выглядит более наглядно.

(defun match (patternl pattern2)

(cond (or (atom patternl) (atom pattern2));один из шаблонов - атом (match-atom patternl pattern2)) ;вызов match-atom,

;в противном случае (t (and (match (car patternl) (car pattern2))

;проверка соответствия car и (match (cdr patternl) (cdr pattern2)))))) ;cdr

При реализации функции match-a torn учитывается тот факт, что при вызове этой функции один из ее аргументов - атом. Благодаря этому предположению упрощается проверка соответствия шаблонов друг другу, поскольку требуется лишь удостовериться, что оба они представляют собой один и тот же атом (возможно, переменную). Эта функция завершается неудачей, если шаблоны представляют собой различные атомы, либо один из них является неатомарным. Если первая проверка завершается неудачей, то соответствие шаблону может быть достигнуто, только если один из шаблонов является переменной. Эта проверка и составляет заключительную часть определения функции. И, наконец, функция variable-p предназначена для проверки того, является ли шаблон переменной. Обработка переменных как экземпляров абстрактного типа данных упрощает дальнейшее расширение функции (например, распространение этой функции на именованные переменные подобно тому, как это было реализовано в языке PROLOG).

((defun match-atom (patternl pattern2)

(or (equal patternl pattern2) /шаблоны совпадают, или

(variable-p patternl) ;один из них является переменной.

(variable-p pattern2))) (defun variable-p (x) (equal x '?))

15.6. Рекурсивная функция унификации

В разделе 15.5 реализован рекурсивный алгоритм проверки соответствия шаблонам, позволяющий включать в шаблоны неименованные переменные. Расширим эту простую систе-

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

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

Как и в разделе 15.5, будем рассматривать шаблоны, представляющие собой константы, переменные или списочные структуры. В полном алгоритме унификации переменные могут отличаться друг от друга своими именами. Именованные переменные логично представлять в виде списков (var <имя>), где имя - это, как правило, атомарный символ. Примерами допустимых переменных являются (var x), (var у) и (var newstate).

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

> (unify'(p a (var х))'(р а Ь) ( )) ;возвращает подстановку

;Ь для переменной (((var х) . b)) ;(var x)

> (unify' (p (var у) b) ' (р a (var x) ) ( ) ) ; переменные в обоих

;шаблонах ( ( (var x) . b) ( (var у) . а) )

> (unify'(p (var х))'(р (q a (var у))) ( ));переменная, связанная

;с более

(((var x) q a (var у))) ;сложным шаблоном

> (unify'(р а)'(р а) ( )) ;nil означает, что

;подстановки не требуются nil

> (unify '(pa) '(q a) ( )) ;возвращает атом

;failed, означающий

failed ;неудачное завершение

Обратите внимание на использование в этих вызовах символа ., например, в выражении ((var x) .b). Это обозначение будет обсуждаться после описания функции unify. В ней, подобно системе проверки соответствия шаблонам из раздела 15.5, используется схема рекурсии car-cdr.

(defun unify (patternl pattern2 substitution-list)

(cond ((equal substitution-list 'failed) 'failed) ((varp patternl) (match-var patternl pattern2 substitution-list))

;проверка на наличие переменной ((varp pattern2) (match-var pattern2 patternl substitution-list)) ((is-constant-p patternl)

(cond ((equal patternl pattern2) substitution-list)

(t 'failed)))

((is-constant-p pattern2) 'failed) (t (unify (cdr patternl) (cdr pattern2)

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

(unify (car patternl) (car pattern2) substitution-list)))))

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

Затем, если один из шаблонов является переменной, вызывается функция match-var, вьшолняющая дальнейшую проверку и возможное добавление новых связанных переменных в список подстановки. Если ни один из шаблонов не является переменной, то функция unify проверяет наличие констант. При совпадении констант список подстановки возвращается неизменным, в противном случае возвращается значение failed.

Последним элементом оператора cond является декомпозиция задачи по дереву рекурсии. Сначала проводится унификация первых элементов с помощью связанных переменных из списка подстановки substitution-list. Результат передается в качестве третьего аргумента функции unify для унификации хвостов списков шаблонов. Это позволяет использовать подстановки переменных, сделанные при проверке соответствия первых элементов, и проверять вхождение этих переменных в оставшейся части обоих шаблонов.

Вот пример определения функции match-var.

(defun match-var (var pattern substitution-list) (cond ((equal var pattern) substitution-list) (t (let ((binding (get-binding var substitution-list))) (cond (binding (unify (get-binding-value binding) pattern substitution-list)) ((occursp var pattern) 'failed) (t (add-substitution var pattern substitution-list)))))))

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

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

Если переменная var не связана ни с какими значениями, вызывается функция occursp, с помощью которой проверяется наличие var в шаблоне pattern. Проверку вхождения (occurs check) необходимо выполнять для предотвращения попыток унификации переменной с содержащим ее шаблоном, которые могут привести к появлению циклов. Например, если переменная (var x) связана с выражением (р (var x) ), то любая попытка применения этих подстановок к шаблону приведет к бесконечному циклу. Если в шаблоне pattern встречается фрагмент var, функция match-var возвращает значение failed. В противном случае новая пара подстановки добавляется в список substitution-list с помощью функции add-substitution.

Функции unify и match-var составляют основу алгоритма унификации. Ниже описаны функция occursp (выполняющая проход по дереву шаблона в поисках вхождений в него заданной переменной), varp и is-constant-p (проверяющая, чем является аргумент: переменной или константой). Затем будут рассмотрены функции обработки множества подстановок.

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

(defun occursp (var pattern)

(cond ((equal var pattern) t)

((or (varp pattern) (is-constant-p pattern)) nil) (t (or (occursp var (car pattern))

(occursp var (cdr pattern)))))) (defun is-constant-p (item)

(atom item)) (defun varp (item)

(and (listp item)

(equal (length item) 2) (equal (car item) 'var)))

Множества подстановок можно представить с помощью встроенного в LISP типа данных, известного под названием ассоциативного списка (association list) или а-списка (a-list). Работа с такими структурами данных положена в основу функций add-substitutions, get-binding и binding-value. Ассоциативный список- это список записей данных или пар ключ-значение (key/data). Первый элемент каждой записи - это ключ для ее восстановления, а оставшаяся часть записи содержит данные, которые могут представлять собой либо список значений, либо отдельный атом. Извлечение данных осуществляется с помощью функции assoc, параметрами которой являются ключ и ассоциативный список, а возвращаемым значением - первый элемент ассоциативного списка, соответствующий данному ключу. При вызове функции assoc можно дополнительно указать третий аргумент, означающий тип проверки, используемой для сравнения ключей. По умолчанию для проверки в Common LISP используется функция eql, согласно которой равенство двух аргументов означает, что они указывают на один и тот же объект (т.е. занимают одну и ту же область памяти или принимают одинаковое числовое значение). При реализации множеств подстановок будем использовать менее жесткий тест equal, проверяющий синтаксическое соответствие аргументов (идентичность имен). Приведем примеры использования функции assoc.

(assoc 3 '((la) (2 b) (3 с) (4 d) ) )

(3 с)

(assoc 'd '((a b с) (b с d e) (d e f) (c d e)) :test tt'equal)

(d e f)

(assoc 'c '((a . 1) (b . 2) (c .3) (d . 4)) :test #'equal)

(c . 3)

Заметим, что функция assoc возвращает всю запись, соответствующую указанному ключу. Данные из этого списка можно извлечь с помощью функции cdr. Заметим также, что в последнем вызове элементами а-списка являются не списки, а структуры, получившие название точечных пар (dotted pair), например (а . 1).

Точечная пара - это базовый конструктор в LISP. Она является результатом объединения двух s-выражений. Обозначение списка, используемое в этой главе, - это лишь один из вариантов точечных пар. Например, при вызове (cons I nil) на самом деле возвращается значение (1 . nil), что эквивалентно (1). Аналогично список (1 2 3) можно записать в виде точечных пар (1 . (2 . (3 . nil) ) ). Хотя на самом деле функция cons создает точечные пары, списочные обозначения гораздо понятнее, а потому предпочтительнее.

При объединении двух атомов результат всегда записывается в обозначениях точечных пар. Хвост точечной пары - это ее второй элемент, а не список, содержащий второй атом. Например,

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

(cons 'a 'b)

(a . b)

(car '(a . b))

a

(cdr '(a . b))

b

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

Наряду с assoc в Common LISP определена функция aeons, аргументами которой являются ключ, данные и ассоциативный список, а возвращаемым значением - новый ассоциативный список, первый элемент которого - это результат объединения ключа и данных. Например,

> (aeons 'a I nil)

((а . 1))

Заметим, что если в функцию aeons передаются два атома, то в ассоциативный список добавляется их объединение.

> (aeons 'pets '(emma jack Clyde)

'((name . bill) (hobbies music skiing movies) (job . programmer)))

((pets emma jack clyde) (name . bill) (hobbies music skiing movies) (job . programmer))

Элементами ассоциативного списка могут быть точечные пары и списки.

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

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

(defun get-binding (var substitution-list)

(assoc var substitution-list :test #'equal)) (defun get-binding-value (binding) (cdr binding)) (defun add-substitution (var pattern substitution-list)

(aeons var pattern substitution-list))

На этом реализация алгоритма унификации завершена. Она будет использована в разделе 15.8 для реализации простого интерпретатора для языка PROLOG и в разделе 15.10 для построения оболочки экспертной системы.

15.7. Интерпретаторы и внедренные языки

Верхний уровень интерпретатора LISP называется циклом read-eval-print. Это название отражает функции интерпретатора по чтению, оцениванию и выводу значений

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

s-выражений, введенных пользователем. Функция eval, определенная в подразделе 15.1.4, составляет основу интерпретатора LISP. С ее помощью цикл read-eval-print можно написать на самом языке LISP. В следующем примере будет разработана упрощенная версия этого цикла. Упрощение состоит в отсутствии обработки ошибок, хотя LISP обеспечивает средства, необходимые для ее реализации.

Для создания цикла read-eval -print воспользуемся двумя функциями LISP read и print. Первая из них не зависит от параметров и возвращает следующее s-выражение, введенное с клавиатуры. Функция print зависит от одного аргумента, оценивает его и выводит результат в стандартный поток вывода. При этом нам понадобится также функция terpri, не зависящая от аргументов и выводящая в стандартный поток символ новой строки newline. По завершении вызова функция terpri возвращает значение nil. Цикл read-eval-print реализуется как вложенное s-выражение.

(print (eval (read)))

При этом сначала оценивается s-выражение самого глубокого уровня вложенности (read). Возвращаемое этой функцией значение (следующее введенное пользователем s-выражение) передается функции eval для оценки, результат которой в свою очередь передается функции print и выводится на экран. В завершение цикла выводится приглашение, а с помощью функции terpri после отображения результатов выводится символ newline, и цикл рекурсивно повторяется. Таким образом, окончательно определение цикла read-eval-print имеет вид.

(defun my-read-eval-print ( ) ;не зависит от аргументов

(print':) ;вывод приглашения :

(print (eval (read))) ;цикл read-eval-print

(terpri) ;вывод символа newline

(my-read-eval-print)) ;повтор цикла

Этот цикл можно использовать "поверх" встроенного интерпретатора.

> (my-read-eval-print)

:(+ 1 2) ;новое приглашение

3

: ; и т . д .

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

Примером реализации подобного специализированного интерпретатора на LISP может служить модификация цикла my-read-eval-print, позволяющая оценивать арифметические выражения в инфиксной, а не префиксной системе обозначений. Работа такого интерпретатора показана на следующем примере (обратите внимание на модифицированное приглашение inf ix->).

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

infix-> (1+2)

3

infix-> (7-2)

5

infix-> ((5 + 2) * (3 - 1)) /цикл должен допускать вложенные выражения

14

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

Модифицируем разработанный ранее цикл read-eval-print, добавив функцию, переводящую инфиксные выражения в префиксную форму перед их передачей функции eval. Первая попытка определения этой функции может иметь такой вид.

(defun simple-in-to-pre (exp)

(list (nth 1 exp) ;средний элемент (символ операции)

;становится первым

(nth 0 ехр) ;первый операнд

(nth 2 ехр) ;второй операнд

Функцию simple-in-to-pre удобно применять для преобразования простых выражений. Однако с ее помощью не удастся корректно обработать вложенные выражения, в которых операнды сами являются инфиксными выражениями. Для решения этой проблемы операнды необходимо транслировать в префиксную форму. Рекурсия завершается проверкой типа аргумента: если он представляет собой число, то оно возвращается неизменным. Полная версия транслятора из инфиксной в префиксную форму имеет вид.

(defun in-to-pre (exp)

(cond ((numberp exp) exp) (t (list (nth 1 exp)

(in-to-pre (nth 0 exp)) (in-to-pre (nth 2 exp))))))

С помощью этого транслятора можно модифицировать цикл read-eval-print и обеспечить интерпретацию инфиксных выражений. Например, так.

(defun in-eval ( ) (print 'infix->)

(print (eval (in-to-pre (read)))) (terpri) (in-eval))

С помощью такого интерпретатора можно обрабатывать бинарные выражения в инфиксной форме.

> (in-eval)

infix->(2 + 2)

4

infix->((3*4) - 5)

7

В приведенном примере на LISP реализован новый язык - язык инфиксной арифметики. Поскольку наряду с символьными вычислениями (списочными структурами и

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

функциями их обработки) LISP поддерживает управление оценкой, то решить эту задачу на LISP гораздо легче, чем на многих других языках. Этот пример иллюстрирует важную методологию программирования задач искусственного интеллекта, получившую название металингвистической абстракции (meta-linguistic abstraction). При решении задач искусственного интеллекта зачастую встречаются ситуации, когда не вполне понятна сама задача, или требуемая для ее решения программа слишком сложна. В рамках подхода металингвистической абстракции базовый язык программирования (в данном случае LISP) применяется для реализации специализированного высокоуровневого языка, который может быть более эффективным для решения конкретного класса задач. Термин металингвистическая абстракция означает использование базового языка для реализации другого языка программирования, а не решения самой задачи. Как показано в разделе 14.6, PROLOG тоже позволяет программисту создавать интерпретаторы метауровня. Преимущества метаинтерпретаторов с точки зрения поддержки программирования задач из сложных предметных областей обсуждались также во введении к части VI.

15.8. Логическое программирование на языке LISP

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

Для простоты этот интерпретатор поддерживает конъюнктивные цели и импликации, операторы or и not в нем не определены, как не определены и арифметические операции, операторы ввода-вывода и другие встроенные в PROLOG предикаты. Мы не пытаемся реализовать полную версию PROLOG и отследить все особенности поиска. Отсутствие оператора отсечения не позволяет корректно обрабатывать рекурсивные предикаты. Тем не менее предлагаемая оболочка иллюстрирует основные функции языков логического программирования. Читатель может добавить к интерпретатору перечисленные свойства в качестве интересного упражнения.

15.8.1. Простой язык логического программирования

Предлагаемый интерпретатор для задач логического программирования поддерживает хорновские выражения - подмножество выражений, применяемых в полном исчислении предикатов. Корректно определенные формулы состоят из термов, конъюнктивных выражений и правил, написанных в стиле LISP. Составной терм - это список, первым элементом которого является имя предиката, а остальные элементы соответствуют аргументам. В качестве аргумента могут выступать константы, переменные или другие

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

составные термы. Как и при описании функции unify, переменные будем представлять списками из двух элементов. Первым элементом является слово var, а вторым - имя переменной. Рассмотрим несколько примеров термов.

(likes bill music) (on block (var x)) (friend bill (father robert))

Конъюнктивное выражение - это список, первым элементом которого является слово and, а последующими - простые термы или конъюнктивные выражения.

(and (smaller david sarah) (smaller peter david))

(and (likes (var x) (var y)) (likes (var z) (var y)))

(and (hand-empty) (and (on block-1 block-2) (on block-2 table)))

Импликация выражается в синтаксически ясной форме, что упрощает ее запись и распознавание.

(rule if <предпосымка> then <заключение>)

Здесь <предпосылка> - это либо простое, либо конъюнктивное предложение, а <заключение> - всегда простое предложение. Приведем несколько примеров правил.

(rule if (and (likes (var x) (var z) )

(likes (var y) (var z))) then (friend (var x) (var y))) (rule if (and (size (var x) small) (color (var x) red) (smell (var x) fragrant)) then (kind (var x) rose))

Логическая база данных - это список фактов и правил, связанных с глобальной переменной *assertions*. Приведем пример базы данных об отношениях симпатии, основанный на вызове функции setq (можно бьшо бы воспользоваться и функцией defvar).

(setq *assertions*

'((likes george beer)

(likes george kate) (likes george kids) (likes bill kids) (likes bill music) (likes bill pizza) (likes bill wine) (rule

if (and (likes (var x) (var z))

(likes (var y) (var z) ) ) then (friend (var x) (var y)))))

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

>(logic-shell) ;вывод приглашения ?

? (likes bill (var x) ) .-успешно выполненные запросы выводятся

;с подстановками

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

(likes bill kids)

(likes bill music)

(likes bill pizza)

(likes bill wine)

?(likes george kate)

(likes george kate)

?(likes george taxes) /если запрос не выполнен, ничего не

;возвращается ?(friend bill george)

(friend bill george) ;из (anddikes bill kids) (likes george kids)) ?(friend bill roy) ;roy не существует в базе знаний, запрос

;не выполнен ?(friend bill (var x))

(friend bill george) ;из (and(likes bill kids)(likes george kids)) (friend bill bill) ,-из (anddikes bill kids) (likes bill kids)) (friend bill bill) ;из (anddikes bill music) (likes bill music)) (friend bill bill) ;из (anddikes bill pizza) (likes bill pizza)) (friend bill bill) ;из (anddikes bill wine) (likes bill wine)) ?quit bye >

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

15.8.2. Потоки и их обработка

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

Одному целевому выражению могут соответствовать различные факты, а значит, и разные множества подстановок. При использовании конъюнкции целей необходимо удовлетворить всем конъюнктам, а также обеспечить согласованность связанных переменных. Аналогично при обработке правил необходимо, чтобы подстановки, сформированные в процессе проверки соответствия заключения правила целевому выражению, были внесены в левую часть правила. Необходимость управления различными множествами подстановок - основной источник сложности интерпретатора. Эту проблему помогают решить потоки. Они позволяют сконцентрировать внимание на изменении последовательности подстановок-кандидатов в рамках ограничений, определяемых логической базой данных.

Поток (stream) - это последовательность объектов данных. Наиболее типичным примером обработки потоков является обычная интерактивная программа. Поступающие с клавиатуры данные рассматриваются как бесконечная последовательность символов, а программа считывает и обрабатывает текущий символ из потока ввода. Обработка потоков - это обобщение этой идеи: потоки не обязательно создаются пользователями. Их могут генерировать и модифицировать функции. Генератор (generator) - это функция, создающая непрерывный поток объектов данных. Функция отображения (map function) выполняет некоторое преобразование над каждым элементом потока. Фильтр (filter) исключает некоторые элементы из потока по условиям, заданным некоторым предикатом.

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

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

(and (likes bill (var z)) (likes george (var z)))

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

На рис. 15.4 показана обработка потока подстановок с помощью этого конъюнктивного целевого выражения. Сначала поток подстановок-кандидатов содержит только пустое множество подстановок. Он расширяется после появления первого соответствия предложения множеству элементов базы данных. После исключения подстановок, не удовлетворяющих второму конъюнкту (likes george (var z) ), в потоке остается одно множество подстановок. Результирующий поток ( ( ( (var z) .kids) ) ) содержит единственную подстановку переменной, обеспечивающую соответствие обеих подцелей базе знаний.

Рис. 15.4. Фильтрация потока подстановок переменных в соответствии с конъюнкцией цепей

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

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

; добавляет в поток новый первый элемент

(defun cons-stream (element stream) (cons element stream))

; возвращает первый элемент потока

(defun head-stream (stream) (car stream))

; возвращает поток, из которого удален первый элемент

(defun tail-stream (stream) (cdr stream))

; возвращает значение "истина", если поток пуст

(defun empty-stream-p (stream) (null stream))

; создает пустой поток

( 3(defun make-empty-stream ( ) nil)

; объединяет два потока

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

(defun combine-streams (streaml stream2)

(cond ((empty-stream-p streaml) stream2)

(t (cons-stream (head-stream streaml) (combine-streams

(tail-stream stream 1) stream2)))))

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