Шаг 60.
Фундаментальные типы данных. Списки свойств

    На этом шаге мы рассмотрим списки свойств.

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

    Список свойств может быть пустым.

    Атом вместе со списком свойств имеет структуру, изображенную ниже (что такое P-имя атома Вы узнаете, если загляните в замечание 3 в конце этого шага):


Рис.1. Структура атома со списком свойств

    Доступ к списку свойств всегда открывается через информационную ячейку данного атома. На рисунке буква A обозначает специальный адрес, по которому могут быть распознаны информационные ячейки.

    Список свойств состоит из звеньев - по две ячейки в каждом звене. Первая ячейка каждого звена содержит так называемый индикатор ik - наименование свойства. Более точно, индикатор - это адрес информационной ячейки атома, используемого в качестве наименования свойства. Во второй ячейке звена содержится адрес pk самого свойства - определяющего выражения функции.

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

    1. Присваивание нового свойства или изменение значения существующего свойства осуществляется псевдофункцией PUT

    (PUT VARIABLE PROPNAME PROPVAL),
где:

    Функция PUT возвращает значение ее третьего аргумента PROPVAL. Например:

   $ (PUT USA CAPITAL WASHINGTON)
   WASHINGTON
   $ (PUT FRANCE CAPITAL PARIS)
   PARIS
   $ (PUT JAPAN CAPITAL TOKYO)
   TOKYO

    Побочный эффект заключается в модификации списка свойств атома VARIABLE:

    Приведем код этой функции:

   (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) ,
где: Например:
   $ (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) ,
где:

    Функция 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) ,
где:

    Функция 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-выражений могут храниться в списках свойств атомов, описывающих тип. Эти функции в дальнейшем могут быть легко извлечены, когда появляется аргумент данного типа. Таким образом, облегчается программирование, управляемое данными, тот стиль программирования, в котором граничная линия между программами и данными становится еще более размытой, чем обычно. Программирование, управляемое данными, особенно уместно, если на этапе начала построения системы, трудно предвидеть типы рассматриваемых объектов.


    Замечания.
  1. Атомы и их свойства графически можно изобразить в виде таблицы свойств:


    Рис.2. Таблица свойств

        Нетрудно видеть, что таблица свойств является другим способом представления списка свойств атома. В самом деле, взгляните на соответствующие таблице свойств списки свойств атомов BAR и Витамин:


    Рис.3. Список свойств атома BAR


    Рис.4. Список свойств атома Витамин

        Грубо говоря, значение атома - это просто одно из свойств, которым может обладать атом. Атомы T и NIL являются особыми атомами в том отношении, что их значения заранее положены равными T и NIL.

  2. Введение в язык LISP средств поддержки атомов со списком свойств способствовало эффективной реализации:

        Понятие фрейма неформально определено М.Минским как "структура данных для представления стереотипной ситуации. С каждым фреймом ассоциирована информация разных видов. Одна ее часть указывает, каким образом следует использовать данный фрейм, другая - что предположительно может повлечь за собой его выполнение, третья - что следует предпринять, если эти ожидания не подтвердятся. Фрейм можно представлять себе в виде сети, состоящей из узлов и связей между ними. "Верхние уровни" фрейма четко определены, поскольку образованы такими понятиями, которые всегда справедливы по отношению к предполагаемой ситуации. На более низких уровнях имеется много особых вершин-терминалов или "ячеек", которые должны быть заполнены характерными примерами или данными" [1, с.7].

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

        Позже эта интерпретация понятия "фрейм" изменилась. Под фреймами стали понимать описания вида "Имя фрейма (Множество слотов)".

        Каждый слот есть пара вида (!)

       (Имя слота. Значение слота).
    

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

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

       

  3. Как Вам уже давно известно, простейшими типами данных в muLISP являются атомы и точечные пары. Тип объектов данных может быть определен с помощью функций, предназначенных для распознавания типов, например: ATOM, NUMBERP, NAME и др.

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

        Атом - это объект данных, состоящий из четырех элементов-указателей:


    Рис.5. Структура атома

        Опишем их назначение:

    • Value (указатель значения атома) - этот элемент содержит указатель текущего значения атома. При создании атома эа его значение принимается он "сам" (его "печатное" имя), и ссылка на него устанавливается в элементе Value. Такая автоматическая ссылка символа самого на себя называется автоссылкой. Для изменения содержимого элемента Value атома используются функции типа SET, SETQ и т.д.. При вызове функции содержимое элемента Value временно переопределяется с учетом фактических параметров функции, а после выполнения тела функции содержимое элемента Value восстанавливаются;
    • Property (указатель списка свойств) - этот элемент содержит указатель списка свойств атома. Список используется и модифицируется с помощью специальных функций для работы со свойствами (PUT, GET, REMPROP) и флагов. При создании атома Property содержит NIL;
    • Function (указатель функции) - этот элемент содержит указатель на определение функции. При создании атома его функциональный элемент содержит NIL;
    • Р-name (указатель "печатного" имени атома). Этот элемент содержит указатель на Print-имя атома. Для диалекта muLISP85 первые 2 байта содержат длину имени атома, а остальные - само имя атома. Следовательно, имена "ограничены" по размеру - не более 65536 символов. Как только тело Print-имени считано или образовано с помощью какой-нибудь строковой функции, включается в работу алгоритм хэширования, определяющий, существует ли уже атом с таким же Print-именем. Если да, то используется существующий атом. Если нет, то создается новый атом с новым P-name. Никакие два атома в системе не могут иметь одинаковые P-имена, более того, созданное однажды Р-name атома не может быть видоизменено.

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

       $ (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))
    
  4. Заметим, что список свойств может быть организован разными способами. Приведем самый простой [3, с.66-67].

        Список имеет структуру, изображенную ниже (смысл обозначений такой же, как и ранее):


    Рис.6. Структура списка

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

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





(1)Минский М. Фреймы для представления знаний. - М.: Энергия, 1979. - 152 с.
(2)Агафонов В.Н. Спецификация программ: понятийные средства и их организация. - Новосибирск: Наука, 1987. - 240 с.
(3)Лавров С.С., Силагадзе Г.С. Автоматическая обработка данных. Язык лисп и его реализация. - М.: Наука, 1978. - 176 с.


    На следующем шаге мы рассмотрим использование стека.




Предыдущий шаг Содержание Следующий шаг