5. Структурные скобки. Дифференцирование
B этом параграфе мы рассмотрим несколько более сложных примеров. Первый пример связан с превращением символов "(" и ")" в структурные скобки, так называемое "спаривание скобок". Во втором примере мы рассматриваем вопрос о дифференцировании на языке рефал произвольных функций математического анализа.
Структурные скобки Рассмотрим следующие объектные выражения:
'(a+b)*(c+d)'
('a+b') '*' ('c+d')
Они соответствуют одной и той же формуле из алгебры - ( а + b ) ( c + d ), но способы записи этой формулы совершенно различные. В первом случае мы записали эту формулу как последовательность из 11 простых символов: "(", "a", "+",..., "d", ")". Bo втором случае мы использовали две пары структурных скобок. В первой скобке записаны три символа "a" , "+" , "b", во второй - три символа "c" , "+" , "d" , между скобками стоит один символ "*".
Второе объектное выражение отождествляется с типовым выражением
( e.1 ) s.a ( e.2 )
но первое объектное выражение с этим типовым выражением не отождествится.
Функция CARD (см.п.2, п.6) помещает в поле зрения символы очередной введенной строки. Если мы наберем первое выражение, то после вычисления функции <CARD > в поле зрения будем иметь объектное выражение, состоящее из 11 символов. Второе выражение вообще невозможно подготовить для функции Card.
При обработке же алгебраических формул на языке рефал удобно использовать структурные скобки.
Таким образом, мы приходим к задаче превращения символов "(", ")" в структурные скобки.
Отметим, что структурные скобки всегда присутствуют парами - каждой левой структурной скобке соответствует правая, и наоборот. Символ "(" равноправен среди остальных простых символов, поэтому в объектных выражениях он может присутствовать и без символа ")".
Если мы будем просматривать последовательность символов слева направо, то нам будут по отдельности попадаться то символы "(", то символы ")". Для того, чтобы вставить пару структурных скобок, мы должны для каждого символа "левая скобка" найти соответствующий ему символ "правая скобка" и одновременно заменить их на структурные скобки. Такой процесс описывается предложением
e.1 '(' e.2 ')' e.3 = e.1 ( e.2 ) e.3
Обратимся к примеру. Пусть скобочная структура имеет вид:
( ( ) ( ) ) ( )
Ясно, что первая правая скобка соответствует последней левой скобке, лежащей левее этой правой скобки. После замены найденных скобок-символов на структурные скобки опять ищем первый символ ")" и т.д.
Поэтому можно было бы предложить такой алгоритм: двигаемся вправо до символа ")", затем влево до символа "(", превращаем найденные символы "(" и ")" в структурные скобки. Далее повторяем эту процедуру, пока не кончатся символы "(", ")".
Приведенный алгоритм обладает тем недостатком, что требуются многократные просмотры всего выражения. Оказывается, что задачу спаривания скобок можно решить за один просмотр последовательности символов!
Ведь двигаясь вправо до первого символа ")" мы уже находим все символы "(", лежащие на пути. Надо их только не потерять, т.е. как-то отметить, чтобы сразу можно было найти, когда они понадобятся.
Как можно отделить одну часть последовательности от другой? Опять на помощь приходит понятие "сумки" из п. 4. Будем каждый символ "(" отмечать сумкой. Поскольку левых скобок может встретиться несколько, то и сумок потребуется несколько.
Обозначим функцию спаривания скобок через Spar. Тогда функция Spar записывается следующими предложениями (использование функции можно посмотреть в программе diff.ref ).
Spar { e.1 = <Spar1 ('*') e.1 >; }
Spar1 {
(e.1) '(' e.3 = <Spar1 ((e.1)) e.3 >;
((e.1) e.2) ')' e.3 = <Spar1 (e.1 (e.2)) e.3 >;
('*'e.1) ')' e.3 = 'error' e.1 ')' e.3;
(e.1) s.A e.3 = <Spar1 (e.1 s.A) e.3 >;
('*'e.1) = e.1;
((e.1) e.2) = 'error' e.1 '(' e.2;
}
Вопросы к программе Spar:.
1. Почему при обращении к функции Spar1 в сумку поставлен символ "*"?
2. Какое предложение обнаруживает случай непарной левой скобки?
3. Какое предложение обнаруживает случай непарной правой скобки?
4. Какое предложение заканчивает вычисление функции, если все скобки сбалансированы?
5. Написать работу функции Spar по шагам для первого объектного выражения в начале параграфа.
Задача. Если нам надо в последовательности символов лишь убедиться в правильности расстановки символов "(" и ")", то существует более простой алгоритм. Скобки расставлены правильно, если (а) количество левых скобок равно количеству правых, и (б) при просмотре слева направо в каждый момент количество правых скобок не больше количества левых скобок.
Написать функцию, которая применяется к последовательности символов, и результат работы которой равен "1", если скобки расставлены правильно, и равен "0" в противном случае.
Задача. Написать функцию расспаривания скобок, т.е. превращения структурных скобок в символы "(" и ")" . (ответ можно посмотреть в программе gener.ref)
Дифференцирование
Задача дифференцирования функций математического анализа относится к числу символьных преобразований формул, поэтому язык рефал очень хорошо справляется с этой задачей. Предположим, что формат обращения к функции дифференцирования следующий:
<Diff (e.t) e.Function >
где e.t - имя переменной, по которой происходит дифференцирование, e.Function - дифференцируемое выражение.
Сформулируем ограничения, которым должна удовлетворять формула e.Function.
1. Формула записывается по правилам записи арифметических выражений алгоритмических языков, т.е. операции сложение, вычитание, умножение, деление, возведение в степень обозначаются через "+", "-", "*", "/", "^".
2. Показатель степени не должен зависеть от переменной e.t.
3. Ограничимся использованием лишь следующих функций: sin, cos, exp; введение остальных функций достигается добавлением по одному предложению на каждую новую функцию.
4. Функция Diff не будет делать никаких алгебраических упрощений полученной формулы (приведение подобных и т.д.), потому что упрощение формулы - задача гораздо более сложная, чем дифференцирование.
5. Все скобки являются структурными, если это не так, то можно воспользоваться функцией Spar.
Diff {
(e.t) e.1 '+' e.2 = <Diff (e.t) e.1> '+' <Diff (e.t) e.2>;
(e.t) e.1 '-' e.2 = <Diff (e.t) e.1> '-' <Diff (e.t) e.2>;
(e.t) e.1 '*' e.2 = (e1 '*' <Diff (e.t) e.2>
'+' <Diff (e.t) e.1> '*' e.2);
(e.t) e.1 '/' e.2 = (( <Diff (e.t) e.1> '*' e.2 '-'
e.1 '*' <Diff (e.t) e.2>) '/'
(e.2 '*' e.2) );
(e.t) e.1 '^' e.2 = (e.1 '^' (e.2 '-1' )) '*'
<Diff (e.t) e.1>;
(e.t) 'sin'(e.1) = 'cos' (e.1) '*' (<Diff (e.t) e.1>);
(e.t) 'cos'(e.1) = ('-sin' (e.1)) '*' (<Diff (e.t) e.1>);
(e.t) 'Ґеа'(e.1) = 'Ґеа' (e.1) '*' (<Diff (e.t) e.1>);
(e.t) (e.1) = ( <Diff (e.t) e.1> );
(e.t) e.t = '1';
(e.t) e.1 = '0';
}
Отметим, что почти все предложения являются перезаписью известных правил дифференцирования (суммы, произведения, частного, сложной функции и т.д.).
Поскольку лишние скобки не влияют на процесс вычисления по формуле, то мы не следим за появлением "лишних" скобок.
Почему именно такой порядок предложений?
Задача. Как правило, не удается написать сразу программу без ошибок. При написании функции Diff была допущена ошибка. Мы ее и оставили. Цель данного упражнения состоит в нахождении оставленной ошибки. Какие формулы дифференцируются правильно функцией Diff ? Для каких формул производная будет вычисляться неправильно?
Задача. Расширьте возможности функции Diff так, чтобы она обрабатывала все функции библиотеки подпрограмм, а также возведение в степень, являющуюся функцией от переменной.
Задача. Проведите анализ алгоритма Diff на эффективность. В каких местах происходит многократный просмотр выражения?
Задача. Два последних предложения функции Diff ясно показывают, что в получающейся формуле будет много лишних нулей и единиц. Напишите программу упрощения алгебраических выражений (в разумных пределах).