Образцовое выражение (образец, pattern) представляет собой запись выражения, которое, в отличие от объектного выражения, может содержать переменные — неизвестные части. Если вместо переменных в образцовое выражение подставить конкретные значения, то получится объектное выражение.
Переменные записываются в виде символ-типа.ИмяПеременной, где
В Модульном Рефале переменные могут быть трёх типов: s-переменные, значением которых могут быть только атомы (в традиционной терминологии символы), t-переменные, значением которых могут быть только термы, и
Сопоставлением объектного выражения E с образцом P называется поиск значений переменных, входящих в образец P, подстановка которых в P даёт выражение E. Если такие значения найти невозможно, то сопоставление считается неуспешным. Будем обозначать сопоставление объектного выражения E с образцом P как E : P.
Если в образце присутствует несколько вхождений переменных с одинаковым типом и одинаковым именем, то такие переменные называются повторными. Все вхождения повторной переменной должны иметь одинаковое значение. В образце не может быть переменных, имеющих одинаковое имя, но при этом разные типы.
Рассмотрим для примера следующие сопоставления
'суббота' : e.Begin s.R s.R e.End успешно:
e.Begin = 'су', s.R = 'б', e.End = 'ота'
('Cd') ('Ab' 13) ('Cd' 42) ('Ef' 666) :
(e.Var) e.B (e.Var s.Val) e.E также успешно:
e.Var = 'Cd', e.B = ('Ab' 13'),
e.E = ('Ef' 666), s.Val = 42
('Gh') ('Ab' 13) ('Cd' 42) ('Ef' 666) :
(e.Var) e.B (e.Var s.Val) e.E неуспешно
'оборона' : e.Begin 'о' e.End
успешно, причём возможно несколько вариантов:
e.Begin = пустое выражение, e.End = 'борона'
e.Begin = 'об', e.End = 'рона'
e.Begin = 'обор', e.End = 'на'
'cat' : 'dog' неуспешно
Success 'Ef' 42 : Success e.VarName s.Value
успешно: e.VarName = 'Ef', s.Value = 42
NotFound 'Gh' : Success e.VarName s.Value
неуспешно
В этих примерах s.R и e.Var повторные переменные.
Если существует несколько вариантов сопоставления, то выбирается тот, в котором первая переменная (при чтении слева-направо) принимает кратчайшее значение (имеется ввиду длина в термах). Если это правило не устраняет неоднозначности, то анализируется следующая переменная и т. д. Очевидно, что для разрешения неоднозначности достаточно рассматривать только
'одновременно' : s.First e.Beg s.Rep e.Mid s.Rep e.End Варианты сопоставления: s.First = 'о', e.Beg = 'д', s.Rep = 'н', e.Mid = 'овреме', e.End = 'но' s.First = 'о', e.Beg = 'д', s.Rep = 'н', e.Mid = 'овремен', e.End = 'о' s.First = 'о', e.Beg = 'дн', s.Rep = 'о', e.Mid = 'временн', e.End = s.First = 'о', e.Beg = 'дновр', s.Rep = 'е', e.Mid = 'м', e.End = 'нно' s.First = 'о', e.Beg = 'дновреме', s.Rep = 'н', e.Mid = , e.End = 'о'
Выбор кратчайшего значения первой e-переменной e.Beg = 'д' не разрешает неоднозначности, поэтому рассматриваем следующую e-переменную e.Mid. Выбор кратчайшего значения e.Mid = 'однореме' устраняет неоднозначность, определяя тем самым первый вариант сопоставления.
Важно отметить, что не все e-переменные, присутствующие в образце, участвуют в разрешении неоднозначности. В примере выше переменные e.Beg и e.Mid влияют на выбор варианта сопоставления, так как могут принимать различные значения (относительно) независимо друг от друга. В то время, как переменная e.End однозначно определяется значениями других переменных.
Ещё один пример:
(1 2 2 3) ('ABBC') : (e.B1 2 e.E1) (e.B2 'B' e.E2)
Варианты:
e.B1 = 1, e.E1 = 2 3, e.B2 = 'A', e.E2 = 'BC' (1)
e.B1 = 1 2, e.E1 = 3, e.B2 = 'A', e.E2 = 'BC' (2)
e.B1 = 1, e.E1 = 2 3, e.B2 = 'AB', e.E2 = 'C' (3)
e.B1 = 1 2, e.E1 = 3, e.B2 = 'AB', e.E2 = 'C' (4)
Тут также будет выбран первый вариант. Здесь на разрешение неоднозначности будут влиять только переменные e.B1 и e.B2: в вариантах с кратчайшим значением e.B1 (строки 1 и 3) значение e.E1 будет одинаково, поэтому анализируется значение переменной e.B2.
E-переменные, способные влиять на разрешение неоднозначности, называются открытыми. В примерах выше открытыми переменными были e.Begin (в примере со словом суббота), e.B, e.Begin (в примере со словом оборона), e.Beg, e.Mid, e.B1 и e.B2.
Обычно сопоставление с открытой e-переменной осуществляется путём её последовательного удлинения: сначала открытая переменная получает значение пустого объектного выражения, если при этом сопоставление с остальной частью образца невозможно, то она удлиняется на один терм, и попытка сопоставления повторяется. E-переменная продолжает итеративно удлиняться до тех пор, пока или не произойдёт успешное сопоставление, или достигнет своего максимального значения.
Следует помнить, что сопоставление с открытыми переменными выполняется в самую последнюю очередь, после того, как сопоставятся все остальные элементы образца.
Эффективность сопоставления с образцом
Операции компьютер выполняет не мгновенно, и сопоставление с образцом не является исключением. Также очевидно, что разные образцы могут выполняться за разное время. При помощи следующих правил можно оценить сложность сопоставления с конкретным образцом.
- Простые операции: сопоставление с атомом,
s-переменной , с парой скобок выполняются за постоянное время. - Повторная t- или
e-переменная требует рекурсивного сравнения объектных термов или объектных выражений, соответственно, поэтому сложность сопоставления линейно зависит от числа атомов и скобок, входящих в сравниваемые выражения. Пара повторных переменных требует одного сравнения, 3 переменных — двух сравнений и т. д. - Сложность сопоставления каждой открытой e-переменной линейно зависит от длины «сканируемого» объектного выражения, поэтому одна
e-переменная добавляет линейную сложность, две — квадратичную сложность, три — кубическую сложность.
