Главная > Документ


Р.Д. Григорьев, А.А. Красилов

Автоматический синтез программ

Корпорация «Галактика»

г. Москва, Россия

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

Введение

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

Под синтезом программ ныне понимается:

- автоматическое составление программ по её спецификации,

- сборка программ из подпрограмм библиотеки,

- настройка имеющихся программ по параметрам или структуре,

- перевод программ с одного формального языка (ФЯ) на другой,

- полусинтез программ, ориентированных на конкретную специальность или информационную технологию.

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

- исходное задание в форме вопроса или утверждения,

- схема программы в форме графа,

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

- текст готовой программы (в случае перевода с одного языка на другой).

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

1. Коммерческое понятие знания.

Для описания сведений при синтезе программы основным понятием является само понятие как таковое. Наше представление имеет форму пары

(имя понятия, значение понятия), или (термин, лексема).

Эта пара сохраняется на все время обработки знаний. Термин представляется последовательностью лексем (слов, чисел, строк, символов и т.п.), он задает имя величины. Значение понятия (лексема) задает смысл этого понятия [3].

Теперь определим понятие представления знания (далее просто знание) в трех ипостасях простых представлений. Знание – это:

  1. факты, представляемые указанными парами,

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

  3. правила вывода новых фактов или утверждений по имеющимся фактам и утверждениям.

Правила вывода новых правил избыточны, они выводятся композицией правил вывода по пункту 3. Функции входят в пункт 2. Процедуры (команды) и операторы присваивания нового значения для термина также относятся к пункту 2. Многие практические вопросы представления знаний рассмотрены в [4, 5, 6].

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

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

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

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

ч – знания для человека,

м – знания для машины,

р – знания имеются на рынке,

- знания отсутствуют на рынке (например, базы знаний).

номер

п/п

Назначение вида знаний

условные обозначения

основные формы представления

1

Описательные

ч р

литература, учебники

2

Смысловые

ч р

энциклопедии, лексиконы

3

Понятийные

ч м р

словари

4

фактографические

ч м -

таблицы

5

Теоретические

ч м р

статьи, учебники

6

Алгоритмические

ч м р

программы

7

Системные

ч м -

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

человек-машина

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

Виды знания

Функции знания

Области наук

1.Лингво-

семиотические

Описывать объекты (предметы, явления и процессы)

Естественные науки, естествознание

2.Семантические

Осмысливать знания

Гуманитарные науки

3.Концептуальные

Определять понятия

Информатические науки

4.Фактографические

Представить данные

Искусствоведческие науки

5.Теоретические

Обобщить и формализовать знания

Фундаментальные науки

6.Алгоритмические

Применить знания

Технические и технологические науки

7.Кибернетические

Формировать новые знания

Системологические науки

2. Базы знаний в Интеллсист.

База знаний (БЗ) - это совокупность определений констант, величин, массивов и таблиц, операций, процедур, синонимов понятий, масштабов величин. Общее число БЗ соответствует числу конкретных наук или специализаций (более 600). По происхождению БЗ бывают: встроенные, поставляемые, заказные, пользовательские. Рассмотрим пример БЗ, которые в первую очередь должны быть представлены на рынке.

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

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

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

Оформление отчетов (БЗО - отчёт) связано с автоматическим формированием отчетной документации. Здесь используются отчеты-шаблоны с возможностью параметрической подстановки последовательностей лексем. Сегодня актуальной является БЗО с описанием заданий на отчеты с применением естественного языка (ЕЯ). Эта БЗ, как правило, используется совместно с базой знаний интерфейса.

Взаимодействие с программой (БЗИ - интерфейс) обеспечивает пользователю описания собственного интерфейса. За счёт использования ЕЯ скрываются от пользователя программистские аспекты разработки интерфейса. БЗИ позволяет описывать интерфейс программы с различной степенью использования программирования (от минимальной – стандартный интерфейс, до максимальной – полное программирование).

Статистическая обработка (БЗА – обработка анкет) касается обработки анкет после проведения массового опроса. На рынке программ имеются автономные программы обработки данного вида анкет. Общий подход к решения такого класса задач состоит в автоматическом создании анкет двух сортов: исследовательской и статистической. Исследовательская анкета задает для запроса разнообразные исходные данные для вычислений и преобразований, статистическая анкета предназначается для обработки результатов анкетирования.

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

Относительно новыми идеями в реализации решения классов задач являются:

- введение естественного понятия термина (взамен идентификатора),

- максимальное использование (русского или английского) ЕЯ,

- представление понятия парой (имя, значение),

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

- введение элементов программирования (школьного курса),

- введение понятия экологии знания [8],

- использование языка профессиональной прозы (ЯПП),

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

- использование масштабов, правил преобразования и подстановок.

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

3. Результаты работы комплекса Интеллсист

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

Фактами являются пары (термин, значение), представленные равенствами типа Х = 34 или простыми логическими величинами типа «снег идет». Заметим, что при этом в задании не содержатся операторы ввода данных и вывода результатов, они формируются автоматически для исходных и искомых величин соответственно. Если решение единственное, то печатается вся совокупность фактов для указанных искомых величин. Если решение не единственное, имеются альтернативы решений, они возникают при неполноте знаний, то печатается перечень совместных фактов в виде альтернатив.

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

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

4. Формализация в обработке информации.

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

  1. Простыми утверждениями, например, Х = 0.

  2. Сложными утверждениями, например, Х = А + В.

  3. Программными действиями, например, P(X) или A:=B.

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

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

  1. Простыми утверждениями, например, Х = 0.

  2. Сложными утверждениями, например, Х = А + В.

  3. Программными действиями, например, P(X) или A:=B.

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

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

  1. Простыми утверждениями, например, Х = 0.

  2. Сложными утверждениями, например, Х = А + В.

  3. Программными действиями, например, P(X) или A:=B.

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

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

  1. Простыми утверждениями, например, Х = 0.

  2. Сложными утверждениями, например, Х = А + В.

  3. Программными действиями, например, P(X) или A:=B.

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

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

  1. Простыми утверждениями, например, Х = 0.

  2. Сложными утверждениями, например, Х = А + В.

  3. Программными действиями, например, P(X) или A:=B.

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

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

  1. Простыми утверждениями, например, Х = 0.

  2. Сложными утверждениями, например, Х = А + В.

  3. Программными действиями, например, P(X) или A:=B.

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

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

  1. Простыми утверждениями, например, Х = 0.

  2. Сложными утверждениями, например, Х = А + В.

  3. Программными действиями, например, P(X) или A:=B.

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

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

  1. Простыми утверждениями, например, Х = 0.

  2. Сложными утверждениями, например, Х = А + В.

  3. Программными действиями, например, P(X) или A:=B.

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

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

  1. Простыми утверждениями, например, Х = 0.

  2. Сложными утверждениями, например, Х = А + В.

  3. Программными действиями, например, P(X) или A:=B.

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

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

  1. Простыми утверждениями, например, Х = 0.

  2. Сложными утверждениями, например, Х = А + В.

  3. Программными действиями, например, P(X) или A:=B.

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



Скачать документ

Похожие документы:

  1. Пинжин алексей евгеньевич алгоритмы интеллектуальной обработки информации и структурного синтеза программ

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

    Автореферат диссертации
    на заседании совета по защите докторских и кандидатских диссертаций Д 212.269.06 в Томском политехническом университете по адресу: 634034, г. Томск, ул.
  3. Программа вступительного экзамена в магистратуру (5)

    Программа
    Программа вступительного экзамена состоит из трех разделов – информатика, математика, дополнительные вопросы по специализации (в зависимости от выбранной магистерской программы).
  4. Программа вступительного экзамена в магистратуру (9)

    Программа
    Программа вступительного экзамена состоит из трех разделов – информатика, математика, дополнительные вопросы по специализации (в зависимости от выбранной магистерской программы).
  5. Программа вступительного экзамена в магистратуру (11)

    Программа
    Программа вступительного экзамена состоит из трех разделов – информатика, математика, дополнительные вопросы по специализации (в зависимости от выбранной магистерской программы).
  6. Программа междисциплинарного вступительного экзамена

    Программа
    Методы организации сетей ЭВМ. Основные принципы их функционирования. Классификация сетей по масштабу и топологии. Понятие сетевого протокола. Семиуровневая модель OSI/ISO.

Другие похожие документы..