Разработка способа и средств реализации программ на основе системы функциональных продукций

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

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

В процессе своего развития понятие программы претерпело значительные изменения. Произошел постепенный переход от представления программы как последовательности машинных команд к ее представлению в виде последовательности операторов алгоритмических языков. Наиболее распространенными в это время являлись задачи численного характера, при решении которых основное внимание уделяется скорости вычислений. Постановка новых задач, прежде всего, символьно-логических, выдвинуло на первое место вопросы удобства реализации программ. При этом основным критерием удобства выступает легкость понимания и естественность восприятия понятий и структур, используемых для описания действий по решению поставленной задачи. В связи с этим особое внимание стало уделяться декларативным средствам реализации программ, в которых описываются свойства требуемого результата, но не указывается способ его полученияподходит любой способ получения требуемого результата, обладающий указанными свойствами. При использовании декларативных средств программист может сосредоточиться на описании внутренних связей и особенностей решаемых задач. Исследования в этом направлении вели Б. Дисков, Р. Ковальски, А. Колмероэ, Дж. Маккарти, Дж. А. Робинсон и др. С точки зрения практических результатов, созданы такие известные языки программирования, как Пролог и Лисп. В нашей стране данную проблематику исследовали В. Н. Агафонов, В. Ф. Турчин, Э. X. Тыугу и др. Были разработаны язык концептуального программирования УТОПИСТ, метаалгоритмический язык Рефал и др.

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

Одним из наиболее перспективных направлений в современном теоретическом программировании является семантическая теория программ. Этот раздел изучает методы формального описания семантики программ, семантические методы преобразования и доказательства утверждений о программах, методы проверки семантической правильности программ. Исследования в этой области ведут такие специалисты, как К. А. Р. Хоар, Дж. В. Беккер, В .Б. Борщев, Ю. Л. Ершов, В. Н. Касьянов, Ю. П. Кораблин, В. Е. Котов. В результате исследований предложены методы и средства, позволяющие выявлять в программах семантические ошибки и способствующие, таким образом, повышению их качества. Поэтому разработка способов и средств, позволяющих анализировать программы и выявлять в них семантические ошибки, является актуальной проблемой.

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

Задачи исследования:

— разработка формальной модели программы, основывающейся на системе продукций;

— разработка модели выполнения программ, реализованных с использованием предлагаемой формальной модели;

— разработка языка реализации программ;

— создание инструментального средства, позволяющего реализовывать программы на предложенном языке;

— проверка достоверности полученных результатов на примерах решения практических задач.

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

Основными результатами, содержащимися в диссертационной работе и полученными автором, являются:

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

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

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

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

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

6) Создано инструментальное средство «Софист», поддерживающее реализацию программ на языке СФП, позволяющее проводить их отладку и тестовое выполнение, а также преобразовывать СФП-программы в программы на алгоритмическом языке.

Научная новизна полученных результатов заключается в следующем:

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

2) Модель выполнения программ, в качестве основы которой выступает двудольный ориентированный И/ИЛИ граф, допускает их автоматический анализ и выявление структурной неполноты и структурной некорректности.

3) Продукционный язык СФП позволяет реализовывать программы в соответствии с моделью СФП и предусматривает проведение их структурно-семантического анализа.

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

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

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

3) Предложены методики реализации и отладки программ на языке СФП, которые раскрывают особенности предлагаемого способа и способствуют созданию требуемых программ.

4) Создано инструментальное средство «Софист», предоставляющее возможность реализовывать программы на языке СФП.

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

Работа выполнялась в рамках госбюджетной НИР ГБ2/МО-15. Разработанный язык СФП и инструментальное средство «Софист» использованы в учебных процессах СПбГЭТУ, СПбГАМТУ при проведении лабораторных работ по дисциплине «Базы данных, знаний и экспертные системы».

Апробация результатов проведена на следующих конференциях: 6-я Международная конференция «Знание — Диалог — Решение», Ялта, 1997; Всероссийская межвузовская научно-техническая конференция студентов и аспирантов «Микроэлектроника и информатика — 98», Москва, 1998; 6-я Национальная конференция по искусственному интеллекту РАН, Пущино, 1998; 51-я научно-техническая конференция профессорско-преподавательского состава СПбГЭ-ТУ, Санкт-Петербург, 1998; 1-я Всероссийская научно-техническая конференция «Компьютерные технологии в науке, проектировании и производстве», Нижний Новгород, 1999.

Доклад по теме диссертационной работы занял второе место на конкурсе работ аспирантов по секции «Автоматизированные системы, методы моделирования и оптимизации», проходившем на Всероссийской межвузовской научно-технической конференции студентов и аспирантов «Микроэлектроника и информатика — 98» (Москва, 1998).

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

На защиту выносятся следующие основные положения диссертационной работы:

1) Формальная модель программы продукционного типа, названная системой функциональных продукций (СФП).

2) Графовая модель выполнения программ, реализованных в соответствии с моделью СФП.

3) Продукционный язык реализации программ, названный языком СФП.

4) Инструментальное средство «Софист», поддерживающее реализацию программ на языке СФП.

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

Основные результаты по главе 4.

1. Разработано инструментальное средство, названное «Софист», предназначенное для поддержки реализации программ на языке СФП и отвечающее современным представлениям об инструментальных средствах. ИС предоставляет следующие возможности: реализовывать программы на языке СФП, проводить их отладку и тестовое выполнение, осуществлять преобразование СФП-программ в программы на языке Паскаль с формированием шаблонов процедур или подключением уже существующих процедур.

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

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

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

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

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

— удобочитаемость и концептуальная целостность языка реализации программ;

— возможность структурно-семантического анализа программ;

— использование единых программ для решения задач с данными разных типов;

— возможность выполнения программ.

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

ЗАКЛЮЧЕНИЕ

.

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

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

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

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

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

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

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

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

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

6) Создано инструментальное средство «Софист», поддерживающее реализацию программ на языке СФП, позволяющее проводить их отладку и тестовое выполнение, а также преобразовывать СФП-программы в программы на алгоритмическом языке.

Способ, предложенный в диссертационной работе, отвечает концепции семантического программирования (^-программирования) [24, 34, 69], которая нашла воплощение в языке АФС, и в соответствии с которой в создаваемом языке программирования предусматривается возможность анализа текстов, записанных на этом языке, т. е. программ. В диссертации предлагается проведение структурно-семантического анализа, позволяющего выявлять в программе пути решения, не описанные программистом, т. е. структурную неполноту, а также описанные неоднократно, т. е. структурную некорректность. При выявлении участков программы, не удовлетворяющих этим условиям, программист может внести необходимые изменения и получить, таким образом, программу, в которой (при конечности решения) будет получено единственное по значению решение исходной задачи.

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

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

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