ПРИЛОЖЕНИЕ 1
Эквивалентные преобразования
алгоритмов на рефале
Предлагаемый вашему вниманию параграф был написан 15 лет назад и по мнению автора представляет определенный интерес в контексте данного пособия. |
Синтаксис языка рефал
очень просто устроен. Поэтому можно
преобразовывать описания функций языка рефал,
так же как мы производим алгебраические
преобразования.
В этом параграфе мы решим две задачи, которые были сформулированы ранее. С помощью довольно очевидных преобразований мы получим такие описания функций, которые можно назвать красивыми, и до которых так просто додуматься было бы нелегко.
Сразу же сделаем пояснение. Цель данного параграфа состоит не в том, чтобы научить кого-либо преобразованиям алгоритмов, а в том, чтобы показать на ярких примерах небольшой кусочек той работы, которая ведется в этой области. Более того, те преобразования, которые мы рассмотрим, должен делать компилятор с языка рефал, а не программист. Компилятор должен не только транслировать программу на машинный язык, но и получать при этом эффективную программу.
Программист должен без ошибок описать на рефале алгоритм, а забота об эффективности выполнения ложится на компилятор. Многое уже сделано в этой области, многое предстоит сделать.
П Р И М Е Р. Написать функцию, которая по трем символам из множества "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 = sa. e.1 e.2 e.3; }
Итак, количество предложений в функции Alfa уменьшилось с 8 до минимума ( до одного предложения).
П Р И М Е Р. Сложение двух чисел, записанных в двоичной системе счисления. Формат обращения: <Add (e.M) e.N > , где е.М, e.N - слагаемые.
Р Е Ш Е Н И Е. Воспользуемся функцией Add1 из п..4 и опишем всевозможные случаи, которые возникают при "сложении столбиком". Перенос мы не будем держать в "уме", а будем прибавлять его к первому слагаемому.
Add { (e.1 '0') e.2 '0' = <Add (e.1) e.2> '0'; (e.1 '0') e.2 '1' = <Add (e.1) e.2> '1'; (e.1 '1') e.2 '1' = <Add (e.1) e.2> '1'; (e.1 '1') e.2 '1' = <Add (<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'; }
Три последние предложения описывают случаи окончания вычислений.
Заметим, что если мы правильно описали функцию Add, то результат вычисления рабочего выражения <Add1 e.N> совпадает с результатом вычисления выражения <Add (e.N) '1 '>. Поэтому не будем пользоваться функцией Add1, а четвертое предложение перепишем так:
(e.1 '1' ) e.2 '1' = <Add ( <Add (e.1) '1' > ) e.2 > '0'
Последние три предложения объединяются в одно:
( e.1 ) e.2 = e.1 e.2
Поскольку первые четыре предложения описывают взаимноисключающие случаи, то их можно переставлять. Итак,
Add { (e.1 '0') e.2 '0' = <Add (e.1) e.2> '0'; (e.1 '1') e.2 '1' = <Add (<Add (e.1) '1'>) e.2> '0'; (e.1 '1') e.2 '0' = <Add (e.1) e.2> '1'; (e.1 '0') e.2 '1' = <Add (e.1) e.2> '1'; (e.1) e.2 = e.1 e.2; }
Правые части у третьего и четвертого предложений совпадают, поэтому их можно объединить так:
(e.1 s.a) e.2 s.b = <Add (e.1) e.2> '1'
Так как прибавление нуля к числу не должно изменять его значения, то первое предложение можно записать в виде
(e.1 '0' ) e.2 '0' = <Add (<Add (e.1) '0' > ) e.2 > '0'
Итак, получаем описание функции Add
Add { (e.1 '0') e.2 '0' = <Add (<Add (e.1) '0'>) e.2> '0'; (e.1 '1') e.2 '1' = <Add (<Add (e.1) '1'>) e.2> '0'; (e.1 s.a) e.2 s.b = <Add (e.1) e.2> '1'; (e.1) e.2 = e.1 e.2; }
Теперь видно, чем отличаются первое и второе предложения: вместо символа "0" стоит символ "1". Поэтому их можно объединить, написав вместо "0" и "1" переменную s.a
Add { (e.1 s.a) e.2 s.a = <Add (<Add (e.1) s.a>) e.2> '0'; (e.1 s.a) e.2 s.b = <Add (e.1) e.2> '1'; (e.1) e.2 = e.1 e.2; }
Первое предложение соответствует случаю, когда оба числа оканчиваются одинаковой цифрой s.a . B этом случае "0 пишем, sa - в уме". Второе предложение - случаю, когда числа оканчиваются разными цифрами. В этом случае "1 пишем, 0 - в уме". Последнее предложение заканчивает сложение.