Для примера рассмотрим следующую задачу. Требуется написать функцию 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 = ;
};
Основная функция Cut-by-delim рассматривает очередной символ,
анализирует его посредством функции Oneof, а результат анализа
поручает обработать вспомогательной функции Cut-by-delim1,
которая либо завершает работу, либо рекурсивно "зацикливается"
на исходную функцию Cut-by-delim, "выплевывая" наружу
рассмотренный символ. Ясно, что без вспомогательной функции
здесь не обойтись, поскольку нужно произвести проверку,
которая не выразима в форме одиночного образца.
На практике такое встречается довольно часто. В этих случаях
очень удобно использовать следующее расширение Рефала,
которое позволяет дописать к предложению дополнительное
условие применение.
Условие записывается после образца в виде:
, 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';
};
Условие в первом предложении содержательно является чистым
присваиванием, поскольку, с учетом возможных результатов функции
Add-digits, сопоставление всегда выполняется успешно.Задачу краткого описания функции 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 = '*';
};
При использовании условий часто возникает ситуация, когда несколько рядом стоящих предложений, начинаются с одинаковых образцов, а также одинаковых условий или одинаковых левых частей условий. Такие группы можно объединять в блоки, вынося общее начало "за скобки". Правда, такое преобразование, вообще говоря, меняет смысл программы, поэтому блок следует использовать с учетом его особой семантики, которая определяется ниже.
Для того, чтобы аккуратно определить понятие блока, введем понятия образцового окончания и результатного окончания. Мы исходим из базисного Рефала, расширенного условиями. Образцовым окончанием назовем окончание предложения, начинающееся с образца. Соответственно, результатным окончанием назовем окончание предложения, начинающееся с результатного выражения, входящего в условие.
Результатным (соответственно, образцовым) блоком назовем последовательность результатных (образцовых) окончаний, заключенную в фигурные скобки. После правой фигурной скобки может стоять необязательная точка с запятой. Разрешим также опускать точку с запятой перед правой фигурной скобкой. Заметим, что тело функции - это образцовый блок.
Теперь в качестве результатного (образцового) окончания разрешим использовать результатный (образцовый) блок. Для полноты картины, в качестве тела функции будем допускать не только блок, но и образцовое окончание, т.е. наружные фигурные скобки могут опускаться, если тело состоит из одного окончания.
При исполнении блок заменяется на одно из входящих в него окончаний. Вначале делается попытка использовать первое окончание. Но если его исполнение завершается неуспехом, то выбирается второе, и т.д. Если же последнее окончание блока оканчивается неуспехом, то весь блок оканчивается аварийно. (В Рефале-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;
};
Здесь после вызова функции COMPARE используется образцовый блок: все его окончания начинаются
с образцов. Результатное выражение <COMPARE tA
tB> вычисляется один раз перед входом в блок,
после чего поочередно сопоставляется с
каждым из образцов.Если условия на разных предложениях имеют разные источники (результатные выражения), то следует использовать результатный блок. Покажем это на примере функции Compset, сравнивающей два множества на включение: не является ли одно подмножеством другого. Предполагаем, что функция Diff, вычисляющая разность двух множеств уже определена (см. упражнение 1 в разделе 1.5):
Compset (e1) (e2) , {
<Diff (e1) (e2)> : = '<';
<Diff (e2) (e1)> : = '>';
: = '?';
};
Обратите внимание на двоеточие в третьем окончании. Оно выражает
условие, которое всегда истинно: пустота сопоставляется с
пустотой.Функция Merge фактически вычисляет объединение упорядоченных множеств. Напишите функции, вычисляющие пересечение, разность и симметрическую разность упорядоченных множеств. Результат должен быть также упорядоченным. Оцените время их работы.