Введение к работе
Актуальность проблеиы, Б настоящее время в языках программирования все большее кесто начинают заникать дескриптивные структуры, зачастую вытесняя чисто алгоритмические.
Дескриптивный подход характеризуется использованием разного рода правил в качестве основной элементарной единицы прох-рамшірсванійЯ. Характерными представителям отого направления являются языки РЕФАЛ и ПРОЛОГ.
Дескриптивный подход привлекает все большее внимание исследователей и системных программистов, разрабатывающих новые языки и инструментальные средства для построения разного рода интеллектуальных систем, з том числе, експертних систем.
Вместе с тем, наряду с несомненными успехами дескриптивного подхода, стали очевидными и определенные трудности, препятствующие его широкому практическому распространению. Эти трудности прямо или косвенно связаны с з а з и с я-костью правил и станозятся весьма серьезными, а зачастую, и непреодолтшыи при попытках реализации неформальных "человеческих" процедур (лингвистические процессоры естественного язика, машинный перевод, информационный поиск по смыслу, ,..). Отличительной особенностью подобных процедур, вполне естественных для человека, по пока вт с трудоа аоддающихся формализации, является обилие исключении аз правил.
Многочисленность исключений в неформальных процедурах приводит к сильной зависимости правил, причем характер этой зависимости пока еще не вполне ясен я требует уточнения.
Сказанное свидетельствует об актуальности проблемы представления процедур с исключениями из правил. Реаекие этой проблема позволит существенно приблизить уровень программирования к естественно?^ понятийному мышлению человека в даст возможность перейти к кассовой реализации Еа ЗВЙ неформальных "человеческих" процедур.
Диссертация посвящена систематическому иселедовашге комплекса вопросов, связанных с исключениями нз правил в системах, основанных на правилах.
Цель работы состоит в разработке концепции программирования, ориентированной на реализацию процедур с исклвчениями кз правил.
Основные положения, которые выносятся на защиту:
-
Показано, что существующие подходы к программированию, как традиционные алгоритмические, так и новые, основанные на правилах, не учитывают в достаточной мере, зависимость между правилами, характерную для неформальных процедур. Эта зависимость связана с уместностью действий и порождается исклвчениями кз правил.
-
Показано, что процедуры с исключешями из правил требувт для своей реализации выхода за пределы традиционной концепции программирования, основанной на финитной (в частности, алгоритмическом) фориализме, в область яефинитных формальных систем.
-
Построен нефинитный формализм (К-систеыы), адекватный представления процедур с исклвчениями.
-
Сформулирована концепция системы программирования с исключениями из правил.
-
На основе аппарата К-сястем дано точное определение семантики ПРОДОГа.
Научная новизна работы:
.I. Предложен новый класс формальных систем (К-систеш), ориентированный на формализацию исключений из правил.
г. Показано, что К-системы представляют собой нефинитное обобщение класса финитных формальных систем.
-
Выделен важный класс полных К-мнояеств. Доказало, что этот класс замкнуг относительно операций дополнения к квантификации (универсальной и экзистенциальной), в отличие от класса рекурсивно перечисдкмых множеств. Это дает возыое-аость точного представления в полных К-системах интуитивно естественных теории типа арифметики, не формализуемых финитно в силу известной теоремы Гёделя о неполноте.
-
Предложено уточнение режима возвратов, учитывающее специфику систем с исключениями и показана важная роль этого уточнения в ограничении перебора пря реализации неформальных процедур.
-
Определено понятие семантически корректного интерпретатора систем с исключениями и доказана теорема о невоэмох-ности всюду определенного корректного интерпретатора. Этим уточнены пределы возможного при практическом построении интерпретаторов.
-
На примере языка ПРОЛСГ показано фактическое возникновение нефинитных конструкций в современном программировании и дано точное определение семантики ПРСЛОГа на основе аппарата К-систем,
Практическая ценность работы:
-
Предложена новая концепция программирования - программирование в системах с исключениями. Эта концепция основана на аппарате К-систеи и может быть использована при реализации сложных неформальных процедур иструктур данных. Особый практический интерес эта концепция программирования представляет при разработке лингвистических процессоров естественного языка.
-
На основе результатов работы разработаны и программно реализованы два экспериментальных языка программирования: К-язык и МАРТ (Малинный Анализ Русских Текстов). Проведено экспериментальное исследование разработанных языков, подтвердившее практическую реализуемость концепции программирования в системах с исключениями. Результаты диссертации использованы в НИР "Концепт".
-
Аппарат К-систен успешно использован. С.В.Марковым при разработке интеллектуальной системы, на базе которой им реализована и внедрена интеллектуальная САПР конструкторской документации печатных плат.
В целом, из результатов диссертации следует, что решение проблемы представления в ЭВН процедур с исключениями из правил приводит к коренному пересмотру концептуальных основ теории и практики программирования. С учетом этого совокупность научных положений, сформулированных и обоснованных в диссертации, можно квалифицировать как новое перспективное направление в информатике.
Апробация работы и публикации. Основные результаты дяс-сертацконной работы докладывались на следующих конференциях
и семинарах: УП Всесоюзная конференция по планирование и автоматизации эксперимента в научных исследованиях (Москва, 1983); семинар лаборатории машинного перевода во Всесоюзном центре переводов (Москва, 1983); семинар отдела теоретических основ информатики ВИНИТИ (Москва, 1983); межотраслевой научный семинар "Теория информационных систем" при Совете по комплексной проблеме "Кибернетика" АН СССР (Москва, 1983); Всесоюзная школа молодых ученых "Проектирование автоматических систем контроля и управления слоаными объектами" (Туапсе, 1984); Всесоюзный семинар "Промышленная технология создания и применения программных средств в организационном управлении и НИОКР" (Свердловск, 1984); Всесоюзная конференция "Психологические проблемы создания и использования ЭВМ" (Москва, 1985); заседание секции V? "Искусственный интеллект" научно-технического совета при межведомственной комиссии по выделительной технике (Москва, 1986); семинар кафедры 28 МИФИ (Москва, 1986); постоянно действующий семинар " Проблемы искусственного интеллекта" (Переславль-Залесский, 1986, октябрь); семинар в ИХ АН УССР (Киев, 1986); семинар в ИПМ АН СССР (Москва, 1987); общемосковский семинар "Проблемы искусственного интеллекта" (ИЛУ АН СССР, 1988, октябрь); Всесоюзная конференция по искусственному интеллекту (Переславль-Залесский, 1988).
По теме диссертации опубликовано II печатных работ, а 10 из них соответствуют спискам перечня издательств и издательских организаций, в научных изданиях которых могут публиковаться основные научные результаты, включенные ь докторскую диссертацию. Основные результаты диссертации достаточно полно отражены в 9 печатных работах, опубликованных лично соискателем и приведенных в конце автореферата. По результатам работы подготовлена монография в изд-во "Наука", включенная в издательский план 1989 г.
Метода исследования. При выполнении работы использовался аппарат математической логики, продукционных систем, теории алгоритмов, канонических исчислений Поста, искусственного интеллекта и др.
Структура, а.объем диссертации. Диссертация состоит из введения, девяти глав, приложения, заключения и списка лите-
ратуры на 64 наименование. Объем работа 211 страниц основного текста, рисунки - 20 страниц, приложение - 2 страницы, список литературы - б страниц. В главе I приводятся предварительные сведения о системах, основанных на правилах, поясняется причины возникновения систем с исключениями из правил и уточняется постановка задачи. Главы 2-6 представляют собой критический обзор современных концепций программирования с позиций представления процедур с исключениями из правил. Каждая из этих глав начинается с подробного изложения известной концепции, все более "неалгоритмической" от главы к главе, и заканчивается ее критическим анализом. Главы 7-9 и приложение полностью оригинальны и посвящены изложению основных результатов диссертации по К-системаы.
