Модель вычислений и Рефал-программа
Основные два шага в Рефал-вычислениях — конкретизация переменных в образце в соответствии с областью зрения и подстановка полученных значений в другое метавыражение. В языке рассматривается лишь частный случай конкретизации.
Конкретизация образца Me в объектное выражение E называется такая подстановка значений вместо переменных Me, что после применения данной подстановки Me совпадет с E.
Заметим, что одно и то же метавыражение может иметь много конкретизаций в одно и то же объектное выражение. Например, рассмотрим метавыражение
e.Begin s.Middle e.End (5.3)
и объектное выражение
AhAhAh 'OhOhOh' (Ugu','Udgu) '(((' Basta'!' (5.4)
Имеется 11 вариантов конкретизации (5.3) в (5.4) (проверьте!).
Если у метавыражения Me есть много вариантов конкретизации в E, то они упорядочиваются по предпочтительности в следующем порядке.
Пусть Env1 и Env2 — два варианта конкретизации Me в P. Рассмотрим все вхождения переменных в Me. Если Env1 и Env2 не совпадают, они приписывают некоторым переменным различные значения. Найдем в P самое первое слева вхождение переменной, которому Env1 и Env2 приписывают разные значения и сравним длину этих значений. Та из конкретизаций, в которой значение, приписываемое данному вхождению переменной, короче, предшествует другой и имеет приоритет перед ней.
Например, сопоставим объектное выражение (A1 A2 A3)(B1 B2) с образцом e.1 (e.X s.A e.Y) e.2. В результате получится следующее множество вариантов сопоставления:
{e.1 = , eX = , sA = A1, eY = A2 A3, e.2 = (B1 B2) } {e.1 = , eX = A1, sA = A2, eY = A3, e.2 = (B1 B2) } {e.1 = , eX = A1 A2, sA = A3, eY = , e.2 = (B1 B2) } {e.1 = (A1 A2 A3), eX = , sA = B1, eY = B2, e.2 = } {e.1 = (A1 A2 A3), eX = B1, sA = B2, eY = , e.2 = }
Пример 5.1. Множество вариантов сопоставления
Варианты сопоставления перечислены в соответствии с их приоритетами, т. е. самый первый вариант находится на первом месте и т. д. Описанный способ упорядочения вариантов сопоставления называется сопоставлением слева направо.
Тот алгоритм конкретизации, который используется в Рефале, называется проецированием и согласован с введенным нами отношением порядка. Опишем его (описание взято из учебника Турчина [38]). Обратите внимание, как в данном случае общая и не всегда эффективно реализуемая операция 'проецируется' на свою частную реализацию, одновременно повышающую эффективность, сохраняющую общность и предписывающую методику программирования.
