Глава 4. Расширенный РЕФАЛ (koi8-r)

4. РАСШИРЕННЫЙ РЕФАЛ

В этой главе вводится некоторое расширение базисного РЕФАЛа, которое делает программирование более легким, а программы - более наглядными. Средствами расширения являются:

where-конструкции, или условия;
with-конструкции, или блоки;
функции закапывания-выкапывания.

4.1. Условия

4.2. Блоки

4.3. Функции закапывания-выкапывания

4.1. УСЛОВИЯ

Рассмотрим функцию Pre-alph , которая устанавливает отношение предшествования между символами в смысле обычного алфавитного порядка. В Главе 3 она была определена следующим образом:

  Pre-alph {
  *1.This relation is reflexive
     s.1 s.1 = T;
  *2.If the letters are different, see whether the
  *  first is before the second in the alphabet
     s.1 s.2 = <Before s.1 s.2 In <Alphabet>>; }
   
  Before {
     s.1 s.2 In e.A s.1 e.B s.2 e.C = T;
     e.Z = F; }
   
  Alphabet { = 'abcdefghijklmnopqrstuvwxyz'; }

Это определение записано средствами базисного РЕФАЛа. В полном РЕФАЛе функцию Pre-alph можно определить, не вводя вспомогательную функцию Before:

  Pre-alph {
     s.1 s.1 = T;
     s.1 s.2, <Alphabet>: e.A s.1 e.B s.2 e.C 
            = T;
     e.1 = F;  }

Здесь было использована where-конструкция, которая накладывает дополнительное условие на применимость предложения. Этим условием служит:

  <Alphabet>: e.A s.1 e.B s.2 e.C

Она следует за левой частью предложения, отделяясь от него специальным where-with знаком РЕФАЛа. В языке РЕФАЛ-5 этот знак может быть представлен либо амперсендом & , либо запятой , . Он используется для выделения как where-конструкций, так и with-конструкций (блоков). Как вскоре будет видно, with-конструкцию легко отличить от where-конструкции с помощью фигурных скобок. Однако некоторые программисты, возможно, предпочтут использование запятой в качестве where-знака и амперсенда в качестве with-знака (либо наоборот). В этой книге в обоих случаях используется запятая.

Условие является сопоставляемой парой, где образцом (правым операндом) может служить любое выражение-образец, а аргументом (левым операндом) может являться любое РЕФАЛ-выражение; единственным ограничением для аргумента является то, что он должен включать только те переменные, которые имеют определенные значения на момент проверки условия ( связанные переменные). Для условия, которое непосредственно следует за левой частью предложения, это требование означает, что в его аргументе могут использоваться только те переменные, которые появляются в левой части предложения. Выражение-образец в правой части условия может включать как связанные переменные, так и свободные переменные, которые еще не были определены и получают значения в процессе сопоставления.

В предложении могут встретиться несколько последовательных where-конструкций. Условия, введенные таким образом, будут вычисляться (проверяться) в заданной последовательности.

Пусть задано условие Е : P. Оно вычисляется следующим образом. Во-первых, РЕФАЛ-машина порождает новое поле зрения, помещает Е в это поле и заменяет переменные из Е их значениями. Затем машина работает, как обычно, над этим полем зрения до тех пор, пока его содержимое пассивно. В процессе вычислений могут порождаться дополнительные поля зрения. Когда процесс завершается, результат сопоставляется с образцом Р . При этом сопоставлении те переменные в Р , которые являются уже связанными, заменяются на свои значения, в то время как свободные переменные принимают значения в процессе сопоставления. Если сопоставление является успешным, вычисляется следующее условие; если больше нет условий, имеет место замена левой части предложения на правую его часть. Если сопоставление терпит неудачу, объявляется тупиковая ситуация в предшествующем сопоставлении, (которое могло относиться как к условию, так и к левой части сопоставления с образцом). В этом случае открытые переменные в образце будут удлиняться до тех пор, пока это возможно. Если больше не остается переменных, подлежащих удлинению, тупиковая ситуация снова переносится на предшествующее сопоставление; если это происходит при сопоставлении в левой части, предложение неприменимо, как и в базисном РЕФАЛе, и испытывается следующее предложение. После того как проверка условия завершается успехом либо неудачей, временное поле зрения, созданное для Е, уничтожается, и РЕФАЛ-машина возвращается к полю зрения, из которого вызывалось Е.

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

В случае функции Pre-alph при проверке условия вычисляется значение функции <Alphabet> . В последующем процессе сопоставления s.1 и s.2 заменяются их значениями, т.е. символами, подлежащими сравнению. Сопоставление завершится успешно тогда и только тогда, когда s.1 предшествует s.2 в алфавите.

Интерпретация условий, по существу, занимает столько же, сколько и трансляция условий в базисный РЕФАЛ. Для каждого условия создается специальная вспомогательная функция, которая выполняет сопоставление, требуемое по условию. Имена этих функций образуются из имени вызывающей функции добавлением $1, $2, и т.д. Предположим, имеется вызов < F Х > , такой, что на следующем шаге РЕФАЛ-машины применяется одно из предложений F , которое включает условие:

   F {...
      L, E : P  =  R;
      ...
     }

Тогда система вставит вызов вспомогательной функции F$n между окончанием аргумента Х и закрывающей вычислительной скобкой:

  <F Х<F$n Е>>

Согласно общему правилу, теперь будут вычислены активные подвыражения из Е (если таковые имеются) ; затем управление перейдет к F$n. Однако, эта функция является специальной; выполняется только сопоставительная часть шага, а именно, вычисленное Е сопоставляется с Р. Затем управление возвращается к F. Если сопоставление было успешным, имеет место подстановка выражения R , в противном случае производится попытка применить следующее предложение. В любом случае вызов F$n, который был ранее вставлен, удаляется.

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

  <Pre-alph 'ba'>

После первого шага в поле зрения появится:

  <Pre-alph 'ba'<Pre-alph$1 <Alphabet>>>

Теперь <Alphabet> проработает с результатом:

  <Pre-alph 'ba'<Pre-alph$1 'ab...z'>>

Если в этот момент есть обращение к трассировщику для печати активного выражения, мы увидим

  <Pre-alph$1 'ab...z'>

как если бы Pre-alph$1 являлась настоящей функцией. Однако, замещению результатом подлежит вызов Pre-alph , а не Pre-alph$1 , так что на следующем шаге мы имеем:

Упражнение 4.1. Определить функцию, которая ищет первое вхождение операции сложения-вычитания на верхнем уровне, т.е., знак'+' или '-' , и заключает предшествующее подвыражение в скобки.

Упражнение 4.2. В некоторых сообщениях о системе РЕФАЛ-5 упоминается только целочисленная арифметика, а предикат Compare не встраивается. Предикаты для сравнения целых чисел могут быть определены в РЕФАЛе посредством вычитания. Определить Less и Lesseq ( и ) для целых чисел (см. Reference Section C , форматы).

На начало

4.2. БЛОКИ

With-конструкции позволяют использовать блоки (напомним, что блоком является список предложений в фигурных скобках) прямо в рамках функционального определения без введения вспомогательной функции для этой цели.

В качестве примера with-конструкции, напомним функцию упорядочения пар из Главы 3 :

  Order {
    (e.1)e.2 = <Order1 <Pre (e.1)(e.2)> (e.1)e.2>;}
   
  Order1 {
     T (e.1)e.2 = e.1 e.2;
     F (e.1)e.2 = e.2 e.1;
          };

Вспомогательная функция становится ненужной, если используется полный РЕФАЛ:

  Order { 
     (e.1)e.2, <Pre (e.1)(e.2)>:
             { T = (e.1)(e.2);
               F = (e.2)(e.1);
             }; }

With-конструкция начинается таким же образом, как и where-конструкция: с where-with-знака, затем следует общее РЕФАЛ-выражение, использующее только связанные переменные (аргумент), затем двоеточие - знак операции сопоставления. Однако вместо образца в with-конструкции используется блок. Фигурные скобки, объединяющие группу предложений в блок, имеют двоякое значение.

Во-первых, они дают возможность сопоставлять аргумент с несколькими образцами. В нашем примере <Pre (e.1)(e.2)> вычисляется однажды, после чего РЕФАЛ-машина пытается сопоставить его с последовательными левыми частями в блоке, замещение выполняется как обычно.

Второй функцией фигурных скобок в with-конструкции является завершение процесса сопоставления в предшествующей левой части и в условиях. Когда управление переходит к левой фигурной скобке, нет пути назад к удлинению e-переменных. Какие бы значения ни были присвоены переменным вне блока, они должны такими и остаться. В случае, когда ни одно из предложений неприменимо, последует аварийное завершение, как если бы это было функциональное определение.

На самом деле блок является функциональным определением, но эта функция не имеет присвоенного имени и вызывается по аргументу, (по выражению, следующему за where-with-знаком) в качестве ее аргумента. Можно видеть, что блок в определении функции Order в точности тот же, что и во вспомогательной функции Order1 . With-констукция позволяет определить безымянную функцию именно в том месте, где она нужна. Определение функции Order в базисном РЕФАЛе можно рассматривать как семантику with-конструкции во втором определении.

Рассмотрим следующее определение:

  F {
     e.1'+'(e.2)e.3, <P e.2>: T = (e.2);
     e.1 = <Prout 'No such term'>;
    };

Эта функция находит первый заключенный в скобки терм после '+', такой, что выражение внутри удовлетворяет предикату P . Если P определен как:

  P { s.1'/'s.2 = T;
     e.X = F;  }

то вычисление функции:

  <F  A-B+(C*D)+(C/D)>

приводит к результату (C/D) . Если заключить условие и правую часть в фигурные скобки, так, что они образуют блок-предложение:

  F { e.1'+'(e.2)e.3>, <P e.2>: { T = (e.2) };
      e.1 = <Prout 'No such term'>;  }

тогда алгоритм следует читать следующим образом: найти первый заключенный в скобки терм, следующий за '+', а затем проверить, удовлетворяет ли заключенное в скобки выражение предикату P . Если теперь вычисляется тот же вызов с измененным определением, результатом будет аварийный останов `Распознавание невозможно'. На самом деле первым термом после '+' является (C*D) , и P не удовлетворяется. Не будет попытки удлинять e.1: можно только войти в фигурные скобки, окружающие блок, но никогда нельзя выйти из них.

Вспомним функцию Sub-a-z , которая выделяет подстроку, начинающуюся на 'a' и оканчивающуюся на 'z' . В Главе 2 , чтобы эффективно задать ее, потребовалось ввести вспомогательную функцию. Теперь эта функция может быть включена как блок:

  Sub-a-z { 
     e.1'a'e.2, e.2 : 
           { e.3'z'e.4 = (e.1)'a'e.3'z'(e.4);
              e.3 = <Prout 'No substring a-z'>;
           };
     e.1 = <Prout "No 'a' found">;  
          }

После того как обнаружено первое 'a', производится вход в блок, и если после этого нет ни одного 'z', e.1 не будет удлиняться; вместо этого будет сформулирован отрицательный результат.

Блоки, как и условия, реализуются через вызовы вспомогательных $-функций, которые вставляются между аргументом главной (вызывающей) функции и правой функциональной скобкой. Вспомогательные функции для блоков даже более близки к обычным функциям, чем аналогичные функции для условий. Подобно обычным функциям, они вычисляются посредством попытки сопоставить аргумент с последовательными предложениями в блоке; после успешного сопоставления соответствующая правая часть используется для замещения. Однако вызов, который замещается результатом, - вовсе не вызов $-функции, а вызов главной функции, определение которой включало эту with-конструкцию.

Отследим вызов функции Order, рассмотренной выше:

  1.   <Order ('abc')'de'> 
  2.   <Order ('abc')'de'<Order$1 <Pre ('abc')('de')>>>

После вычисления Pre, которое производится за четыре шага, имеем:

  6.   <Order ('abc')'de'<Order$1 T>>
  7.   ('abc')('de')

Упражнение 4.3 Переопределить следующую функцию, чтобы сделать ее определение более эффективным :

  s123 {
     e.A 1 e.B 2 e.C 3 e.D = T;
     e.A = F;  }

Упражнение 4.4 Инвертированная пара в последовательности чисел есть такая пара смежных чисел, что предшествующее число больше последующего.
(a) Написать программу, которая отыскивает первую инвертированную пару в данной числовой последовательности, для которой сумма членов пары превосходит 100.
(b) Записать программу, которая определяется, является ли сумма членов первой инвертированной пары превосходящей число 100.
Использовать функцию Less из Упражнения 4.2.

На начало

4.3. ФУНКЦИИ ЗАКАПЫВАНИЯ-ВЫКАПЫВАНИЯ

РЕФАЛ является строго функциональным языком. Но в качестве уступки более традиционным способам программирования, в нем еще остается ряд встроенных функций, которые позволяют пользователю употреблять присваивания. Это не рекомендуется делать и, на самом деле, в этом нет нужды - использовать присваивания для манипуляции объектами. Но иногда желательно поддерживать некоторые глобальные параметры или таблицы, не передавая их как часть аргумента от одного функционального вызова к другому. Тогда можно "закопать'' такие параметры под присвоенными именами, активизируя выражения следующего вида:

  (*)       <Br N '=' Е >

Когда такой параметр потребуется, он "выкапывается'' посредством

  (**)      <Dg N>

Здесь N означает строку символов, которая не включает символ '=', а and Е - любое выражение.

Когда вычисляется (*) , оно исчезает из поля зрения, но на его месте остается выражение Е в реальной связной структуре, представляющей поле зрения. Размещение его связывается со строкой N и сохраняется в таблице. Поэтому вычисление Br занимает постоянный малый квант времени, не зависящий от величины Е . Когда вычисляется (**) , оно снова замещается закопанным выражением , без просмотра последнего, только путем восстановления связей с его концами. Имеется также функция копирования Cp, которая имеет такой же формат и значение, как и Dg , но с ее помощью закапываемое выражение копируется , а не извлекается. При многократном использовании Br и Dg порождают стэк закопанных значений для каждого имени. Функция Br закапывает каждое следующее значение для данного имени, не затрагивая предыдущих значений. Функция Dg извлекает последнее закопанное значение. Таким образом, эти функции работают как стэки значений для каждого используемого имени. Однако, если стэк для данного имени пуст, результатом Dg является пустое значение, т.е. он не является неопределенным, как это должно было бы быть для обычного стэка. Это отклонение от строгой семантики стэков оказалось практически полезным.

Предположим, создается программа, которая имеет дело с некоторыми объектами и время от времени порождает новые объекты того же вида. Им присваиваются последовательные номера, начиная с 1. Функция, которая порождает новые объекты, должна иметь доступ к первому свободному индексу. Он может быть сохранен, будучи закопан под некоторым именем, скажем, 'fr-ind' . Тогда при запуске программы, например, как фрагмента правой части Go , выполняется:

  <Br 'fr-ind=' 1>

Как только понадобится породить новый индекс, используется:

  <Next 'fr-ind'>

в качестве индекса. Функция Next получает число, закопанное под ее аргументом-именем, и увеличивает его на 1 :

  Next { 
     e.Name, <Dg e.Name>: e.Value  =
             e.Value  
             <Br e.Name'=' <+ e.Value 1>>; }

В Разделе 2.1 была написана программа, транслирующая строки итальянских слов в строки слов английских. Функция Table была применена для хранения трансляционной таблицы (словаря):

  * Italian-English dictionary table
  Table { = (('cane') 'dog')
            (('gatto') 'cat')
            (('cavallo') 'horse')
            (('rana') 'frog')
            (('porco') 'pig')   }

Вместо хранения этой таблицы в качестве правой части предложения, можно было бы хранить ее как выражение, закапываемое под одним и тем же именем, скажем, 'dict' .

Выражения, закапываемые при помощи Br, хранятся в форме двухсвязных списков, как и все выражения в поле зрения. В отличие от них, правые части предложений сохраняются в форме кода в языке RASL. Последняя форма гораздо более компактна, чем первая. Однако, закопанное выражение готово к применению, в то время как правая часть предложения подобна той, которой используется для Table, будет прочитана РЕФАЛ-машиной посимвольно в процессе создания соответствующего двухсвязного списка в поле зрения. Поэтому, когда существенны пространственные ограничения, предпочтительнее сохранять таблицу в правой части предложения; но если более важно время выполнения, таблицу следовало бы закапывать.

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

  * This program translates from Italian into
  * English and keeps the dictionary buried.
  $ENTRY Go { =  <Br 'dict='
            (('cane') 'dog')
            (('gatto') 'cat')
            (('cavallo') 'horse')
            (('rana') 'frog')
            (('porco') 'pig') 
                   >
                   <Job <Card>>    }

Теперь следует соответствующим образом изменить использование таблицы. Самый простой способ сделать это - переопределить только одну функцию, Table , так, чтобы она копировала словарную таблицу:

  Table { = <Cp 'dict'>; }

Однако, этот способ ничем не лучше хранения таблицы в предложении, так как перед использованием таблицы РЕФАЛ-машина должна будет сделать вторую ее копию -- с неизбежными потерями по времени и памяти. Для того, чтобы использовать закопанную таблицу эффективно, следует определить процесс так, чтобы именно та копия, которая была закопана, и использовалась в дальнейшем, а затем снова закапывалась без изменений.

Таким образом, вызов <Table> , который встречается в Trans-line , заменяется на <Dg 'dict'> :

  * Translate one line
  Trans-line {
     ' 'e.X = <Trans-line e.X>; 
     e.Word' 'e.Rest = 
            <Trans (e.Word) <Dg 'dict'>>' '
            <Trans-line e.Rest>;
      =  ;
     e.Word = <Trans (e.Word) <Dg'dict'>>' ';
             }

Полная словарная таблица будет теперь аргументом Trans . Модифицируем Trans так, чтобы она опять закапывала таблицу после использования:

  * Translate Italian word into English by table
  Trans { 
      (e.It) e.1 ((e.It)e.Eng) e.2 = 
           e.Eng <Br 'dict=' e.1 ((e.It)e.Eng) e.2>; 
      (e.It) e.1 = 
           ***<Br 'dict=' e.1>; 
                 /* the word not in table */
        }

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

Упражнение 4.5 Модифицировать итало-английский транслятор таким образом, чтобы словарь постоянно сохранялся на диске как файл DICT . В начале работы программа предлагает пользователю сделать (возможные) дополнения к словарной таблице. Пользователь вводит дополнения, программа обновляет файл и затем работает, как описано выше.

На начало