Этюды для программистов

20. Квадратный трехчлен, или Пакет Для Алгебраических Вычислений

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

Объекты, с которыми мы будем работать, — это рациональные функции. Их можно определить рекурсивно.

Пусть c — любая вещественная константа. Тогда c — рациональная функция.

Пусть x — любая переменная. Тогда x — рациональная функция.

Пусть р и q — любые рациональные функции. Тогда p + q, p − q, −p, pq, p/q и (p) все суть рациональные функции. При делении рациональных функций производится упрощение, так чтобы остался только один знак деления. Правила этого упрощения хорошо знакомы школьникам, изучающим алгебру. Пусть p — любая рациональная функция, а c — целочисленная константа. Тогда p^c — рациональная функция. Если с отрицательна, образуйте рациональную функцию 1/p|c| и упростите деление как выше.

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

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

Рациональные функции в качестве исходных данных будут похожи на выражения в стандартном языке программирования. Константы могут изображаться любой последовательностью десятичных цифр с десятичной точкой; если десятичная точка отсутствует, то константа автоматически будет целочисленной. В силу правил образования рациональных функций константы не имеют знака, за исключением констант в показателе степени. Переменная выглядит как идентификатор и может быть любой цепочкой из больших и малых литер алфавита. Из-за ограничений на выбор литер в ЭВМ умножение будет изображаться знаком *, а возведение в степень — знаком ↑. Так, рациональную функцию

2xy + (х² + у²)³

можно записать как

2 * X * Y + (X ↑ 2 + Y ↑ 2) ↑ 3

Некоторые другие имена, в частности имена функций, также будут идентификаторами.

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

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

Установить Р равным z*x↑2 + 3.5; Установить fpt равным Р;

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

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

Установить f равным разности р минус q; Образовать алгебраическую разность р и q и записать полученное значение под именем f.

Установить f равным произведению р и q; Образовать алгебраическое произведение р и q и записать результат под именем f.

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

Установить f равным р в степени с; Рациональная функция р возводится в степень с, и результат записывается под именем f. Показатель степени с должен быть целым числом или именем функции с постоянным значением; если с отрицательно, результатом будет 1/р^|с|.

Установить f равным р с заменой х на q; Заменить каждое вхождение переменной х в р на q и записать полученное значение под именем f. Отметим, что в результате подстановки переменная х может снова возникнуть в f, но ее не следует вновь заменять на q.

Установить f равным производной р по х; Вычислить производную dp/dx и записать полученное значение в f. Конечно, идентификатор х должен быть переменной или именем функции, состоящей из одной переменной.

Напечатать р; Напечатать рациональную функцию р в удобном для чтения виде.

Конец; Завершение последовательности команд.

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

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

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

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

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

Инструментовка. Это еще одна задача, требующая списков или деревьев и рекурсивных процедур для их обработки. Для таких задач был создан Лисп, но наравне с ним подойдут и многие другие языки для работы со списками. Снобол несколько слабее по части внутренней обработки данных, но чрезвычайно мощные возможности по анализу вводимой и подготовке выводимой информации делают Снобол конкурентоспособным кандидатом. На самом деле здесь подойдет любой язык типа Паскаля или PL/I, так или иначе приспособленный для работы с текстами, имеющий определяемые структуры данных и рекурсивные процедуры.

Длительность исполнения. Одному исполнителю на 3 недели.

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

Для многих важных математических операций не существует методов, которые позволяли бы всегда вычислять результат в символьном виде. Важное место среди них занимает интегрирование. Хотя любая рациональная функция имеет неопределенный интеграл, простой пример функции 1/х (неопределенный интеграл от нее — ln x) показывает, что нам не надо далеко ходить за функциями, нарушающими границы замкнутого пространства рациональных функций. Расширение пространства функций путем добавления показательных функций и логарифмов, как предложено выше, лишь обостряет проблему. Не решает проблемы даже использование определенного интеграла, поскольку результат определенного интегрирования может и не быть константой, если подинтегральное выражение содержит переменные, отличные от переменной интегрирования, или если пределы интегрирования не константы. Символьные интеграторы были одними из первых программ, написанных для демонстрации «интеллектуального» поведения ЭВМ. Если вы будете работать над предлагаемой задачей в два или три раза дольше, то сможете создать примитивный интегратор.

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

Мозес (Moses J.). Algebraic Simplification: A Guide for the Perplexed, CACM, 14, 8, pp. 527–537, 1971.

Мозес (Moses J.). Symbolic Integration: The Stormy Decade, CACM, 14, 8, pp. 548–560, 1971.

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