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

МОСКОВСКИМ ОРДЕНА ЛЕНИНА, ОРДЕНА ОКТЯБРЬСКОЙ РЕВОЛЮЦИИ И ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНАМЕНИ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМ. М.В.ЛОМОНОСОВА

Факультет вычислительной математики и кибернетики

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

ГРАЧЕВ Андрей Юрьевич

УДК 681.3

СТРУКТУРИРОВАНИЕ ДАННЫХ В ДИАЛОГОВОЙ СИСТЕМЕ ПРОГРАММИРОВАНИЯ ДССП

( 05.13.11 - математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей )

Автореферат

диссертации на соискание ученой степени кандидата физико-математических наук

Москва, 1991

Работа выполнена в научно-исследовательской лаборатории ¡ЭВМ Факультета вычислительной математики и кибернетики Московского государственного университета им. М.В.Ломоносова.

Научный руководитель:

кандидат технических наук, с.н.с. Брусенцов Н.Л.

Официальные оппоненты:

чл.-корр. АН СССР Иванников В.П. к. ф.-м. н. Шумаков М.Н.

Ведущая организация: Институт физики высоких энергий АН СССР.

в . часов в аудитории N на заседании Специа-

лизированного совета Д.053.05.38 N4 по математике Московского государственного университета им. М.В.Ломоносова (119899, Москва, Ленинские Горы, факультет вычислительной математики и кибернетики).

С диссертацией можно ознакомиться в библиотеке Факультету вычислительной математики и кибернетики МГУ им. М.В.Ломоносова.

Защита диссертации состоится "

1991 г.

Автореферат разослан

Ученый секретарь Совета профессор

Н.П.Трифонов

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

АКТУАЛЬНОСТЬ ПРОБЛЕМЫ. Современные задачи, решаемые в программировании (моделирование сложных систем, экспертные системы, логическое программирование и т.д.) характеризуются большой сложность». Для того, чтобы эффективно решать подобные задачи в языках или системах программирования должны присутствовать развитие средства структурирования как процедур, так и данных.

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

ЦЕЛЯМИ ДИССЕРТАЦИОННОМ РАБОТЫ являются исследование возможностей структурирования данных в ДССП, обеспечивающих единообразное представление процедур и данных, и разработка методов и инструментальных средств, поддерживавших такое структурирование.

НАУЧНАЯ НОВИЗНА работы состоит в следующем:

(1) разработаны принципы обеспечения в ДССП структурного единообразия данных и процедур;

(2) создан инструментарий для организации и обработки данных в ДССП на уровне Форматов;

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

ПРАКТИЧЕСКАЯ ЦЕННОСТЬ диссертации заключается в следующем:

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

мистского труда;

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

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

НА ЗАЩИТУ ВЫНОСЯТСЯ методы и инструментальные средства структурирования данных в ДССП.

АПРОБАЦИЯ РАБОТЫ. Результаты исследований и разработок, представленных в диссертации, неоднократно обсуждались на научных семинарах кафедры АСВК и ЛНКЛ ЭВМ факультета ВМК МГУ, докладывались на VIII советско-болгарском семинаре "Проблемы информатики'и ее применения".

СТРУКТУРА ДИССЕРТАЦИИ. Диссертация состоит из введения, трех глав, заключения, списка литературы и приложения. Об'ем диссертации - 107 страниц машинописного текста, приложениям? страниц, список литературы содержит .85 наименований.

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

ВО ВВЕДЕНИИ дана характеристика проблемы структурирования данных, сформулированы цели и задачи диссертационного исследования. Приведено краткое описание содержания диссертации.

В ПЕРВОЙ ГЛАВЕ рассмсцгриваются принципы, на которых ост новано структурироваие данных в ДССП. Определяющим является единообразие структур данных и процедур, порождаемых сочетанием линейной упорядоченности и вложенности.

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

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

Основной характеристикой данного в ДССП является формат. Понятие Формата включает инфо;1 > -«чум емкость, структуру и способы доступа к значении или *.и«понентам.

Структура задает соотношение между компонентами. В отношении структуры различают базовые и составные форматы. Структура базового формата примитивна - он не разбит на компоненты и доступ к нему возможен только как к единому целому, характеризуемому его информационной емкостью (числом битов). Наименьший базовый формат - бит. Другие базовые форматы, используемые в ДССП',8-битный байт, 16-битное слово, 32-битное слово двойной длины. Таким образом, базовые форматы представляют собой монолитные, неразделимые при доступе к ним об'екты определенной информационной емкости.

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

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

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

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

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

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

ВО ВТОРОЙ ГЛАВЕ описываются разработанные инструментальные средства структурирования форматов данных на основе принципов упорядоченности и вложенности.

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

Команды обращения к данным в ДССП имевт вид: (мнемокод команды) (имя данного).

Предопределены четыре команды доступа к данным:

(1) взять значение (мнемокод как правило, умалчивается, то есть имя данного без предшествующего мнемокода доступа эквивалентно команде взять' значение);

(2) присвоить значение (мнемокод "!");

(3) получить адрес элемента (мнемокод ■"");

(4) осуществить инициализации (мнемокод "!!!").

Например:

XI - поместить в стек значение переменной XI;

! Х2 - присвоить переменной Х2 значение, взятое из стека.

Данные должны бить предварительно описаны. Для описания данных базового формата нужно указать имя Формата и имя данного. Например:

BIT FLAG BYTE CHARi WORD X ACT TRANS

Предопределены следующие базовые форматы: BIT, BYTE, WORD и ACT. Базовые форматы BYTE и WORD являвтся, соответственно, 8- и 16-битными словами.

Базовый Формат ACT предназначен для хралёния указателя на процедуру (имени процедуры во внутреннем представлении). При осуществлении доступа "взять значение" процедура, значение указателя которой было присвоено данному с Форматом ACT, будет передана на вход ДССП-процессора, то есть данная процедура будет выполнена.

Предопределены структуры VECTOR, STRING, STACK, FILE, REC, LIST (вектор, строка, стек, Файл, запись, список) с обычными для них способами выбора компонент. Также имеется структура ARRAY, являющаяся композицией векторов. Следует отметить, что все эти структуры построены на основе принципов упорядоченности и вложенности.

Для описания данного составного формата нужно указать структуру, Формат компоненты и имя данного. Если описание структуры требует некоторой дополнительной информации (например, для вектора надо задать максимальный номер компоненты) , то требуемые значения должны быть засланы в стек. Например:

5 VECTOR BYTE А [вектор байтов А с компонентами от 0 до 5] 40000 FILE BYTE BOOK Сфайл байтов максимальной длины 40000] 25 STRING ACT DISPET [строка "процедур" макс, длины 253

В качестве формата компонент может бить указан и составной Формат, получению"!, в свою очередь, из структуры и формата. Например, можно определить Формат STACK с максимальной глубиной 10 и компонентами Формата VB5:

: SVB5 10 STACK VB5 ; где формат VB5 определен как

: VB5 5 VECTOR BYTE ;

Формат VB5 можно использовать и непосредственно для описания данных, например, описание VB5 А1 эквивалентно описанию 5 VECTOR BYTE A1.

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

Новые структуры также могут быть построены путем композиции уже известных структур. Например, описание структуры двумерный массив (матрица) выглядит так: : MATRIX VECTOR VECTOR ;

Полезная для моделирования некоторых сложных систем структура VECSTACK (вектор стеков) описывается в виде : VECSTACK VECTOR STACK ; Среди предопределенных структур структура REC (запись) отличается от других тем, что допускает возможность разноФорматных компонент (запись является неоднородной структурой, вектор, стек, список и т.д. - однородные структуры). Для идентификации компонент в записи используются их имена. Для каждой компоненты записи надо указать имя и Формат. Следовательно, форматы компонент записи следует описывать тем же способом, что и Форматы других поименованных данных. По этой причине, описание Формата со структурой запись было реализовано следующим образом:

REC (имя Формата) (список имен компонент) ; Компонента описывается как обычное данное. Например:

REC COORDIN X Y Z ; С определить формат COORDIN с компонентами X, Y и Z ] WORD X WORD Y WORD Z REC CAR NAME MODEL ; С определить формат CAR

с компонентами NAME И MODEL ] 10 VECTOR BYTE NAME WORD MODEL Формат со струтурой REC используется для описания данных обычным образом:

COORDIN Pointl COORDIN Point2 3 VECTOR COORDINE Square Единственный имеющийся у структуры REC способ выбора компоненты соответствыет команде "взять значение" и настраивает компоненты на данную запись. Например, выполнение присваивания компоненте X данного Pointl компоненты X данного Po1nt2 будет выглядеть следующим образом: Po'int2 X [Pointf.X] Pointl ! X □ Конструктор Форматов данных состоит из описателей новых базовых форматов и структур (FORMAT: и STRUCT:).

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

- 9 -

Описание базового формата: FORMAT: <имя Формата) <инф. емкость в байтах) MP: <мнемокод команды) <имя процедуры доступа)

MP: <мнемокод команды) (имя процедуры доступа) Прежде чем привести пример описания базового формата, опишем порядок выполнения команды доступа. В каждую из процедур, реализующих доступ к данному, вложена запускающая процедура. Данному, в свою очередь, сопоставлен дескриптор, где хранится ссылка на формат и область памяти, где расположено его значение. При выполнении команды запускающая процедура получает адрес области памяти, сопоставленный указанному в команде данному, помещает этот адрес в стек операндов, а затем передает управление процедуре, реализующий данный доступ для формата данного. Зная адрес данного, процедура доступа может выполнить необходимые действия над память», отведенной под значение данного.

Пюимер описания базового формата: 'FORMAT: WORD 2

MP: ~ @ MP: i !Т

■MP: 'NOP MP: !!! !T В данном примере вводится базовый формат WORD, его информационная емкость равна 2 байтам. Префикс "MP:" и следующие за ним мнемокод команды и имя процедуры определяют один способ доступа. Например, тройка "MP: ~ означает, что допускается доступ с мнемокодом команды (взять значение), реализуемый для данного Формата процедурой с именем "У". Процедура изымает из стека адрес и заносит в стек значение слова, хранящегося по данному адресу (адрес, как уже говорилось , предварительно занесен в стек запускающей процедурой). К данному Формату, как видно, можно осуществить все четыре вида доступа, имеющихся в базовой версии ДССП.

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

Другая проблема, связанная с описанием новой структуры,

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

В КФД данная проблема решена следующим образом. Каждой структуре ставится в соответствие процедура стандартного выбора компоненты, а для тех видов доступа, которые требуют иной, нестандартной процедуры выбора компоненты, эту процедуру определяют особо для каждого мнемокода доступа. Если для некоторого доступа не предусмотрен свой способ выбора компоненты, то будет задействован стандартный способ. Формат описателя структуры: STRUCT: <имя структуры)

(процедура вычисления информационной емкости) (процедура стандартного выбора)

MP: (мнемокод команды) (процедура выбора компоненты)

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

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

STRUCT: VECTOR LVECTOR TVECTOR

MP: !!! !!¡VECTOR Здесь LVECTOR - процедура, определяющая информационную емкость формата с данной структурой. Данная процедура извле-

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

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

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

Рассмотрим на примере вектора А как будет происходить выполнение доступа к данному с составным Форматом. Например, команда

CN], 2 ! А С]

означает, что компоненте с номером 2 нужно присвоить значение N. Последовательность действий, инициализируемых этой командой выглядит следующим образом. Запускающая процедура, вложенная в процедуру доступа с мнемокодом "!", выясняет, что для указанных доступа и структуры не предусмотрена нестандартная процедура выбора. Поэтому управление передается процедуре стандартного выбора TVECT0R, которая потребит из стека операндов номер компоненты (в данном случае 2) и по данному номеру и информационной емкости компоненты определит местоположение нужной компоненты, а затем осуществит к указанной компоненте предписанный доступ "присвоить значение".

Рассотрим более сложный пример. Пусть данное VS1 описано как вектор с компонентами от О до 5, каждая компонента является стеком глубины 10 с компонентами базового Формата WORD. То есть VS1 описан так:

5 10 VECSTACK WORD VS1 Тогда команда

1 POP VS1 [заслать в стек операндов вершину стека, являющегося 1-й компонентой VS13 вызовет следующие действия. Запускающая процедура поместит в стек операндов адрес области памяти, сопоставленной данному ysi й передаст управление процедуре стандартного доступа структуры VECTOR. Данная процедура, зная информационную ем-

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

В ТРЕТЬЕЙ ГЛАВЕ приводятся примеры конкретных прикладных программ, реализованных с помощью описанных во второй главе механизмов и инструментальных средств структурирования данных: продукционная система, Файловая система, механизм классов, консультационная система и реляционная база данных.

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

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

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

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

Для представления продукции в ДССП разработан Формат PROD - двухкомпонентная запись, содержащая имена процедур, реализующих, соответственно антецедент и консекрент. Формат PROD допускает следующие виды доступа - взять значение антецедента и консеквента, присвоить новые значению антецеденту и консеквенту, выполнить продукцию и т.д. Например, чтобы определить продукцию с. именем Р1, присвоить ей в качестве антецедента процедуру P1ANTC, в качестве консеквента - процедуру PICONS, а затем выполнить ее, надо осуществить следующие действия:

PROD PI [определение продукции Pi]

- 13 -

" PIANTEC !ANTEC PI [присваивание антецедента]

" PICONS ICONS PI [и консеквента продукции PIT

VP PI [выполнение продукции PI]

Для об'единения продукций в единый набор правил введен Формат FPS со структурой вектор, компонентами которого являются тройки <продукция, приоритет, признак вкл/выкл). Приоритет определяет порядок тестирования продукций, а признак -нужно ли вообще тестировать данную продукцию.

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

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

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

В Файловой системы <ФС) КФД использован при разработке справочника Файлов на диске и для реализации каналов.

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

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

Механизм классов предназнаен для организации данных в иерархическую структуру (дерево). Каждый узел имеет некото-

рые атрибуты (свойства). Считается, что узел наследует свойства вышележащего узла (узел-сын наследует свойства узла-отца).

Для представления отдельного узла реализован Формат CLASS. Данный формат состоит из следующих компонент: имя отца, список сыновей и список свойств. Список сыновей содержит имена сыновей данного класса, а список свойств - имена и значения свойств данного узла.

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

Таким образом, КФД позволил достаточно просто (текст описания данной структуры занимает вместе с комментариями около 2 КБ и менее 100 строк) реализовать подобную организацию с очень высокой гибкостью.

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

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

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

Гипотезы об'единены в вектор. Каждая гипотеза представляется трехкомпонентной записью. Первая компонента является текстовой расшифровкой гипотезы (формат TEXT). Вторая компонента содержит информацию о текущем состоянии гипотезы и используется в процессе вывода. Третья компонента содержит сведения о связанных с гипотезой свидетельствах. Данная компонента представляет собой структуру KEYSET, компонентами которой являются тройки (имя свидетельства, вероятность при истинной и при ложной гипотезе).

При разработке организации данных для данной модели предметной области были специально разработаны структура KEYSET ("множество с бирками") и формат TEXT (текстовый).

- 15 -

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

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

В реляционных базах данных (РБД) данные организованы в отношения. Каждое отношение является множеством n-ок, называемых кортежами.

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

Преимущества использования КФД для построения РБД выразились также и в том, что компонентами кортежей могут быть данные произвольных форматов, в том числе введенных пользователем. Это делает реализованную РБД более гибкой по сравнению с большинством имеющихся баз данных для микрокомпьютеров (РБД-МИКРО, dBASE), где набор возможных типов атрибутов ограничен и не может быть расширен.

В ЗАКЛЮЧЕНИИ подводится краткий итог диссертационной работы и формулируются основные результаты.

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

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

(1) Систематически рассмотрены методы организации и построе-

- 16 -

ния форматов данных на основе линейной упорядоченности и вложенности;

<2) Разработаны методы и реализованы инструментальные средства представления и манипулирования данными с произвольой организацией: конструктор форматов данных; (3) На основе разработанных методик и средств реализованы конкретные, прикладные программные средства: продукционная система, Файловая система; механизм классов, реляционная база данных, 'консультационная система.

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

РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ ОТРАЖЕНЫ в следующих печатных работах:

1. Грачев А.Ю., Руднев И.А. Организация Файловой системы в ДССП-80.// Управление периферией в микрокомпьютерных системах.: Сб.статей / Под ред. Н.П.Брусенцова и А.М.Шаумана. -М.: изд-во МГУ, 1988, с. 30-39.

2. Грачев А.Ю. Продукционная система на базе диалоговой системы структурированного пограммирования ДССП-80. // Приборы

и системы управления, 1988, N 12, с. 7-8. о. Грачев А.Ю. Файловая система ДССП с точки зрения пользователя. // Проблемы оптимизации дискретных систем. -Л.: Изд-во ЛГУ, 1989, С. 82-89.

4. Грачев А.ю. Продукционная система в ДССП-80. // Программное оснащение персональных компьютеров. Сб.статей / Под ред. Н.П.Брусенцова и А.М.Шаумана. - М.: изд-во МГУ, 1990, с. 51-63.

Подписано в печать 15.04.91 г. Формат 60x84/16. Объём 1,0 п.л. Тирая 100 экз. Заказ й 20. Бесплатно.

Ротапринт НИЩ МГУ