[ Вызов функции по определению.
(Семинар №7 29.03.2006)
А. П. Немытых1, *
1 Институт программных систем РАН
Кроме вызова функции по имени, то есть через указание имени
данного определения функции, а не самого определения, синтаксис РЕФАЛа
позволяет определить функцию непосредственно в точке её вызова, если
обращение к такой функции в программе происходит лишь один раз. Начиная с этого места нашего изложения мы выходим за рамки базисного РЕФАЛа.
1. БЛОКИ Вызов функции по определению иногда бывает удобен с точки зрения прозрачности исходного текста программы. Напомним, что в базисном РЕФАЛе определение функции имеет вид последовательности предложений, заключённой в фигурные скобки;
а имя функции ставится перед её определением:
FunctionName { sentence1 ;
.........
sentencen ;
}, где левая и правая части предложений разделены знаком равенства. Таким образом, определение само по себе (без имени) есть:
{ sentence1 ;
.........
sentencen ;
} * Electronic address: [email protected] Если мы хотим определить функцию непосредственно в точке её вызова, то вместо имени функции (его у нас теперь нет) мы пишем сам текст определения, а аргументы этого вызова пишем перед фигурной скобкой, открывающей данное имя, отделив их от скобки знаком двоеточия :. Непосредственно за вызовом функции по определению всегда ставится точка с запятой ;. Например, вызов ’abcd’ (e.x) : { e.y (e.y) = True;
e.y (e.z) = False;
};
определяет совпадает ли значение переменной e.x со строкой ’abcd’, а вызов (e.x) : { e.y (e.y) = True;
e.y (e.z) = False;
};
определяет совпадает ли значение результата вызова (по имени) функции F со значением переменной e.x.
Теперь мы расширим понятие РЕФАЛ предложения: кроме предложений допускаемых базисным РЕФАЛом, введём предложения, в которых левая часть отделяется от правой части запятой (а не знаком равенства, как в базисном, РЕФАЛе). Мы потребуем, чтобы в этом случае в правой части предложения (после запятой) обязательно стоял один вызов функции по определению, и только он.
Естественно, мы допускаем вызовы по определению внутри любого определения – поименованного или непоименованного.
Пример №1: Следующая функция S-Type определяет какого типа символ подан ей в качестве аргумента и сообщает об ошибке, если аргумент не является РЕФАЛсимволом. Мы предварительно, используя встроенную функцию Lower, преобразуем все прописные буквы имени данного символа в строчные.
S-Type { s.x, : { True = Letter;
False = Other;
};
e.y = "Wrong argument: " e.y;
} BelongsTo { s.x (e.y s.x e.z) = True;
s.x (e.y) = False;
} Letters { = ’abcdefghijklmnopqrstuvwxyz’ ’абвгдеёжзийклмнопрстуфхцчшщъыьэюя’;
} Заметим, что =. Причина сего в том, что ’f’ есть символбуква, а f есть символ-слово, имя которого состоит из одной буквы.
Рассмотрим общий вид РЕФАЛ предложения с вызовом функции по определению:
pattern, argument : { sentence1 ;
.........
Множество переменных, входящих в образец pattern, может пересекаться с множеством переменных входящих в некоторое предложение sentencei. Например, t.x e.y, : { Здесь первые два предложения (функции, вызванной по определению) содержат в левых частях переменные из образца t.x e.y основного предложения (вызывающего функцию по определению), а третье предложение содержит в правой части переменные из того же образца. Как понимать такую ситуацию? Какой смысл приписать подобному синтаксису? Семантика подобного синтаксиса в РЕФАЛе следующая: значения всех переменных, которые определились до запятой, РЕФАЛ машина подставляет и в аргумент, и в само определение вызова функции по определению; и только после этого вычисляет указанный вызов (естественно, предварительно вычислив его аргументы).
Следовательно, в третьем предложении нет синтаксической ошибки, ибо в момент вызова оно превратится в, где e.y0 и t.x0 конкретные данные (константы) – значения переменных e.y и t.x.
Пример №2: Следующая функция a-z { e.1 ’a’ e.2, e.2: { выделяет первое вхождение в данном тексте строки, начинающейся на ’a’ и кончающейся на ’z’. В последнем предложении мы экранировали две одинарные кавычки символом \, так как они заключены в другую пару одинарных кавычек.
Задача 1 Рассмотрим другое определение функции из примера №2:
a-z-1 { e.1 ’a’ e.2 ’z’ e.3 = (e.1) ’a’ e.2 ’z’ (e.3);
Объясните, почему определение a-z более эффективно, чем определение a-z-1 (то есть РЕФАЛ данное d0 такое, что время вычисления вызова будет значительно меньше времени вычисления вызова )?
Вызов функции по определению в РЕФАЛе принято называть блоком. Присутствие блока в определении функции F приводит к неопределённости понятия шага РЕФАЛ машины при исполнении F: шаг функции F ещё не завершился, а уже внутри него начинают вычисляться вызовы функции, готовящие аргументы – входные данные для блока, да и сам блок вычисляется до окончания рассматриваемого шага функции F.
Задача 2 Провести пошаговый просмотр выполнения программы из примера № посредством отладчика. Понять и объяснить какое действие РЕФАЛ машины отладчик воспринимает за шаг РЕФАЛ-5 машины. Изучить поведение отладчика на последовательность команд p act; com res;.
Задача 3 Глубину пустого выражения положим равной нулю. Глубина Depth РЕФАЛ-символа также, по определению, равна нулю. Depth((e.d)) = 1+Depth(e.d).
Глубиной выражения называется максимум глубин всех термов, входящих в это выражение. Определить на РЕФАЛе функцию, значение которой есть глубина данного выражения.
Задача 4 В данном РЕФАЛ-выражении (со скобками) уничтожить первое вхождение символа ’a’, если таковое существует.
Задача 5 Даны две конечные неубывающие последовательности макроцифр.
Построить неубывающую последовательность, элементами которой являются все элементы (включая их кратные вхождения) двух данных последовательностей.
Задача 6 Нарисовать ёлочку на экране компьютера средствами псевдографики.
Высота ёлочки должна быть равна высоте экрана.
Задача 7 Дана конечная последовательность макроцифр x1 = 1, xn+1 = 1 + xn.
Построить все различные перестановки данной последовательности.
Задача 8 Дана симметрическая группа перестановок Sn. Придумать представление элементов этой группы во множестве данных РЕФАЛа и реализовать групповые операции умножения и построения элемента обратного к данному элементу.
Задача 9 Рассмотрим полугруппу по умножению квадратных матриц размера nn, состоящих из целых чисел. Придумать представление элементов этой полугруппы как данных РЕФАЛа и реализовать операцию умножения двух матриц.
«