РЕФАЛ-5

• Условие
• Блок

УСЛОВИЕ

Для примера рассмотрим следующую задачу. Требуется написать функцию Cut-by-delim которая из входной строки выделяет ее начало, ограниченное одним из трех символов: ".", "," или ";". Для удобства введем функцию Oneof ("один из"), которая узнает, входит ли данный символ (терм) в заданный список символов (термов):

Oneof {
      tA (e1 tA e2) = T;
      tA (e1) = F;
      };

Обращение к ней имеет вид: <Oneof tA (eX)> . Результат - символ-слово T, если терм tA входит в список eX, в противном случае - символ-слово F. Форматные скобки введены исключительно для читабельности, чтобы не было затруднений с пониманием таких обращений как <Oneof s1 (s2 s3)> . Эта функция на практике очень полезна, поэтому рекомендуем поместить ее в свой "архив".

Теперь обратимся к основной функции Cut-by-delim. На базисном рефале ее можно описать так:

Cut-by-delim {
    sA eX = <Cut-by-delim1 sA eX <Oneof sA ('.,;')>>;
   = ;
   };
Cut-by-delim1 {
   sA e1 F = sA <Cut-by-delim e1>;
   sA e1 T = ;
   };

Условие записывается после образца в виде:

            , ER : EP

где ER - произвольное результатное выражение, а EP - произвольный образец. В одном предложении может быть несколько условий. Выражение ER может содержать переменные, которые уже встречались в этом же предложении слева от запятой. Образец EP может содержать как старые, так и новые переменные. Условия "работают" последовательно, после того как успешно завершится основное сопоставление. Значения старых переменных подставляются в ER и EP , в результате получаются рабочее выражение ER' и новый образец EP'. Затем ER' вычисляется, и результат вычислений - объектное выражение ER" - сопоставляется с образцом EP'. В случае успеха новые переменные с их значениями добавляются к списку старых переменных, и продолжается вычисление предложения: следующих условий или правой части. В случае неуспеха работа переходит на предыдущий образец: последний вариант сопоставления отвергается, и продолжается поиск других вариантов.

Перепишем функцию Cut-by-delim с использованием нового средства:

Cut-by-delim {
     sA eX , <Oneof sA ('.,;')> : F = sA <Cut-by-delim eX>;
     e1 =
     };

Заметим, что второе предложение объединяет два случая: когда строка начинается с разделителя и когда она пуста.

Наконец, мы можем еще упростить эту функцию, используя открытую переменную:

Cut-by-delim {                                           
    e1 sA e2 , <Oneof sA ('.,;')> : T = e1;           
    e1 = e1;                                             
    };

Мы назвали введенную конструкцию "условие", но это не совсем точно: кроме проверки условия ее результатом является также присваивание значений новым переменным. Часто именно в них и заключен весь смысл "условия". Будем содержательно различать три вида условий: чистые условия (не определяют новых переменных), чистые присваивания (безусловно срабатывают) и условные присваивания (смешанный случай).

Пример: функция Add складывает два числа, представленные в виде цепочек десятичных цифр, используя функцию сложения двух цифр Ad-digits:

Add {                                                    
   (e1 sA) (e2 sB) , <Ad-digits sA sB> : e.Car s.Sum     
          = <Add (<Add (e1) (e2)>) (e.Car)> s.Sum;       
   (e1) (e2) = e1 e2;                                    
   };                                                    
                                                         
Ad-digits {                                              
     '0' sX = sX;                                        
     sX '0' = sX;                                        
     '11' = '2';                                         
        . . .                                            
     '99' = '18';                                        
     };

Задачу краткого описания функции Ad-digits оставляем читателю в качестве упражнения.

Следующий пример демонстрирует возможность использования рекурсии в условиях.

Задача о назначении. Жители поселка N создали несколько общественных организаций. Каждый житель может входить в несколько организаций или ни в одну. Имеется список членов каждой организации. Требуется выбрать в каждой организации председателя так, чтобы никто не занимал двух постов сразу.

Формально: дан список термов, каждый из которых есть список символов в скобках. Функция Select должна построить список символов, в котором все символы различны, и на i-м месте стоит символ из i-го терма. Если построение удастся, то результатом станет этот список в скобках, если же решений нет, то результат - символ '*'.

Для того, чтобы решить задачу, сначала ее усложним: сведем ее к функции Select1, которая имеет еще один аргумент - "запрещенное множество" eZ, т.е. список символов, которые нельзя использовать. Идея состоит в том, что символы, отобранные из части термов, составляют "запрещенное множество" при отборе из другой части.

Select { eA = <Select1 () eA> };                         
                                                          
Select1 {                                                
    (eZ) = (eZ);                                         
    (eZ) (e1 sA e2) eX , <Oneof sA (eZ)> : F,            
                   <Select1 (eZ sA) eX> : (eR) = (eR);   
    (eZ) eX = '*';                                       
    };

Упражнения

1. Дайте короткое описание функции Ad-digits.
2. Измените функцию Select так, чтобы она вырабатывала список всех возможных решений.
3. Напишите функцию сравнения двух множеств. Множества представлять списками своих элементов в скобках. Два множества совпадают, если каждый элемент первого множества является элементом второго и наоборот. Элементами множеств могут быть либо символы, которые равны только сами себе, либо множества, которые сравниваются вышеописанным способом. 

БЛОК

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

Для того, чтобы аккуратно определить понятие блока, введем понятия образцового окончания и результатного окончания. Мы исходим из базисного Рефала, расширенного условиями. Образцовым окончанием назовем окончание предложения, начинающееся с образца. Соответственно, результатным окончанием назовем окончание предложения, начинающееся с результатного выражения, входящего в условие.

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

Теперь в качестве результатного (образцового) окончания разрешим использовать результатный (образцовый) блок. Для полноты картины, в качестве тела функции будем допускать не только блок, но и образцовое окончание, т.е. наружные фигурные скобки могут опускаться, если тело состоит из одного окончания.

При исполнении блок заменяется на одно из входящих в него окончаний. Вначале делается попытка использовать первое окончание. Но если его исполнение завершается неуспехом, то выбирается второе, и т.д. Если же последнее окончание блока оканчивается неуспехом, то весь блок оканчивается аварийно. (В Рефале-6 - неуспехом). В качестве примера использования блоков рассмотрим функцию слияния двух упорядоченных списков Merge. Для сравнения элементов списков служит встроенная функция COMPARE.

Merge {                                              
     (tA e1) (tB e2) , <COMPARE tA tB> : {         
          '<' = tA <Merge (e1) (tB e2)>;        
          '=' = tA <Merge (e1) (e2)>;              
          '>' = tB <Merge (tA e1) (e2)>;           
          };                                          
     (e1) (e2) = e1 e2;                               
     };

Если условия на разных предложениях имеют разные источники (результатные выражения), то следует использовать результатный блок. Покажем это на примере функции Compset, сравнивающей два множества на включение: не является ли одно подмножеством другого. Предполагаем, что функция Diff, вычисляющая разность двух множеств уже определена (см. упражнение 1 в разделе 1.5):

Compset    (e1) (e2) , {                           
     <Diff (e1) (e2)> : = '<';                     
     <Diff (e2) (e1)> : = '>';                     
     : = '?';                                      
     };

Упражнение

Функция Merge фактически вычисляет объединение упорядоченных множеств. Напишите функции, вычисляющие пересечение, разность и симметрическую разность упорядоченных множеств. Результат должен быть также упорядоченным. Оцените время их работы.