Об одном подходе к проектированию алгебраических типов данных

Робота присвячена методам вирішення проблем які виникли при проектуванні алгебраїчних типів даних шкільної системи комп’ютерної алгебри Терм. Описана ієрархія алгебраїчних типів даних цієї системи, розглянуті основні методи проектуванні та реалізації алгебраїчних обчислень, які ґрунтуються на вико...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2006
1. Verfasser:	Песчаненко, В.С.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут програмних систем НАН України 2006
Schlagworte:	Інструментальні засоби і середовища програмування
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/1640
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Об одном подходе к проектированию алгебраических типов данных / В.С. Песчаненко // Проблеми програмування. — 2006. — N 2-3. — С. 626-634. — Бібліогр.: 7 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-1640
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-16402025-02-09T21:55:28Z Об одном подходе к проектированию алгебраических типов данных About one approach to algebraic data types design. Песчаненко, В.С. Інструментальні засоби і середовища програмування Робота присвячена методам вирішення проблем які виникли при проектуванні алгебраїчних типів даних шкільної системи комп’ютерної алгебри Терм. Описана ієрархія алгебраїчних типів даних цієї системи, розглянуті основні методи проектуванні та реалізації алгебраїчних обчислень, які ґрунтуються на використанні технологій символьних перетворень. The article is dedicated to the methods for solving the problems, aroused during design of school computer algebra system TerM algebraic data type. The algebraic data type hierarchy of the present system is described in the article; also the basic methods of design and realization of the algebraic computing, based on the usage of symbolic conversion technologies, are examined. 2006 Article Об одном подходе к проектированию алгебраических типов данных / В.С. Песчаненко // Проблеми програмування. — 2006. — N 2-3. — С. 626-634. — Бібліогр.: 7 назв. — рос. 1727-4907 https://nasplib.isofts.kiev.ua/handle/123456789/1640 681.3 ru application/pdf Інститут програмних систем НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Інструментальні засоби і середовища програмування Інструментальні засоби і середовища програмування
spellingShingle	Інструментальні засоби і середовища програмування Інструментальні засоби і середовища програмування Песчаненко, В.С. Об одном подходе к проектированию алгебраических типов данных
description	Робота присвячена методам вирішення проблем які виникли при проектуванні алгебраїчних типів даних шкільної системи комп’ютерної алгебри Терм. Описана ієрархія алгебраїчних типів даних цієї системи, розглянуті основні методи проектуванні та реалізації алгебраїчних обчислень, які ґрунтуються на використанні технологій символьних перетворень.
format	Article
author	Песчаненко, В.С.
author_facet	Песчаненко, В.С.
author_sort	Песчаненко, В.С.
title	Об одном подходе к проектированию алгебраических типов данных
title_short	Об одном подходе к проектированию алгебраических типов данных
title_full	Об одном подходе к проектированию алгебраических типов данных
title_fullStr	Об одном подходе к проектированию алгебраических типов данных
title_full_unstemmed	Об одном подходе к проектированию алгебраических типов данных
title_sort	об одном подходе к проектированию алгебраических типов данных
publisher	Інститут програмних систем НАН України
publishDate	2006
topic_facet	Інструментальні засоби і середовища програмування
url	https://nasplib.isofts.kiev.ua/handle/123456789/1640
citation_txt	Об одном подходе к проектированию алгебраических типов данных / В.С. Песчаненко // Проблеми програмування. — 2006. — N 2-3. — С. 626-634. — Бібліогр.: 7 назв. — рос.
work_keys_str_mv	AT pesčanenkovs obodnompodhodekproektirovaniûalgebraičeskihtipovdannyh AT pesčanenkovs aboutoneapproachtoalgebraicdatatypesdesign
first_indexed	2025-12-01T04:46:14Z
last_indexed	2025-12-01T04:46:14Z
_version_	1850279856516890624
fulltext	Інструментальні засоби і середовища програмування © В.М. Зінькович, Є.І. Моренцов, 2006 ISSN 1727-4907. Проблеми програмування. 2006. №2-3. Спеціальний випуск 626 УДК 681.3 ОБ ОДНОМ ПОДХОДЕ К ПРОЕКТИРОВАНИЮ АЛГЕБРАИЧЕСКИХ ТИПОВ ДАННЫХ В.С. Песчаненко Институт кибернетики им. В.М. Глушкова НАН Украины, 03680,Киев, проспект Академика Глушкова, 40 vladim@ksu.ks.ua Робота присвячена методам вирішення проблем які виникли при проектуванні алгебраїчних типів даних шкільної системи комп’ютерної алгебри Терм. Описана ієрархія алгебраїчних типів даних цієї системи, розглянуті основні методи проектуванні та реалізації алгебраїчних обчислень, які ґрунтуються на використанні технологій символьних перетворень. The article is dedicated to the methods for solving the problems, aroused during design of school computer algebra system TerM algebraic data type. The algebraic data type hierarchy of the present system is described in the article; also the basic methods of design and realization of the algebraic computing, based on the usage of symbolic conversion technologies, are examined. Введение Существующие коммерческие системы компьютерной алгебры (Derive, Mathematica, Maple, MathCad и др.) в основном решают проблему поддержки профессиональной математической деятельности. Отметим, что использование таких систем в учебных целях в школе ограничено. Среди нескольких причин выделим главную: они ориентированы на получение ответа математической задачи, а не на получение хода ее решения, что является главной целью ученика. Поэтому системы компьютерной алгебры учебного назначения (системы школьной компьютерной алгебры) должны поддерживать ход решения математической задачи. Эта поддержка заключается либо в генерации шага решения задачи в соответствии с командой пользователя, либо в проверке математической правильности шага решения, если он выполнен пользователем. Математическая деятельность пользователя заключается в следующем: ⇒ построении математических объектов; ⇒ распознавании свойств математических объектов; ⇒ преобразованиях математических объектов. Математическая деятельность осуществляется в рамках соответствующей предметной области, описываемой конструктивно и аксиоматически. Это означает, что: ⇒ математические объекты определены в предметной области в виде математических конструкций; ⇒ свойства математических объектов описаны аксиоматически; ⇒ преобразования объектов определены в виде списка допустимых (элементарных) преобразований. Математическая деятельность направлена на решение математической задачи как основной семантической единицы деятельности. Ход решения задачи представляет собой последовательность шагов, на каждом из которых пользователь: ⇒ распознает некоторое свойство математического объекта, определенного в решаемой задаче; ⇒ преобразует этот объект. Таким образом, процесс решения задачи – последовательность вида T1 T2 Ti Tn S1 S2 . . . Si Si+1 . . . Sn где Si – математические объекты, Ti – их элементарные преобразования. С логической точки зрения ход решения задачи – это логический вывод в соответствующей эквациональной теории, который, как известно, заключается в подстановке термов вместо предметных переменных и замена термов равными термами. ТерМ – это единственная система школьной компьютерной алгебры, которая, в числе прочего, поддерживает математическую деятельность учащегося. Еще одна принципиальная отличительная особенность ТерМ заключается в том, что в системе реализован полный набор учебных объектов, что позволяет эффективно организовать учебный процесс. Это – дидактические материалы (математический учебник, задачник, справочник, тетрадь) и математические , Інструментальні засоби і середовища програмування 627 инструменты (среда решения (задач) решатель и графики). Общая объектная модель системы ТерМ показана на рис. 1. Жирным выделены программные модули, реализация которых требует использования методов компьютерной алгебры и технологий алгебраического программирования. Таким образом, с точки зрения логической архитектуры система ТерМ – типа клиент-сервер. Серверная часть ТерМ, в свою очередь, распределена на двух уровнях – реализации алгоритмов решения системных задач и реализации алгебраических вычислений в многосортной алгебре, представляющей соответствующую предметную область. Уровень реализации алгоритмов решения алгебраических задач представлен алгебраическими модулями соответствующих учебных объектов и режимов. Уровень реализации алгебраических вычислений представлен модулем сервер алгебраических вычислений. Таким образом, возникает важная проблема проектирования многосортных алгебр. При проектировании основные усилия направлены на описания вычислений значений выражений над такими многосортными алгебрами. Постановка задачи В соответствии с техническим заданием на систему ТерМ 7–9 необходимо реализовать вычисления в следующих числовых алгебрах: целые, действительные, рациональные, комплексные и радикальные числа. При этом вычисления должны быть реализованы с неограниченной разрядностью. Отметим, что рациональные числа нужно представить тремя изоморфными реализациями: алгеброй дробей, алгеброй смешанных дробей и алгеброй десятичных периодических дробей. Кроме того, система ТерМ должна поддерживать вычисления в Учебник Задачник Тетрадь Среда Решения Решатель Графики Упражнения Алгебраический модуль „Упражнения” Алгебраический модуль режима Автоматический Справочник Алгебраический модуль режима проверка Алгебраический модуль Решатель Алгебраический модуль Графики Сервер алгебраических вычислений Открыть Открыть Проверить Проверить Алгебраические вычисления Загрузить задачу Выполнить преобразования Решить Решить Сохранить задачу Рис.1. Объектная модель ТерМ Главное окно Персонификация, Выбор языка, Об авторах Інструментальні засоби і середовища програмування 628 таких алгебрах множеств, как алгебра конечных множеств) и алгебра числовых интервалов. Соответственно, в системе ТерМ нужно поддерживать вычисления в следующих символьных алгебрах данных: линейные, векторные, аффинные пространства линейных комбинаций, кольца многочленов от одной и многих переменных, поля рациональных функций от одной и многих переменных. Таким образом, возникает проблема эффективной реализации, а, следовательно, и качественного проектирования алгебраических типов данных для системы типа ТерМ. Проектирование иерархии алгебраических типов ТерМ осуществлялось в терминах частично- упорядоченных многосортных алгебраических систем [2]. Многосортные алгебры Под многосортной алгеброй (МСА) Т будем понимать многоосновную алгебраическую систему A(A1,..,Ak) с главным носителем А, носителями алгебр аргументов nAA ,...,1 Σ, сигнатурой предикатов П, сигнатурой констант Е (выделенных элементов носителя). )],...,([ 1,, nAAAT ΕΠΣ . (1) Алгебры аргументов, в свою очередь, определяются как многосортные. Например, на рис. 2 показан фрагмент структуры многоосновности. Стрелочки, проведенные на нем из А1,…,Ак в А означают, что сигнатура МСА А определяется через сигнатуры А1,…,Ак. Мы описываем структуру МСА в терминах наследования алгебр, расширения алгебр и морфизмов алгебр. Алгебра–элемент иерархии МСА описываются сигнатурой, носителем, алгоритмами реализации операций сигнатуры и набором аксиом. Проектирование осуществляется в 2 этапа: прототипирования, анализ свойств прототипа и реализации окончательной версии. Прототипирование заключается в построении МСА в терминах наследования, расширения, морфизмов и реализации построенной иерархии на языке АПЛАН в системе алгебраического программирования АПС [3]. Реализация заключается в выделении абстрактных алгебр, в терминах которых описываются алгебры иерархии и их реализации на нижнем уровне АПС. Наследование Механизм наследования является одним из основных характерных механизмов для объектно- ориентированного проектирования программных систем. При проектировании алгебр данных использование этого механизма имеет свои отличительные особенности. На содержательном уровне свойство наследования (B наследует A) означает, что: а) сигнатура B наследует сигнатуру A; На B могут быть определены собственные элементы сигнатуры-операции, константы и отношения; б) на B могут быть доопределены правила вычислений (интерпретирующие правила) для каждого элемента сигнатуры A; в) на B могут быть выполняться некоторые дополнительные свойства (например: коммутативность, ассоциативность, идемпотентность, отсутствие делителей нуля и т.д). Пусть ][,,, AT TTTT AXΕΠΣ , ][,,, BQ QQQQ AXΕΠΣ – две многосортные алгебры, в которых дополнительно к (1) описаны еще системы аксиом AXТ, AXQ. Будем говорить, что алгебра Q наследует алгебру T, если A ◄ B, ΣT ◄ ΣQ, ΠT ◄ ΠQ, ΕT ⊆ ΕQ, AXT ⊆ AXQ. (2) . . . A1 A2 Ak A Рис. 2. Фрагмент структуры многоосновности Інструментальні засоби і середовища програмування 629 Обозначение A ◄ B означает, например, что носитель B является уточнением носителя A в том смысле, что любой элемент B можно получить из некоторого элемента A путем доопределения (уточнения) некоторых фрагментов его структуры. Аналогичный смысл имеют и другие обозначения в (2). Некоторая алгебра может наследовать свойства и нескольких алгебр. В этом случае наследуемые свойства должны быть совместимыми. Для строгого определения механизма наследования нам необходимо более детально рассмотреть те средства описания алгебр данных, которые используются в определении наследования. Примеры наследования: 1. Абстрактная группа наследует свойства абстрактной полугруппы. В этом примере свойства полугруппы дополнены операцией a-1 и соответствующей аксиомой. 2. Абстрактное коммутативное кольцо наследует свойства абелевой группы (группы по сложению) и коммутативной полугруппы. Например, показано, множественное наследование. (рис. 3). Стрелочки, проведенные из А1,…,Ак в А на рис. 3 означают a), б), в) (см. выше). Расширения Пусть А и B - подобные алгебры. Алгебра В называется расширением алгебры А, если А ⊆ В и ограничение алгебры В на подмножестве А совпадает с алгеброй А.Конструкция расширения широко используется для введения в алгебру новых операций или придания алгебре новых свойств. Расширение алгебры описывается с помощью конструкций и вложений. Конструкции – это определения структуры носителя расширения алгебры, а вложения – это определения функций редукции элементов носителя расширения, принадлежащих расширяемой алгебре (функции преобразования типов). Примером расширения может быть построение поля рациональных чисел R как расширения кольца целых чисел Z: − элементами расширения называют конструкции вида a/b, где 1),(,0,, =>∈ baGCDbZba , }1),(,0,,,/{ =>∈= baGCDbZbabaR ; (3) − на множестве R определяют операции кольца Z(+,-,). Например, =+ dcba // Reduce ))/()*(( dbbcda + ; (4) − расширяют сигнатуру R, дополняя её операциями (/,()-1). Например, =)//()/( dcba Reduce ))/()(( cbda ; (5) − осуществляют вложения кольца Z в R, определяя изоморфизм Z в R тождеством вложения a/1=a (функция Reduce) (6) На рис 4, например, стрелка из А1 в А2 означает, что в А2 является расширением А1 определенное с помощью конструкции и вложения. Морфизмы A1 . . . Ak А Рис. 3. Фрагмент структуры наследования . . . Рис. 4. Фрагмент структуры расширений-вложений A1 A2 A3 A4 Інструментальні засоби і середовища програмування 630 Пусть А и В – подобные алгебры. Алгебра В называется гомоморфной алгеброй А, если существует такое отображение BA →:ϕ , что для любой операции ),...,( 1 naaF , сигнатуры AΣ ))(),...,(()),...,(( 11 nn aaFaaF ϕϕϕ = , аналогичные по смыслу соотношения имеют место для предикатов и констант сигнатуры ЕА и ПА. Подобные алгебры А и В называются изоморфными, если существует взаимнооднозначный морфизм: BA ↔:ϕ . Морфизмы алгебр – удобное средство для описания алгебраических вычислений во многих ситуациях. С точки зрения языка программирования морфизмы – это функции преобразования типа. Рассмотрим пример морфизма. Алгебра А – рациональных чисел над полем целых чисел. Это означает, что элементы А имеют вид: bau /= . Алгебра В – десятичных периодических дробей над полем целых чисел в сигнатуре обобщенной числовой функции PeriodNumeric. Это означает, что элементы В имеют вид: ),,( PeriodPPeriodWholericPeriodNumev = , где Whole – целая часть, PPeriod – число до периода, Period – число периода. Вычисления значений выражений и решение других алгебраических задач коротко и эффективно реализуются в алгебре А, а вывод необходимо осуществлять в сигнатуре алгебры В. Поэтому должны быть описаны алгебры А и В, причем вычисления в В описываются в терминах изоморфизма BA ↔:ϕ следующим образом: (.))(.),(.),(/(.))((.) PeriodPPeriodWholericPeriodNume=ϕ , (7) /(.)(.)(.)))(.),(.),((1 =− PeriodPPeriodWholericPeriodNumeϕ . (8) Если f,g – элементы алгебры В, и – одна из бинарных операций сигнатура В, то результат fg вычисляется по формуле: f ( g = ϕ -1(ϕ(f) * ϕ(g)). В более общем виде, если F – выражение над А, то его значение вычисляется как ))((1 Fϕϕ − . Двойная стрелка на рис. 5 из А1 в А2 означает, что реализованы 12 1 21 :,: AAAA →→ −ϕϕ , а стрелка из А2 в А3 – 32: AA →ϕ . Алгебраические типы данных ТерМ В результате проектирования алгебраических типов данных ТерМ получена следующая диаграмма наследования (рис. 6), морфизмов (рис. 7), расширений (рис. 8). MultyRadical – алгебра данных (АД) )(ATΩ с сигнатурой }^/,,,,,,,{ −+==><=Ω и носителем },;;{ CoefcbalMultyRadicacbaA ∈∈+= . MultyRadical – кольцо радикалов над полем Coef. Radical – АД )(ATΩ с сигнатурой }^/,,,,,,,{ −+==><=Ω и носителем },,;{ CoefcbacbaA ∈+= . Radical – полугруппа с одним образующим элементом. Complex – алгебра данных (АД) )(ATΩ с сигнатурой }^/,,,,,,,{ −+==><=Ω и носителем },;{ CoefbabiaA ∈+= . Complex– поле над полем Coef. Coef, RatPolynom, RatMultyPolynom – будут рассмотрены подробно на рис. 8. Изоморфизм Rational и PeriodNum был описан выше. Их изоморфизм с Real – известен. MultyPolinom – описанный на рис.9. RecPolynom – АД )(ATΩ с сигнатурой },,^/,,,,,,,{ NOKNOD−+==><=Ω и носителем },...,,,......{ 00 omMultyPolynaaDegreexaxaxaA n ii i n n ∈∈++++= . RecPolynom – кольцо многочленов от одной переменной над кольцом многочленов от нескольких переменных. Рис. 5. Фрагмент структуры морфизмов, двухсторонними стрелками обозначены изоморфизмы A1 A2 A3 A3 Інструментальні засоби і середовища програмування 631 Variable – алгебра данных (АД) )(ATΩ с сигнатурой },,{ ==><=Ω и носителем ,...},...,,,...,{ ZAzaA = . Эта АД используется для обозначения переменных, ее носитель состоит из больших и малых букв латинского алфавита, и этих букв с индексами. Coef – АД )(ATΩ с сигнатурой }^,,/,,,,,,,{ NOKNOD−+==><=Ω и носителем A для которого могут быть определены такие операции. Coef – поле. Эта АД используется для обозначения коэффициентов МСА. Рис. 6. Диаграмма наследования МСА ТерМ Coef MultyRadical Radical Rational RatPolynom Complex RatMultyPolynom Real Integer Рис. 7. Фрагмент диаграммы морфизмов МСА ТерМ Rational PeriodNum Real RecPolynom MultyPolynom Рис. 8. Диаграмма расширений МСА ТерМ Variable x Degree X^n(SemiGroupe) LinMonom Ax(Vector Space) Monom AD(SemiGroupe) Coef A(Field) LinSpace LM + LS(Vector Space) Polynom M + Pol(Ring) MultiDegree DMD(SemiGroupe) MultiMonom AMD(SemiGroupe) MultiPolynom MM + PM(Ring) AffSpace LS + A(Affine Space) RatPolynom Pol / Pol(Field) RatMultyPolynom MultyPol/MultyPol(Field) Інструментальні засоби і середовища програмування 632 Degree –АД )(ATΩ с расширенной сигнатурой }^,,/,,,,,{ NOKNOD==><=Ω и носителем },,^^{ CoefcVariablevcvA ∈∈= . Degree – полугруппа с одним образующим элементом над полем Coef. LinMonom – АД )(ATΩ с сигнатурой /},,,,,,{ −+==><=Ω (деление и умножение на число) и носителем },,{ CoefcVariablevvcA ∈∈= . LinMonom – одномерное векторное пространство над полем Coef.. MultyDegree – АД )(ATΩ с сигнатурой }^,,/,,,,,{ NOKNOD==><=Ω и носителем },,{ AaDegreedadA ∈∈= . MultyDegree – расширение Degree по операции умножения, т.е. полугруппа степеней многих переменных над полем Coef.. Monom – АД )(ATΩ с сигнатурой }^,,/,,,,,,,{ NOKNOD−+==><=Ω и носителем },,{ DegreedCoefcdcA ∈∈= . Monom – расширение Degree по операции умножения, т.е. полугруппа мономов с одним образующим элементом над полем Coef.. LineSpace – АД )(ATΩ с сигнатурой /},,,,,,{ −+==><=Ω (сложение и умножение на число) и носителем },,{ AlsLinMonomlmlslmA ∈∈+= . LineSpace – расширение LinMonom по операции сложения, т.е. векторное пространство линейных комбинаций над полем Coef.. MultyMonom – АД )(ATΩ с сигнатурой }^,,/,,,,,{ NOKNOD==><=Ω и носителем },,{ eMultyDegremdCoefcmdcA ∈∈= . MultyMonom – расширение MultyDegree по операции умножения, т.е. полугруппа мономов многих переменных над полем Coef. Polynom – АД )(ATΩ с сигнатурой }^,,/,,,,,,,{ NOKNOD−+==><=Ω и носителем },,{ AplMonommnplmnA ∈∈+= . Polynom – расширение Monom по операции сложения, т.е. кольцо многочленов одной переменной над полем Coef. Affspace – АД )(ATΩ с сигнатурой /},,,,,,{ −+==><=Ω (умножение и деление на число) и носителем },,{ CoefcLinSpacelsclsA ∈∈+= . AffSpace – расширение LinSpace по операции сложения с числом, т.е. аффинное пространство линейных комбинаций со свободным членом над полем Coef. MultyPolynom – АД )(ATΩ с сигнатурой /,,,,,,,{ −+==><=Ω }^,,NOKNOD и носителем },,{ omMultyPolinmpMultyMonommmmpmmA ∈∈+= . MultyPolynom – расширение MultyMonom по операции сложения, т.е. кольцо многочленов многих переменных над полем Coef. RatPolynom – АД )(ATΩ с сигнатурой /,,,,,,,{ −+==><=Ω }^,,NOKNOD и носителем }1),(;,;/{ =∈= yxGCDPolinomyxyxA .RatPolynom – расширение Polynom по операции деления, т.е. поле рациональных функций от одной переменной над полем Coef. RatMultyPolynom – АД )(ATΩ с сигнатурой /,,,,,,,{ −+==><=Ω }^,,NOKNOD и носителем }1),(;,;/{ =∈= yxGCDomMultyPolinyxyxA . RatMultyPolynom – расширение MultyPolinom по операции деления, т.е. поле рациональных функций многих переменных над полем Coef. Реализация многосортной алгебры, выполненная в соответствии с диаграммами (рис. 6, рис. 7, рис. 8) позволила полностью реализовать стандартные алгоритмы символьных вычислений в классической алгебре. Однако эта реализация имеет недостатки: во-первых, рекурсивный спуск при вычислениях «проходит» около 10 систем переписываний; во-вторых, в тех случаях, когда схемы расширений алгебр подобны, желательно использовать методы параметрического программирования, что не предусмотрено диаграммой расширений (рис. 8). Первый недостаток приводит к неоправданно большим затратам времени и памяти. Второй недостаток приводит к тому, что вместо того, чтобы повторно использовать код, приходится фактически копировались фрагменты уже написанного исходного кода, модифицировать и вставлять их в другое место программы. Отметим, что эти проблемы можно решить средствами инсерционного программирования [4] и перенести на нижний уровень только числовые алгебры. В данной версии, однако, использовалась техника параметрического программирования. После прототипирования и определения основных свойств нижнем уровне были реализованы алгебры данных, указанные на рис. 9. Алгебры данных Variable, Coef, Degree, MultyDegree – остались содержательно такими же, как и на рис. 7. Factor – АД )(ATΩ с сигнатурой }^,,/,,,,,{ NOKNOD==><=Ω и носителем };;/{ MComponentDegreeVariablexCoefcxcA ∪∪∈∈= . Factor – расширение Degree, MComponent по операции умножения, т.е. полугруппа над полем Coef. Інструментальні засоби і середовища програмування 633 LinSpase – АД )(ATΩ с расширенной сигнатурой ,,,,,{ −+==><=Ω },^/,, NOKNOD (умножение и деление на число) и носителем };;{ AcFactorfcfA ∈∈+= . LinSpace – расширение Factor по операции сложения, т.е. кольцо над полем Coef. AffSpace – АД )(ATΩ с расширенной сигнатурой ,^/,,,,,,,{ −+==><=Ω },NOKNOD (умножение и деление на число) и носителем },,{ CoefcCpmponentcpccpA ∈∈+= . AffSpace – расширение Component по операции сложения, т.е. кольцо со свободным членом над полем Coef GLAlgebra – АД )(ATΩ с сигнатурой /,,,,,,,{ −+==><=Ω }^,,NOKNOD и носителем }1),(,,;/{ =∈= yxGCDAppendyxyxA . RatPolynom – расширение Polynom по операции деления, т.е. поле частных над полем Coef. Используя конкретное значение правой части в определении носителя Factor, несложно установить гомоморфизм между соответствующими алгебрами рис. 8 и рис. 9. Поле такой реализации для проверки оптимальности перепроектированной диаграммы расширений МСА ТерМ, был поставлен вычислительный эксперимент. Небольшая часть результатов представлена в таблице. Таблица. Результаты вычислительного эксперимента МСА ТерМ Пример Время вычисления Используемая память Рис. 9 38 с 121 Мб Рис. 10 10)( zyx ++ 3 с 4 Мб Рис. 9 10 с 32 Мб Рис. 10 Время загрузки ядра сиcтемы 2 с 1 Мб Таким образом, реализация на нижнем уровне расширений МСА системы решила вышеописанные проблемы. Заключение Использование понятий наследования, расширения и морфизмов приводит к качественной реализации таких многосортных алгебр, при условии оптимального проектирования расширений. Построенные многосортные алгебры для ТерМ являются достаточно быстрой реализацией алгоритмов компьютерной алгебры и могут быть использованы для построения коммерческих программных продуктов в данной области знаний. Дальнейшее развитие ТерМ предполагает расширение поддерживаемых многосортных алгебр данных и повышение эффективности процедур интерпретации. Опыт и традиции разработки приложений с использованием APS накапливаются и используются в Институте кибернетики им. В.М. Глушкова НАН Украины, Херсонском государственном университете и в других научных заведениях. Выражаю благодарность научным руководителям А.А. Летичевскому, М.С. Львову, за постоянный интерес, руководство в проектировании ТерМ, адаптации APS и ценные замечания по содержанию данной работы. 1. Львов М.С. Терм VII – шкільна система комп’ютерної алгебри. Комп’ютер у школі та сім’ ї. – 2004. – № 7. – С. 27–30. 2. Математическая логика в програм-мировании: Сб. статей М34 1980-1988 / Пер. c англ. – М.: Мир, 1991. – 408 c. 3. Kapitonova U., Letichevsky A., Volkov V., Lvov M. Tools for solving problems in the scope of algebraic programming. Lectures Notes in Computer Sciences. – 1995 –№ 958.. – PP. 31–46. Рис. 9. Новая диаграмма расширений МСА ТерМ Variable V Coef A(Field) Degree V^^A(SemiGroupe) Factor A* (V\|D\|MC)(SemiGroupe) MultyDegree D**MC(SemiGroupe) AffSpace C++A(Ring) GLAlgebra Append/Append(Par. Field) Інструментальні засоби і середовища програмування 634 4. Капитонова Ю.В., Летичевский А.А., Волков В.А.. Дедуктивные средства системы алгебраического программирования // Кибернетика и системный анализ, 2000, 1, C. 17–35. 5. Volkov V., Kuprienko A., Lvov M. Applied Computer Support of Mathematical Training. Proc. of Internal Work Shop in Computer Algebra Applications, Kiev., 1993. – PP. 25–26. 6. Lvov M. AIST: Applied Computer Algebra System. Proc. of ICCTE’93. Kiev. – pp. 25–26. 7. Песчаненко В.С. Розширення стандартних модулів системи алгебраїчного програмування APS для використання у системах навчального призначення. Науковий часопис НПУ ім. МП Драгоманова Сер. № 2. Комп’ютерно-орієнтовні системи навчання –К.: НПУ ім. М.П. Драгоманова. 2005 – №3(10).

Об одном подходе к проектированию алгебраических типов данных

Institution

Ähnliche Einträge