Как мы видели, в языке Athanor большая часть реальной вычислительной работы выполняется функторами. Они реализуют как сами манипуляции над числовыми (add/sub/mul/div …) и строковыми (s_cat/s_rep …) значениями, так и управление потоком вычисления (if/unless/while/until …) и ввод/вывод (f_get/f_put …). Можно сказать, что 90—95% выполнения программы — это выполнение/вычисление функторов. Заметим, что все функторы, которые пока нам встречались — были предопределенными (и встроенными в систему). Но пользователь без труда может определить и свои собственные функторы, работа с которыми (в большинстве случаев) не сложнее, чем со встроенными. Это — основной механизм, реализующий расширение языка.
Чтобы функтор стал доступен, его надо декларировать. В самом общем виде декларация выглядит так:
Здесь:
Обязательными элементами в этом описании являются только имя функтора и его тело. Если у описываемого функтора вообще нет параметров (т. е. он является нульарным), то список параметров может быть просто опущен (и даже вместе с окружающими его круглыми скобками). Если у функтора нет локальных переменных, их список также может быть опущен (вместе с окружающими квадратными скобками и предшествующим ему двоеточием). Тело функтора должно быть непустым, им может быть произвольное выражение (которым, на практике, чаще всего является блок). Впрочем, телом может быть даже пустое значение () или [], или же пустой блок {} — это вполне законно, хотя пользы от такого функтора немного.
Заметим, что разделителями (в списках параметров и локальных переменных) являются пробельные символы или их последовательности. Запятые здесь не требуются!
Декларация функтора создает свою собственную область видимости (т.н. пространство имен), в которой локализуются как все его параметры (par1 … parM), так и локальные переменные (loc1 … locN). По умолчанию все они недоступны за пределами функтора (но доступны в его теле). В своей области видимости локальные переменные временно замещают внешние с теми же именами, если такие имеются. Любая переменная, не декларированная в каком-то из этих двух списков, рассматривается как глобальная.
После того как функтор декларирован полностью, его можно вызывать (то есть обращаться к нему). Синтаксис вызова совершенно тот же, что и для системных функторов:
— это вызов функтора funcname с аргументами (arg1, arg2, ... argN). При вызове функтора автоматически создаётся его локальный контекст (из параметров и локальных переменных), а параметрам присваиваются значения всех аргументов по порядку. Локальным переменным ничего не присваивается, точнее, они получают значение (). Затем выполняется (и вычисляется) тело функтора body, значением которого и становится результат вызова функтора. После того как функтор выполнен, все аргументы и локальные переменные очищаются, их значения уничтожаются. Всякий функтор в языке возвращает значение (но им, конечно, может быть и (), то есть пустота).
Если функтору передаётся ровно столько же аргументов, сколько у него декларировано параметров, то всё вполне очевидно — но что, если их число не совпадает? В общем случае применяется семантика спискового присваивания, довольно подробно описанная в статье 7. Напомню главное сформулированное там правило: если аргументов передано меньше, чем параметров, параметры, которым «не хватило» значений, просто получат значения (), как и все локальные переменные. Если же аргументов больше, чем параметров, то весь не присвоенный «хвост» списка аргументов присваивается последнему параметру (также в виде списка), и ни одно значение из него не «пропадает»! Сами параметры также могут быть (и нередко бывают) списками с произвольной глубиной вложенности.
Это свойство очень полезно для описания функторов с нефиксированной арностью (то есть переменным числом аргументов). Если у нас есть функтор:
— то его можно вызвать примерно так:
В этом случае параметр form_string получит своим значением строку «User %s, hello from %s!», а параметр arguments — список (user, host). После чего уже совсем нетрудно разобрать содержимое форматной строки и подставить вместо форматов (вроде %s) нужные аргументы по порядку. Вообще, функторы с переменным количеством аргументов реализуются в языке тривиально. В самом «экстремальном» случае вполне можно написать в заголовке просто functor (arglist) — тогда любой список аргументов передаётся функтору целиком, и интерпретация arglist целиком перекладывается на него.
До некоторой степени это напоминает передачу параметров в языке Perl — когда все параметры передаются в виде одного списка-массива "@_" (а разбирать его на элементы уже должна сама функция). Как видите, и в Athanor так тоже можно (но, когда количество и интерпретация параметров более-менее однозначны, их лучше сразу включать в заголовок декларации функтора).
И ещё один важный момент! Функтор считается декларированным (т.е. доступным для вызова) сразу после того, как декларирован его заголовок (и ещё до того, как полностью определено его тело). Практически это означает, что в теле декларируемого функтора уже можно обращаться к нему самому (то есть вызывать его рекурсивно). Рекурсивные вызовы могут быть вложенными на большую глубину (при этом каждый вызов имеет свой собственный локальный контекст, то есть набор локальных переменных и параметров).
Приведём несколько примеров. Определим что-нибудь полезное, чего в стандартном математическом наборе нет — например, факториал от N (N!):
! factor (N) = N > 1 ? N * factor (N - 1) : 1;
Это пример рекурсивного определения: функция от N определяется через себя для (N-1), пока мы не спустимся до 1 (для которого факториал равен 1 по определению). Это определение настолько простое, что умещается в одну строку (и нам даже не требуются локальные переменные). Конечно, факториал можно определить и итеративно (но тут уже потребуются и локальные переменные, и блок):
! factor (N) : [i Fac] =
N > 1 ? {
Fac = 1;
for_inc (i, N, Fac =*: i + 1);
Fac }
: 1;
Оба определения работают одинаково, в этом нетрудно убедиться:
for_inc (n, 1..13, <: (n, "! = ", factor (n), "\n"));
В результате получим:
1! = 1 2! = 2 3! = 6 4! = 24 5! = 120 6! = 720 7! = 5040 8! = 40320 9! = 362880 10! = 3628800 11! = 39916800 12! = 479001600
Факториал — довольно быстро растущая функция: как бы мы его ни вычисляли, мы очень скоро столкнёмся с арифметическим переполнением (конечно, если не перейдём от целых чисел к плавающим — но тогда есть риск получить сомнительные результаты). Попробуем теперь определить субфакториал. Если факториал от N — это число всех возможных перестановок из N элементов, то субфакториал от N (он обозначается !N) — это именно число «неправильных» перестановок (т. е. тех, где ни один элемент не стоит «на правильном месте»):
! subfactor (N) : [i j Prod Sum] =
N > 0 ? {
++ N;
Sum = 0;
for_inc (i, 2..N, {
Prod = 1;
for_inc (j, (i+1)..N, Prod =*: j);
(i & 1) ? (Sum =-: Prod) : (Sum =+: Prod);
});
Sum }
: 1;
Субфакториал здесь вычисляется как знакопеременная сумма ряда произведений последовательных целых (чётные произведения прибавляются, нечётные — вычитаются). Проверим этот функтор в работе:
for_inc (n, 0..13, <: ("!", n, " = ", subfactor (n), "\n"));
Результат получается именно такой, какой следует ожидать:
!0 = 1 !1 = 0 !2 = 1 !3 = 2 !4 = 9 !5 = 44 !6 = 265 !7 = 1854 !8 = 14833 !9 = 133496 !10 = 1334961 !11 = 14684570 !12 = 176214841
Субфакториал растёт хотя и помедленнее, чем факториал, но тоже довольно резво: для !13 мы уже столкнёмся с переполнением. Попробуем теперь определить и функтор для вычисления биномиальных коэффициентов. Биномиал (N, M) — это число возможных выборок M элементов из N (без различения их порядка). Его тоже нетрудно вычислить рекурсивно:
! binom (N M) = (0 < M && M < N) ? binom (N-1, M) + binom (N-1, M-1) : 1;
но эффективнее будет чисто итеративное определение:
! binom (N M) : [i Num Den] =
(N >= 0 && M >= 0 && M <= N) ? {
Num = Den = 1;
for_inc (i, min (M, N - M), {
Num =*: (N - i);
Den =*: (1 + i);
});
Num % Den }
: 1;
Здесь мы вычисляем биномиал (N, M) как частное от двух произведений: целых от 1 до M и от N до N-M. Заметим, что это частное мы вычисляем целым делением с отбрасыванием остатка (операцией "%") — но, когда всё подсчитано правильно, числитель гарантированно будет делиться на знаменатель без остатка. Для эффективности (и чтобы уменьшить риск переполнения) мы выбираем для M меньшее значение из M и N-M. Нетрудно проверить, как это работает:
for_inc (n, 15, {
<: (n, ": ");
for_inc (m, n + 1, <: (binom (n, m), ' '));
<: "\n";
});
В результате получим хорошо известную треугольную таблицу чисел ("Треугольник Паскаля"):
0: 1 1: 1 1 2: 1 2 1 3: 1 3 3 1 4: 1 4 6 4 1 5: 1 5 10 10 5 1 6: 1 6 15 20 15 6 1 7: 1 7 21 35 35 21 7 1 8: 1 8 28 56 70 56 28 8 1 9: 1 9 36 84 126 126 84 36 9 1 10: 1 10 45 120 210 252 210 120 45 10 1 11: 1 11 55 165 330 462 462 330 165 55 11 1 12: 1 12 66 220 495 792 924 792 495 220 66 12 1 13: 1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1 14: 1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1
Имея в распоряжении биномиальные коэффициенты — нетрудно вычислить и другой любопытный (и тоже часто встречающийся в комбинаторике) числовой ряд: числа Каталана. Впрочем, их проще и быстрее вычислять напрямую:
! catal (N) : [i Val] = (N >= 1) ? {
Val = 1;
for_inc (i, N - 2, {
Val =*: 4 * i + 6;
Val =%: i + 3;
});
Val } : 0;
Здесь на каждой итерации цикла переменную Val мы сперва умножаем (на 4*i + 6), после чего сразу делим (на i + 3). Заметим (хотя из кода это совсем не очевидно) — что здесь на каждой итерации целочисленное деление тоже будет выполняться без остатка! Если мы выведем первые 16 чисел этого ряда — получим в результате:
1 1 2 1 3 2 4 5 5 14 6 42 7 132 8 429 9 1430 10 4862 11 16796 12 58786 13 208012 14 742900 15 2674440 16 9694845
Результатом вычисления определённого нами функтора — не обязано быть скалярное значение! Им вполне может быть произвольная структура данных, в том числе и список. Рассмотрим довольно типичную задачу: как разрезать строку по заданной контекстной подстроке? Эту задачу проще всего решить рекурсивно:
! split_str (sep string) : [len pos] = ((len = #$sep) && (pos = string >>$ sep) >= 0) ? (string $[0..pos], split_str (sep, string $[pos + len ..])) : string;
Функтор split_str — разрезает строку-операнд string по всем найденным вхождениям разделителя sep. Здесь мы активно используем две (описанные в статье 2) строковые операции: поиск подстроки в строке (string >>$ sep) и отрезок строки (string $[from..to]). Но первым делом мы проверяем длину (len) разделителя (она обязана быть ненулевой, иначе операция бессмысленна!), затем ищем первое вхождение sep в string. Если её удалось найти (pos неотрицательно), мы возвращаем список из двух элементов: фрагмента строки до pos, и результата рекурсивного применения той же split_str к хвосту строки (от pos + len до конца). Но результатом этого вызова split_str также может быть список — поэтому в окончательном результате может быть не два элемента, а значительно больше. Если подстроку в строке найти не удалось — мы просто возвращаем саму строку string (и рекурсия на этом завершается).
Легко убедиться в том, что это определение работает правильно: split_str (" : ", "North : East : South : West") — возвращает в качестве результата список ("North", "East", "South", "West"). Довольно часто нужно решить аналогичную, но другую задачу: заменить в строке все вхождения подстроки на заменитель. Её решение очень похоже:
! replace_str (sep repl string) : [len pos] = ((len = #$sep) && (pos = string >>$ sep) >= 0) ? (string $[0..pos] +$ repl +$ replace_str (sep, repl, string $[pos + len ..])) : string;
Функтор replace_str — заменяет в строке string все вхождения разделителя sep на заменитель repl. И реализован практически так же, как split_str, только результатом всегда является строка, а не список из строк. Вызов replace_str (" : ", "+", "North : East : South : West") — как результат, вернёт строку "North+East+South+West". Кстати, используя split_str — это можно было б реализовать компактнее:
! replace_str (sep repl string) = s_join (repl, split_str (sep, string));
Обе операции вполне можно определить и как итеративные — но с рекурсией это заметно проще. На самом деле, все эти усилия избыточны: в языке уже есть встроенные функторы (rx_split и rx_replace), которые прекрасно решают те же задачи (к тому же, они существенно мощнее). Однако, они работают не со статической строкой-разделителем, а с произвольным регулярным выражением. А образцы, или регулярные выражения — это совершенно отдельная, и непростая тема (но мы обязательно дойдём и до неё). В любом случае, определить эти операции самим весьма полезно — как наглядный пример решения подобных задач на практике.
В заключение рассмотрим реализацию элементарной алгебры для простых двухмерных векторов. Каждый из них будем представлять очень просто: как список декартовых координат (X, Y). Заметим, что поскольку каждый такой список состоит из двух скалярных элементов, то он тривиален (т.к. состоит из одного лишь спискового узла). Каждый определённый нами функтор будет начинаться с префикса "vec_" (так же, как для всех списковых операций типичен префикс "l_", для строковых префикс "s_" и т.д.)
Для начала определим операции для сложения (vec_add) и вычитания (vec_sub) векторов:
! vec_add (vecA vecB) = (vecA[0] + vecB[0], vecA[1] + vecB[1]); ! vec_sub (vecA vecB) = (vecA[0] - vecB[0], vecA[1] - vecB[1]);
Также добавим обратный вектор (vec_neg) и умножение вектора на числовой скаляр factor (vec_scale):
! vec_neg (vec) = (- vec[0], - vec[1]); ! vec_scale (factor vec) = (vec[0] * factor, vec[1] * factor);
Для полноты системы операций, добавим ещё и нулевой вектор (vec_null):
! vec_null () = (0.0, 0.0);
Заметим, что в этом определении можно было бы просто опустить пару скобок () — ведь, фактически, это константа! Также нужна операция для получения модуля вектора (vec_mod) и скалярного произведения двух векторов-операндов (vec_prod). (Заметим, что эти операции возвращают уже не вектор, а (числовой) скаляр).
! vec_mod (vec) = sqr (vec[0] * vec[0] + vec[1] * vec[1]); ! vec_prod (vecA vecB) = vecA[0] * vecB[0] + vecA[1] * vecB[1];
Ещё полезно иметь возможность повернуть вектор (vec_rotate) на произвольный угол phi (если помните, похожий пример уже был в предыдущей статье):
! vec_rotate (phi vec) : [sin_phi cos_phi] = {
[sin_phi cos_phi] = (sin(phi), cos(phi));
(vec[0] * cos_phi - vec[1] * sin_phi, vec[0] * sin_phi + vec[1] * cos_phi) };
Это самый нетривиальный из всех примеров: нам даже потребовались локальные переменные и фигурные скобки (но в основном для того, чтобы вычислить синус и косинус для phi только один раз). Наконец, определим пару предикатов для сравнения двух векторов на равенство (vec_eq) и на неравенство (vec_ne):
! vec_eq (vecA vecB) = vecA[0] == vecB[0] && vecA[1] == vecB[1]; ! vec_ne (vecA vecB) = vecA[0] <> vecB[0] || vecA[1] <> vecB[1];
Заметим, что если компонентами векторов являются вещественные (т.е. плавающие) числа, то с их сравнениями надо быть поосторожнее! Вся плавающая арифметика выполняется неточно, и компоненты у (теоретически) равных векторов могут оказаться различающимися (пусть и на очень малую величину). И более реалистичная реализация векторной алгебры должна это учитывать (но мы для простоты этим пренебрежём).
По настоящему, конечно, для реализации таких библиотек, как векторная алгебра — надо было бы использовать механизмы ООП (и оформить все эти векторные операции — как отдельный класс). Позже покажем, как правильно определять классы! Пока убедимся в том, что реализованные здесь векторные операции работают правильно:
vec_prod (vec_scale (2, vec_add ([10 20], [30 20])), vec_scale (3, vec_sub ([40 18], [31 13])));
— что должно вернуть в качестве результата число 3360.
Параметры вызванного функторы — не константны: они тоже могут меняться. В общем-то, от локальных переменных они отличаются лишь одним — инициализацией при вызове. Все данные, с которыми функтор непосредственно работает — лучше всего держать в его локальных переменных. Глобальные переменные — зло: не всегда можно без них обойтись, но чем их меньше, тем лучше.
Вызовы любых функторов (как системных, так и пользовательских) могут быть не только прямыми, но и косвенными. Для чего есть специальный механизм: ссылки на функторы. Но его мы рассмотрим в деталях в следующей статье.