Программные продукты и системы

В Институте проблем кибернетики Российской Академии наук проводятся работы по созданию системы компьютерной алгебры, работающей в составе высокопроизводительной ЭВМ. Создаваемая система задумана как рабочее место математика для выполнения всех необходимых работ без обращения к языку программирования.

Одной из основных задач такого пользователя является ввод и преобразование алгебраических формул, относящихся к области его интересов. Это могут быть, например, выражения числовые, тригонометрические, из теории групп, булевские, в определенном базисе и т.д. Предусмотреть все возможные интересы и запросы такого пользователя практически невозможно. Многие системы предоставляют возможность работать с некоторыми фиксированными классами объектов, а если пользователю нужны другие объекты, то он вынужден обращаться к встроенному в систему языку программирования и писать на нем специальные функции (RLisp в системе REDUCE). Кроме того, недостаточно точно установленный класс объектов, с которыми работает пользователь, делает затруднительным контроль системой входных ошибок. Например, пользователь может работать в кольце, где имеются только операции + • и *. Введенная в формулу другая операция (например деления) должна определяться как ошибочная. Во многих системах компьютерной алгебры пользователь может преобразовать входную' формулу только целиком. Часто, однако, возникает необходимость выделить некоторую подформулу и применить к ней определенную, заданную пользователем последовательность преобразований. Большие неудобства доставляет пользователям некоторых довольно хороших систем компьютерной алгебры слабый пользовательский интерфейс.

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

Ниже следует более подробное описание основных компонентов системы "Алгебра".

НАСТРОЙКА СИСТЕМЫ

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

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

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

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

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

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

СЕАНС РАБОТЫ

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

<алгебр, формула > или

<имя переменной > = < алгебр, формула >.

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

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

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

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

ЯЗЫК ЗАПИСИ СИСТЕМЫ ПРЕОБРАЗОВАНИЙ

Каждая система преобразований представляет собой последовательность преобразований вида

< левая часть > = < правая часть >.

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

@р - любая переменная;

@n - любой носитель (число);

@е - любое алгебраическое выражение;

@f(...) - любая префиксная функция;

@s - любой список алгебраических выражений.

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

diff(@el + @e2, @р) = diff(@el, @р) + diff(@e2, @p).

Алгебраические формулы, включающие такие конструкции, называются общими формулами. Все имена, начинающиеся с буквы, являются конкретными именами (переменных, префиксных функций и т.д.). Имена всех инфиксных функций состоят только из определенных в системе символов (например +, &, *, ~ и т.д.) и могут иметь любую длину. Имена постфиксных функций состоят только из одного символа, который должен содержаться во множестве определенных в системе постфиксных символов (например !). Элемент формулы, начинающийся с цифры, считается элементом носителя алгебры.

АЛГОРИТМ ПРИМЕНЕНИЯ СИСТЕМЫ ПРЕОБРАЗОВАНИЙ К АЛГЕБРАИЧЕСКОЙ ФОРМУЛЕ

Введенная пользователем входная алгебраическая формула представляется во внутренней структуре в виде дерева, во внутренних узлах которого записаны имена операций (функций), а в листьях - имена переменных или элементы носителя (числа). Аналогично представляется и каждое отдельное 'преобразование, причем в деревьях преобразований листьями будут также и общие конструкции. Каждое дерево отсортировывается системой в начале работы с ним, что поддерживается после применения каждого преобразования. Тем самым снимается проблема неоднозначности представления алгебраической формулы в виде дерева и облегчается поиск применимого преобразования. Деревья преобразований находятся в определенном порядке и хранятся связанными в виде списка. Система преобразований применяется к дереву, начиная с его левого нижнего угла. Рассматриваемому узлу дерева естественным образом соответствует поддерево, исходящее из этого узла. Начиная с первого преобразования системы ищется такое, левая часть которого соответствовала бы рассматриваемому поддереву. Соответствие понимается таким образом, что конкретные объекты в обоих поддеревьях должны быть одинаковыми, а общим конструкциям можно поставить в соответствие конкретные (общей переменной - конкретную переменную и т.д.). Если такое преобразование найдено, то рассматриваемое поддерево формулы заменяется на правую часть этого преобразования с учетом установленных соответствий, т.е. все общие конструкции правой части заменяются на соответствующие конкретные. После этого для рассматриваемого узла система вновь сначала ищет применимое преобразование. Узел называется неприменимым, если к нему не применимо ни одно преобразование. После этого система переходит к рассмотрению следующего узла. К "отцу" в дереве система переходит тогда, когда все его "сыновья" неприменимы. Эта стратегия соответствует так называемым "линейным" преобразованиям, когда в алгоритме применения нет ветвлений.

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

 syst (diff(ro, t) + div(ro*V),

p*df(V) + p - Vp(Rot(B), B) – nu1 * V,

diff(B, t) - Rot(Vp(V, B)) +

nu2*Rot(nu*Rot(B)),

diff(p, t) + div(p*V) + (g-l)*p*div(V)),

где V, В — вектора; Vp означает векторное произведение и т.д.

Поиски решений этой системы осуществляются в виде формальных рядов Фурье по Cos или по Sin. Эти ряды подставляются в систему, выполняются все необходимые преобразования, т.е. раскрытие ротора, дивергенции и т.д. до тех пор, пока левые части уравнений также не будут иметь вид рядов Фурье. Затем коэффициенты этих рядов приравниваются к нулю, при этом получается большая система уравнений, которую затем обсчитывают на суперЭВМ. Ранее эта трудоемкая рутинная работа выполнялась вручную и требовала внимательности и большого количества времени. С помощью системы "Алгебра" ее решение занимает полторы минуты.

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

@el V @е2 = @el & @е2 + @el + @e2,

~(@е) = @е + 1,

@el & (@е2 + @еЗ) = @el & @е2 +

@el & @еЗ,

@е & @е = @е,

@е + @е = 0 и т.д.

Такая настройка системы занимает мало времени и позволит не только преобразовывать формулы, но и упрощать их. Теперь, вводя любую булевскую формулу в базисе { &, V, }, пользователь будет в качестве выхода получать ее вид в базисе { &, + }.

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

ИСПОЛЬЗОВАНИЕ ХЕШИРОВАНИЯ В СИСТЕМЕ "АЛГЕБРА"

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

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

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

БИБЛИОТЕКА АРИФМЕТИЧЕСКИХ ФУНКЦИЙ

Если в алгебраической формуле встречаются операции +, -, * или / над числами, то система автоматически вычисляет результат этих операций. Это обеспечивается библиотекой арифметических функций. Как уже говорилось, система допускает классы целых, рациональных, действительных и комплексных чисел произвольной длины. В основе работы с длинными числами лежит представление целого числа в системе счисления по основанию b = 2~n, где п - разрядность ЭВМ. Число моделируется в виде списка разрядов такого представления. Старший бит каждого разряда содержит знак числа. Количество таких разрядов ограничено лишь памятью ЭВМ - в этом смысле можно считать, что число имеет неограниченную точность. Рациональное число моделируется парой целых чисел произвольной длины, соответствующих числителю и знаменателю, и представляется парой указателей на списки разрядов этих чисел. Действительное число во внутренней структуре хранится в виде длинного целого числа, представляющего мантиссу и порядок числа. Комплексное число имеет структуру дерева, в котором действительная и мнимая части могут быть целыми, рациональными или действительными числами.

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

Наши представления и алгоритмы работы с действительными числами более просты, чем алгоритмы работы с нормализованными числами. В случае нормализованных положительных чисел [8] надо следить за тем, чтобы результат операции находился в пределах от Ь*(-1) до 1, и производить нормализацию, если это не так. Нормализацию" обычно производят путем побитового сдвига, что может привести к потере правильного знака числа и другим ошибкам. У нас же этих проблем не возникает, так как все операции производятся над целыми числами и затем вычисляется правильный порядок результата. Так как порядок у нас также является целым числом произвольной длины, то не возникает и проблемы исчезновения порядка, которую Кнут [8] приводит как одну из возможных ловушек при работе с длинными действительными числами.

ИНТЕРФЕЙС СИСТЕМЫ "АЛГЕБРА"

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

ПОДСИСТЕМА МЕНЮ И HELP

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

- передвигаться и просматривать уже созданные дерево меню и Help;

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

- изменить (откорректировать) имя, записанное в окне;

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

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

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

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

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

РЕДАКТОР

Разработанный авторами редактор не привязан жестко к системе "Алгебра" и может быть включен так же, как система меню, в любые другие системы. Он спроектирован как редактор иерархической информации, которую можно представить в виде дерева. Примером такой информации являются алгебраические формулы. Например, формуле Sin(alpha + diff(ln(x), x)) соответствует следующее дерево (см. рисунок).

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

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

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

1-е поле с 5-ой по 10-ю позиции

2-е поле с 17 -ой по 40-ю позиции

3-е поле с 56-ой по 78-ю позиции.

Тогда при работе редактору будут доступны только эти поля каждой строки. Если курсор находится на 10-ой позиции и пользователь нажимает клавишу "сдвиг курсора вправо", то курсор перейдет не на 11-ую, а на 17-ую позицию.

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

ДРУГИЕ ОБРАБАТЫВАЮЩИЕ ПРОГРАММЫ

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

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

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

хК' V ~хК" = хК' V ~хК" V К'К"

К' V К" К" = К'.

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

Список литературы

1.  Михаилюк М.В. Арифметика действительных чисел // Тез. докл. Всесоюэ. совещ.: Алгоритмы и программы небесной механики. - Л.» 1989.

2.                Михайлюк М.В.» Петрова И.Н. Арифметика рациональных чисел // Тез. докл. Всесоюэ. конф.: Аналитические преобразования на ЭВМ в автоматизации научно-исследовательских работ. - Вильнюс, 1990.

3.                Михайлюк М.В., Петрова И.П., Сотников A.M., Трушина А.А. Система преобразования формул "Алгебра" // Тез. докл. Всерос. совещ.: Компьютерные методы небесной механики. - С.-П., 1992.

4.       Михайлюк М.В., Петрова И.Н., Трушина А.А. О некоторых компонентах системы компьютерной алгебры // Программные продукты н системы. - 1992. - N 1. -С. 51-53.

5.                Михайлюк М.В., Сотников А.Н. Об одном подходе к построению интегрируемой системы компьютерной алгебры // Тез. докл. Всесоюз. совещ.: Компьютерные методы небесной механики. - С.-П., 1991.

6.                Михайлюк М.В., Седракян Н.Г. Минимизация дизъюнктивных нормальных форм в символьном виде // Сб.: Программно-аппаратные средства и матобеспечение вычислительных систем. - М.: МГУ, 1990.

7.                Михайлюк М.В., Трушина А.А. Инструментальное средство для построения меню: система MENU // Сб.: Проблемы разработки программно-технического обеспечения САПР. - Тверь, 1991.

8.                Кнут Д. Искусство программирования. - М.: Мир, 1977. -Т. 2.

9.                Компьютерная алгебра. Символьные и алгебраические вычисления / Под ред. Б. Бухбергера. - М.: Мир, 1986.

10.                   Mikhajliuk M.V., Sotnikov A.N., Truschina A.A. On the System // Сб. аннот. IV Междунар. совещ. по аналитич. вычислениям на ЭВМ в физич. исслед. - Дубна, 1990.

11.                   Mikhajliuk M.V., Sotnikov A.N., Truschina А.А. On the computer algebra system working as a part of powerful computer system, Proc. of the IV International Conference on Computer algebra in Physical Research, Dubna, USSR, May 1990.