Теперь рассмотрим второй фундаментальный механизм — подстановку значений в результатное выражение или короче построение результата. Но для начала введём пару определений.
Активным выражением называется объектное выражение, пополненное особыми термами — скобками вызова функции (синонимы: скобки активации, скобки конкретизации). Скобки активации имеют следующий вид:
<ИмяФункции активное-выражение>В отличие от записи, традиционно принятой в математике и во многих языках программирования, в Рефале имя функции ставится не перед скобкой: f(x), а после неё: <F x>.
Имя функции записывается точно также, как и атом-идентификатор (начинается с заглавной буквы латинского алфавита, после которой могут быть заглавные или строчные латинские буквы, цифры или символы - и _. Если функция определена в другом модуле, то её имя предваряется именем модуля (которое тоже записывается как идентификатор), отделённое символом точки и квадроточием.
Объектные выражения являются подмножеством активных выражений. Примеры активных выражений:
<Fab 5>
<MMath::Add <Fab 4> <Fab 3>>
<MMath::Add 3 5>
[Table
<RemoveDuplicates ('Xz') ('Eg') ('Pq') ('Eg') ('Xz')>
]
<Lookup ('Cd') ('Ab' 13) ('Cd' 42) ('Ef' 666)>
Success 'Cd' 42
NotFound 'Gh'
FileNotFound
<MInOut::WriteLine 'Hello, World!'>
Результатное выражение (результат, result) представляет собой запись активного выражения, содержащего переменные. Если подставить в результатное предложение вместо переменных их значения, то получится активное выражение. Результатное выражение может не содержать переменных, в этом случае его запись совпадает с активным выражением. Если результатное выражение не содержит ни переменных, ни скобок активации, то оно совпадает с объектным выражением.Примеры результатных выражений:
<Fab s.Number> <MMath::Add <Fab <MMath::Sub s.Num 1>> <Fab <MMath::Sub s.Num 2>> > [Table <RemoveDuplicates e.Words>] <Lookup (e.VarName) e.Variables> Success e.Var s.Val NotFound e.Var FileNotFound <MInOut::WriteLine 'Hello, World!'> <MInOut.WriteLine 'Hello, World!'>Последние две строчки семантически ничем не отличаются, обе означают вызов функции WriteLine из модуля MInOut. В остальном, я думаю, всё понятно.
Предложения и функции
Предложением называется конструкция вида
образцовое_выражение = результатное_выражение;Говоря о предложениях, образец часто называют левой частью, результат — правой частью. В правой части могут использоваться только те переменные, которые определены в левой части.
Функция в Модульном Рефале представляет собой набор предложений, заключённый в фигурные скобки. Синтаксис функций
[ $ENTRY ] ИмяФункции {
образцовое_выражение1 = результатное_выражение1;
образцовое_выражение2 = результатное_выражение2;
. . .
образцовое_выражениеN = результатное_выражениеN;
}Квадратные скобки вокруг ключевого слова $ENTRY говорят о том, что его можно опустить. Функция, у которой ключевое слово $ENTRY присутствует, видна из других модулей, такая функция называется entry-функцией. Если ключевое слово $ENTRY отсутствует, то функция называется локальной и она не видна из других модулей.Функция выполняется следующим образом. Пусть требуется выполнить вызов функции с некоторым аргументом:
<ИмяФункции аргумент>где аргумент функции — некоторое объектное выражение. Далее, аргумент сопоставляется с левой частью первого предложения. Если сопоставление оказывается успешным, то значения переменных, определённых в образце, подставляются в правую часть и вызов функции заменяется на получившийся результат (активное выражение).
Если же сопоставление с образцом в первом предложении оказалось неуспешным, точно таким же образом выполняется второе предложение и т. д. Если сопоставление не удалось в левой части последнего предложения, то программа падает с ошибкой невозможности сопоставления (recognition impossible).
Обычно в левых частях выражений рассматриваются различные варианты допустимых аргументов, поэтому ошибка невозможности сопоставления часто говорит о том, что или на вход функции был передан некорректный аргумент, или сама функция написана с ошибкой.
Таким образом, в Рефале чётко разделены операции анализа аргумента, выполняемые при помощи сопоставления с образцом, и операции синтеза, осуществляемые при помощи подстановки значений переменных в результатное выражение.
Примеры функций
Функция, вычисляющая n-е число Фибоначчи.
Fab {
0 = 1;
1 = 1;
s.N =
<MMath::Add
<Fab <MMath::Sub s.N 1>>
<Fab <MMath::Sub s.N 2>>
>;
}Вызывается как <Fab число>. Первые два предложения означают, что нулевое и первое числа Фибоначчи равны 1, третье предложение предложение задаёт правило для вычисления бо́льших значений: следующее число Фибоначчи равно сумме двух предыдущих. Библиотечные функции MMath::Add и MMath::Sub выполняют, соответственно, сложение и вычитание.Рассмотрим эту функцию поподробнее. В вызове <Fab 1> аргументом функции будет объектное выражение 1. Сначала выполняется первое предложение: происходит сопоставление с образцом 0. Сопоставлнение 1 : 0 оказывается неуспешным, осуществляется переход к следующему предложению. Во втором предложении сопоставление 1 : 1 оказывается успешным — происходит замена вызова <Fab 1> на правую часть с подстановкой переменных. Поскольку переменных в этом предложении нет, то вызов функции просто заменяется на
Вызов <Fab 5> осуществляется несколько сложнее. Первые два предложения, очевидно, не подходят, так как аргумент 5 невозможно отождествить ни с 0, ни с 1. Левая часть третьего предложения состоит из одной s-переменной, то есть может успешно сопоставиться с любым объектным выражением, состоящим из одного атома. Поскольку аргумент представляет собой один атом-число, сопоставление происходит успешно и переменная s.N получает значение 5. После этого вызов функции <Fab 5> заменяется на правую часть последнего предложения с подстановкой вместо переменной s.N значения 5. Таким образом, результатом вычисления функции становится
<MMath::Add <Fab <MMath::Sub 5 1>> <Fab <MMath::Sub 5 2>> >Полезно также рассмотреть случай вызова функции Fab с некорректным аргументом, например <Fab 'Xyzzy'>. В этом случае ни одно из предложений не выполнится (так как пять атомов аргумента невозможно сопоставить ни с одной из левых частей) и программа остановится с выдачей ошибки невозможности сопоставления с образцом.
Рассмотрим другой пример. Функция
Lookup {
(e.Var) e.B (e.Var s.Val) e.E = Success e.Var s.Val;
(e.Var) e.ValueTable = Fails e.Var;
}и вызовы<Lookup ('Cd') ('Ab' 13) ('Cd' 42) ('Ef' 666)>
<Lookup ('Gh') ('Ab' 13) ('Cd' 42) ('Ef' 666)>Рассмотрим первый вызов. Сначала выполняется сопоставление с левой частью первого предложения. Первый скобочный терм аргумента ('Cd') успешно отображается на первый скобочный терм образца (e.Var), в результате чего переменная e.Var связывается со значением 'Cd'.Следующим шагом становится отображение оставшейся части аргумента из трёх скобочных термов на часть аргумента e.B (e.Var s.Val) e.E. Переменная e.B в этом примере является открытой, внутри (e.Var s.Val) переменная e.Var является повторной, так как она уже связана со своим значением. В этом случае, единственным значением переменной e.B, при котором сопоставление возможно, будет значение ('Ab' 13), тогда переменная s.Val свяжется со значением 42, а переменная e.E — со значением ('Ef' 666).
В результате подстановки значений переменных в правую часть мы получим результат выполнения функции Success ('Cd') 42.
Рассмотрим второй вызов. Выполнение функции начнётся с выполнения первого предложения, и точно также, как и в предыдущем случае, терм аргумента
('Gh') успешно отобразится на терм образца (e.Var). Однако, сопоставление с оставшейся частью образца окажется невозможным. Следовательно, сопоставление с левой частью первого предложения окажется неуспешным.Управление будет передано второму предложению. Здесь первый терм аргумента
('Gh') успешно отобразится на терм образца (e.Var), а остаток аргумента успешно отобразится на e.ValueTable. После успешного сопоставления с образцом управление будет передано на правую часть, вызов функции заменится на Fails 'Gh'.Важно отметить, что в тексте программы записываются только образцовые и результатные выражения, а во время выполнения программы существуют только объектные и активные выражения. Образцовые выражения при компиляции программы превращаются в код анализа объектных выражений, результатные выражения — в код синтеза активных выражений.
Эффективность построения результата
Как и в случае сопоставления с образцом, хочется сказать несколько слов о том, насколько быстро выполняются те или иные операции.
Следует отметить, что различные реализации Рефала операции сопоставления с образцом выполняют, как правило, с одинаковой сложностью (постоянная сложность для простых операций, рекурсивное сравнение для повторных переменных, линейная сложность для открытых переменных), чего нельзя сказать о построении результата. Сложность выполнения отдельных операций построения результата существенным образом зависит от структур данных, используемых для представления объектных и активных выражений.
Текущая реализация Модульного Рефала использует для представления объектных и активных выражений двусвязный список, в котором отдельным элементам: атомам, структурным скобкам, скобкам АТД, скобкам вызова функции и именам функций после скобок вызова поставлены в соответствие узлы этого списка — так называемая классическая списковая реализация. Соответственно, Модульному Рефалу свойственны следующие особенности быстродействия этой реализации.
- Конкатенация двух объектных выражений выполняется эффективно, то есть за постоянное время. Для других известных реализаций: списковой и векторно-списковой, конкатенация выполняется за время, пропорциональное длине конкатенируемых выражений в термах (векторно-списковая реализация позволяет избегать во многих случаях лишних конкатенаций).
- Подстановка значений переменных в правую часть выполняется путём переноса объектного выражения из аргумента. Если в левой части некоторая переменная повторяется n раз, а в правой — m раз,
- то если n ≥ m, значения переменных просто переносятся за в результат за постоянное время.
- Если же n < m, то (m − n) переменных приходится копировать, а операция копирования выполняется за время, пропорциональное длине списка, необходимого для представления переменной. Длина списка пропорциональна сумме длин в термах самого выражения, а также всех вложенных подвыражений, находящихся в круглых и квадратных скобках плюс ещё сами скобки.
Подробнее об эффективности операций в списковых реализаций можно прочитать в руководстве к Рефалу 5: здесь и здесь.
