Образцы и клозы

Нотация абстрактного языка

Необходимо отметить, что в нотации абстрактного функционального языка, который использовался до сих пор для написания примеров функций, можно было бы использовать такую конструкцию, как if-then-else. Например, при описании функции Append (см. пример 7), её тело можно было бы записать следующим образом:

Append (L₁, L₂) = if (L₁ == []) then L₂

else head (L₁) : Append (tail (L₁), L₂)

Однако данная запись чревата непониманием и трудным разбором. Поэтому даже в примере 7 была использована нотация, которая поддерживает так называемые «образцы».

Определение:

Образцом называется выражение, построенное с помощью операций конструирования данных, которое используется для сопоставления с данными. Переменные обозначаются прописными буквами, константы — строчными.

Примеры образцов:

5 — просто числовая константа

X — просто переменная

X : (Y : Z) — пара

[X, Y] — список

К образцам предъявляется одно требование, которое должно выполняться беспрекословно, иначе сопоставление с образцами будет выполнено неверно. Требование это звучит следующим образом: при сопоставлении образца с данными означивание переменных должно происходить единственным образом. Т.е., например, выражение (1 + X Þ 5) можно использовать как образец, т.к. означивание переменной X происходит единственным образом (X = 4), а выражение (X + Y Þ 5) использовать в качестве образца нельзя, ибо означить переменные X и Y можно различным образом.

Кроме образцов в функциональном программировании вводится такое понятие, как «клоз» (от англ. «clause»). По определению клозы выглядят так:

def f p₁, ..., p_n = expr

где:

def n = — константы абстрактного языка

f — имя определяемой функции

p_i — последовательность образцов (при этом n ³ 0)

expr — выражение

Таким образом, определение функции в функциональном программировании есть просто последовательность клозов (возможно состоящая из одного элемента). Для того, чтобы упростить запись определений функций, далее слово def будет опускаться.

Пример 9. Образцы и клозы в функции Length.

Length ([]) = 0

Length (H:T) = 1 + Length (T)

Пусть вызов функции Length произведен с параметром [a, b, c]. В этом случае начнет свою работу механизм сопоставления с образцом. Последовательно перебираются все клозы и делаются попытки сопоставления. В данном случае удачное сопоставление будет только во втором клозе (т.к. список [a, b, c] не пуст).

Интерпретация вызова функции заключается в нахождении первого по порядку сверху вниз образца, успешно сопоставимого с фактическим параметром. Значение переменных образца, означиваемые в результате сопоставления, подставляются в правую часть клоза (выражение expr), вычисленное значение которой в данном контексте объявляется значением вызова функции.