recnumb3

rec3.htm

Рекурсивные числа (продолжение)

      Описываю эксперимент, который получился случайно. В какой-то момент в программе rec2.ref в функции Rec1 у меня оказалось "лишнее" предложение. Программа была такова

*$STRATEGY Applicative;

RecNumber {
   e.1 = <Rec ( ) e.1>;
 }

Rec {
  (e.1)  =  e.1;
  (e.1) e.3 (e.2) = <Rec1 (e.2) <Rec ((e.2) e.1) e.3> >;
 }

Rec1 {
  ( ) = ;
  ( ) ('1' e.2) e.3 = (e.2) <Rec1 ( ) e.3>;
  ('1' e.1) ( ) e.3 = <Rec1 (e.1) e.3>;
  ('1' e.1) ('1' e.2) e.3 = (e.2) <Rec1 ('1' e.1) e.3>;
 }

      После суперкомпиляции для чисел произвольной значности получилась программа, похожая на начальную, но время ее суперкомпиляции уменьшалось более чем вдвое ! Подробнее об этом. Привожу остаточную программу

*$STRATEGY Applicative;

RecNumber {
  = ;
 e.1 (e.102 ) (e.101 )  = <F42 (e.101 ) <F42 (e.102 )
                          <F27 (e.1 ) (e.102 ) (e.101 )>>> ;
 }

F68 {
 (e.115 ) (e.117 )  = <F42 (e.115 ) e.117 > ;
 (e.115 ) ((e.142 ) e.117 ) '1' e.134
          = (e.134 ) <F68 (e.115 ) (e.117 ) e.142 > ;
 }

F47 {
  = ;
 ('1' e.122 ) e.117  = (e.122 ) <F47 e.117 > ;
 }

F42 {
 ( )  = ;
 ( ) ('1' e.118 ) e.117  = (e.118 ) <F47 e.117 > ;
 ('1' e.115 ) ( ) e.117  = <F42 (e.115 ) e.117 > ;
 ('1' e.115 ) ('1' e.120 ) (e.143 ) e.117
          = (e.120 ) <F68 (e.115 ) (e.117 ) e.143 > ;
 }

F27 {
 ( ) (e.111 ) (e.112 ) e.113  = (e.111 ) (e.112 ) e.113 ;
 (e.110 (e.115 )) (e.111 ) (e.112 ) e.113
     = <F42 (e.115 )
       <F27 (e.110 ) (e.115 ) (e.111 ) (e.112 ) e.113 >> ;
 }

     Время суперкомпиляции этой программы для 7-значных чисел составило 25 секунд.

     Если бы я сам догадался написать именно эту программу, то отношение времен выглядело бы более внушительным -

     25 секунд против 378 секунд для исполнения без суперкомпиляции.

     Чтобы разобраться, в чем тут дело (за счет чего происходит ускорение суперкомпиляции более чем в два раза), я стал постепенно изменять исходную программу  Rec2.ref.

     Первоначальная программа берет первую цифру неизвестного числа, которая равна количеству нулей, и удаляет эти нули, при этом остальные цифры уменьшая на 1.

     Затем то же самое делает со второй цифрой, которая равна количеству единиц (они к этому времени стали нулями), и так далее.

     Для чего построилась функция F47 ? Она соответствует случаю, когда все нули уже найдены, значит теперь надо все оставшиеся цифры уменьшить на единицу.

     Ввожу в своей программе дополнительную функцию Rec1a, суперкомпилирую - время суперкомпиляции осталось прежним - 58 секунд.

    Функция F68. Нули еще не все найдены, встретился не 0. Функция F68 уменьшает встречающиеся ненули на 1, при этом известно, что нули еще будут. Ввожу функцию Rec1b, которая аналогична функции F68 , суперкомпилирую - время уменьшилось незначительно - 57 секунд.

     В чем дело ? Оказалось, что для того, чтобы отличить пустоту от непустоты, очередная цифра помещается заранее справа, и тогда эти два случая различаются по количеству скобок в аргументе.

     Учитываю данное замечание и получаю программу

*$STRATEGY Applicative;

RecNumber {
   e.1 = <Rec ( ) e.1>;
 }

Rec {
  (e.1)  =  e.1;
  (e.1) e.3 (e.2) = <Rec1 (e.2) <Rec ((e.2) e.1) e.3> >;
 }

Rec1 {
  ( ) = ;
  ( ) ('1' e.2) e.3 = (e.2) <Rec1a e.3>;
  ('1' e.1) ( ) e.3 = <Rec1 (e.1) e.3>;
  ('1' e.1) ('1' e.2) (e.a) e.3 = (e.2) <Rec1b (e.1) (e.3) e.a>;
 }

Rec1a {
   = ;
  ('1' e.2) e.3 = (e.2) <Rec1a e.3>;
 }

Rec1b {
  (e.1) (e.3) = <Rec1 (e.1) e.3>;
  (e.1) ((e.a) e.3) '1' e.2 = (e.2) <Rec1b (e.1) (e.3) e.a>;
 }

     Теперь время суперкомпиляции составляет 25 секунд.

     Итак, я описал необычное использование суперкомпиляции. При помощи самого суперкомпилятора выясняется вариант написания программы, который будет суперкомпироваться быстрее.