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

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 gx-кольца

2.3.1 Многочлены над с-евклидовым кольцом

2.3.2 Прямая сумма колец.

2.3.3 Кольцо остатков

2.3.4 Преобразования описаний колец.

2.3.5 gx-действия в программах

2.4 Усиление способа ЛЛЛ-Григорьева разложения на простые множители в GF(q) [х, у].

2.4.1 Нахождение неприводимого множителя многочлена / из F[t] [ж] для конечного поля F

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 Категории алгебраической библитеки проекта BAL.

3.7.2 О логическом программировании в языках Cayenne,

Aldor.

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 О расширении языка зависимыми типами

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

Целью работы является

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

2. изучение и программирование методов вычислительной алгебры с применением принципов (1) и с упором на современные высокопроизводительные методы, методы большой степени общности, разработка новых методов;

3. выработка на основе опыта (1) и (2) главных требований к языку программирования математических вычислений.

Применяется только наиболее естественный и действенный категорный подход, впервые опробованный в программировании в проекте Scratchpad (Axiom) [Je], приблизительно, в 1980 году.

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

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

Далее, отметим, что по причинам, объясняемым ниже, мы рассматриваем только функциональные языки программирования.

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

Сначала описывается построение системы вычислений на уровне методов, без привязки к средству программирования. Затем обсуждаются различные средства программирования. Далее описываются основы архитектуры программ Построитель алгебраических областей DoCon (кратко - Построитель) [Ме2, Меб] и библиотеки BAL [МеЗ], разработанных автором в 1995-2001 годах. Эти программы написаны на языке Хаскел (Haskell) [На, HFP],

Объясняются преимущества данной архитектуры, причины выбора расширения языка. Внимательно разбираются те алгоритмические решения, которые не поддерживаются системой типов языка Хаскел. Как выход из затруднения обсуждается подход образцового элемента, примененный в программах Построитель, BAL, и возможность расширение языка зависимыми типами.

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

О результатах и вспомогательной части изложения.

Авторские результаты данной работы выделены на местах, а также перечислены отдельно в Разделе 1.3.

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

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

S : x2 + y2 + z2 = l в пространстве Q3 над полем рациональных чисел Q. Известно, что геометрия такой поверхности задается полем Q(S') рациональных функций на S. Алгебраическая параметризация S может быть получена выбором пары независимых рациональных координат х, у и присоединением третьей координаты z, подчиненной алгебраическому уравнению над Q(x,y). Так что поле Q(S) выражается в виде композиции функторов (конструкторов алгебраических областей)

Pol (кольцо многочленов), Fraction (поле частных), (*)

Residue (кольцо остатков) :

Z = Кольцо целых чисел; Q(x,y) = Fraction Z[x,y]; (**) р = х~2 + у~2 + z~2 - 1; К = Q(х,у) [z]/(р);

Записав это в виде композиции конструкторов Построителя [Ме2] из набора (*), — почти в том же виде, как это записано в формулах (**), — можно далее задавать вычисления в области К с такими выражениями как, например, l+z)*(l-z)/(x~2+y~2) :: К

Система самостоятельно приведет их к каноническому виду, распознает равенство, и так далее, выполняя действия по законам области К.

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

Задание вычислений в такой 'категорной' системе основано на том, что всякий конструктор области (Многочлен, Дробь, Вектор, .) рассматривается как алгоритмический функтор. То есть как функтор, строящий некий стандартный набор алгоритмов действий +,-,*, /, .для области назначения через алгоритмы со-отвествующего (возможно, другого) набора действий областей, данных функтору. Например, выражение "запрограммировать арифметику многочленов" означает выразить действия 0,1,+,-,* для кольца многочленов R[xi,., хп] (Pol R) через такие же действия в кольце R. Причем кольцо R и функции для 0, 1, +, -, * суть переменные (аргументы) для функтора Pol.

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

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

Данный способ построения программ для алгебраических областей близок к обычно применяемому в математических работах способу описания вычислений. Наиболее известные на настоящее время языки и системы, применяющие категорный подход, суть Axiom [Je], Aldor [Al], MuPAD [Ми]. Система Axiom является в настоящее время обширной библиотекой математики для языка программирования Aldor (сейчас еще продолжается переписывание Axiom на Aldor).

Нам не известны какие-либо отечественные разработки этого направления — кроме упоминаемых здесь программ Построитель [Ме2], BAL [МеЗ].

Работу на этом направлении автор начал в 1990-м году. Первым итогом была программа САС [Mel], написанная на безтиповом функциональном языке. Описания алгебраических областей dR строились из других описаний согласно конструкторам (Многочлен, Вектор, .). Далее, описания dR передавались функциям в качестве дополнительного аргумента, и добавлялась система расстановки препроцессором по умолчанию подходящих аргументов dR.

Из этого опыта стало ясно, что желательно использовать языки программирования с более богатыми средствами задания типов. Последние получили к тому времени достаточно работоспособные и доступные воплощения, например, [GH].

Вернемся к рассмотрению программ Построитель, Aldor - Axiom, MuPAD.

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

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

Вот некоторые сведения об этих средствах.

Отметим, что системы Aldor - Axiom и MuPAD не полностью доступны: не предоставляют пользователю исходный код, и следовательно, возможности самостоятельно исправлять эту программу. Axiom даже является полностью коммерческой системой. Такое положение мало отвечает потребностям научного сообщества.

Далее, Построитель применяет чисто функциональное программирование и 'ленивый' способ вычисления. Aldor (Axiom), MuPAD не являются функциональными системами и применяют только 'прямые' вычисления.

Aldor [А1] есть язык программирования похожий на ML, отчасти — на Haskell, но расширенный возможностью действовать с (абстрактными) типами данных (представляющих математические области) как с обычными значениями. Языковым средством для этого являются зависимые типы (dependent types) — типы, зависящие от значения. Притом допускается откладывать распознавание некоторых типов на этап выполнения программы.

Так, например, это позволяет более естественно запрограммировать область вычетов Ъ/(т) с динамически меняющимся т (Подраздел 4.2).

В этом смысле, — смысле программной архитектуры, — Построитель есть библиотека, случаев (instances) для алгебраических конструкторов языка Haskell. Причем отсутствие в языке зависимых типов восполнено применением подхода образцового элемента (Подраздел 4.1.1 пункт (sa)). Подраздел 4.1.4 объясняет трудности, встречающиеся на этом пути.

Перечислим коротко главные отличия программы Построитель от системы Aldor - Axiom.

Построитель

• функционален и вычисляет 'лениво', применяет другую систему программирования (Haskell),

• применяет подход образцового элемента как замену языкового средства зависимых типов,

• чаще, чем Aldor, возлагает распознавание случаев категорий на прикладную программу недостаток, возникающий изза предыдущего пункта),

• распространяется свободно вместе с исходным текстом и опирается на свободно распространяемую с исходным текстом реализацию языка Хаскел.

Что касается общего математического подхода, примененного во всех этих системах, то он более-менее очевиден. Подробности же математических методов (Раздел 2) относятся не к основаниям системы, а к научной библиотеке, каковая особенно велика по охвату в системе Axiom.

Раз существует весьма естественно построенное средство математических вычислений Aldor - Axiom, то чем вызвана разработка Построителя?

Она вызвана следующими причинами.

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

• Система Aldor - Axiom слишком 'закрыта'. Очень недавно этот недостаток был немного исправлен за счет выделения языка Aldor. К тому же до этого события трудно было даже понять, где в системе Axiom язык программирования, а где алгебраическая библиотека.

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

• Язык Haskell имеет несколько свободных реализаций. Aldor имеет одну реализацию, не проверенной пользователями надежности; библиотека Axiom в настоящее время еще переписывается на Aldor. Разработчики системы Aldor объявили о намерении сделать исполняемый код свободно распространяемым.

Помимо Построителя, некоторые опыты использования Хаскела в программировании алгебры, описаны в статьях [Fo, Ка].

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

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

5 Заключение

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

1. О методах вычисления.

В основном, они взяты из классической вычислительной алгебры (смотри Подразделы 2.1, 2.2). От автора добавлены

1) метод gx-действий (Подраздел 2.3),

2) усиление способа JIJIJI-Григорьева разложения на простые множители многочлена двух переменных над конечным полем (Подраздел 2.4). gx-действия описывают кольцо с разрешимыми линейными уравнениями с некоторыми дополнительными условиями каноничности. Эти условия позволяют задать арифметику и канонические формы в областях довольно общей природы и в их областях остатков.

2. О выразительности программирования.

Рассматривая языки и системы Aldor-Axiom, Cayenne, Maude, Haskell - Построитель, мы выявили следующие требования к языку программирования математики и объяснили их важность (Раздел 3):

1) функциональность, (2) богатые средства задания типов,

3) категорность, (4) поддержка полиморфизма,

5) гибкость стратегии вычисления,

6) поддержка стандартных отображений областей,

7) выразимость свойств значений,

8) выразимость области, зависящей от значения.

Каждое из названных средств далеко от полного удовлетворения приведенным требованиям. Выставим данным средствам оценки уровней 0, 1, 2, 3, 4 за каждое из требований 1—8. Получим, примерно, следующую таблицу:

12345678

Aldor-Axiom 0 4 4 4 0 3? 1 4

Haskell-Построитель 3 3 3 3 1 2 2 3

Maude 4 2 2 2? 4 0? 4 0?

Cayenne 3 4 3 3 1 0 2 3

Знак '?' означает недостаточную осведомленность автора о данной черте языка. Также здесь не учитываем недостатки воплощений этих языков программирования.

Опыт применения языка Haskell в программах Построитель [Ме2], BAL [МеЗ] дал следующие итоги.

Требование (6) наполовину поддерживается за счет введения категории Cast (Подраздел 3.6).

Требование (7) наполовину поддерживается за счет а) подхода образцового элемента (ОЭ), base-действий (Подраздел 4.1.1), б) введения библиотеки классических категорий алгебры (Подраздел 3.7.1). Требование (8) наполовину поддерживается за счет подхода ОЭ

Подраздел 4.1.1), который позволил воплотить на языке Haskell в программах

Ме2, МеЗ] расширенные возможности задания алгебраических категорий и областей.

Причина всех этих оценок 'наполовину' есть та, что эти решения поддерживаются на уровне прикладной системы (Построитель) и почти не поддерживаются самим языком Haskell (компилятором).

3. О развитии средств программирования математики.

Нам представляется, что развитие языка программирования в сторону зависимых типов, — как в языках Aldor, Cayenne, — и в сторону привлечения явных наборов равенств, переписывания термов (как в Maude) [НО, GM, Md], даст средство программирования математики близкое к требуемому.

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

4. О производительности.

Проект Построитель можно рассматривать и как проверку практической применимости чисто функционального программирования и 'ленивого' способа вычисления. Построитель воплощает весьма богатый набор методов, и притом достигает хорошей средней производительности (смотри [Ме2]: Руководство, Раздел о сравнении производительности). Он отрицает распространенное мнение о том, что функциональное программирование и 'ленивое' вычисление трудно применимы на практике.

1. Al. S. М. Watt et al. Aldor Co7npiler User Guide.

2. M Thomas J. Watson Research Center, <http://www.aldor.org>

3. Au. L. Augustsson. Cayenne — a language with dependent types.

4. Proceedings of International Conference on Functional Programming (ICFP'98). ACM Press, September 1998.

5. AV. В. M. Антимиров, А. А. Воронков, А. И. Дегтярев, M. В. Захарьящев, В. С. Проценко. Математическая логика в программированиии. Сборник статей. Москва, Мир, 1991.

6. Ва. X. Барендрегт. Лямбда-исчисление: его синтаксис и семантика. Перевод с английского. МИР. 1985.

7. Be. Е. R. Berlekamp. Factoring polynomials over large finite fields. Mathematics of Computation, Vol.24 (1970), 713-735.1. Bu. Б. Бухбергер.

8. Базисы Гребнера. Алгоритмический метод в теории полиномиальных идеалов.

9. В сборнике статей Компьютерная алгебра под редакцией Б.Бухбергера и др., стр 331-372. Москва, МИР, 1986.

10. BL. Б. Бухбергер, Р. Лоос. Упрощение алгебраических выражений.

11. В сборнике статей Компьютерная алгебра под редакцией Б.Бухбергера и др., стр. 23-65. Москва, МИР, 1986.

12. CG. A. L. Chistov, D. Yu. Grigoryev.

13. Polynomial-time factoring of the multivariable polynomials over a global field. Preprint E-5-82 of the Leningrad department of Steklov Mathematical Institute LOMI, USSR, 1982.

14. J. H. Davenport, В. M. Trager.

15. Scratchpad's View о j Algebra I: Basic Commutative Algebra. Lecture Notes in Computer Science, Vol. 429, pp.40-54 (1990).

16. А. Филд, П. Харрисон. Функциональное программирование. Перевод с английского. Москва, МИР, 1993.

17. J. Fokker. Explaining algebraic theory with functional programs.

18. Proceedings of FPLE'95, LNCS 1022, pp. 139-158.

19. Смотри также Интернет: <http://www.cs.ruu.nl/people/jeroen>1. Д. Ю. Григорьев.

20. Разложение многочленов над конечным полем и решение систем алгебраических уравнений.

21. Записки научных семинаров ЛОМИ АН СССР (1984), том 137, стр. 20-79. Glasgow Haskell Compiler. Смотри Интернет: <http://haskell.org>. J. von zur Gathen, E. Kaltofen.

22. Polynomial-Time Factorization of Multivariate Polynomials over Finite Fields. "Appears in Mathematics of Computation, Vol.45 pp.251-261"

23. Дж. А. Гоген, Ж. Мезегер. Модели и равенство в логическом программировании.

24. Перевод с английского, в сборнике статей "Математическая логика в про-граммированиии". Москва, Мир, 1991.

25. Haskell 98: A Non-strict, Purely Functional Language. Report of February 1999.

26. Смотри Интернет: <http://www.haskell.org>

27. R. Hinze, S. P. Jones. Derivable type classes.

28. В Proceedings of the Haskell Workshop, Montreal, 2000.

29. Также смотри Интернет: <http://www.dcs.gla.ac.uk/~simonpj>

30. HFP. P. Hudak, J. Fasel, J. Peterson. A gentle introduction to Haskell. Technical report, YALEU/DCS/RR-901, Yale University. 1996. Смотри Интернет: <http://haskell.org/tutorial>

31. НО. Ж. Юэ, Д. Оппен. Равенства и правила переписывания. Обзор.

32. Перевод с английского, в сборнике статей "Математическая логика в про-граммированиии", Москва, Мир, 1991.

33. Je. R. D. Jenks, R. S. Sutor, et al.

34. Axiom, the Scientific Computation System. Springer-Verlag, New York-Heidelberg-Berlin (1992).

35. JJM. S. P. Jones, M. Jones, E. Meijer.

36. Type classes: an exploration of the design space. 1997. In Proceedings of the Haskell Workshop.

37. Смотри также Интернет: <http://www.dcs.gla.ac.uk/~simonpj/>1. Jo. S. L. P. Jones et al.1.plementation of Functional Programming Languages. Prentice Hall. 1987.1. Ka. J. Karczmarczuk.

38. Functional Programming and Mathematical Objects. Proceedings of FPLE'95, Nijmegen 1995; Springer LNCS 1022.

39. Kn. Д. E. Кнут. Искусство программирования для ЭВМ. Тома 1, 2, 3. Мир, Москва, 1977.1.. А. К. Lenstra.

40. Factoring Multivariate Polynomials over Finite Fields.

41. Journal of Computer and System Sciences, Volum 30 (1985), pp.235-248.

42. L. A. K. Lenstra, H. W. Jr. Lenstra, L. Lovasz.

43. Factoring polynomials with rational coefficients. Math. Ann. Volum 261 (1982), pp.515-534.

44. Ma. И. Г. Макдональд. Симметрические функции и многочлены Холла. Перевод с английского. Москва, "Мир", 1985.1. Md. М. Clavel & al.

45. Maude: Specification and Programming in Rewriting Logic. Руководство по логической системе программирования. 1999. Смотри Интернет: <http: //maude. csl. sri . com>1. Mel. S. D. Meshveliani.

46. The Algebraic Constructor CAC: Computing in Construction-defined Domains. Lecture Notes in Computer Science, 722, 1993.1. Me2. S. D. Mechveliani.

47. DoCon, the Algebraic Domain Constructor. Manual and program. Переславль-Залесский, 1998-2001. Рукопись руководства и исходная программа. Смотри Интернет:http://www.botik.ru:/pub/local/Mechveliani/docon/>

48. МеЗ. S. D. Mechveliani. BAL basic algebra library for Haskell. Рукопись статьи и исходная программа. Переславль-Залесский, 2000-2001. Смотри Интернет: <http://www.botik.ru/pub/local/Mechveliani/basAlgPropos/>1. Ме4. S. D. Meshveliani.

49. Algebraic Domain Constructor: K-rings plus pure functional programming. In Proceedings of International Workshop "New Computer Technologies in Control Systems", 1995, Pereslavl-Zalessky, Russia.

50. Me5. С. Д. Мешвелиани. Оценка сложности способа ЛЛЛ Григорьева факторизации в GF(q)x,y],

51. Принято к печати в журнал Фундаментальная и Прикладная Математика, Мех-мат МГУ, Москва (2001). Смотри также Интернет: <http://www.math.msu.su/~fpm/>.1. Меб. S. D. Mechveliani.

52. Computer algebra with Haskell: applying functional-categorial-'lazy' programming .

53. Proceedings of International Workshop CAAP-200I, Dubna, Russia.

54. Mi. M. Mignotte. Mathematiques pour le caclul formel. Presses Universitaires de France, 1989.

55. Перевод на английский: Mathematics for computer algebra. Springer Verlag, 1992.

56. Mo. H. M. Mceller. On the Construction of Groebner Bases Using Syzygies. Journal of Symbolic Computation (1988), Vol. 6.

57. MoM. H. M. Mceller, F. Mora.

58. New Constructive Methods in Classical Ideal Theory. Journal of Algebra, v 100, pp.138-178 (1986)

59. Mu. MuPAD the Multi Processing Algebra Data Tool программная система компьютерной алгебры. Смотри Интернет: <http://www.mupad.de>, <ftp.mupad.de>, <http://math-www.uni-paderborn.de/MuPAD/>

60. NQ. П. Ноден, К. Китте. Алгебраическая Алгоритмика. Перевод с французского. МИР, 1999.

61. Wa. Б. Л. ван дер Варден. Алгебра. Москва, Наука, 1979.

62. Yu. D. Y. Y. Yun. The Hensel Lemma in Algebraic Manipulation. MIT, Cambridge, Mass., 1974; Garland, New York, 1980