9. Эквивалентные преобразования алгоритмов на рефале
Синтаксис языка рефал очень просто устроен. Поэтому можно преобразовывать описания функций языка рефал, так же как мы производим алгебраические преобразования.
В этом параграфе мы решим две задачи, которые были сформулированы ранее. С помощью довольно очевидных преобразований мы получим такие описания функций, которые можно назвать красивыми, и до которых так просто додуматься было бы нелегко.
Сразу же сделаем пояснение. Цель данного параграфа состоит не в том, чтобы научить кого-либо преобразованиям алгоритмов, а в том, чтобы показать на ярких примерах небольшой кусочек той работы, которая ведется в этой области. Более того, те преобразования, которые мы рассмотрим, должен делать компилятор с языка рефал, а не программист. Компилятор должен не только транслировать программу на машинный язык, но и получать при этом эффективную программу.
Программист должен без ошибок описать на рефале алгоритм, а забота об эффективности выполнения ложится на компилятор. Многое уже сделано в этой области, многое предстоит сделать.
Пример. Написать функцию, которая по трем символам из множества "0", "1" выдает двузначное число, обозначающее количество единиц в исходной последовательности (задача сформулирована в конце п. 4).
Решение. Обозначим искомую функцию через Alfa и опишем ее 8-мью предложениями, которые соответствуют всевозможным наборам "0" и "1"
Alfa {
'111' = '11';
'110' = '10';
'101' = '10';
'100' = '01';
'011' = '10';
'010' = '01';
'001' = '01';
'000' = '00';
}
Первое и последнее предложения можно объединить, записав их так:
s.a s.a s.a = s.a s.a;
Предложения 2, 3, 5 тоже поддаются объединению, ведь левые части их содержат по две единицы, а правые совпадают:
e.1 '1' e.2 '1' e.3 = '10';
Произведя то же преобразование с предложениями 4, 6, 7 получаем следующее описание функции:
Alfa {
s.a s.a s.a = s.a s.a;
e.1 '1' e.2 '1' e.3 = '10';
e.1 '0' e.2 '0' e.3 = '01';
}
Bo втором предложении две из трех переменных e.1, e.2, e.3 принимают значение пусто, а третья - "0". В третьем предложении также две переменные принимают значение пусто, но третья - "1". Поэтому функцию Alfa можно переписать так:
Alfa {
s.a s.a s.a = s.a s.a;
e.1 s.a e.2 s.a e.3 = s.a e.1 e.2 e.3;
}
Наконец, первое предложение можно вообще убрать (убедитесь все таки!):
Alfa {
e.1 s.a e.2 s.a e.3 = s.a e.1 e.2 e.3;
}
Итак, количество предложений в функции Alfa уменьшилось с 8 до минимума ( до одного предложения).
Пример. Сложение двух чисел, записанных в двоичной системе счисления. Формат обращения: <Add2 (e.M) e.N > , где е.М, e.N - слагаемые.
Решение. Воспользуемся функцией Add1 из п..4 и опишем всевозможные случаи, которые возникают при "сложении столбиком". Перенос мы не будем держать в "уме", а будем прибавлять его к первому слагаемому.
Add2 {
(e.1 '0') e.2 '0' = <Add2 (e.1) e.2> '0';
(e.1 '0') e.2 '1' = <Add2 (e.1) e.2> '1';
(e.1 '1') e.2 '1' = <Add2 (e.1) e.2> '1';
(e.1 '1') e.2 '1' = <Add2 (<Add1 e.1>) e.2> '0';
( ) e.2 = e.2;
(e.1) = e.1;
( ) = ;
}
Add1 {
e.1 '0' = e.1 '1';
e.1 '1' = <Add1 e.1> '0';
= '1';
}
Три последние предложения описывают случаи окончания вычислений.
Заметим, что если мы правильно описали функцию Add2, то результат вычисления рабочего выражения <Add1 e.N> совпадает с результатом вычисления выражения <Add2 (e.N) '1 '>. Поэтому не будем пользоваться функцией Add1, а четвертое предложение перепишем так:
(e.1 '1' ) e.2 '1' = <Add2 (<Add2 (e.1) '1'> ) e.2> '0';
Последние три предложения объединяются в одно:
(e.1) e.2 = e.1 e.2;
Поскольку первые четыре предложения описывают взаимноисключающие случаи, то их можно переставлять. Итак,
Add2 {
(e.1 '0') e.2 '0' = <Add2 (e.1) e.2> '0';
(e.1 '1') e.2 '1' = <Add2 (<Add (e.1) '1'>) e.2> '0';
(e.1 '1') e.2 '0' = <Add2 (e.1) e.2> '1';
(e.1 '0') e.2 '1' = <Add2 (e.1) e.2> '1';
(e.1) e.2 = e.1 e.2;
}
Правые части у третьего и четвертого предложений совпадают, поэтому их можно объединить так:
(e.1 s.a) e.2 s.b = <Add2 (e.1) e.2> '1';
Так как прибавление нуля к числу не должно изменять его значения, то первое предложение можно записать в виде
(e.1 '0' ) e.2 '0' = <Add2 (<Add2 (e.1) '0'> ) e.2> '0';
Итак, получаем описание функции Add2
Add2 {
(e.1 '0') e.2 '0' = <Add2 (<Add2 (e.1) '0'>) e.2> '0';
(e.1 '1') e.2 '1' = <Add2 (<Add2 (e.1) '1'>) e.2> '0';
(e.1 s.a) e.2 s.b = <Add2 (e.1) e.2> '1';
(e.1) e.2 = e.1 e.2;
}
Теперь видно, чем отличаются первое и второе предложения: вместо символа "0" стоит символ "1". Поэтому их можно объединить, написав вместо "0" и "1" переменную s.a
Add2 {
(e.1 s.a) e.2 s.a = <Add2 (<Add2 (e.1) s.a>) e.2> '0';
(e.1 s.a) e.2 s.b = <Add2 (e.1) e.2> '1';
(e.1) e.2 = e.1 e.2;
}
Первое предложение соответствует случаю, когда оба числа оканчиваются одинаковой цифрой s.a . B этом случае "0 пишем, sa - в уме". Второе предложение - случаю, когда числа оканчиваются разными цифрами. В этом случае "1 пишем, 0 - в уме". Последнее предложение заканчивает сложение.