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

О г, Л V.

МОСКОВСКИЙ ордена ЛЕНИНА и ордена ОКТЯБРЬСКОЙ РЕВОЛЮЦИИ ЭНЕРГЕТИЧЕСКИЙ ИНСТИТУТ

разработка и реализация систем!! флицконшного №огра/.:.у:1говак1я

Специальность С5.13.13 - Вцчислитэлыше- мажаш, ксжлоксн,

системы 11 сэти 05.13.11 - Математическое и программной

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

ГРЫЗУНОВ Валерия Борисович

обеспочошю югшсдито.пышх машин

и систем

АВТОРЕФЕРАТ

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

Москва 1990

Работа выполнена на кафедре Прикладной математики Московского ордена Ленина и ордена Октябрьской Революции энергетического института

Научный руководитель - доктор технических наук, профессор ХУТЕЛОВ В.П.

Официальные оппоненты: доктор технических наук, профессор ТРАХТЕНГЕРЦ Э.А.

кандидат технических каук, додэнт ШЪК В.Н.

Ведущая организация: Вычислительный центр СО АН СССР.

Заадга диссертации состоится "26 " дек г. (зря 1990 Г. в аудитории Г-310 в 18 час. 30 мин. на заседании Специализированного Совета К.053.16.09 Московского ордена Ленина и ордена Октябрьской Революции Энергетического института.

Отзывы в двух экземплярах, заверенные печатью, просим присылать по адресу: 1058838, ГСП, Москва Е-250, Красноказарменная ул., 14, Ученый Совет МЭИ.

С диссертацией можно ознакомиться в библиотеке МЭИ.

Автореферат разослан "26" 11 1990 г.

Ученый секретарь Специализированного Совета

К.053.16.09 К.г.В. А.Ф. БОЧКОВ

ОП&'-Я XAP/JíTEPiK11!KA PAEOTli

Летальность тцмл В нпстоя-даэ ьромл eco больную актуальность приобретает задача сокршушяя прскоз и удешевления процесса разработки и программного обеспечения. Решение этой гадочи можэт осуаэствдяться в трм различных направлениях. Персов направление связано с разработкой язиксв нового поколения, наггрпмзр, языков функционального, логического, объектно-ориентированного программирования. Прогркл'э в таких языках опнсызаетсл в понятиях из какой-либо привычней человеку области деятельности." Второе напрамогма связано с разработкой оряонтярозоятк на конкретный язык прсгра!.«зровакия технологий разраоот:::! прзгра;.?.: и систем лрограмгвфоншш, реалкзуюада эти технологи;!. Третье направленно состоит в прпжЕеняи различных средств, позволяющих выявлять автоматически различные оаиоки в программах к такта образом уменьпать затрата труда на отладку и сопровожден::-:! програ!"1.

С точки зрения реяения описанной выло задачи языки функционального ггрогражегрпва'кя обладают рядом пропмусеств. В частности, функциональные программы к.-оют четкую композиционную структуру. Эта структура мозгет бить положена в основу создания технологи! функционального программирования. Такая технология позволяет производить управление разработкой сложных программой комплексов как снизу-вверх, так и сворку-вгшз. На каждом шаге определяется совокупность подзадач, определяющих решение основной задачи, осуществляется контроль за тем, какие задачи ужо реализованы, а какие - еще требуют решения, осуществляется поиск вновь возникающих задач среди ухе реализованных. >

Особый интерес представляют языки композиционного функционального программирования (ставяио известными благодаря работам Их. Бэнуса, Редько В.Н., Фалька В.Н., Кутепова В.II. и др.). Этот интерес объясняется возмозностыо распараллеливания процесса выполнения программы и, таким оОразом, сокращения общего времени ое исполнения. Поскольку в композиционной структуре функциональной программы полностью отражены ее информационные зависимости, эта информация непосредственно

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

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

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

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

- исследования различных подходов к определению и реализации языкое программирования;

создания типизированного функционального языка программирования;

- определения задачи контроля типов выражений языка и разработки эффективного алгоритма для реиения этой задачи;

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

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

Научные результата роботы.

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

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

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

4. Разработан алгоритм контроля типов, вычисляющий типы

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

5. Выполнена реализация разработанного языка в виде диалоговой системы, функционирующей на* ЭВМ IBM PC/XT/AT под управлением операционной система мз воз.

Практическая значимость и внедрение результатов работа.

Диссертация представляет собой результат работы автора, проводившейся в рамках ШР, выполняемых кафедрой Прикладной математики МЭИ (Научный руководитель Кутепов В.П.). Созданная система программирования внедрена на ши ЭВМ, г. Минск.

Ащобация работы. Результата диссертационной работа докладывались и обсуждались на семинарах кафедры Прикладной математики МЭИ и следующих конференциях:

на v Всесоюзной шоле-семииарэ "Распараллеливание обработки информации" (Львов, 1985г.),

на viii-m Всесоюзном семинаре "Параллельное программирование и высокопроизводительные структуры" (Киев, 1988г.),

на конференции молодых ученых и специалистов МЭИ, 1988г.

Публикации. Основные результаты работы отражена в 4 публикациях и 3-х отчетах по НИР. •

Структура и объем работы.

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

, содержание работы

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

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

¡to пржс'ре язнксе Lisp, их, и других л-ос нованных языков паказет.з, что использэнание для определения фушодй операций ^.-абстракции и етликзшк приводят к полученз» плохо струк7уи:р«яшх хгзогрз:::-,. Это усложняет как пошашко смысла nporp's:гак к англзз »4срга«ясжах заьиспмостей програ?.м с цель» эффокгзз.'геЛ реадизаигл прсцасса начислений. Один из возмогках путей ревспия этой ярсблвкн состоит в дареводе прогркои в ксмокззторнув форму, да содергзду» првременаах. При таком првооргаовапк! схрнтко ккОДрмшюнше связи программ, устзяэ&тшаеяые погрздотвен аергконнях, выражаются явно в структуре ггрсгрз.'.-'.:; :: потому могут онть легко учтена.

Поскольку в кожозинкоигшс. прстражагс всо ет:£срмацг.онныэ зазисжасти тначзлшо каряхока явно, они оказывается нгкоолзе пригодны;,и: для организации наралделыдл: вычисления:. Внчислзние значения Оункцин ия этих языков описывается как асжссронний процесс прооорззов&иая граро, соотвэтствукг.эго фуикциональксй структуре программа. Кгждй ■ вот такого преоОразовзния ззшпс«29тся замене фрагмента графа, соотеетствувдего редуцируемому вира:;;ению, на некоторый новк" фрагмент.

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

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

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

1 ) развитие Сор:,гы схемного задания функций и данных;

2) возможность задания разлгдшх тмюв данных и эффективного контроля типовой правильности г-ыратений языка как условия повышения эффективности разработки программ;

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

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

Во второй главе определяется типизированный язык композиционного программирования Pun. •

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

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

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

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

определенна данного

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

Определение данного .газет вид:

val did. = dexpr, где did - идентификатор данного, а ¿expr - выражение данных. Идентификатор данного представляет из себя последовательность букв и цифр, начинающуюся с буквы, которой предшествует символ •?'. Пркмераш! допустимых идентификаторов данных являются следующие: ?зс, ?у99, ? Alpha.

Выражзнке dexpr имеет следующий синтаксис:

dsxpr ti- doon&i j tupio j fexpr (dexpr} j d&xpr:texpr,

где dsonst - это данное-константа, tupie - кортеж значений, fexpv - функциональное выражение, и texpr - тип.

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

tupie í dc-xpr j tuple , dexpr.

Константа dconst представляет из себя некоторое Оазисное значение данных:

deenst ::= () ¡ boolean I Integer | etring,

где () - специальное значение, называемое пустим кортеком; boolean обозначает логическую константу true или false; integer обозначает полое число, изображаемое в виде последовательности десятичных цифр, которой может предаэствовать символ минус a strins представляет из себя некоторую строку, т.е. последовательность символов (еозисжно, ¡i пустую), заключенную в двойные кавычка.

Ниже приведены прибери различных констант данных:

(), true, false, 1, О, -32, "abe", "строка".

Выражение техрг задает некоторую функцию, a texpr - тип. Выражение fexpr(dexpr) представляет результат применения

функции, задаваемой fexpv в значении, задаваемому dexpr.

Выражение aespr:texpr имеет тот же смысл, что и а&хрг, но оно сообщает, что эта выражение га.гает тип texpr.

Определение функции

Новые функции или функциональные схеш могут Сыть введены в программе посредством функциональных определений. Функциональное определение состоит из одного или нескольких функциональных равенств foq вида

feq ::= fid texpr] [i fn_l3t ]] = fexpr,

где fia является ■ идентификатором определяемой функции, необязательный элемент' определения tezpr указывает тип определяемой функции, a ;eiPг представляет из себя функциональное выражение. Если в равенстве присутствует список схемных переменных fn_iet:

fr._ut ::= fia | fn_lst , ftd, это означает что вводится описание схема функций относительно переменных, входящих в fr._tat.

Идентификатор функции представляется в языке в виде некоторой последовательности букв к цифр, начииакцсйся с буквы, например: Primes, res, х, y9s.

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

Необязательные элементы определений здесь и далее обозначаются заключением в квадратные скобки [ ].

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

Все определения фущщиЯ faef начилоюгея с клвчевого слова fun. Б случае рэкурсивкого определения за ним следует клвчевое слово гм:

fdef ::= iU3 fbauy | furi rsc fbody.

Тело функционального определения представляет из себя

функциональнее равенство /eq или систему

функциональных равенств, заключенную в фигурные скобки:

fbody fan I { /яув }.

Система функциональных равенств /аь»з записывается в вида последовательности функциональных равенств, разделенных ключевым словом and:

feys ::= fcq I fs%a jmd feq.

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

foz-pr- ::-- fconst { fid | fid [ fexpr_J.st J J

feen | /anal | fleet | select | id | fexpr op fespr j ( fexpr ) | fexpr : tezpr

f&xpr_let : fc-xpv j f&Tpv_lst , f&zp,

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

op ::= . | * | ++ | -> .

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

О, <12>, <ialse>, <"Str">.

Выражение fid является ссылкой на использование определенной ранее функции, a fid[fexPr_i3t] -функциональной

схемы. Список фактических параметров fexpr_iat представляет из сеоя последовательность функциональных выражений /.-?грг, перечисленных через запятую. Результат такого использования функциональной cxomj представляет из себя функцию, полученную подстановкой в определение fid вместо схемных переменных Функциональных ЕыраэвниП, находящихся на соотеетстзукких местах в /expr_ist. Во время такой подстановки выполняется переименование переменных таким образом, чтобы не возникало коллизии.

Функции-конструкторы ¡сап, анализаторы fanal, и функции проверки /test позволяют оперировать с составными структурами данных. Все эти функции неявно определяются вместе с соответствующими типами данных. При ото;,!, для кзадоа функции-конструктора ¡мается в точности одна функция-зпализатор и в точности одна функция проверки значения.

Функции-конструкторы служат для построения составных структур данных. Пусть con является конструктором составного значения из и кемленент. Тогда результат применения ооп к последовательности аргументов ^.....а имеет вид con(d1,...

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

Например, конструктору ооп соответствует анализатор "con, применение этой функция к значению ccn(d) ,...,d ) дает в результате сц,...,d . Если же анализатор применяется к значению, построенному нахим-лиоо другим конструктором оол1, то результат не определен.

Функция проверки значения ftest позволяет проверить вид использованного для построения значения конструктора. Идентификаторы этих функций строятся из идентификатора соответствующего конструктора путс-м приписывания ствола Пусть в программе определен тип данных с конструкторами con и corn. Тогда применение функщш проверки Зссп к значению

oon(d1.....da) дает в результате true, а применение Зсоп к

значению ooni ,...,ет) дает в результате false.

Функция выбора аргумента select извлекает из кортежа заданное значение. Идентификаторы этих функций записываются в виде двух десятичных чисел т и п без знака, мекду которым! стоит символ '": и"п. Результатом применения такой функции к кортежу, содержащему m элементов, является элемент с номером п. Например, результатом вычисления 3'2( true, "second", -100 ) является строка "second".

Тождественная функция id всегда возвращает в точности свой аргумент.

Для построения функциональных выражений используются четыре операции: '->' •*' '++'. Эти операции имеют

следующий смысл. Пусть f , 1>1 представляют из себя некоторые функции. Интерпретация операций функциональной композиция определяется следующий равенствами:

(f1.f2)(d) = i1 (f2(d)),

f -fg(ti), если it(d) определено и равно true

(i1->i2Xd' = | не определено, если г (сО нэ определено [ или равно ialse

^»...«^(d) = f,(d).....fn(d)

.++fn(d) = X1(4),

где 1<1<п, и значение f^d) определено. Для того, чтобы это условие выполнялось не более, чем 'для одного i, функции г,....,f должны быть ортогональными.

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

=> # ! ++!>-': Для отмены влияния приоритетов операций в гехрг могут Сыть использованы круглые скобки.

В качестве примера рассмотрим определение функции вычисления факториала, в котором реализуется метод "разделяй и властвуй". В этом определении вводится вспомогательная функция pfac(m,n), которая производит перемножение чисел в отрезке от и до п (включая концы отрезка). Очевидно, что п! = рГас(1 ,п).

Функция pfao может быть определена рекурсивно: Г ns,

{

если ts=n,

р£ас(п,г»)' =

т+п

рГао(т, X pfac(^- + 1, rj>, если гг.=гп

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

fun reo { íaot - (<1>*id).píact and pfact =

eq -> 2Л1 /»конца интервала совпадают*/

++ ne -> ( ((2"1 * hair).píact) * /*не совпадают*/ (((half * <1>).р1из * 2"2).píaot) J.EUlt and hall = (plus*<2>).div }

где вспомогательная функция half вычисляет среднее арифметическое двух чисел, функции eq и г.е являются встроенными функциям:, осущоствляксими сравнение значения, а функции plus, Dult и iiv - встроенными арифметическим функция®!.

СледукщиЯ npiu.íop демонстрирует использование функциональной схемы тар, реализующей применение заданной функции ко всем элементам списка, построенного с помощью конструкторов списка nil и cons:

fun reo rr.aptf] = ~nil.nil +4 ~сог.з. ((2"1. Í )* (2л2.п>ар)) .оопз Задав в качестве интерпретации переменной í функции увеличения целого значения на 1, получаем функцию ir.o:

fun ino = г.ар[ (id*<1>).plus ], увеличивавшую всэ элементы списка на 1.

Гилы программы строятся исходя из Оазиса, включакдего в себя различные типы данных. Множество типов данных включает в себя базисные тиш данных языка (такие, как int), а такке типы данных, определенные в программе. Важной особенность» языка Fun является наличие для любого типа данных функций конструирования и анализа данных, принадлежащих этому типу.

Определение типа данных начинается с ключевого слова data, за которым следует тело определения аъойу:

Тело определения dbody представляет из себя одиночное

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

data dbody.

равенство, ила последовательность равенств áeq, заключенную в фигурные скобки:

с£Ьcay dc?q ¡ { dLoys },

&зуз d&q j days and deq.

Равенство ¿«j содержит указание на идентификатор определяемого типа данных tycan, список тягов-переменных, если определяется полиморфный тин данных tyv_iet, и описание набора конструкторов .тина данных жсз:

cU-Q : : — tj/con £ [iyU—2et] ] cases,

где

cajea :сазе ¡ cases '¡' оазе, case ::- fcon ¡ fcan of texpv.

В этом определении fcon являются конструкторами значений типа данных. Если тип texpr не указан, то считается, что конструктор определен на значениях типа unit. В качестве примера рассмотрим определение типе данных "список", .использованный при описании функциональной схемы шар:

data l^stí'x] = nil ! cons oí 'xttlist . После того, как введено это определение, в программе можно использовать тип данных liet, для которого имеются конструкторы значений nil и cons, анализатора ~nil и ~оопз, и функции проверки ínil и Scons. Типы этих функций содержат переменную (например, nil: unit=>'x, cons: •x#liet['xj=>listl) и поэтому могут быть использованы для списков - целых чисел, списков логических значений и т.д.

Определение типа вводит имя типа, которое можно использовать в программе наравне со встроенными типами. 'Множество типов строится с помощью операции произведения типов # и операщш построения функционального типа => из Оазиса, включающего типы данных и переменные специального вида. Использование переменных позволяет вводить полиморфные типы, которые являются обобщенными описаниями множества типов, получаемых путем подстановки вместо типов-переменных типов-констант (не содержащих переменных). Определение типа начинается с ключевого слова taje и имеет следующий синтаксис:

type ttd£ Iti/K_Í0t) ] = texpr.

Это определение вводит тип на с переменными, перечисленными

в tyu_ist, который етвт быть далее использовал в программе вместо типа, задаваемого выражением texpr.

Список тппов-пйром5шых t у и_ist заключается в квадратные

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

tyv_l3t tyv | tyu_iai , tyt;.

Типы-перемонные ¡vu записываются в вщо символа апострофа, за которым следует последовательность букв и цифр, начппатаяся с оуква. Например, следу кию выражения являются дспусг.с.пл.и! типами-переменными языка: 'i, 'alpha, 'V93-

Еырмсекие texpr строится следукци образом:

texp-r tyoon I tyceni ierpr ] j tyv [ ( texpr ) j

ieipr top teipr ,

tcp ::= ft J =>.

Мхентафакатсри tycon (с парохетрзгя! или без) представляют Ото как базисные типы, например, тип логически: значений bool, т;ш целых значелкй int, или строковый тип sirin,;, так л ти::ы данных, определз-шшо пользователе:,;.

Символ i обозначает операции декартова произведения тглоз. Результат прадакекая этей операции епкенвоот т;пх ксртезса, элементы которых пршшдлежат •кяем-саяюгато.чля. Кзсрмер, кортеж (1 ,"Str", true) ::,-.кот тип in.t-»3trin£Sbool.

ФушаагсаальнкЯ тип te=pr1=>texpri3 являзтея типом функций, аргумент которых имеет тип tesprt, а значения и:,:еют тих t&xpr .

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

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

Milner R. A theory of type polymorphism in programing, J. of Comp. Sußtea. Sei. , vol. 17 , pp. 348-375, 1978.

Синтаксическая область типов гу определяется следующими правилами:

1 ) если базисный тип данных из коночного множества

гусст, ТО «у;

2) если а является типом-переменной из некоторого счетного множества хуи, то а е гц;

3) если р « «у и о « су, то р»а е гу и рха « гу',

4) других правил получения типов нот.

В этом определении и далее для типов-переменных выбираются буквы а, р, а для произвольных типов - буквы р, о и г.

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

V: ой* Ц<о •

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

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

выражение ограничение на типн

(/егргр (с1еа:рг0) )т р = О X

</ехрг' « Гехргг ) О1 = О2 = О, -С =

а-л . о2-*'!2

(Гехрг\ . Техрг2 ) Т1 = О2. О = О1, X = X2

(/ехрг1, 1 -> 2) Х1=Ьоо1, О1 = О2 = О,

0-41

"С

О2-«2

(/«р!-1, , ++- /вхрг-гг г) о1 = а2 = о, I1 '= т®

а -л а чх

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

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

Теорема. Пусть сЦ - правильно типизированное выражение языка. Тогда значение выражения & также имеет тип х.

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

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

Четвертая глава описывает реализацию разработанного языка в составе системы функционально-логического программирования для персональных ЭВМ типа 1ВХ РС/ХТ/АТ. На рис. 1 представлена общая структура системы. Она включает в себя подсистему организации процесса разработки программ, подсистем логического и функционального программирования, и подсистему верификации программ.

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

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

О б оТоТк а

с> т е м ы

организация процесса разработки программ

программный редактор

система функционального программирования

система упранлешш базой данных разработчика

система | верификации < программ

система логического программи-

систома управления

Рис. 1. Структура системы

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

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

Далее описывается реализация вычисления значений функций.

который, как ив3, реализован в виде преобразования древовидной структуры по правилам специального вида, начинаемым правилами преобразования деревьев. Квзздое такое правило определяет шаг ' вычисления, состоящий в преобразовании некоторого фрагмента дерева. Важным свойством такой модели вычислений является ее параллелизм, вытекакций из свойств операций функциональной композиции: ота модель допускает одновременное применение нескольких правил к различным нетвям дерева. Поскольку в настоящей реализации такая возможность отсутствует, производится псэвдопараллельная реализация процесса вычислений, когда время единственного процессора распределяется между различными процессам! преобразования деревьев. Следует однако отметить, что при переносе данной системы на ЭВМ с параллельной архитектурой потребуется модификация только, подсистемы выполнения, трудоклкость которой составляет около от общего объема разработки. При этом ухе реализованная система выполнения позволит производить отладку программ на последовательной ЭВМ.

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

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

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

^ Борздовэ Т.В. и др. Полиязычная система параллельного программирования, основанная на одном семействе функциональных языков. Программирование, 2, '984, с. 31-45.

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

Реализация системы выполнена на языке с с использованием программ Уаоо и Ьех. Обпцгй объем разработанных программных средств составляет около 230К байт.

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

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

3. Построена система типов языка, разработан и реализован алгоритм контроля типов.

4. Докззы'.;), что при выполнении правильно типизированных программ типовых ошибок не возникает.

5. Выполнена реализация разработанного языка в виде системы программирования для персональных ЭВМ IBM рс/хт/ат.

Основные положения диссертации отражены в следующих печатшх работах:

1. Кутепов В.П., Ульяновский КЛ., Грызунов В.В. Язык программирования, основанный на использовании отношений // Сб. науч. трудов, ли54. М.: Моск. Энерг. ин-т. 1888. ■

2. Грызунов Б.Б. Типизированный язык параллельного функционального программирования // Параллельное программирование и высокопроизводительные структуры: Тез. докл. vin-ro Всесоюзного семинара. 1988, Киев, с. 83.

3. Грызунов В.Б. Типизированный функциональный язык программирования .// Тез. докл. II Всесоюзной конференции по прикладной логике. 1988, Новосибирск, с. 68.

4. Вахрушева М.Б., Грызунов В.Б. Язык для представления параллельных функциональных программ // Распараллеливание обработки информации: Тез. докл. и сообщ. V Всесоюзной школы-семинара. 1985, Львов, ч. 1, с. 42-43.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАЕОТН

»».»И, К .■ .л1.«с.<11,.ч, !3