1.5.2. ПЕРЕСТРОЙКИ
Рассмотрим следующую задачу: пусть нам задано некоторое объектное выражение
Oe, которое заведомо содержит на нулевом уровне не менее двух символов-литер '+'. Требуется разбить это выражение Oe на три части OeX, OeA и OeY, такие, что Oe = OeX '+' OeA '+' OeY, и при этом OeX и OeY не содержат '+' на нулевом уровне скобок. Функцию, решающую данную задачу назовем "++". Тогда, например<"++" 'AAA+BBB+CCC+DDD+EEE'> =>
('AAA')('BBB+CCC+DDD')('EEE')
Таким образом, требуется найти в Oe самый левый '+' и самый правый '+'. Самый левый '+' легко найти с помощью сопоставления Oe с образцом $l eX '+' eP, а самый правый - с помощью сопоставления с образцом $r eQ '+' eY. Внутри одного образца сопоставление выполняется либо слева направо, либо справа налево, поэтому мы не можем объединить эти два образца в один, и вынуждены выполнять сопоставление в два приема. Таким образом, мы можем решить задачу следующим образом:$func "++" eZ = (eX)(eA)(eY);
$func "++Aux" (eX)(eP) = (eX)(eA)(eY);
"++" $l eX '+' eP = <"++Aux" (eX)(eP)>;
"++Aux" $r (eX)(eA '+' eY) = (eX)(eA)(eY);
Мы видим, что из-за необходимости выполнять анализ выражения в два этапа, пришлось ввести вспомогательную функцию. Однако, без этого можно было бы обойтись. Перестройками называются тропы видаS : Snt
где S - источник, а Snt - предложение вида P R, состоящее из образца P и хвоста R. Если хвост R состоит из одной запятой, его разрешается опускать, в результате чего перестройка принимает вид S : P. Вычисление перестроек производится следующим образом. Сначала вычисляется S. Если получится неуспех, то результатом всей перестройки считается неуспех. Если же в результате вычисления S получится объектное выражение Oe, то Oe сопоставляется с образцом P. При этом на рассматриваемые варианты сопоставления накладывается дополнительное ограничение: если в той среде, в которой вычисляется перестройка, значения некоторых переменных уже определены, то рассматриваются только те варианты сопоставления, для которых эти переменные сохраняют прежние значения. Например, если переменная sX уже имеет значение 1, то в результате сопоставления объектного выражения 1 2 1 2 с образцом eA sX eB получатся только два варианта сопоставления{eA = , sX = 1, eB = 2 1 2}
{eA = 1 2, sX = 1, eB = 2}
а не четыре. Пусть теперь Env1, Env2, ..., Envn - все получившиеся варианты сопоставления, перечисленные в соответствии с порядком, введенным ранее для вариантов сопоставления. Далее делается попытка вычислить R, используя значения переменных из первого варианта сопоставления. Если результатом вычисления R является объектное выражение Oe, оно и считается результатом перестройки. Если же вычисление хвоста R завершилось неуспехом , то этот неуспех "перехватывается", т.е. самый первый вариант сопоставления отбрасывается и делается попытка точно так же вычислить R для оставшихся вариантов сопоставления. Если для всех вариантов сопоставления результатом вычисления хвоста R является неуспех, то и результатом всей перестройки является неуспех. Например, вычисление тропы'ABC' : $r e1 sX e2, <Print sX> $fail
приведет к тому, что будет напечатанa последовательность литер 'CBA', после чего вычисление тропы завершится с результатом "неуспех".Теперь мы можем дать новое определение функции "++"
, не использующее вспомогательную функцию "++Aux":$func "++" eZ = (eX)(eA)(eY);
"++"
$l eX '+' eP,
eP : $r eA '+' eY
= (eX)(eA)(eY);