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

• Автор: Мешвелиани, Сергей Давидович
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2002
• Место защиты: Переславль-Залесский
• Количество страниц: 103 с. : ил

Содержание
1 Введение

1.1 Цель и предмет исследования .

1.2 История и аналоги

1.3 Основные результаты, выносимые на защиту.

2 Математические основы Построителя

2.1 Что содержит Построитель

2.2 Некоторые сведения о применяемых алгоритмах

2.2.1 Действия с перестановками

2.2.2 Дроби .

2.2.3 Линейная алгебра

2.2.4 Арифметика многочленов.
2.2.5 Факторизация многочленов.
2.2.6 Базис Гребнера.
2.2.7 Симметрические функции
2.3 х кольца .
2.3.1 Многочлены над севклидовым кольцом .
2.3.2 Прямая сумма колец.
2.3.3 Кольцо остатков .
2.3.4 Преобразования описаний колец
2.3.5 йхдействия в программах
2.4 Усиление способа Л Л Л Григорьева
разложения на простые множители в Ра,у
2.4.1 Нахождение неприводимого множителя многочлена из х
для конечного поля Р
2.4.2 Обоснование правильности алгоритма.
2.4.3 Оценка сложности
2.5 Выводы .
3 Общие требования к языку программирования
3.1 Гибкость стратегии вычисления .
3.2 Функциональность.
3.3 Богатые средства задания типов.
3.4 Категорность
3.5 Поддержка полиморфизма
3.6 Поддержка стандартных отображений между областями
3.7 Выразимость свойств значений.
3.7.1 Категории алгебраической библитеки проекта.
3.7.2 О логическом программировании в языках ,
3.7.3 О применении правил, равенств .
3.8 Выводы
4 Параметрические алгебраические области
4.1 Архитектура библиотеки основной алгебры .
4.1.1 Ключевые черты проекта.
4.1.2 Категории, представленные в проекте
4.1.3 Начальный пример.
4.1.4 Использование подхода образца.
4.1.5 Смысл случаев для параметрической области .
4.2 О расширении языка зависимыми типами
5 Заключение
Список литературы


Итак, применение конструкторов системы строит алгоритмическое представление алгебраической поверхности, в общем случае — представление алгебраической области. Вообще же, задание пространственного объекта М в виде алгебры А числовых функций на А/ (алгебраических, гладких, непрерывных . А (с идеалами Л) делает топологию и геометрию предметом вычислительной алгебры и программирования. Задание вычислений в такой ‘категорной’ системе основано на том, что всякий конструктор области (Многочлен, Дробь, Вектор, . То есть как функтор, строящий некий стандартный набор алгоритмов действий +, *, /, . Например, выражение “запрограммировать арифметику многочленов1’ означает выразить действия 0,1,+,-,* для кольца многочленов . Pol. Выбор программного представления алгебраической области зависит от привлекаемого средства программирования. Система Построитель применяет язык Хаскел и представляет алгебраическую категорию в виде класса языка Хаскел, а алгебраическую область — в виде случая (instance) класса вместе с образцовым данным. Данный способ построения программ для алгебраических областей близок к обычно применяемому в математических работах способу описания вычислений. Наиболее известные на настоящее время языки и системы, применяющие категорный подход, суть Axiom [Je], Aldor [Al], MuPAD [Ми]. Система Axiom является в настоящею время обширной библиотекой математики для языка программирования Aldor (сейчас еще продолжается переписывание Axiom на Alder). Нам не известны какие-либо отечественные разработки этого направления — кроме упоминаемых здесь программ Построитель [Ме2], BAL [МеЗ]. Работу на этом направлении автор начал в -м году. Первым итогом была программа САС [Mel], написанная набезтиповом функциональном языке. Описания алгебраических областей dR строились из других описаний согласно конструкторам (Многочлен, Вектор, . Далее, описания dR передавались функциям в качестве дополнительного аргумента, и добавлялась система расстановки препроцессором по умолчанию подходящих аргументов dR. Из этого опыта стало ясно, что желательно использовать языки программирования с более богатыми средствами задания типов. Последние получили к тому времени достаточно работоспособные и доступные воплощения, например, [GH). Вернемся к рассмотрению программ Построитель, Aldor - Axiom, MuPAD. Про систему MuPAD [Mu] нам известно, что она использует язык MuPAD, с проце-дурами и другими нефункциональными средствами, делающими эту программную архитектуру далекой от Построителя. Поэтому в дальнейшем мы считаем, что достаточно только сравнения Построителя с программой Aldor - Axiom. Вот некоторые сведения об этих средствах. Отметим, что системы Aldor - Axiom и MuPAD не полностью доступны: не предоставляют пользователю исходный код, и следовательно, возможности самостоятельно исправлять эту программу. Axiom даже является полностью коммерческой системой. Такое положение мало отвечает потребностям научного сообщества. Далее, Построитель применяет чисто функциональное программирование и ‘ленивый’ способ вычисления. Aldor (Axiom), MuPAD не являются функциональными системами и применяют только ‘прямые’ вычисления. Aldor |А1) есть язык программирования похожий на ML, отчасти — на Haskell, но расширенный возможностью действовать с (абстрактными) типами данных (представляющих математические области) как с обычными значениями. Языковым средством для этого являются зависимые типы (dependent types) — типы, зависящие от значения. Притом допускается откладывать распознавание некоторых типов на этап выполнения программы. Так, например, это позволяет более естественно запрограммировать область вычетов Z/(m) с динамически меняющимся т (Подраздел 4. В этом смысле, — смысле программной архитектуры, — Построитель есть библиотека случаев (instances) для алгебраических конструкторов языка Haskell. Причем отсутствие в языке зависимых типов восполнено применением подхода, образцового элемента (Подраздел 4. Подраздел 4. Перечислим коротко главные отличия программы Построитель от системы Aldor - Axiom.