На этом шаге мы рассмотрим списки свойств.
Мы уже знаем, что атомы могут быть наделены различными свойствами - атом может быть наименованием переменной, константы, функции или же числом. Все это отражено в памяти в виде так называемого списка свойств атома (P-список, Property List). Среди прочих свойств в этом списке должно содержаться и P-имя (это внешнее представление атома) - последовательность литер, изображающих его в программе.
Список свойств может быть пустым.
Атом вместе со списком свойств имеет структуру, изображенную ниже (что такое P-имя атома Вы узнаете, если загляните в замечание 3 в конце этого шага):
Рис.1. Структура атома со списком свойств
Доступ к списку свойств всегда открывается через информационную ячейку данного атома. На рисунке буква A обозначает специальный адрес, по которому могут быть распознаны информационные ячейки.
Список свойств состоит из звеньев - по две ячейки в каждом звене. Первая ячейка каждого звена содержит так называемый индикатор ik - наименование свойства. Более точно, индикатор - это адрес информационной ячейки атома, используемого в качестве наименования свойства. Во второй ячейке звена содержится адрес pk самого свойства - определяющего выражения функции.
Список свойств атома можно по необходимости обновлять или удалять, однако программист должен сам предусматривать и обрабатывать интересующие его свойства.
1. Присваивание нового свойства или изменение значения существующего свойства осуществляется псевдофункцией PUT
(PUT VARIABLE PROPNAME PROPVAL),
- VARIABLE - атом;
- PROPNAME - имя свойства;
- PROPVAL - значение свойства.
Функция PUT возвращает значение ее третьего аргумента PROPVAL. Например:
$ (PUT USA CAPITAL WASHINGTON) WASHINGTON $ (PUT FRANCE CAPITAL PARIS) PARIS $ (PUT JAPAN CAPITAL TOKYO) TOKYO
Побочный эффект заключается в модификации списка свойств атома VARIABLE:
- если в списке свойств не было свойства с именем PROPNAME, то свойство с таким именем и значением PROPVAL будет добавлено в список;
- если свойство с именем PROPNAME уже присутствовало в списке свойств атома VARIABLE, то значение этого свойства будет заменено на новое значение PROPVAL.
Приведем код этой функции:
(DEFUN PUT (SYM KEY OBJ)
( (NULL (ASSOC KEY (CDR SYM)) )
( RPLACD SYM (ACONS KEY OBJ (CDR SYM))) OBJ )
( RPLACD (ASSOC KEY (CDR SYM)) OBJ ) OBJ
)
2. Выяснить значение свойства, связанного с атомом, можно с помощью функции GET:
(GET VARIABLE PROPNAME) ,
- VARIABLE - атом;
- PROPNAME - имя свойства.
$ (PUT A SVOISTVO 1111) 1111 $ (GET A SVOISTVO) 1111
В приведенном ниже примере предполагается, что была выполнена команда PUT.
$ (GET FRANCE CAPITAL) PARIS $ (GET USA CAPITAL) WSHINGTON $ (GET AUSTRIA CAPITAL) NIL
Если у атома VARIABLE отсутствует свойство PROPNAME, то функция возвращает NIL.
Приведем код этой функции:
(DEFUN GET (SYM KEY)
( (NULL (ASSOC KEY (CDR SYM))) NIL )
( CDR (ASSOC KEY (CDR SYM)) )
)
3. Удаление свойства и его значения осуществляется псевдофункцией REMPROP:
(REMPROP VARIABLE PROPNAME) ,
- VARIABLE - атом;
- PROPNAME - имя свойства.
Функция REMPROP возвращает в качестве значения имя удаляемого свойства. Если удаляемого свойства нет, то возвращается NIL.
Свойство можно "удалить", присвоив ему значение NIL:
(PUT VARIABLE PROPNAME NIL)
В этом случае имя свойства и значение NIL физически остаются в списке свойств.
В примере предполагается, что приведенные выше действия с функцией PUT выполнены:
$ (REMPROP USA CAPITAL) WASHINGTON $ (GET FRANCE CAPITAL) PARIS $ (GET USA CAPITAL) NIL
Приведем код этой функции:
(DEFUN REMPROP (SYM KEY)
( (ATOM (CDR SYM)) NIL )
( (EQUAL (CAADR SYM) KEY)
(SETQ KEY (CDADR SYM))
(RPLACD SYM (CDDR SYM))
KEY )
( REMPROP (CDR SYM) KEY )
)
Пример 1. Пусть X и Y - атомы, у которых имеется свойство VAL, значением которого является число. Функция VALPLUS возвращает сумму значений свойства VAL ее аргументов.
(DEFUN VALPLUS (LAMBDA (X Y VAL) ; X и Y - атомы ; ; VAL - свойство атомов X и Y ; (+ (GET X VAL) (GET Y VAL)) ))
Протестируем приведенную функцию, выполнив следующую последовательность действий:
$ (PUT X VAL 3) 3 $ (PUT Y VAL 4) 4 $ (VALPLUS X Y VAL) 7
Уточните определение функции, включив в нее проверку значения свойства VAL с помощью предиката NUMBERP.
Следующий пример является очень важным!
Пример 2.
$ (SETQ A 0) 0 $ (PUT A SVOISTVO1 111) 111 $ (PUT A SVOISTVO2 222) 222 $ (CAR A) 0 $ (CDR A) ((SVOISTVO1 . 111) (SVOISTVO2 222))
Таким образом, вычисление функции CDR от P-имени атома позволяет "проникнуть" в список свойств! Оказывается, что список свойств - это ассоциативный список, где на месте ключей расположены свойства, а на месте данных, ассоциированных с ключами, находятся значения соответствующих свойств.
4. Для описания свойств, принимающих всего два возможных значения, в языке LISP имеется механизм флагов.
Флаг - это свойство без значения. Единственно, что можно сказать о флаге - есть он у атома или нет.
Для того, чтобы снабдить атом флагом, существует функция FLAG. Эта функция имеет два аргумента. Первый - список атомов, второй - имя флага:
(FLAG ATOM FLAGNAME) ,
- ATOM - атом;
- FLAGNAME - имя флага, который появится у атома.
Функция FLAG делает FLAGNAME первым элементом в списке свойств атома ATOM, если он там отсутствовал. Например:
$ (FLAG JOHN MALE) $ (FLAG SUE FEMALE) MALE FEMALE
(DEFUN FLAG (SYM ATTRIB)
( (FLAGP SYM ATTRIB) ATTRIB )
( RPLACD SYM (CONS ATTRIB (CDR SYM)))
ATTRIB
)
Функция (REMFLAG ATOM FLAGNAME) "снимает" с атома ATOM флаг FLAGNAME (удаляет флаг FLAGNAME из списка свойств атома ATOM) и возвращает T. Если флаг не найден, то функция возвращает NIL. Например:
$ (FLAG JAN MALE) MALE $ (FLAG JAN TALL) TALL $ (REMFLAG JAN MALE) T $ (FLAGP JAN MALE) NIL $ (FLAGP JAN TALL) (TALL)
(DEFUN REMFLAG (SYM ATTRIB)
( (ATOM (CDR SYM)) NIL )
( (EQUAL ATTRIB (CADR SYM)) (RPLACD SYM (CDDR SYM))
T )
( REMFLAG (CDR SYM) ATTRIB )
)
Если FLAGNAME является элементом списка свойств атома ATOM, то функция (FLAGP ATOM FLAGNAME) возвращает значение не NIL (а именно: список свойств, начиная с FLAGNAME), иначе - NIL. Например:
$ (FLAGP JOHN MALE) (MALE) $ (FLAGP SUE MALE) NIL
Приведем код функции:
(DEFUN FLAGP (SYM ATTRIB)
(MEMBER ATTRIB (CDR SYM) 'EQUAL)
)
Пример 3.
(DEFUN DEMO_1 (LAMBDA NIL
; Присвоим значения свойствам атома P1 ;
(PUT P1 PROP1 111)
(PUT P1 PROP2 222)
(PUT P1 PROP3 333)
; Посмотрим значения свойств ;
(PRINT (GET P1 PROP1))
(PRINT (GET P1 PROP2))
(PRINT (GET P1 PROP3))
; Взглянем на список свойств ;
(PRINT (CDR P1))
; Установим флаг с именем FL у атома P1 ;
(FLAG P1 FL)
; Проверим наличие флага с именем FL у атома P1 ;
(PRINT (FLAGP P1 FL))
; Взглянем на список свойств ;
(PRINT (CDR P1))
; "Снимем" у атома P1 флаг FL ;
(REMFLAG P1 FL)
; Проверим наличие флага с именем FL u атома P1 ;
(PRINT (FLAGP P1 FL))
; Взглянем на список свойств ;
(PRINT (CDR P1))
))
Результаты работы функции:
111 222 333 ((PROP3 . 333) (PROP2 . 222) (PROP1 . 111)) (FL (PROP3 . 333) (PROP2 . 222) (PROP1 . 111)) (FL (PROP3 . 333) (PROP2 . 222) (PROP1 . 111)) NIL ((PROP3 . 333) (PROP2 . 222) (PROP1 . 111)) ((PROP3 . 333) (PROP2 . 222) (PROP1 . 111))
Списки свойств служат полезными хранилищами информации, отражающими знания об объектах, их свойствах и взаимосвязях. Большая часть ставших классическими больших программ в значительной степени опирается на использование списков свойств.
Специфические для некоторого типа данных функции в форме LAMBDA-выражений могут храниться в списках свойств атомов, описывающих тип. Эти функции в дальнейшем могут быть легко извлечены, когда появляется аргумент данного типа. Таким образом, облегчается программирование, управляемое данными, тот стиль программирования, в котором граничная линия между программами и данными становится еще более размытой, чем обычно. Программирование, управляемое данными, особенно уместно, если на этапе начала построения системы, трудно предвидеть типы рассматриваемых объектов.
Замечания.
- Атомы и их свойства графически можно изобразить в виде таблицы свойств:
Рис.2. Таблица свойств
Нетрудно видеть, что таблица свойств является другим способом представления списка свойств атома. В самом деле, взгляните на соответствующие таблице свойств списки свойств атомов BAR и Витамин:
Рис.3. Список свойств атома BAR
Рис.4. Список свойств атома Витамин
Грубо говоря, значение атома - это просто одно из свойств, которым может обладать атом.
Атомы T и NIL являются особыми атомами в том отношении, что их значения заранее положены
равными T и NIL.
Понятие фрейма неформально определено М.Минским как "структура данных для представления стереотипной ситуации.
С каждым фреймом ассоциирована информация разных видов. Одна ее часть указывает, каким образом следует использовать данный фрейм,
другая - что предположительно может повлечь за собой его выполнение, третья - что следует предпринять, если эти ожидания не подтвердятся.
Фрейм можно представлять себе в виде сети, состоящей из узлов и связей между ними. "Верхние уровни" фрейма четко определены, поскольку
образованы такими понятиями, которые всегда справедливы по отношению к предполагаемой ситуации. На более низких уровнях имеется
много особых вершин-терминалов или "ячеек", которые должны быть заполнены характерными примерами или данными" [1, с.7].
Отметим, что в искусственном интеллекте произошла трансформация смысла понятия "фрейм". М.Минский понимал под
фреймом объекта или явления то его минимальное описание, которое содержит всю существенную информацию об
этом объекте или явлении и обладает тем свойством, что удаление из описания любой его части приводит к потере существенной информации,
без которой описание объекта или явления не может быть достаточным для их идентификации.
Позже эта интерпретация понятия "фрейм" изменилась. Под фреймами стали понимать описания вида "Имя фрейма (Множество слотов)".
Каждый слот есть пара вида (!)
(Имя слота. Значение слота).
Допускается, чтобы слот сам был фреймом. Тогда в качестве значений слота выступает множество слотов. Для заполнения слотов могут быть использованы константы, переменные, любые допустимые выражения в выбранной модели знаний, ссылки на другие слоты и фреймы и т.п.
Под сетью можно понимать любую графовую структуру, но чаще графы с каким-нибудь специальным свойством (оно соответственно оговаривается в определении сети) [2, с.109].
Каждый объект данных конкретного типа состоит из фиксированного числа указателей, которые мы в дальнейшем будем называть элементами. Элементы указывают на другие объекты данных (т.е. содержат адреса их местонахождения в памяти). Множество всех объектов данных образовывает связанную сеть указателей, называемую областью данных. Элементы могут указывать на другие объекты только внутри области данных. Следовательно, область данных в этом смысле является "замкнутой".
Атом - это объект данных, состоящий из четырех элементов-указателей:
Рис.5. Структура атома
Опишем их назначение:
В силу сказанного, становится ясно, что литеральный атом может одновременно именовать некоторое значение и функцию, и эти возможности не мешают друг другу. Позиция атома в выражении определяет его интерпретацию. Например:
$ (DEFUN LIST1 (LAMBDA (X Y) (CONS (CONS Y NIL))) LIST1 $ (SETQ LIST1 A) A $ (LIST1 LIST1 B) (A B) $ (GETD LIST1) (LAMBDA (X Y) (CONS (CONS Y NIL))
Список имеет структуру, изображенную ниже (смысл обозначений такой же, как и ранее):
Рис.6. Структура списка
Описанная структура списков свойств атомов удобна тем, что число свойств у атома не ограничивается, наряду со стандартными свойствами атому можно приписывать любые дополнительные свойства, которые могут понадобиться в программе. Для исследования и преобразования списков свойств можно пользоваться теми же средствами, которые применяются для обработки любых других списков.
Недостаток этой структуры в том, что списки свойств занимают много места в памяти, и на их просмотр может уходить много времени.
(1)Минский М. Фреймы для представления знаний. - М.: Энергия, 1979. - 152 с.
(2)Агафонов В.Н. Спецификация программ: понятийные средства и их организация. - Новосибирск: Наука, 1987. - 240 с.
(3)Лавров С.С., Силагадзе Г.С. Автоматическая обработка данных. Язык лисп и его реализация. - М.: Наука, 1978. - 176 с.
На следующем шаге мы рассмотрим использование стека.
