автореферат диссертации по документальной информации, 05.25.01, диссертация на тему:Системы программирования с исключениями из правил

АКАДЕМИЯ НАУК СССР ИНСТИТУТ ПРОБЛЕМ ИНФОРМАТИКИ

На правах рукописи

КУЗШОВ ВЛАДИМИР ЕВГЕНЬЕВИЧ

УДК 681.3.06

СИСТЕМЫ ПРОГРАММИРОВАНИЯ С ИСШЧШЯШ 13 ПРАВИЛ

Специальность: 05.25.fi - Теоретические основы информатика

Автореферат диссертации на соискание учевой степени доктора технических наук

¿2. 06, Москва - 1988

31£

$в.бвт вшолаева во ВНИШдвагроярявод НПО "Элекгро-врав0д"с у» Иосава.

Офецкедьш© оппоненты:

Доктор хехшгчвских каух, профессор Поспелов Д.А.

Доктор «еквическнк наук, профессор Кутепоз В.П. Доктор технических щук, профессор Растрате 1„А»

В®душя ору&шазацшк:

Евбпгеу? вробяаи управлвшя АН СССР

Защита сссмнгея я- .. ".............. 1989 г. в " с

ев заседашш специализированного совета Д003,56*01 оря Явсгазузд пробяен информатики АН СССР по адресу: II7900, т. Москва» уя„Вавилова 10/6.

G диссертацией aesso ©знахомигшз в библиотек® висга-

ryz&c

р.

(О

Ученый секретарь

спвцшалйЗйровавного созета С.Н.Гргшчевво

- 3 -

ОБЩАЯ ХАРАКТЕРИСТИКА РАБ01Н

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

Дескриптивный подход характеризуется использованием разного рода правил в качестве основной элементарной единицы прох-раммирсвашя. Характерными представителям; этого направления являются языки РЕФАЛ и ПРОЛОГ.

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

Вместе с тем, наряду с несомненными успехами дескриптивного подхода, стали очевидными и определенные трудности, препятствуввде его широкому практическому распространению. Эти трудности пряно или косвенно связаны с з а з и с я-костью правил и становятся весьма серьезными, а зачастую, и непреодолтшш при попытка:; реализации неформальных "человеческих" процедур (лингвистические процессора естественного язика, машинный перевод, инфортционтШ поиск по сшслу, Отличительной особенностью подобных проце-

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

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

Сказанное свидетельствует об актуальности проблемы представления процедур с исключениями из правил. Ренекие этой проблема позволит существенно приблизить уровень программирования к естественно?^ повятийиому ышлению человека в даст возможность перейти к кассовой реализации иа ЭВ?1 неформальных "человеческих" процедур.

Диссертация посвящена систематическому исследованию комплекса вопросов, связанных с исключениями из правил; в системах, основаааых на правилах.

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

Основные положения,., которые выносятся на защиту:

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

2. Показано, что процедуры с исключениями из правил требуют для своей реализации выхода за пределы традиционной концепции программирования, основанной на финитном (в частности, алгоритмическом) формализме, в область нештатных формальных систем.

3. Построен нефинитный формализм (К-системы), адекватный представлении процедур с исключениями.

4. Сформулирована концепция системы программирования с исключениями из правил.

5. На основе аппарата К-систец дано точное определение семантики ПРОДОГа.

Научная новизна работы:

.I. Предложен новый класс формальных систем (К-системы), ориентированный на формализацию исключений из правил.

Z. Показано, что К-системы представляют собой незнатное обобщение класса финитных формальных систем.

3. Выделен важный класс полных К-мнояеств. Доказало, что этот класс зашснуг относительно операций дополнения к квантификавдш (универсальной и экзистенциальной), в отличие от класса рекурсивно перечислкмых множеств. Это дает возмое-ность точного представления в полных К-системах интуитивно естественных теорий типа арифметики, Ее формализуемых финитно в силу известной теоремы Гёделя. о неполноте.

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

5. Определено понятие семантически корректного интерпретатора систем с исключениями и доказана теорема о невозможности всюду определенного корректного интерпретатора. Этим уточнены пределы возможного при практическом построении интерпретаторов.

6. На примере языка ПРОЛСГ показано фактическое возникновение нефинитных конструкций в современном программировании и дано точное определение семантики ПРСЛОГа на основе аппарата К-систем,

Практическая ценность работы:

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

2. На основе результатов работы разработаны и программно реализованы два экспериментальных языка программирования: К-язык и МАРТ (Ыавикный Анализ Русских Текстов). Проведено экспериментальное исследование разработанных языков, подтвердившее практическую реализуемость концепции программирования в системах с исключениями. Результаты диссертации использованы в НИР "Концепт".

3. Аппарат К-систен успепшо использован. С.В.Марковым при разработке интеллектуальной системы, иа базе которой им реализована и внедрена интеллектуальная САПР конструкторской документации печатных плат.

В целом, из результатов диссертации следует, что решение проблемы представления в ЭБЫ процедур с исключениями из правил приводит к коренному пересмотру концептуальных основ теории и практики программирования. С учетом этого совокупность научных положений, сформулированных и обоснованных в диссертации, можно квалифицировать как новое перспективное направление в информатике.

Апробация работы и публикации. Основные результаты диссертационной работы докладывались на следующих конференциях

и семинарах: УП Всесоюзная конференция по планированию и автоматизации эксперимента в научных исследованиях (Москва,

1983); семинар лаборатории машинного перевода во Всесоюзном центре переводов (Москва, 1983); семинар отдела теоретических основ информатики ВИНИТИ (Москва, 1983); межотраслевой научный семинар "Теория информационных систем" при Совете по комплексной проблеме "Кибернетика" АН СССР (Москва, 1983); Всесоюзная школа молодых ученых "Проектирование автоматических систем контроля и управления сложными объектами" (Туапсе,

1984); Всесоюзный семинар "Промышленная технология создания

и применения программных средств в организационном управлении и НИОКР" (Свердловск, 1984); Всесоюзная конференция "Психологические проблемы создания и использования ЭВМ" (Москва,

1985); заседание секции I? "Искусственный интеллект" научно-технического совета при межведомственной комиссии по вычислительной технике (Москва, 1986); семинар кафедры 28 МИФИ (Москва, 1986); постоянно действующий семинар " Проблемы искусственного интеллекта" (Переславль-Залесский, 1986, октябрь); семинар в ИК АН УССР (Киев, 1986); семинар в ИПМ АН СССР (Москва, 1987); общемосковский семинар "Проблемы искусственного интеллекта" (ИЛУ АН СССР, 1988, октябрь); Всесоюзная конференция по искусственному интеллекту (Переславль-Залесский, 1988).

По теме диссертации опубликовано II печатных работ, а 10 из них соответствуют спискам перечня издательств и издательских организаций, в научных изданиях которых могут публиковаться основные научные результаты, включенные ь докторскую диссертацию. Основные результаты диссертации достаточно полно отражены в 9 печатных работах, опубликованных лично соискателем и приведенных в конце автореферата. По результатам работы подготовлена монография в изд-во "Наука", включенная в издательский план 1989 г.

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

Структура, и,объем диссертации. Диссертация состоит из введения, девяти глав, приложения, заключения и списка лите-

ратуры на 64 наименований. Объем работы 211 страниц основного текста, рисунки - 20 страниц, приложение - 2 страницы, список литературы - б страниц. В главе I приводятся предварительные сведения о системах, основанных на правилах, поясняются причины возникновения систем с исключениями из правил и уточняется постановка задачи. Главы 2-6 представляют собой критический обзор современных концепций программирования с позиций представления процедур с исключениями из правил. Каждая из этих глав начинается с подробного изложения известной концепции, все более "неалгоритмической" от главы к главе, и заканчивается ее критическим анализом. Глава 7-9 и приложение полностью оригинальны и посвящены изложению основных результатов диссертации по К-системаы.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

Задача. Описать процедуру, реализующую преобразование из именительного падека в родительный для существительных следующих типов: ДОМ, Ш, ВИЛКА, КИНО, НОЧЬ, ТОКАРЬ, КИЛЬ.

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

Дополнительная.задача. Расширить алгоритм, представленный на ркс.1, на слова типа: ВАСЯ, РЕШЕНИЕ, ВРЕМЯ, АКЦИЯ, ЗАДАЧА.

д_ ,_

( КИВО?)-^ -оКИНО

нет

да

К4-КИ

3

да

( АРЬ? )Д&~с4РЬ-^1РЯ

вех

.М:С2ИЛЬ

» о о

^Н: з cb?S>

ESS (

Ь —Ï

fttc.I. Решение I. Алгоритм.

Разумеется, программист без особого труда составит соответствующую блок-схему алгоритма. Однако сделать это придется, по всей видимости, заново - блок-схема на рис.1 явно не приспособлена для эффективного внесения изменения!

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

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

Теперь значительно упрощается расширение на новые классы слов - необходимо жяшь обеспечить внесение вставок на нужное место в таблице решений.

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

Продукционные системы отличает высокая степень общности правил обработки данных. Однако именно эта общность приводит к ухудшению динамических свойств соответствующих продукционных программ, к трудностям их модификации и раззития. Чтобы понять о чем причина, обратимся снова к рис.2. Пока эта таблица содержит несколько строк, не представляет особого труда установление правильного порядка их следования. Если теперь учесть, что реальное количество продукций в подобных задачах исчисляется сотнями и более, трудоемкость их правильного взаимного расположения становится очевидной. Практически, при программировании неформальных "человеческих" процедур, подобные таблицы можно вручную создавать и сопровождать для нескольких десятков продукций, максиму« для 100-200 продукций. Продукции зависимы и за правильное выявление этой зависимости отвечает программист. Новые продукции необходимо вручную

Ситуация Действие

КИНО КИНО

-ча -чи

~КА -га

-А -ы

-АРЬ -АРЯ

-Ь£М:зсЬ -Я

-Ь -И

-ие -ия

-мя -меив

-я -и

-

Рис.2. Решение 2. Таблица решений. Мелкий прифтои выделены вставки»

а) алгоритмические системы - 6) продукционные системы -ситуации не пересекается возможно пересечение ситуаций

Рйс.З. Классификация ситуаций в различных системах.

вставлять на нужное место»

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

Теперь основная проблема состоит в установлении природа отношения предпочтения на множестве продукций. Объективная необходимость такого отноиения обоснована пока чисто эмпирически - мы просто выявили используемый в программировании прием. Так, в описании языка РЕФАЛ прямо говорится, что частные правила должны располагаться перед общшн. Аналогично, изменение порядка следования двух продукций на рис,2 может привести к нелепостям, например:

-А ~Ы, -КА — ~КЙ.

Такая последовательность приведет к неправильной обработке слов ВЯЖА, ПАЛКА и т.д. - система ответит ВНЖЫ, ШШШ,... . Здесь вторая продукция содержит условие -КА, более частное по отношению к условию -А первой продукции.

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

Теперь, если отношение "правило - исключение" встроено в систему, она сака сможет понять, что преобразование ПАПКА -^ПАЖЫ незаконно. При этом система должна руководствоваться простым принципом: если применимо исключение, общее правило запрещено. Соответствующие системы будем называть системами с исключениями.

Традиционное программирование на алгоритмических языках выполняется по схеме:

содержательнее процедура —алгоритм — программа. На практике, разумеется, уже написанные программы могут перерабатываться. Однако серьезные качественные изменения тре-

буют, как правило, большого объема программирования, сравнимого по трудоемкости с начальным программированием. Таким образом, традиционное программирование имеет статический характер.

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

содержательная процедура —продукционная система с

Глава 2 содержит необходимые сведения об алгоритмах и является отправным пунктом, от которого мы двигаемся в сторону все большей "неалгоритмичности" по маршруту: алгоритм, продукционный алгоритм, язык РЕЗДЛ, режим возвратов, логический вывод, язык ПРОЛОГ, продукционные системы с исключениями, К-системы. В главе показано, что несмотря не, очевидный рост' уровня алгоритмических языков программирования эти языки мало приближают нас к неформальной-природе естественных для человека процедур. На практике это приводит к непомерно высокой трудоемкости программирования неформальных процедур независимо от того, на каком конкретно языке производится программирование: Ассемблере - языке низкого уровня, или Си, ПЛ/1, Бейсике и т.д. - языках высокого уровня.

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

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

исключениями

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

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

В главе 3 рассмотрена алгоритмическая концепция продукционна систем. Продукционное?* у нас ассоциируется с выполнением системой действий непосредственно во внешней среде или в ее модели, представленной г базах данных, в отличие от "мысленных" или "логических" действий, не приводявщх к непосредственному воздействию, на мир. Таким образом, продукции мы будем связывать неизменно с процедурными фактами, т.е. выражениями вида о. ё , где сс и £ - слова в заданном алфавите, а слуаебный знак стрелки используется не в смысле логической импликации, а как обозначение причинно-следственных связей реального мира. Слово а будем называть стимулом, ё - реакцией.

Алгоритмическая концепция продукционной системы иллюстрируется нормальными алгоритмами Маркова и языком РЕФАЛ.

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

Ч ■ ■ ■

I '

где I г £ >-•»;. ¿^ - образцы. Образцы Ьп называ-

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

зуется). По типу заключения будем называть продукции соответственно процедурными или информационными. Продукционная система - это тройка

{А.,У,Р}

где А - алфавит* V - список переменных, Р - конечное мно-кество продукций.

Продукционные системы алгоритмического типа "работают" следующим образом. Обозреваемое на входе слово сс последовательно сопоставляется с каздой продукцией в заранее заданном порядке. Бели удалось сопоставить слово а. с некоторой продукцией р , то эта продукция однозначно определяет некоторое слово & р (а.) . Далее процесс повторяется для слова ё и т.д. Окончание процесса либо при невозможности найти подходящую продукцию, либо по специальной команде или признаку остановки.

Рассмотренный подход к продукционным системам следует концепции, принятой в нормальных алгоритмах Маркова, а по своей сути является алгоритмическим. Это значит, что;

вся система продукций преобразует каждое слово однозначно;

преобразование, осуществляемое ка&дой продукцией, однозначно в алгоритм его известен;

. процесс перебора продукций заранее жестко фиксирован»

Алгоршгс1ческая концепция продукционной системы вполне уместна при обработке форгшышх текстов. Однако при обработке иепее формальных объектов, например, текстов естественного языка, алгоритмическая концепция оказывается слишком стеснительной. Во-первых, неприемлемой оказывается однозначность преобразования. Так, в математическом плане, нас может устраивать получение всегда одного и того же ответа 137 при обращении со словом кХ1 к РЕ§АЛ-программе

а кXI — ¿5?,

.§2. кXI — 272 . Здесь фактически §2 никогда не используется. Но как быть в случае продукций:

НАШ (МАТЬ) ЙМШГШЪНЫИ,

ПАДЕЖ (ШЬ) ВИНИТЕЛЬНЫЙ ? В этом случав обе реакции в принципе правильные а любая аз

них мояет понадобиться в зависимости от контекста.

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

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

Таким образом, мы выделили три недостатка алгоритмической концепции продукционных систем. Попытки их устранения приводят к необходимости включения в общую концепцию продукционной системы соответствующих трех новых понятий, рассматриваемых в следующих главах - это: режим возвратов (гл.4); логический вывод (гл.5,6); исключение из правил (гл.7).

Глава 4 посвящена режиму возвратов (РВ). Проблема управления выбором развилок подробно освещена в литературе и в диссертации не рассматривается, поскольку продукционные системы в зтот круг вопросов ничего нового не вносят. Иное положение с выбором альтернатив в продукционных системах. Если продукционная система работает в режиме возвратов, го на шаге выбора продукции необходимо организовать перебор продукций так, чтобы выполнялось ограничение, принятое в системах с исключениями: общее правило запрещено, если применимо исключение. Отсюда следует, что, во-первых, перебор продукций должен производиться в порядке приоритета, определяемого отноиением "правило - исключение", - исключения испытываются прежде общих правил. Во-вторых, применимость какого-либо правила запрещает все другие правила, для которых данное является исключением.

Таким образом, наряду с номером продукции С для работы системы теперь необходим еще и список запретов С данного аага, который, разумеется, должен сохраняться (восстанавливаться) ащ повторном вызове РВ-процедуры выбора продукции (при возврате). Для правильною ведения списка запретов достаточно предположить, что продукции заранее занумерованы в порядке приоритета, причем к каждой продукции с номером I

присоединяется возможно пустой список ^ указателей отноае-ндя "правило - исключение" (ПЙ-указатели). Каждый такой указатель - это номер правила, для которого данное является исключением. Ведение списка запретов на каждом иаге выбора продукции осуществляется следующим образом. При первом вызове на данном ваге процедуры выбора продукции список пуст. Далее для каждого с на этом шаге выбора, если с е С , то продукция пропускается. Если же , то разрешается проверять совпадение "ситуации" данной продукции с текущей ситуацией. Если будет получен положительный результат, то все номера из списка , отсутствующие в списке запретов, заносятся в этот список. Такую модификацию режима возвратов будем называть режимом возвратов с исключениями [Ц.

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

Совершенно иное положение возникает при решении неформальных задач. В этом случае, как правило, отсутствует какоЕ-либо эффективный критерий.достижения цели. Да и сама цель, уяе не может быть описана в точных математических терцинах. Например, если система выполняет анализ текста естественного языка и представляет его в виде семантической сети или какой-либо иной.формализованной.структуры, то что здесь является целью? Конечно мы можем сказать, что цель состоит в представлении, исходного текста в структуре заданного вида, но сказав это мы мало что получим для построения реальной системы анализа, поскольку совершенно не ясно: как из мно-кества возможных таких представлений, количество которых обычно растет экспоненциально в зависимости от длина текста, выбрать то нужное и, как правило, единственное, с точке зрения правильной передачи смысла?

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

дибо удается в результате анализа "придумать" некоторый

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

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

либо альтернатив иного и для анализа каждой требуется много шагов;

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

В первой случае происходит неограниченный рост числа вариантов - 1010, Ю20 и т.д. - это "практическая" бесконечность. Во втором случае вариантов лишь несколько - 10, 20 и т.д. Можно сказать, что имеет место закон "бесконечно иного или несколько".

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

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

Для обнаружения неуспеха естественно использовать продукции специального вида, а именно:

4 ВОЗВРАТ

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

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

В главе 5 рассматриваются основные понятия логического вывода. В качестве уточнения понятия формальной системы мы используем канонические исчисления Поста. Будем предполагать, что задан алфавит (список знаков) и другой список символов, называемых переменишь, к отличных от знаков. Образец (или терн) - это любая конечная цепочка знаков и переменных, а правило вывода (короче правило) - это фигура вида £ £ . . . £ ■

где все ¿ , ,{п.%0) суть образца. Образцы , „.., называются посылками, а £ - заключением правила. Правила без посылок называются аксиомами. Каноническое

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

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

1. Применение ахснозад - вывод этого применения.

2, Если - выводы соответственно слов а,,

а„ и

а.

применение некоторого правила, то

Р1 ♦ . . Рц

а.

вывод слова а .

Слово, для которого имеется вывод, называется выводимым в данном каноническом исчислении.

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

Если дано рекурсивно-перечислимое множество Е в алфавите <>сл ... «.б,, , то его дополнение Е до множества всех слов в этом алфавите, вообще говоря, не является рекурсивно перечислимым - класс рекурслвяо перечислимых множеств не замкнут относительно дополнения. Рекурсивно перечислимое множество Е слов в данном алфавите рекурсивно или разрешимо, если его дополнение Е рекурсивно перечислимо. Из предыдущего следует, что не всякое рекурсивно перечислимое множество разрешимо.

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

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

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

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

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

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

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

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

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

достаточна для программирования процедур с исключениями.

В главе 6 рассматривается язык ПРОЛОГ. В результате анализа языка сделаны два основных вывода.

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

Во-вторых, попытки определения семантики ПРОЛОГа с отрицанием в рашсах финитных систем не могут привести к успеху в силу принципиальной ограниченности финитного формализма. Отсюда следует необходимость в разработке новой концепции программирования, основанной на Еефинитном формализме. Указанная необходимость подтверждается и анализом роли финитного формализма в развитии математики.

В главе 7 определяется семантика продукционных систем с исключениями из правил. Как уке отмечалось, для выяснения природы исключений из правил следует определить отношение "общее - частное" в системе продукций С2-4~3-

Рассмотрим обобщение продукций. Задача состоит в том, чтобы для любых двух продукций р , определить при каких условиях продукция р - частный случай продукции , а -обобщение р .

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

-г- _ • ' • \

6 - и •■•

где эс; - попарно различные переменные, ^ - информационные образцы= ,,..,Угг). Выражение 2- это продукция, получаемая из продукций у, заменой всех вхождений переменной на образец й^ (¿~ ¿ ,...,уч) . Если существует подстановка ?Г такая, что для продукций р , выполнено соотношение р - , то продукция р . называется частный случаем продукции £ , а £ - обобщение продукции р . Обобщение в соответствии с данный определением называется подстановочный.

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

В.ПЕНЬ ПЕНЬ подстановочным обобщением можно получить аксиому В. ос ОС

Эта аксиома определяет правило преобразования существительных типа ПЕНЬ, ДОМ, СШ и т.д. в винительный падеж. Для слов типа КОНЬ имеем факт

В.КОНЬ КОНЯ. Подстановочное обобщение этого факта -

В.хЬ зсЯ -недостаточно. Необходимо еще указать, что это правило применимо только для одушевленных существительных. Для этого следует ограничить область переменной ос0 Сделать это в продукционной системе можно введя посылку: зсЬ:ОДУШЕВЛЕННОЕ

В.хЬ

Подстановочное обобщение не позволяет сделать такой переход.

Процесс построения обобщенного правила с посылками из исходного факта можно представить следующим образом. Сначала к исходному факту добавляется посылка КОНЬ:ОДУШЕВЛЕННОЕ. В результате получается продукция

КОНЬ:ОДУШЕВЛЕННОЕ

В.КОНЬ КОНЯ Затем над полученной продукцией выполняется подстановочное обобщение - получаем продукцию с посылкой. Рассмотренный тип обобщения, таким образом, строится с помощью присоединения посылок-констант и совместного подстановочного обобщения этих

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

Наконец, отметим еще один интуитивно очевидный тип обобщения - отбрасывание посылок.

Вели дана цепочка продукций

Р Р* ' Рг ' >Вг в £ >

причем каждая следующая продукция получается из предыдущей Р1 по одному из трех рассмотренных выше типов обобщения, то продукция р - частный случай продукции у, . Данное определение вводит отношение "общее - частное". Непосредственно из определения следует, что обобщение транзитивно.

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

Однако допустив пересечение ситуаций мы долены позаботиться о реаекзш проСлеш приоритета. Дня получения содержательно обоснованного метода распознавания приоритета продукций необходимо учесть два момента [2-4]:

1. Процедурное правило р является исключением аз процедурного правила а, , если область определения правила р является строго частика случаем области определения у. .

2. Исключения пользуются приоритетом перед общими правилами.

В общем случае, если дана процедурная продукция Ь £

I ... <- п

Р Ш Л л, '

то естественно считать, что ее область определения - это информационная продукция

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

Рассмотрим продукционную систему с отношением "правило ~ исключение" на множестве продукций. Это отношение позволяет дать нефинитную интерпретацию продукционных систем. Основная задача, при этом, состоит в установлении семантики исключений [2-8]. Заметим, что при рассмотрении простых примеров (см. рис.2) семантика исключений была предельно проста -перебор продукций осуществлялся с учетом приоритета исключений. В общем случае, когда продукции содеркат посылки, дп проверки выполнимости этих посылок может снова понадобиться просматривать продукции в соответствии с отношением "правило - исключение". В конечном счете задача сведется к построению дерева вывода, допустимого с точки зрения приоритета исключений. Рассмотрим в чем состоит упомянутая допустимость. Предварительно заметив, что отношение исключения естественным образом переносится на множество выводов. Отношение исключения на множестве выводов обозначим через ^ . Запись Р < £? , таким образом, означает, что вывод Р - исключение из вывода <Э „ Если Е - каноническое исчисление, то пара {_ЕУ ■{} называется К-системой. К-скстема - это каноническое исчисление с отнопениеы исключения на множестве выводов.

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

выводы, используемые для вывода истинности слов; выводы, используемые для вывода ложности слов. Первые будем называть выводами типа И или 1-выводазш, вторые - выводами типа Л или Д-выводами. И-ваводы н Д-выводы определяются по индукции [8,7,8]:

1. Вывод, не имеющий исключений, является Е-выводом.

2. Вывод, имеюяяй исключением Е-вывод, является Я-виво-

доы.

3- Вывод, все исключения из которого типа Л, является И-выводом.

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

Слово истинно а К-системе, если существует его И-вывод. Множество слов в данном алфавите, истинных в некоторой К-системе, называется К-нножеством. К-множество К-разрешимо, если его дополнение до множества всех слов в данном алфавите является К-мяожеством. Слово ложно в К-системе, если все его выводы являются Л-виводами или оно вообще не имеет вывода. Данное определение истинности непротиворечиво - слово не может быть истинным и ложным одновременно. К-систена, все слова которой разрешимы - истинны или ложны - называется полной. К-множество полно, если оно представиио в полной К-системе.

Бели имеется запрос - слово а, и процедурное слово а. & истинно, то о-вех на запрос дается словом ё .

Доказано, что всякое рекурсивно перечиеллмое множество является К-ннохеством, но существует К-множество, которое не является рекурсивно перечислимым. Таким образом, концепция исключения из правила естественным образом приводит к выходу за пределы финитных систем.

В этой главе дака также последовательная интерпретация К-систем и сформулировано понятие К-нашшы. Результаты главы 7 опубликованы в [2-93.

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

Пусть дана произвольная формальная система Е , Пусть на множестве выводов системы £ задано некоторое рекурсивное бинарное отнощение, для обозначения которого будем использовать знак < . Если для двух выводов Р , С? имеет место со-

отношение Р-< О , попрежнему будем вывод Р называть исключением из вывода О . Пара { Е, н) называется К-системой. Для классификации выводов по типам И, Л и для введения понятий истинности, ложности и К-множества попрежнему используются определения из главы 7.

Б качестве исходной формальной системы в этой главе примем следующую простую модификацию канонического исчисления [7,8]. Продукция - это фигура вида / * «У «т*

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

1. Применение аксиомы - вывод этого применения.

2. Если Рл ,.<,., Рп - выводы соответственно слов о-л , ..., ап и

■ * а. & „ » . & $ ГУ1 а.

применение некоторой продукции, то

Рл . . . Рп . . е^

а.

гивод слова а.

Если некоторый вывод О содержит выражение ®си, где О. - слово, к Р •> вывод слова л, то Р - исключение из О . В этом случае попрежнему используем запись Р < О .

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

Доказаны следующие теоремы. Теорема 8.1.

I. Класс К-множеств замкнут относительно операций конеч-

ного пересечения и объединения, слабого дополнения и кванти-фнкации (универсальной и экзистенциальной).

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

Теорема 8.2. Существует K-отношение U между натуральными числами и словами в данном алфавите, такое, что m. Ucl тогда и только тогда, когда «г есть гёделевсвий номер ¡{-системы, в которой истинно слово et .

Теорема 8.3. Диагональное К-мкоаество натуральных чисел,

с

определяемое схемой —~- , К-неразреиимо.

Обозначим через УС - класс всех K-множеств, представи-тх в K-системах с рассматриваемым в этой главе вариантом отношения исключения.

Теорема 8.4. Пусть Е - произвольная йянктнал формальная система, а •{ - произвольное рекурсивное отношение исключения на миояестве выводов система Ш. Пусть Е - К-нно-жество, определяемое K-системой {_Е, •{} . Тогда Е sJ^T.

Теорема 8.5. Любое арифметическое по Гёделю отношение является полным К-отношепием.

Теорема 8.6. Существует полное К-отношение & меаду натуральными числами, такое, что глАуь тогда и только тогда, когда т- есть номер арифметического множества, которому принадлежит слово с геделевским номером п. .

Следствие I. Отношение Л неаэайметачно.

Следствие 2. Множество истинных замкнутых формуя арифметики является полным неарифметически.»! Я-мнояеетвом.

Нетрудно видеть, что теоремы 8.1-8.3 аналогичны известным теоремам для рекурсивно перечислите мкокеств. Из теоремы 8.4 следует, что мы "охватили" все К-мноаества - другие варианты финитных формальных систем п рекурсивных отношений исключения ве могут расширить класс К-ккокеств. Для практики весьма интересна замкнутость класса полных К-инояеств относительно операций дополнения и квантизации (теорема 8.1), в отличие от класса рекурсивно перечислимых множеств. Это дает возможность точного представления в полных К-системах

интуитивно естественных теорий тша арифметики, не формализуемых <|инитно в силу известной теоремы Гёделя (теоремы 8.5 и 8.6). Доказан также ряд других теорем (8.7-8.12), свидетельствующих о том, что в классе полных К-систеи представимы и значительно более богатые, чем арифметика, интуитивные теории.

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

Результаты главы опубликованы в [7].

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

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

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

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

Математическая "неформальность" означает, что продукционные программы более выразительны, чем формальные системы финитного типа и, в частности, алгоритмические системы.

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

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

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

Разумеется, отмеченная выше независимость продукций имеет место лишь внешне, с точки зрепня программиста. На самом деле между продукциями существует зависимость, вытекающая из отношения "правило - исключение". Эта зависимость, однако, "скрыта" от программиста и устанавливается компилятором языка продукционного программирования.

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

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

ПЕРЕВОД (КАТЕ) -»КШ РП(ХАТй) — КАТИ ПЕРЕВОД (SOSE) -«-РОЗА

~~ ПЕРЕВОД (KATE HAS A 2DSE) У КАТИ F03A '

Таким образом, для вычисления значения функции ПЕРЕВОД с аргументом KATE HAS A 20SE необходимо выполнить следующее: вызвать функцию ПЕРЕВОД с аргументом КАТЕ; вызвать функцию РП преобразования в родительный падеж о аргументом КАТЯ;

вызвать функцию ПЕРЕВОД с аргументом EOSE. После выполнения этих действий будут получены значения соответствующих функций: КАТИ, РОЗА, которые используются при вычислении реакции заключения, г результате получим текст У КАТИ РОЗА, представляющий значение выражения ПЕРЕВОД(КАТЕ

HAS A 20SE). Из приведенного примера можно сделать выводы:

X. Стимул заключения задает имя функция, которую реализует данная продукция ПЕРЕВОД, РП, ... , и устанавливает значения аргумента, за обработку которых "отвечает" данная продукция. В приведенном примере это было единственное значение KATE HAS A ROSE. Можно сказать, что стимул заключения реализует проверку применимости продукции внутренними средствами санов продукции.

2» Посылки реализуют проверку применимости данной продукции внешними средствами вызывая функции ПЕРЕВОД, РП, ... с некоторыми значениями аргументов (КАТЕ, КАТЯ, BQSE, .„.).

3. Наконец, реакция заключения содержит значение функции, реализуемой данной продукцией.

Таким образом, в традиционных терминах программирования продукция представляет собой программный модуль вида: <имя функции> ( б)

Г, C*Á) - ^ ;

К (О -« • • •

Fn С 4 J =

RETURN (т) • Здесь й , х , áÁ , zx дп , хп - образца, еоответст^

эующие продукции

<ЕЫЯ ФУНХЦ1Ю> i 4) -4" *

^ >•••» F'n. ~'таена вызываемых функций, а ^"-отношение равенства,, Аксиомы представляются в виде модуля <(имя функцви> (4)

RETURN (»;

Отметим теперь различия операционной семантики продукций и модулей-функций традиционных алгоритмических языков программирования. Во-первых, в противоположность языкам типа Фортран, Си, ПЛ/1, имя модуля теперь не обязательно уникально. Точнее, имя модуля в продукционной программе, как правило, не уникально. Так, продукции

зсКА лКК ХА — лЫ гс —асА

реализуют выполнение одной и той же функции РП преобразования в родительный падеж. Соответственно имеем три модуля с одним и тем же именем:

РП (хКА) Я£П//?А/(х Кй);

РП {рек)

РП (ос) Д£ГиЯА/(хк); Формально, вызов РП(ВИЛКА) может быть обработал каждым из этих трех модулей, однако правильно построенная продукционная система выберет первый из них, т.к. он является исключением из двух других.

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

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

Таким образом, продукция представляет собой естественное расширение традиционного понятия программного модуля на случай многозначных процедур.

Как следует из результатов гл.8 продукционная система, включающая в себя средства логического вывода и аппарат исключений, является нефинитяой формальной системой. В то же время реально выполнить на ЭВИ можно только алгоритм. Таким образом, для выполнения на ЭВМ продукционных программ необходимо иметь интерпретатор, обеспечивающий преобразование типа "нефинитная формальная система —финитная формальная система". В то же время очевидно, что нефинитная система, вообще говоря, не может быть точно представлена с помощью финитной системы. Из сказанного следует, что в общем случае возможна лишь "приближенная интерпретация" или аппроксимация продукционных программ на 3Ш. Подобная ситуация впервые

возникла на практике в связи с языком ПРОЛОГ. Рассмотрим в каком смысле можно говорить об аппроксимации продукционной программы (или K-системы) с помощью интерпретатора.,310т интерпретатор для любой программы Р , представленной в виде K-системы, и для любого запроса а должен найти какое-нибудь процедурное слово cl-*- £ , истинное в Р . Тогда слово 8> -результат работы программы Р для запроса а.. Если же такого истинного слова а. ё не существует, то интерпретатор должен дать специальное сообщение (обозначим А/) .

С учетом сказанного естественно следующее определение. Пусть I - интерпретатор, а. - некоторый запрос, Р - произвольная продукционная программа (K-система). Результат работы интерпретатора I с программой Р для запроса а. будем обозначать в виде 1(а.,Р). Интерпретатор I называется семантически корректным при выполнении следующих условий.

1. Если I(cl , Р)~ £ (ё*А/), то а. ё истинно ъР ,

2. Если I(atP) = N, то не существует слова ё такого, ЧТО ё истинно в Р .

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

Результаты главы опубликованы в [2-4,9].

В приложении на основе версии K-систем, построенной в гл.8, определяется семантика ПРОЛОГа с отрицанием. Для этого отрицание языка ПРОЛОГ выражается с помощью правила [8]

BJC not ОС

Определение семантики ПРОЛОГа в K-системах расширяет традиционную операционную семантику ПРОЛОГа, но не изменяет ее в тех случаях, когда она приводит к результативной работе ПРОЛОГ-кнгерпретатора [в].

Основные результаты работы.

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

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

3. Исследован простейший класс дескриптивных систем, основанный на алгоритмической концепции продукционной системы. Этот класс систем существенно повышает динамичность процессов программирования и модификации программ.

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

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

5. Показано, что трудности алгоритмического программирования присуши и всем финитным системам. Таким образом, концепция финитной системы не достаточна для программирования процедур с исключениями.

6. Необходимость перехода к кефинитньи системам обоснована также анализом семантических трудностей языка ПРОЯОГ -показано, что семантика языка ПРОЛОГ не может быть определена в финитных системах.

7. Сформулировано определение отношения "общее - частное" в системе продукций и доказана его полнота.

8. Предложено решение проблемы приоритета продукций на

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

9. Построен математический аппарат, ориентированный на представление процедур с исключениями (К-систеыы).

10. Доказано, что К-системы действительно нефинятны и, таким образом, представляют собой нетривиальное обобщение класса финитных систем.

11. Исследованы выразительные возможности К-систем ы доказан ряд теорем о свойствах К-систем и К-множеств.

12. Выделен важный класс полных К-ыножеств. Доказано, что этот класс замкнут относительно операций дополнения и квантифнкавдш, в отличие от класса рекурсивно перечислимых множеств. Это дает возможность точного представления в полных К-сйстемах интуитивно естественных теорий гипа арифметики, не формализуемых финитно в силу известный теоремы Гёделя о неполноте.

13. Показано, что в полных К-систенах представимы и неарифметические множества. Это свидетельствует о том, что выразительные возможности К-систем позволяют существенно приблизиться к неформальным интуитивным построениям.

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

15. Определено понятие семантически корректного интерпретатора систем с исключениями. Доказана теорема с невозможности всюду определенного корректного интерпретатора.

16. На основе аппарата К-систем дало точное определение семантики ПРОЛОГа.

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

СПИСОК ОСНОВНЫХ РАБОТ, ОПУБЛИКОВАННЫХ ПО ТЕМЕ ДОСЕРТАЩИ

1. Кузнецов В.Е- Реаим возвратов с исключениями из правил. - Известия АН СССР "Техническая кибернетика", 1989, К.

2. Кузнецов В.Е. Концептуальные модели информационных объектов. - Научно-техническая информация, сер.2, 1983, М, С.24-26.

3. Кузнецов В.Е. Реализация неформальных процедур с исключениями. - Известия АН СССР "Техническая кибернетика", 1984, »5, С.50-54.

4. Кузнецов В.Е. Концептуальное моделирование производственных процессов. - Заводская лаборатории, 1984, 8?,с.45-47.

5. Кузнецов В.Е. К-системы. - Тезисы докл. УП Всес. конф. по планированию а автоматизации эксперимента в научных исследованиях. - М.: МЭИ, 1983. Часть I, с.Ш-ПЗ.

6. Кузнецов В.Е. К-системы. - Доклада АН СССР, 1.273, 1983, М, с.815-816.

7. Кузнецов В.Е. Ыатематическяе построения в К-систенах. - Сетотяш и информатика, вып.27, 1986, с.62-81.

8. Кузнецов В.Е. ПРОЛОГ и формальные систеш с исключениями из правил. - Тезисы докладов Всесоюзной конференции по искусственному интеллекту. - Н.: ВИНИТИ, 1988, том 3,

с.412-416.

9. Кузнецов В.Е. Технология программирования неформальных процедур организационного управления. - Тезисы докладов Всесоюзного семинара "Промышленная технология создания и применения программных средств в организационном управлении и ЕИСКР". - Свердловск: УВД, АН СССР,. 1984, С.189.

Зак. 29а тир. 100 ПКБ ЦВ МНС Т 11356 от 7.07.89