На этом шаге мы рассмотрим реализацию задачи сопоставления с образцом.
Часто при обработке символьной информации приходится решать вопрос об эквивалентности двух символьных объектов. Такая задача возникает обычно в случае, когда заданы некоторые правила в виде левой части (образец), правой части и условия. Если обрабатываемая символьная информация может быть отождествлена с образцом таким образом, что условие будет выполнено, то для ее дальнейшей обработки используется правая часть, входящая в состав данного правила.
Сопоставление с образцом - это процесс сравнения символьных выражений. Он является неотъемлемой частью любой развитой системы аналитических вычислений на ЭВМ.
В языке LISP в отличие, например, от Рефала [1, 2] нет встроенного механизма для работы с образцами. Однако программу, позволяющую сопоставлять достаточно сложные образцы, можно легко написать. В этом смысле говорят, что LISP является хорошим языком для реализации сопоставления образцов.
Итак, предположим, что у нас имеются два списка атомов: образец и факт. Часто список, соответствующий факту, будет использоваться для представления истинных утверждений, относящихся к некоторому реальному или вымышленному миру.
Ниже мы построим функцию MATCH, которая будет сопоставлять один образец и один факт [3,с.380-384].
Когда с некоторым фактом сравнивается образец, не содержащий специальных атомов (? и *), то сопоставление считается успешным только тогда, когда они одинаковы, т.е. каждая позиция занята одинаковыми атомами.
Мы будем придерживаться стратегии движения вдоль образца и вдоль факта атом за атомом, проверяя, совпадают ли атом образца и атом факта в каждой позиции.
(DEFUN MATCH (LAMBDA (P D)
; P - образец; D - факт ;
(COND ( (AND (NULL P) (NULL D)) T )
( (OR (NULL P) (NULL D)) NIL )
( (EQ (CAR P) (CAR D)) (MATCH (CDR P) (CDR D)) )
)
))
Расширим полезные возможности функции MATCH. Предположим, что образец содержит специальный атом ?. Выделенный атом ? обладает тем свойством, что он сопоставим с любым атомом.
Обобщим функцию MATCH:
(DEFUN MATCH (LAMBDA (P D)
; P - образец; D - факт ;
(COND ( (AND (NULL P) (NULL D)) T )
( (OR (NULL P) (NULL D)) NIL )
( (OR (EQ (CAR P) '?) (EQ (CAR P) (CAR D)))
(MATCH (CDR P) (CDR D))
)
)
))
В MATCH совершается рекурсия пока текущий первый атом в образце является либо ?, либо совпадает с текущим первым атомом в факте.
Атом * также расширяет возможности функции MATCH, благодаря тому, что он сопоставим с одним или несколькими атомами. Образцы, содержащие атом *, могут оказаться сопоставимыми с фактами, у которых больше атомов, чем в образце.
Продолжим обобщение функции MATCH:
(DEFUN MATCH (LAMBDA (P D)
; P - образец; D - факт ;
(COND ( (AND (NULL P) (NULL D)) T )
( (OR (NULL P) (NULL D)) NIL )
( (OR (EQ (CAR P) '?) (EQ (CAR P) (CAR D)))
(MATCH (CDR P) (CDR D))
)
( (EQ (CAR P) '*)
(COND ( (MATCH (CDR P) D) )
( (MATCH (CDR P) (CDR D)) )
( (MATCH P (CDR D)) )
)
)
)
))
Тестовые примеры:
$ (MATCH '(* is *) '(My Name is John)) T $ (MATCH '(Color is ?) '(Color is Red)) T
Переключаемое звездочкой предложение COND обеспечивает рекурсивное обращение к MATCH. Срабатывает одна из трех возможностей:
1) * ни с чем не сопоставима, в этом случае она выбрасывается и сопоставлению подвергается остальная часть образца;
2) * сопоставима с одним атомом, в этом случае отбрасывается и *, и этот атом;
3) * сопоставима с двумя или более атомами, в этом случае мы продолжаем действовать в рекурсивной манере, сохраняя * в образце, отбрасывая первые атомы, с которыми она сопоставима успешно.
Второй член в указанном предложении COND на самом деле излишен, если * может сопоставляться с любым числом атомов, включая нулевое их число. От него можно избавиться, и функция MATCH будет все равно работать. В этом случае MATCH отделяет * и сопоставляет оставшуюся часть P с нетронутым списком D или же сохраняет * и передвигается на один атом в данных в предположении, что это один из атомов, сопоставимых с *.
С другой стороны, в этой функции COND может быть опущено первое предложение, а не второе. Тогда * должна будет обязательно сопоставима, по крайней мере с одним атомом, как и определялось первоначально [3, с.383].
Следующее направление усовершенствования лежит в обобщении функции MATCH таким образом, чтобы она присваивала определенные значения, когда сопоставление проходит успешно [3, с.384-387].
Пусть атомы, P-имена которых начинаются с символов > или *, действуют как ? и * в процессе сопоставления, но в случае успеха их значениями становится то, с чем они сопоставимы. Ясно, что атомы, чьи P-имена начинаются с >, должны иметь в качестве значений атомы, тогда как атомы с P-именами, начинающимися с *, должны иметь в качестве значений списки сопоставляемых атомов. Обозначение >, использованное здесь, должно наводить на мысль о "заталкивании" значений в атомы, чьи P-имена содержат "предлог" >.
Например:
$ (MATCH '(PLUS >A >B) '(PLUS 2 3)) T $ A 2 $ B 3 $ (MATCH '(*L is *R) '(My Name is John)) T $ L (My Name) $ R (John)
Сопоставление с > и присваивание могут быть реализованы путем использования функций ATOMCAR и ATOMCDR:
(DEFUN ATOMCAR (LAMBDA (X) ; Выделение первого символа имени литерного атома ; (CAR (UNPACK X)) )) ; ---------------------- ; (DEFUN ATOMCDR (LAMBDA (X) % Выделение "хвоста" имени литерного атома % (PACK (CDR (UNPACK X))) ))
Обратите внимание на использование SET для присваивания значения переменной образца тому элементу в данных, с которым оно сопоставимо:
( (AND (EQ (ATOMCAR P) >) (MATCH (CDR P) (CDR D)))
(SET (ATOMCDR P) (CAR D))
)
Переменные со * обрабатываются таким же образом , на этот раз путем присваивания им значения в виде списков атомов, которые сопоставимы с этими переменными, с использованием следующего:
( (EQ (ATOMCAR (CAR P)) '*)
(COND ( (MATCH (CDR P) (CDR D))
(SET (ATOMCDR (CAR P)) (LIST (CAR D))) T)
( (MATCH P (CDR D))
(SET (ATOMCDR (CAR P))
(CONS (CAR D) (EVAL (ATOMCDR (CAR P))))) T)
)
)
Заметьте, что никакого присваивания и никакого применения SET не происходит до тех пор, пока не будет проведена вся рекурсия и не будет заведомо известно, что сопоставление удалось.
Приведем окончательный вариант функции MATCH:
(DEFUN MATCH (LAMBDA (P D) ; P - образец; D - факт ; (COND ( (AND (NULL P) (NULL D)) T ) ( (OR (NULL P) (NULL D)) NIL ) ( (OR (EQ (CAR P) '?) (EQ (CAR P) (CAR D))) (MATCH (CDR P) (CDR D)) ) ( (AND (ATOM (CAR P)) (EQ (ATOMCAR (CAR P)) '>) (MATCH (CDR P) (CDR D))) (SET (ATOMCDR (CAR P)) (CAR D)) T ) ( (EQ (CAR P) '*) (COND ( (MATCH (CDR P) (CDR D)) ) ( (MATCH P (CDR D))) ) ) ( (AND (ATOM (CAR P)) (EQ (ATOMCAR (CAR P)) '*)) (COND ( (MATCH (CDR P) (CDR D)) (SET (ATOMCDR (CAR P)) (LIST (CAR D))) T) ( (MATCH P (CDR D)) (SET (ATOMCDR (CAR P)) (CONS (CAR D) (EVAL (ATOMCDR (CAR P)))) ) T ) ) ) ) )) ; ---------------------- ; (DEFUN ATOMCAR (LAMBDA (X) ; Выделение первого символа имени литерного атома ; (CAR (UNPACK X)) )) ; ---------------------- ; (DEFUN ATOMCDR (LAMBDA (X) ; Выделение "хвоста" имени литерного атома ; (PACK (CDR (UNPACK X))) ))
Описанная система сопоставления является простой, потому что она ориентирована на сопоставление одного списка атомов с другим. Более того, не существует представления о степени близости: либо сопоставление успешно, либо нет. Работа с сетями, фреймами или другими большими объемами знаний может оказаться намного более трудным делом, потому что возникают следующие возможности:
- система сопоставления должна выдавать некоторый показатель по шкале, простирающейся от полного отсутствия совпадения до абсолютного совпадения;
- система сопоставления должна работать с "более" разнообразными структурами.
Включение этих возможностей может оказаться чрезвычайно трудной задачей.
(1) Базисный Рефал и его реализация на вычислительных машинах. / ЦНИПИАСС. - М., 1977. - 238 с.
(2) Турчин В.Ф. Базисный РЕФАЛ. Описание языка и основные приемы программирования. - М.: ЦНИПИАСС, 1974. - 258 с.
(3) Уинстон П. Искусственный интеллект. - М.: Мир, 1980, с.303-512.
На следующем шаге мы смоделируем психиатра.
