index , prev , next

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 - в уме". Последнее предложение заканчивает сложение.

index , prev , next