Рекомендации исполнителю. Чтение программой команд и рациональных функций требует привлечения некоторых простых методов компиляции, в частности лексического анализа для распознавания символов и синтаксического анализа для построения внутреннего представления. Необходимые сведения содержатся в литературе, указанной в других главах. В процессе выполнения программы вам придется поддерживать расширяющуюся таблицу имен и значений; для этого также имеется простой метод. Самая трудная часть реализации — это выбор внутреннего представления для рациональных функций. Они, несомненно, должны представляться с помощью некоторого варианта списочной или древовидной структуры, но какого именно?
Одним из возможных представлений является стандартное арифметическое дерево, содержащее переменные и константы в листьях, а операции — во внутренних узлах. Такая форма представления особенно подходит для подстановки и алгебраических операций, но для печати она слишком беспорядочна. Другая возможность — дерево, содержащее на верхнем уровне числитель и знаменатель, на следующем уровне — одночлены и на еще более низком уровне — сомножители. Такое дерево будет легко напечатать, но с ним трудно работать. Что бы вы ни выбрали, не забывайте копировать структуры данных при выполнении подстановки, иначе более позднее изменение в подставляемой функции повлияет также и на функцию, в которую она подставлялась.
Инструментовка. Это еще одна задача, требующая списков или деревьев и рекурсивных процедур для их обработки. Для таких задач был создан Лисп, но наравне с ним подойдут и многие другие языки для работы со списками. Снобол несколько слабее по части внутренней обработки данных, но чрезвычайно мощные возможности по анализу вводимой и подготовке выводимой информации делают Снобол конкурентоспособным кандидатом. На самом деле здесь подойдет любой язык типа Паскаля или PL/I, так или иначе приспособленный для работы с текстами, имеющий определяемые структуры данных и рекурсивные процедуры.
Длительность исполнения. Одному исполнителю на 3 недели.
Развитие темы. В настоящее время широко используются многие системы алгебраических преобразований. Как правило, в их основе лежат функции, подобные описанным выше. Дальнейшее развитие происходит по трем направлениям: введение новых типов данных, новых операций и эвристических процедур, предназначенных для выполнения действий с нечетко определенным результатом. Новые типы данных взаимосвязаны с новыми операциями. Можно, например, добавить к рациональным функциям тригонометрические, показательные функции и логарифмы. В таком случае надо будет изменить операцию возведения в степень, чтобы она допускала любой операнд в качестве показателя степени, кроме того, понадобится операция логарифмирования, в которой будет указываться основание логарифмов и логарифмируемая функция. Отметим, что при введении новых типов данных и операций следует убедиться в замкнутости пространства функций, которые могут быть порождены произвольной последовательностью операций. Замкнутость означает, что всякую функцию, которую можно породить, можно также в принципе записать в команде Установить.
Для многих важных математических операций не существует методов, которые позволяли бы всегда вычислять результат в символьном виде. Важное место среди них занимает интегрирование. Хотя любая рациональная функция имеет неопределенный интеграл, простой пример функции 1/х (неопределенный интеграл от нее — ln x) показывает, что нам не надо далеко ходить за функциями, нарушающими границы замкнутого пространства рациональных функций. Расширение пространства функций путем добавления показательных функций и логарифмов, как предложено выше, лишь обостряет проблему. Не решает проблемы даже использование определенного интеграла, поскольку результат определенного интегрирования может и не быть константой, если подинтегральное выражение содержит переменные, отличные от переменной интегрирования, или если пределы интегрирования не константы. Символьные интеграторы были одними из первых программ, написанных для демонстрации «интеллектуального» поведения ЭВМ. Если вы будете работать над предлагаемой задачей в два или три раза дольше, то сможете создать примитивный интегратор.
Введение новых функций создает еще одну проблему. Для более сложных функций, которые теперь можно построить, не существует стандартного формата вызова. Кроме того, выбор применяемых законов упрощения становится нелегким делом. Поскольку теперь применимо гораздо больше алгебраических законов — тригонометрические тождества, законы, связывающие показательные и логарифмические функции, законы о константах, — может случиться, что программа будет тратить большую часть времени на упрощение внутреннего представления выражений. Упрощение с целью облегчить человеку понимание результатов — очень важная и сложная тема; от программиста требуется немалое искусство, чтобы успешно реализовать упрощение.