научная статья по теме МОНАДЫ ДЛЯ ФОРМАЛИЗАЦИИ ПРОЦЕДУРЫ СОПОСТАВЛЕНИЯ С ОБРАЗЦОМ Математика

Текст научной статьи на тему «МОНАДЫ ДЛЯ ФОРМАЛИЗАЦИИ ПРОЦЕДУРЫ СОПОСТАВЛЕНИЯ С ОБРАЗЦОМ»

ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ПРОГРАММИРОВАНИЯ

УДК 681.3.06

МОНАДЫ ДЛЯ ФОРМАЛИЗАЦИИ ПРОЦЕДУРЫ СОПОСТАВЛЕНИЯ С ОБРАЗЦОМ *

© 2014 г. A.B. Жожикашвили

Институт проблем передачи информации РАН 127994 Москва, ГСП-4, Большой Каретный переулок, 19, стр. 1.

E-mail: zhozhik@iitp.ru Поступила в редакцию 27.12.2012

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

1. ВВЕДЕНИЕ

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

* Работа выполнена при поддержке РФФИ, грант 0907-00233 и по программе N211 Президиума РАН

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

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

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

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

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

Однако область использования правил, основанных на описанной выше процедуре сопоставления с образцом, значительно шире, чем задачи искусственного интеллекта. К таким правилам относятся, например, правила, используемые в нормальном алгоритме Маркова [4] или в лингвистических конструкциях Н. Хомского [5]. Техника сопоставления с образцом (pattern matching) широко используется в программировании. Существуют языки программирования, основанные на правилах, например, язык Prolog. Формализации таких правил в самом широком понимании и посвящена дальнейшая часть статьи. В статье используется существенно более развитый теоретико-категорный аппарат, чем применялся в прежних работах автора.

2. СИТУАЦИИ, ОБРАЗЦЫ, СОПОСТАВЛЕНИЕ

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

Пусть S - множество ситуаций, которые могут возникнуть при работе некоторой системы, использующей правила. Каждому образцу соответствует множество X допустимых конкретиза-торов, которые могут быть использованы для его конкретизации. Сам образец можно рассматривать как отображение ф : X ^ S. Образец сопоставим с ситуацией s £ S, если s имеет прообраз в X. Правило - это пара образцов ф : X ^ S, ф : X ^ S с одинаковыми множествами ситуаций и конкретизаторов. Можно рассмотреть также чуть более общий случай - правило из S в T, представляющее собой пару образцов ф : X ^ S и ф : X ^ T. Правило применимо в ситуации s £ S, или, как я буду писать в дальнейшем,

s, s

поставима с левой частью правила - образцом ф : X ^ S, т.е. если найдется конкретизатор х £ X такой, что ф(х) = s. В этом случае резуль-

s

ситуация ф(х). Отметим, что результат применения правила к ситуации определен неоднознач-

x

дит к различным результатам.

Приведем ряд примеров, иллюстрирующих введенные понятия.

Начнем с известного всем образца - шаблона имени файла. Скажем, запись «paper*.doc» во многих операционных системах означает файл, имя которого начинается с «paper» и оканчивается на «.doc». В этом примере ситуация - это имя файла, т.е. строка символов, «paper*.doc» -образец, не полностью определенная ситуация, он содержит информацию о том, что стоит в начале и в конце строки, но не сообщает, что стоит в середине. Конкретизация - подстановка

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

Такой же по сути пример дает правило нормального алгоритма Маркова. Скажем, правило аЬ ^ Ьа означает, что если в строке символов встретилась подстрока аЬ, ее следует заменить на Ьа. Левая часть этого правила - образец. В нем содержится информация о том, что в стро-

а Ь,

не говорится о том, что стоит перед ними и после них. Конкретизация - явное указание этих двух подстрок. Таким образом, в этом примере б _ множество последовательностей символов из некоторого множества А, X = Б2, образец ф : X ^ Б задается формулой ф(з,1) = ваЫ, где з,1 е Б, образец ф : X ^ Б - формулой ф(з, ¿) = зЬа1.

Еще один пример. Рассмотрим правило х + у ^ у + х, означающее, что в арифметическом выражении можно переставить местами слагаемые. Если Е - множество правильно построенных арифметических выражений, левую часть правила можно рассматривать как отображение Е2 ^ Е, ставящее в соответствие паре выражений (в1,в2) е Е2 выражение, получающееся подстановкой в1, в2 вместо переменных х и у в х + у. Соответственно, правая часть - отображение, ставящее в соответствие паре выражений (в1, в2) выражение в2 + е1. Хотя этот пример близок к предыдущему, есть и различие, состоящее в том, что выражения - это не строки, а более сложные структуры. К примеру, выражение а(Ь + с) не сопоставимо с образцом х + у, ибо а(Ь не является правильным арифметическим выражением.

3. ОБРАЗЦЫ НА ЯЗЫКЕ ТЕОРИИ КАТЕГОРИЙ

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

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

На языке теории категорий основные понятия, связанные с сопоставлением, определяются сле-

Б

Б-образцом называется любой морфизм ф : X ^ Б, где X - произвольный объект категории. Мно-Б

Б

физмы являются ситуациями, определяется спецификой конкретной задачи. Единствен

Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.

Показать целиком