Часть 12.

(defun combine-streams (streaml stream2)

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

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

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

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

15.8.3. Интерпретатор для задач логического программирования на основе потоков

Реализуем интерпретатор с помощью функции logic-shell, которая является упрощенным вариантом цикла read-eval-print, описанного в разделе 15.7. После вывода приглашения ? эта функция считывает следующее введенное пользователем s-выражение и связывает его с символом goal. Если целевое утверждение goal соответствует значению quit, функция завершает работу. В противном случае она вызывает функцию solve для генерации потока множеств подстановок, удовлетворяющих данному целевому утверждению. Этот поток передается в функцию print-solutions, которая выводит целевое утверждение с каждой из найденных подстановок. Затем функция рекурсивно вызывает сама себя. Вот определение функции logic-shell.

(defun logic-shell ( ) (print '? ) (let ((goal (read)))

(cond ((equal goal 'quit) 'bye)

(t (print-solutions goal (solve goal nil)) (terpri) (logic-shell)))))

Основой интерпретатора является функция solve. Она получает целевое утверждение и набор подстановок и находит все решения, согласованные с содержимым базы знаний. Эти решения возвращаются как поток множеств подстановок. Если соответствия не найдены, функция solve возвращает пустой поток. С точки зрения обработки потоков функция solve является источником (source), или генератором (generator), потока решений. Вот ее определение.

(defun solve (goal substitutions)

(declare (special *assertions*)) (if (conjunctive-goal-p goal)

(filter-through-conj-goals (body goal)

(cons-stream substitutions (make-empty-stream))) (infer goal substitutions *assertions*)))

Ключевое слово special означает, что переменная *assertions* является специальной (special), или глобальной (global), и будет динамически связываться со средой,

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

в которой вызывается функция solve. (Во многих современных версиях LISP объявления special не требуется.)

Функция solve сначала проверяет, является ли цель конъюнктивной. Если да, то вызывается функция filter-through-conj -goals, выполняющая описанную в подразделе 15.8.2 фильтрацию. Если целевое утверждение goal не конъюнктивно, вьпывается функция, определенная ниже infer, выполняющая разрешение цели с помощью базы знаний.

Функция filter-through-conj -goals вызывается для тела конъюнкции (т.е. последовательности конъюнктов, из которой удален оператор and) и потока, содержащего только исходное множество подстановок. Результатом ее работы является поток подстановок, представляющий все решения для данного целевого утверждения. Приведем определение функции f ilter-through-conj -goals.

(defun filter-through-conj-goals (goals substitution-stream) (if (null goals)

substitution-stream

(filter-through-conj-goals (cdr goals)

(filter-through-goal (car goals) substitution-stream))))

Если список целей пуст, функция завершает работу и возвращает поток substitution-stream без изменений. В противном случае вызывается функция filter-through-goal для фильтрации потока подстановок на основе первого целевого выражения в списке. Результат ее работы передается вызываемой рекурсивно функции f ilter-through-conj -goals для обработки оставшейся части списка целей. Таким образом поток передается по списку целей слева направо, расширяясь и сужаясь при обработке каждого целевого утверждения.

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

(defun filter-through-goal (goal substitution-stream) (if (empty-stream-p substitution-stream) (make-empty-stream) (combine-streams

(solve goal (head-stream substitution-stream)) (filter-through-goal goal (tail-stream substitution-stream)))))

Таким образом в функции f ilter-through-conj-goals поток множеств подстановок передается последовательности целевых утверждений, а функция filter-through-goal обрабатывает этот поток для каждой конкретной цели. Рекурсивный вызов функции solve обеспечивает разрешение цели для каждого набора подстановок.

Если конъюнктивные цели обрабатываются в функции solve с помощью вызова f ilter-through-conj -goals, то отдельные цели разрешаются с помощью определенной ниже функции infer, которая получает целевое утверждение и набор подстано-

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

вок, а возвращает все решения, найденные в базе знаний. Третий параметр kb функции infer - это база знаний логических выражений. При первом вызове infer из функции solve ей передается база знаний, связанная с глобальной переменной ?assertions*. Функция infer последовательно выполняет поиск в базе знаний kb, сверяя соответствие целевого утверждения каждому факту или заключению правила.

Такая рекурсивная реализация функции infer обеспечивает обратный вывод, свойственный интерпретатору PROLOG и многим оболочкам экспертных систем. Сначала проверяется, не пуста ли база знаний kb, и, если да, возвращается пустой поток. В противном случае первый элемент базы знаний kb связывается с символом assertion с помощью блока let*. Этот блок аналогичен блоку let, но при этом гарантированно оценивает исходные значения локальных переменных в последовательно вложенных контекстах, т.е. обеспечивает порядок связывания и видимость предыдущих переменных. В нем также определяется переменная match. Если assertion- это правило, переменная match инициализируется подстановкой, требуемой для унификации цели с заключением этого правила. Если же assertion - это факт, переменная match инициализируется подстановкой, требуемой для унификации assertion с целевым утверждением. После унификации цели с первым элементом базы знаний функция infer проверяет, удалась ли она. Если соответствие не найдено, она рекурсивно вызывает сама себя, пытаясь разрешить целевое утверждение с помощью оставшейся части базы знаний. Если же унификация завершилась успешно, a assertion - это правило, функция infer вызывает функцию solve для предпосылки этого правила, причем множество подстановок связывается с переменной match. Функция combine-stream объединяет полученный поток решений с потоком, построенным функцией infer при обработке оставшейся части базы знаний. Если assertion - не правило, значит, это факт. Тогда функция infer добавляет решение, связанное с переменной match, к решению, полученному при обработке оставшейся части базы знаний. На этом поиск прекращается. Приведем определение функции infer.

(defun infer (goal substitutions kb) (if (null kb)

(make-empty-stream)

(let* ((assertion (rename-variables (car kb))) (match (if (rulep assertion)

(unify goal (conclusion assertion) substitutions) (unify goal assertion substitutions)))) (if (equal match 'failed)

(infer goal substitutions (cdr kb)) (if (rulep assertion) (combine-streams

(solve (premise assertion) match) (infer goal substitutions (cdr kb))) (cons-stream match (infer goal substitutions (cdr kb))))))))

Перед связыванием первого элемента базы данных kb с переменной assertion он передается в функцию rename-variables, где каждой переменной присваивается уникальное имя. Это позволяет предотвратить конфликт имен между переменными в целевом утверждении и базе знаний. В частности, если в целевом утверждении встречается фрагмент (var x), его нужно обрабатывать как переменную, отличную от (var x) в описании правила или факта. Решить эту проблему проще всего путем переименования

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

всех переменных в базе знаний и присвоения им уникальных имен. Определение функции rename-variables будет приведено в конце этого раздела.

На этом реализация ядра интерпретатора для решения задач логического программирования завершена. Итак, solve - это высокоуровневая функция, которая генерирует поток множеств подстановок, представляющих решения для целевого утверждения, полученные с использованием базы знаний. Функция filter-through-conj -goals разрешает конъюнктивные цели слева направо, при этом каждая цель выступает в качестве фильтра для потока решений-кандидатов. Если целевое утверждение не принимает значение "истина" с учетом базы знаний для потока множеств подстановок, функция filter-through-conj -goals удаляет эти подстановки из потока. Если целевое утверждение - это простой литерал, функция solve вызывает функцию infer для генерации потока всех подстановок, удовлетворяющих целевому утверждению с учетом базы знаний. Подобно PROLOG, полученный интерпретатор для заданного целевого утверждения находит все удовлетворяющие ему связанные переменные из имеющейся базы знаний.

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

(defun print-solutions (goal substitution-stream)

(cond ((empty-stream-p substitution-stream) nil)

(t (print (apply-substitutions goal (head-stream substitution-stream))) (terpri)

(print-solutions goal (tail-stream substitution-stream)))))

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

(defun apply-substitutions (pattern substitution-list) (cond ((is-constant-p pattern) pattern) ((varp pattern)

(let ((binding (get-binding pattern substitution-list)))

(cond (binding (apply-substitutions (get-binding-value binding)

substitution-list)) (t pattern))))

(t (cons (apply-substitutions (car pattern) substitution-list) (apply-substitutions (cdr pattern) substitution-list)))))

Функция infer переименовывает переменные в базе знаний до проверки их соответствия целевому утверждению. Это необходимо для предотвращения нежелательных конфликтов имен. Например, целевое утверждение (р a (var x) ) должно соответствовать элементу базы знаний (р (var х) Ь), поскольку область видимости каждой переменной (var x) ограничена одним вьфажением. Однако при унификации это соответствие не требуется. Кон-

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

фликт имен можно предотвратить за счет присвоения каждой переменной уникального имени. В основу схемы переименования можно положить встроенную функцию Common LISP gensym, не зависящую от аргументов. При каждом вызове она возвращает уникальный символ, состоящий из числа с префиксом #: G. Например,

(gensym)

#:G4

(gensym)

#:G5

(gensym)

#:G6

>

В процессе переименования имя каждой переменной в выражении заменяется результатом вызова функции gensym. Функция rename-variables выполняет необходимую инициализацию (описанную ниже) и вызывает функцию rename-rec для рекурсивного выполнения подстановок в шаблоне. Когда встречается переменная, вызывается функция rename, возвращающая ее новое имя. Чтобы при нескольких вхождениях в шаблон одной и той же переменной ей было присвоено одно имя, при каждом переименовании переменной ее имя помещается в ассоциативный список, связанный со специальной переменной *name-list*. Благодаря объявлению этой переменной как специальной все ссылки на нее являются динамическими, и их можно использовать в различных функциях. Так, при каждом обращении к переменной *name-list* в функции rename мы получаем доступ к экземпляру этой переменной, объявленному в функции rename-variables. При первом вызове для данного выражения функция rename-variables инициализирует переменную *name-list* значением nil. Приведем определения этих функций.

(defun rename-variables (assertion) (declare (special *name-list*)) (setq *name-list* nil) (rename-rec assertion)) (defun rename-rec (exp)

(declare (special *name-list*)) (cond ((is-constant-p exp) exp) ((varp exp) (rename exp))

(t (cons (rename-rec (car exp))(rename-rec (cdr exp)))))) (defun rename (var)

(declare (special *name-list*))

(list 'var (or (cdr (assoc var *name-list* :test#'equal)) (let ((name (gensym)))

(setq *name-list* (aeons var name *name-list*))name))))

Функции доступа к компонентам правил и целевых утверждений не требуют дополнительных пояснений.

(defun premise (rule) (nth 2 rule)) (defun conclusion (rule) (nth 4 rule)) (defun rulep (pattern) (and (listp pattern)

(equal (nth 0 pattern)'rule))) (defun conjunctive-goal-p (goal) (and (listp goal)

(equal (car goal)'and))) (defun body (goal) (cdr goal))

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

15.9. Потоки и оценивание с задержкой

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

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

Вторая проблема - невозможность обработки потоков сколь угодно большой длины. Хотя эта проблема в программе logic-shell не возникает, с ней приходится сталкиваться при решении многих важных задач. Предположим, что нужно написать функцию, возвращающую поток из первых п нечетных чисел Фибоначчи. Для этого можно использовать генератор потока чисел Фибоначчи, фильтр для удаления из него четных чисел и функцию для накопления полученных решений в списке из п элементов (рис. 15.5). К сожалению, длина потока чисел Фибоначчи неизвестна, поскольку неясно, сколько чисел потребуется для получения первых л нечетных чисел.

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

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

Для оценивания с задержкой воспользуемся замыканием функции (function closure). Замыкание включает функцию и все ее связанные переменные в текущей среде. Такое замыкание можно связать с переменной или передать его в качестве параметра и обрабатывать с помощью функции funcall. По существу, замыкание "замораживает" выполнение функции до нужного момента. Замыкание можно создать с помощью формы LISP function. Например, рассмотрим следующую запись на LISP.

(setq v 10)

10

(let ((v 20)) (setg f_closure (function (lambda ( ) v))))

#

(funcall f_closure)

20

>v 10

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

Рис. 15.5. Потоковая реализация программы поиска первых п нечетных чисел Фибоначчи

Поток на основе списка, содержащий неопределенное число элементов (е, е2е3е4...)

Поток с отложенным оцениванием хвостовой части содержит только два элемента, но может включать любое число элементов

(et . <отложенное оценивание хвостовой части потока>) Рис. 15.6. Реализация потоков на основе списков и оценивания с задержкой

Изначально функция setq связывает переменную v со значением 10 в глобальной среде. В блоке let переменная v локально связывается со значением 20 и создается замыкание функции, возвращающей это значение переменной v. Интересно отметить, что при выходе из блока let это связанное значение переменной v не исчезает, поскольку оно сохраняется в замыкании функции, связанном с переменной f„closure. Однако это лексическое связывание не имеет отношения к глобальному связыванию переменной v. Следовательно, если оценить это замыкание, будет возвращено значение 2 0 локальной переменной v, хотя глобальная переменная v по прежнему принимает значение 10.

Эта реализация потоков основана на паре функций delay и force. Первая из них получает в качестве параметра выражение и не оценивает его, а возвращает замыкание. Функция force получает замыкание в качестве аргумента и запускает его с помощью функции f uncall. Приведем определения этих функций.

(defmacro delay (exp) '(function (lambda О, ехр))) (defun force (function-closure) (funcall function-closure)

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

737

Функция delay- это пример формы LISP, получившей название макроса (macro). Эту функцию нельзя определить с помощью функции def un, поскольку определенные таким образом формы оценивают свои аргументы до выполнения тела. Макросы обеспечивают программистам полный контроль над оцениванием параметров. Макрос определяется с помощью формы defmacro. При его выполнении аргументы не оцениваются, а исходные s-выражения при вызове связываются с формальными параметрами, и тело макроса оценивается дважды. Первый этап оценивания называется макрорасширением (macro-expansion), а второй состоит в оценке полученной формы.

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

Например, рассмотрим вызов (delay (+ 2 3)). Выражение (+2 3) не оценивается, а связывается с формальным параметром ехр. При первом оценивании макроса возвращается выражение, следующее за обратной кавычкой, в котором формальный параметр ехр заменен его значением - неоцененным s-выражением (+ 2 3). Получится выражение (function (lambda () (+2 3))). Оно снова оценивается, и возвращается замыкание функции.

Если позднее передать это замыкание в функцию force, то будет оцениваться выражение (lambda () (+ 2 3) ). Это функция, не зависящая от аргументов, тело которой соответствует значению 5. С помощью функций force и delay можно реализовать потоки на основе оценки с задержкой. Перепишем функцию cons-stream в виде макроса, зависящего от двух аргументов. Этот макрос должен присоединять значение первого к оценке второго. При этом второй аргумент оценивается с задержкой и может возвращать поток любой длины. Определим функцию tail-stream, оценивающую хвост потока.

(defmacro cons-stream (ехр stream) '(cons, ехр (delay, stream) )) (defun tail-stream (stream) (force (cdr stream)))

Переопределим также в виде макроса функцию combine-streams. Она должна получать два аргумента, но не оценивать их. В этом макросе для создания замыкания второго потока используется функция delay. Полученный результат вместе с первым потоком передается в функцию comb-f, аналогичную определенной ранее функции combine-streams. Однако, если первый поток оказывается пустым, то новая функция оценивает второй поток. Если первый поток не пуст, выполняется рекурсивный вызов функции comb-f с помощью обновленной версии cons-stream. При этом рекурсивный вызов в замыкании "замораживается" для дальнейшей оценки.

(defmacro combine-streams (streaml stream2)

"(comb-f ,streaml (delay ,stream2))) (defun comb-f (streaml stream2) (if (empty-stream-p streaml) (force stream2) (cons-stream (head-stream streaml)

(comb-f (tail-stream streaml) stream2))))

Если эти определения добавить к версиям функций head-stream, make-empty-stream и empty-stream-p из подраздела 15.8.2, получим полную реализацию потоков на основе оценивания с задержкой.

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

Эти функции можно использовать для решения задачи получения первых л нечетных чисел Фибоначчи. Функция f ibonacci-stream возвращает поток всех чисел Фибоначчи. Заметим, что это бесконечная рекурсивная функция. Бесконечный цикл предотвращается за счет оценивания с задержкой, поскольку следующий элемент вычисляется только в случае необходимости. Функция filter-odds получает поток целых чисел и исключает из него четные элементы. Функция accumulate получает поток и число п и возвращает список, состоящий из первых п элементов потока.

(defun fibonacci-stream (fibonacci-1 fibonacci-2) (cons-stream (+ fibonacci-1 fibonacci-2)

(fibonacci-stream fibonacci-2 (+ fibonacci-1 fibonacci-2)))) (defun filter-odds (stream)

(cond ((evenp (head-stream stream)) (filter-odds (tail-stream stream)))

(t (cons-stream (head-stream stream) (filter-odds (tail-stream stream)))))) ((defun accumulate-into-list (n stream) (cond ((zerop n) nil)

(t (cons (head-stream stream) (accumulate-into-list (- n 1)(tail-stream stream))))))

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

(accumulate-into-list 25 (filter-odds (fibonacci-stream 0 1)))

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

В следующем разделе интерпретатор для решения задач логического программирования будет модифицирован в оболочку экспертной системы. Однако сначала будут введены две дополнительные функции работы с потоками, используемые впоследствии в реализации оболочки. В разделе 15.3 были представлены обобщенные функции отображения и фильтрации списков. Эти функции map-simple и filter можно модифицировать для работы с потоками. В следующем разделе будут использоваться функции filter-stream и map-stream. Их реализацию предлагается разработать читателю в качестве упражнения.

15.10. Оболочка экспертной системы на LISP

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

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

15.10.1. Реализация факторов достоверности

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

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

Элементы потока реализуем как абстрактный тип данных. Для управления подстановками и факторами достоверности используем функции subst-record, subst-list и subst-cf. Первая из них строит пару, состоящую из множества подстановок и фактора достоверности, вторая возвращает множество связанных переменных для этой пары, а третья - фактор достоверности. Записи будут представлены как точечные пары вида (<список подстановюо. «рактор достоверности>). Приведем определения этих функций.

/Возвращает список связанных переменных на основе пары ;подстановка-фактор достоверности, (defun subst-list (substitutions)

(car substitutions))

;Возвращает фактор достоверности на основе пары подстановка-фактор ;достоверности. (defun subst-cf (substitutions)

(cdr substitutions))

/Формирует пару множество подстановки-фактор достоверности, (defun subst-record (substitutions cf)

(cons substitutions cf))

Правила и факты в базе знаний тоже связаны с фактором достоверности. Факты представляются точечными парами (<утверждение>. <фактор достоверности>), где <утверждение> - это положительный литерал, а <фактор достоверности> - мера его определенности. Правила записываются в формате (rule if <предпосылка> then <заключение> «рактор достоверности>). Приведем пример правила из предметной области описания цветов.

(rule

if (and (rose (var x)) (color (var x) red)) then (kind (var x) american-beauty) 1)

Определим функции для обработки правил и фактов.

/Возвращает предпосылку правила. (defun premise (rule)

(nth 2 rule))

; Возвращает заключение правила, (defun conclusion (rule)

(nth 4 rule))

; Возвращает фактор достоверности правила. (defun rule-cf (rule)

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

(nth 5 rule))

,-Проверяет, является ли данный шаблон правилом, (defun rulep (pattern)

(and (listp pattern)

(equal (nth 0 pattern) 'rule))) ;Возвращает часть факта, являющуюся шаблоном, (defun fact-pattern (fact)

(car fact))

;Возвращает фактор достоверности факта, (defun fact-cf (fact)

(cdr fact))

С помощью этих функций можно реализовать интерпретатор правил путем модификации интерпретатора для решения задач логического программирования из раздела 15.8.

15.10.2. Архитектура оболочки lisp-shell

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

(defun solve (goal substitutions) (filter-stream

(if (conjunctive-goal-p goal) (filter-through-conj-goals (cdr (body goal))

(solve (car (body goal)) substitutions)) (solve-simple-goal goal substitutions)) #'(lambda (x) (< 0.2 (subst-cf x)))))

Это определение мало отличается от определения функции solve в оболочке logic-shell. Эта функция по-прежнему содержит условный оператор, выделяющий простые и конъюнктивные цели. Различие состоит в использовании обобщенного фильтра filter-stream, удаляющего любые решения, фактор достоверности которых оказывается ниже заданного значения. Эта проверка реализуется с помощью лямбда-выражения. Второе отличие состоит в использовании функции solve-simple-goal вместо формы infer. Обработка простых целей усложняется за счет возможности запросов к пользователю.

(defun solve-simple-goal (goal substitutions) (declare (special *assertions*)) (declare (special *case-specific-data*)) (or (told goal substitutions *case-specific-data*)

(infer goal substitutions *assertions*)

(ask-for goal substitutions)))

В этой функции для поочередного использования трех различных стратегий применяется форма or. Сначала вызывается функция told, проверяющая, было ли данное целевое утверждение уже разрешено пользователем в ответ на предыдущий запрос. Ответы пользователя связываются с глобальной переменной *case-specif ic-data*. Функция told просматривает этот список в поисках соответствия целевому утверждению. Благодаря этому оболочка lisp-shell не запрашивает дважды одну и ту же информацию. Если целевое утверждение

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

в списке ответов не найдено, функция solve-simple-goal пытается вывести это утверждение с помощью правил из базы данных *assertions *. И, наконец, если это не удается, вызывается функция ask-for, отправляющая пользователю запрос на получение информации. Эти функции определены ниже.

Цикл верхнего уровня read-solve-print изменился мало. В него лишь добавлен оператор инициализации переменной *case-specif ic-data* значением nil перед разрешением нового целевого утверждения. Заметим, что при первом вызове функции solve ей передается не просто пустое множество подстановок, а пара, состоящая из пустого множества подстановок и фактора достоверности cf, принимающего значение 0. Это число не имеет реального значения. Оно лишь включается для согласованности синтаксиса и заменяется реальным фактором достоверности, введенным пользователем или полученным из базы знаний.

(defun lisp-shell ()

(declare (special *case-specific-data*))

(setq *case-specific-data* ( ))

(prinl 'lisp-shell> ) ;prinl не выводит новую строку

(let ((goal (read)))

(terpri)

(cond ((equal goal 'quit) 'bye)

(t (print-solutions goal (solve goal (subst-record nil 0)))

(terpri)

(lisp-shell)))))

Функция filter-through-conj-goals не меняется, а функция filter-through-goal должна вычислять фактор достоверности конъюнктивного выражения как минимум соответствующих факторов-конъюнктов. Для этого первый элемент потока substituion-stream связывается с символом subs в блоке let. Затем вызывается функция solve для данного целевого утверждения goal и множества подстановок. Результат передается в обобщенную функцию отображения map-stream, которая получает поток пар подстановок, возвращаемых функцией solve, и пересчитывает их факторы достоверности. Приведем определения этих функций.

(defun filter-through-conj-goals (goals substitution-stream) (if (null goals)

substitution-stream

(filter-through-conj-goals (cdr goals)

(filter-through-goal (car goals) substitution-stream)))) (defun filter-through-goal (goal substitution-stream) (if (empty-stream-p substitution-stream) (make-empty-stream)

(let ((subs (head-stream substitution-stream))) (combine-streams (map-stream (solve goal subs) #'(lambda (x) (subst-record (subst-list x) (min (subst-cf x)

(subst-cf subs)))))

(filter-through-goal goal (tail-stream substitution-stream))))))

Определение функции infer изменяется с учетом факторов достоверности. Хотя общая структура этой функции соответствует ее версии, написанной для интерпретатора раздела 15.8, теперь в этой функции вычисляется фактор достоверности решений на ос-

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

нове факторов достоверности правил и степени соответствия решений предпосылкам правил. Функция solve-rule вызывает функцию solve для нахождения всех решений на основе предпосылок правил и использует функцию map-stream для вычисления результирующего фактора достоверности для заключения этого правила.

(defun infer (goal substitutions kb) (if (null kb)

(make-empty-stream)

(let* ((assertion (rename-variables (car kb))) (match (if (rulep assertion)

(unify goal conclusion assertion) (subst-list substitutions)) (unify goal assertion (subst-list substitutions))))) (if (equal match 'failed)

(infer goal substitutions (cdr kb)) (if (rulep assertion) (combine-streams

(solve-rule assertion (subst-record match (subst-cf substitutions)))

(infer goal substitutions (cdr kb))) (cons-stream (subst-record match (fact-cf assertion))

(infer goal substitutions (cdr kb)))))))) ((defun solve-rule (rule substitutions)

(map-stream (solve (premise rule) substitutions) #'(lambda (x) (subst-record (subst-list x) (* (subst-cf x) (rule-cf rule))))))

И, наконец, с учетом факторов достоверности модифицируется функция print-solutions.

(defun print-solutions (goal substitution-stream)

(cond ((empty-stream-p substitution-stream) nil)

(t (print (apply-substitutions goal (subst-list (head-stream substitution-stream)))) (write-string "cf =")

(prinl (subst-cf (head-stream substitution-stream) )) (terpri)

(print-solutions goal (tail-stream substitution-stream)))))

Остальные функции, в том числе apply-substitutions и функции доступа к компонентам правил и целевых утверждений, остаются неизменными. Их определения приведены в разделе 15.8.

Для реализации оболочки lisp-shell остается определить функции ask-for и told, обрабатывающие взаимодействие с пользователем. Они определяются достаточно просто, однако читатель должен понимать, что при их описании сделаны некоторые упрощающие предположения. В частности, в ответ на запросы можно вводить лишь значения у или п, соответствующие значениям фактора достоверности 1 и -1. Пользователь не может дать недостоверный ответ на запрос. Функция ask-rec выводит запрос и считывает ответ. Эти действия повторяются до тех пор, пока пользователь не ответит у или п. Читатель может дополнить функцию ask-rec таким образом, чтобы принимались

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

любые значения из диапазона от -1 до 1. (Этот диапазон, конечно же, выбран произвольно. В других приложениях можно выбирать другие диапазоны.)

Функция askable проверяет, можно ли задать вопрос пользователю по поводу данного целевого утверждения. Для этого вводится глобальный список *askables*. С его помощью архитектор экспертной системы может определить, для каких целевых утверждений допустимы запросы к пользователю, а какие должны выводиться только из базы знаний. Функция told выполняет поиск элементов в глобальном списке *case-speci fie -data*, содержащем запросы, на которые пользователь уже отвечал. Ее реализация аналогична определению функции infer с учетом того, что в списке *case-specif ic-data* хранятся только факты. Приведем определения этих функций.

(defun ask-for (goal substitutions) (declare (special *askables*)) (declare (special *case-specific-data*)) (if (askable goal *askables*)

(let* ((query (apply-substitutions goal (subst-list substitutions)))

(result (ask-rec query)))

((setq *case-specific-data* (cons (subst-record query result)

*case-specific-data*))

(cons-stream (subst-record (subst-list substitutions) result)

(make-empty-stream))))) (defun ask-rec (query) (prinl query) (write-string ">")

(let ((answer (read))) (cond ((equal answer 'y) 1)

((equal answer 'n) - 1) (t (print "введите у или п") (terpri)

(ask-rec query))))) (defun askable (goal askables) (cond ((null askables) nil)

((not (equal (unify goal (car askables) ( )) 'failed)) t) (t (askable goal (cdr askables))))) (defun told (goal substitutions case-specific-data)

(cond ((null case-specific-data) (make-empty-stream)) (t (combine-streams

(use-fact goal (car case-specific-data)

substitutions)

(told goal substitutions (cdr case-specific-data))))))

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

15.10.3. Классификация с использованием оболочки lisp-she 11

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

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

основные свойства экспертных систем. База знаний связана с двумя глобальными переменными: *assertions* и *askables*. С первой из них связана база данных правил и фактов, а со второй - список целевых утверждений, по которым можно задавать вопросы пользователю. Используемая в этом примере база знаний строится с помощью двух вызовов функции setq.

(setq *assertions*'( (rule

if (and (size (var x) tall) (woody (var x)))

then (tree (var x)) .9) (rule

if (and (size (var x) small) (woody (var x)))

then (bush (var x)) .9) (rule

if (and (tree (var x)) (evergreen (var x))(color (var x)

blue))

then (kind (var x) spruce) .8) (rule

if (and (tree (var x)) (evergreen (var x))(color (var x)

green))

then (kind (var x) pine) .9) (rule

if (and (tree (var x)) (deciduous (var x)) (bears (var x)

fruit))

then (fruit-tree (var x)) 1) (rule

if (and (fruit-tree (var x)) (color fruit red) (taste fruit

sweet))

then (kind (var x) apple-tree) .9) (rule

if (and (fruit-tree (var x)) (color fruit yellow) (taste

fruit sour))

then (kind (var x) lemon-tree) .8) (rule

if (and (bush (var x)) (flowering (var x)) (thorny (var x)))

then (rose (var x)) 1) (rule

if (and (rose (var x)) (color (var x) red))

then (kind (var x) american-beauty) 1))) (setq *askables*'(

(size (var x) (var y)) (woody (var x)) (soft (var x)) (color (var x) (var y)) (evergreen (var x)) (thorny (var x)) (deciduous (var x)) (bears (var x) (var y)) (taste (var x) (var y)) (flowering (var x))))

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

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

> (lisp-shell)

lisp-shell>(kind tree-1 (var x))

(size tree-1 tall) >y

(woody tree-1) >y

(evergreen tree-1) >y

(color tree-1 blue) >n

color tree-1 green) >y

(kind tree-1 pine) cf 0.81

(deciduous tree-1) >n

(size tree-1 small) >n

lisp-shell>(kind bush-2 (var x))

(size bush-2 tall) >n

(size bush-2 small) >y

(woody bush-2) >y

(flowering bush-2) >y

(thorny bush-2) >y

(color bush-2 red) >y

(kind bush-2 american-beauty) cf 0.9

lisp-shell>(kind tree-3 (var x))

(size tree-3 tall) >y

(woody tree-3) >y

(evergreen tree-3) > n

(deciduous tree-3) >y

(bears tree-3 fruit) >y

(color fruit red) >n

(color fruit yellow) >y

(taste fruit sour) >y

(kind tree-3 lemon-tree) cf 0.72

(size tree-3 small) >n

lisp-shell>guit

bye

??

В этом примере можно заметить несколько аномалий. Например, система задает пользователю вопрос о том, является ли дерево низким, хотя уже сообщалось, что оно высокое. В другом случае пользователю задается вопрос о том, является ли дерево лиственным, хотя оно уже охарактеризовано как вечнозеленое. Это типичные примеры поведения экспертной системы. В базе знаний не содержится никакой информации о взаимосвязи понятий "высокий" и "низкий" (определяемых литералами tall и small) или "лиственный" и "вечнозеленый" (deciduous и evergreen). С точки зрения базы знаний это лишь шаблоны для проверки соответствия. Поскольку поиск выполняется полным перебором, то проверяются все правила. Для того чтобы система демонстрировала более глубокие знания, в базе знаний необходимо закодировать и отношения между понятиями. Например, можно написать правило, утверждающее, что small соответствует not tall. В рассматриваемом примере такие отношения не представлены, поскольку в системе lisp-she 11 не реализован оператор not. Читателю предлагается реализовать его в качестве упражнения.

15.11. Семантические сети и наследование в LISP

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

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

ных систем вывода. Мы не будем обсуждать все возможные варианты, а сконцентрируем внимание на основном подходе к построению сетевых представлений с помощью списков свойств (property list). После их использования для определения простой семантической сети будет введена функция для реализации наследования классов. Изложенные в этом разделе идеи являются важным источником развития объектно-ориентированной методологии программирования, описанной в разделе 15.12.

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

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

((а (1 . Ь))

<Ь (2 . с))

(с (2 . Ь) (3 . а)))

Рис. 15.7. Простой маркированный направленный граф

Такой подход положен в основу многих сетевых реализаций. Однако семантические сети можно реализовать и на основе списков свойств (property list).

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

Для управления списками свойств используются функции get, setf, remprop и plist. Функция get вида

(get <символ> <имя-свойства>)

позволяет получить свойство объекта <символ> по его имени. Например, если для символа rose свойство color принимает значение red, а свойство smell - значение sweet, значит, функция get будет вести себя следующим образом.

(get 'rose 'color)

red

(get 'rose 'smell)

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

sweet

(get 'rose 'party-affiliation) nil

Из последнего вызова видно, что при попытке получить значение несуществующего свойства (отсутствующего в списке свойств) функция get возвращает значение nil.

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

(setf <формахзначениё>)

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

? (setq х'(а Ь с d e))

(a b с d e)

? (setf (nth 2 х) 3)

3

? х

(a b 3 d e)

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

(setf (get 'rose 'color) 'red)

red

(setf (get 'rose 'smell) 'sweet)

sweet

Параметрами функции remprop, удаляющей именованное свойство, являются символ и имя свойства. Например,

(get 'rose 'color)

red

(remprop 'rose 'color)

color

(get 'rose 'color)

nil

Функция plist получает в качестве аргумента символ и возвращает список его свойств. Например,

(setf (get 'rose 'color) 'red)

red

(setf (get 'rose 'smell) 'sweet)

sweet

(plist 'rose)

(smell sweet color red)

С помощью списков свойств достаточно просто реализовать семантическую сеть. Например, следующие вызовы функции setf определяют описание семантической сети видов птиц, показанной на рис. 14.7. Отношение isa определяет связи наследования.

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

(setf (get 'animal 'covering) 'skin)

(setf (get 'bird 'covering) 'feathers)

(setf (get 'bird 'travel) 'flies)

(setf (get 'bird 'isa) 'animal)

(setf (get 'fish 'isa) 'animal)

(setf (get 'fish 'travel) 'swim)

(setf (get 'ostrich 'isa) 'bird)

(setf (get 'ostrich 'travel) 'walk)

(setf (get 'penguin 'isa) 'bird)

(setf (get 'penguin 'travel) 'walk)

(setf (get 'penguin 'color) 'brown)

(setf (get 'opus 'isa) 'penguin)

(setf (get 'canary 'isa) 'bird)

(setf (get 'canary 'color) 'yellow)

(setf (get 'canary 'sound) 'sing)

(setf (get 'tweety 'isa) 'canary)

(setf (get 'tweety 'color) 'white)

(setf (get 'robin 'isa) 'bird)

(setf (get 'robin 'sound) 'sings)

(setf (get 'robin 'color) 'red)

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

Функция inherit-get - это вариация функции get, которая сначала пытается получить свойство данного символа. Если это свойство отсутствует, функция inherit-get вызывает функцию get-f rom-parents для реализации поиска. Первым параметром функции get-f rom-parents является либо один родительский объект, либо список таких объектов, а вторым параметром- имя свойства. Если параметр parents принимает значение nil, поиск завершается неудачно. Если родительским объектом является атом, для него вызывается функция inherit-get для получения свойства самого родительского объекта либо продолжения поиска. Если в качестве параметра указан список родителей, функция get-f rom-parents рекурсивно вызывает сама себя для головы и хвоста этого списка. Функция прохода по дереву inherit-get определяется следующим образом.

(defun inherit-get (object property) (or (get object property)

(get-from-parents (get object 'isa) property))) (defun get-from-parents (parents property) (cond ((null parents) nil)

((atom parents) (inherit-get parents property)) (t (or (get-from-parents (car parents) property) (get-from-parents (cdr parents) property)))))

15.12. Объектно-ориентированное программирование с использованием CLOS

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

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

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

Объектно-ориентированное программирование поддерживают многие языки, в том числе Smalltalk, C++, Java и Common LISP Object System (CLOS). На первый взгляд LISP уходит корнями в функциональное программирование, а объектная ориентация с созданием объектов, сохраняющих со временем свое состояние, не вписывается в его исходную концепцию. Однако многие средства языка, в том числе динамическая проверка соответствия типов и возможность динамического создания и разрушения объектов, делают его идеальной основой для создания объектно-ориентированного языка. LISP лежит в основе многих ранних объектно-ориентированных языков, таких как Flavors, KEE и ART. После разработки стандарта Common LISP сообщество его почитателей предложило систему CLOS как средство объектно-ориентированного программирования на LISP.

Чтобы называться объектно-ориентированным, язык программирования должен обеспечивать три возможности: инкапсуляцию (encapsulation), полиморфизм (polymorphism) и наследование (inheritance). Определим эти возможности более детально и опишем, как их поддерживает система CLOS.

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

сложные структуры данных, в которых элементарные (атомарные) элементы объе

диняются в одну структуру. Объектно-ориентированная инкапсуляция - это соче

тание в одной структуре элементов данных и процедур для их обработки. Такие

структуры называются классами (class). Например, рассмотренные в разделе 14.2

абстрактные типы данных вполне обоснованно можно считать классами. В таких

объектно-ориентированных языках, как Smalltalk, инкапсуляция процедур (или ме

тодов) в определении объекта реализуется явно. В CLOS принят другой подход.

Эта возможность реализуется за счет проверки соответствия типов. Здесь поддер

живаются методы, получившие название родовых функций (generic function). Они

проверяют типы своих параметров и тем самым гарантируют, что их можно при

менять только к экземплярам заданного класса объектов. Это можно рассматри

вать как логическую связь методов со своими объектами.

Полиморфизм. Слово "полиморфизм" произошло от двух корней: "поли", озна

чающего "много", и "морф" - "форма". Функция считается полиморфной, если

она демонстрирует различное поведение в зависимости от типов своих аргументов.

Наиболее типичный пример полиморфных функций и их важной роли дают про

стые графические редакторы. Допустим, для каждой фигуры (квадрат, круг, пря

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

классе определить метод draw. Каждый метод должен работать по-разному (в за

висимости от изображаемой фигуры), однако имя у всех одно. Для каждого объек-

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

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

3. Наследование. Наследование - это механизм для поддержки языком программирования абстрактных классов. Оно позволяет определить общие классы и задать структуру и поведение их специализаций. Так, класс деревьев tree может описывать свойства сосен, тополей, дубов и других видов деревьев. В разделе 15.11 был построен алгоритм наследования для семантических сетей. Он иллюстрирует простоту реализации наследования с помощью встроенных в LISP структур данных. Система CLOS обеспечивает более робастный и выразительный встроенный алгоритм наследования.

15.12.1. Определение классов и экземпляров в CLOS

Базовой структурой данных в CLOS являются классы. Класс - это описание множества экземпляров объектов. Классы определяются с помощью макроса defclass, имеющего следующий синтаксис.

(defclass <имя-класса> (<имя-суперкласса>*) {<спецификатор-элемента>*))

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

Спецификатор-элемента ::= имя-элемента\(имя-элемента [параметр])

Например, можно определить класс прямоугольников rectangle, сегментами которого являются длина length и ширина width.

> (defclass rectangle()

(length width)) #

Функция make-instance позволяет создавать экземпляры класса. Ее параметром является имя класса, а возвращаемым значением - его экземпляр. В экземплярах класса хранятся реальные данные. Символ rect можно связать с экземпляром класса rectangle с помощью функций make-instance и setq.

> (setq rect (make-instance 'rectangle))

#

Параметры элементов в определении класса задавать необязательно. Они имеют следующий синтаксис (где символ | означает альтернативные варианты).

параметр :: = :reader <имя-функции-чтения> \

.•writer <имя-функции-записи> | :accessor <имя-функции-чтения> I

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

:allocation <тип-размещения> \ :initarg <имя> \ :initform <форма>

Параметры элементов задаются с помощью ключей. Ключ - это вид необязательного параметра в функции LISP. Перед значением ключа указывается ключевое слово, которое всегда начинается с символа :. Параметры элементов обеспечивают доступ к ним. Ключ : reader определяет имя функции, возвращающей значение данного элемента для конкретного экземпляра. Ключ :writer задает имя функции записи элемента. Ключ : accessor определяет функцию, которая может использоваться для считывания значения элемента или изменения его значения (с помощью функции setq). В следующем примере определяется класс прямоугольников rectangle, элементами которого являются длина length и ширина width с функциями доступа get-length и get-width соответственно. Связав символ rect с экземпляром класса прямоугольников с помощью функции make-instance, воспользуемся функцией доступа get-length для присваивания с помощью функции setq элементу length значения 10. Для считывания этого значения снова воспользуемся функцией доступа.

> (defclass rectangle ()

((length :accessor get-length) (width :accessor get-width))) #

(setq rect (make-instance 'rectangle))

#

(setf (get-length rect) 10)

10

(get-length rect)

10

Помимо функций доступа для обращения к элементам класса можно использовать функцию-примитив slot-value. Она определена для всех элементов. Ее параметром является экземпляр класса и имя элемента, а возвращаемым значением - значение этого элемента. Эту функцию можно использовать совместно с setq для изменения значения элемента. Например, функцию slot-value можно применить для получения значения элемента width экземпляра rect.

(setf (slot-value rect 'width) 5)

5

(slot-value rect 'width)

5

Функция : allocation определяет размещение элемента в памяти. Существует два возможных типа размещения : instance и : class. В первом случае система CLOS размещает элементы класса локально для каждого экземпляра, а во втором - все экземпляры используют один и тот же элемент. Если в качестве типа размещения выбран : class, то значения данного элемента для всех экземпляров совпадают, а его изменения отражаются на всех экземплярах класса. По умолчанию используется тип размещения :instance.

Ключ : initarg позволяет указать аргумент, который будет использоваться функцией make-instance для задания начального значения элемента. Например, можно модифицировать определение класса rectangle, инициализируя значения элементов legth и width его экземпляров.

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

> {defclass rectangle ()

((length :accessor get-length :initarg init-length) (width :accessor get-width :initarg init-width)))

#

>(setq rect (make-instance 'rectangle 'init-length 100 'init-width 50))

#

(get-length rect)

100

(get-width rect)

50

Ключ : ini t form позволяет задавать форму, оцениваемую при каждом обращении к функции make- instance для вычисления начального значения элемента. Например, можно написать программу, запрашивающую у пользователя значения элементов каждого нового экземпляра прямоугольника. Это можно сделать с помощью ключа : ini t form.

(defun read-value (query) (print query)(read))

read-value

(defclass rectangle ()

((length :accessor get-length rinitform

(read-value "введите длину"))

(width :accessor get-width :initform (read-value

"введите ширину")))) #

> (setq rect (make-instance 'rectangle))

"введите длину" 100

"введите ширину" 50 #

(get-length rect)

100

(get-width rect)

50

15.12.2. Определение родовых функций и методов

Родовая функция - это функция, поведение которой зависит от типа ее аргументов. В CLOS родовые функции содержат множество методов (method), индексированных по типу аргументов. Вызов родовой функции аналогичен вызову обычной функции. Просто при ее вызове реализуется метод, связанный с данным типом аргументов.

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

Родовые функции определяются с помощью функций def generic или defmethod. Функция defgeneric позволяет определять родовую функцию и несколько методов с помощью одной формы. Функция defmethod определяет отдельные методы, которые

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