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);