Оператор RECURSION

Оператор RECURSION - создание свойства, реализующего рекурсию.

Синтаксис

RECURSION initialExpr STEP stepExpr [CYCLES policy]

Описание

Оператор RECURSION создает свойство, реализующее рекурсию. Выражение, которое описывает очередной шаг рекурсии, может содержать, кроме обычного обращения к параметрам свойства, обращение к значению параметра на предыдущем шаге. Это обращение имеет синтаксис $name, где name - имя параметра. Если используется ссылка $name, соответствующий параметр name (без $) должен также присутствовать в initialExpr или stepExpr — одного только $name в stepExpr недостаточно.

Значения, полученные на всех итерациях, агрегируются в разрезе параметров свойства: если initialExpr и stepExpr принадлежат числовому классу, значение очередной итерации равно значению предыдущей, умноженному на stepExpr, а значения всех итераций суммируются (SUM), так что результат — это сумма по всем путям от начальных наборов объектов к данному, где значение initialExpr в начале пути умножено на произведение значений stepExpr вдоль пути (в частности, при initialExpr и постоянном stepExpr, равных 1, — количество таких путей); в остальных случаях (как правило, при классе BOOLEAN) используется агрегация OR. Подробное описание семантики и политик работы с циклами см. в разделе Рекурсия (RECURSION).

Внутри stepExpr нельзя использовать ещё один оператор RECURSION — вложение запрещено. Ограничение касается только stepExpr; в initialExpr оператор RECURSION допускается.

Параметры

• initialExpr

  Выражение, значение которого является начальным свойством.

• stepExpr

  Выражение, значение которого является свойством шага рекурсии. Допускает специальный синтаксис $name для обращения к значению параметра name на предыдущем шаге.

• policy

  Политика обработки циклов. Одно из значений:

  • YES — циклы допускаются: при обнаружении цикла для повторившегося набора объектов добавляется значение-маркер — округлённый квадратный корень из максимального значения класса результата (46341 для INTEGER, 3037000500 для LONG), и следующие итерации из строки с маркером не строятся; итоговое значение для набора — сумма маркера с остальными накопленными для него значениями, поэтому оно может быть больше маркера. Для рекурсии со значениями класса BOOLEAN маркера нет: повторяющиеся наборы объектов отбрасываются, и цикл не меняет результат.
  • NO (по умолчанию) — циклы не допускаются; дополнительно создаётся ограничение, запрещающее результат больше половины маркера цикла. Это числовой порог, поэтому его может превысить и достаточно большое значение рекурсии без циклов. Для initialExpr/stepExpr класса BOOLEAN при этой политике каждое значение, не равное NULL, заменяется числом 1, а классом результата становится LONG.
  • IMPOSSIBLE — циклы невозможны (подсказка оптимизатору, обычно используется, когда один из параметров — строго возрастающий счётчик).

Примеры

CLASS Node;
edge = DATA BOOLEAN (Node, Node);

// итерация по integer от from к to (это свойство по умолчанию входит в модуль System)
iterate(i, from, to) = RECURSION i==from AND from IS INTEGER AND to IS INTEGER STEP i==$i+1 AND i<=to CYCLES IMPOSSIBLE;

// считает количество различных путей от a до b в графе
pathes 'Кол-во путей' (a, b) = RECURSION 1 AND a IS Node AND b==a STEP 1 IF edge(b, $b);

// не NULL, если parent — предок группы child или сама эта группа (тем самым свойство отбирает всех потомков parent);
// числовое значение — количество путей от child к parent по свойству parent, в дереве всегда 1
parent = DATA Group (Group);
isParent 'Является родителем' (Group child, Group parent) = RECURSION 1 IF child IS Group AND parent == child
                                                                      STEP 1 IF parent == parent($parent);

// уровень группы в иерархии — количество её предков вместе с ней самой (для корня 1)
level 'Уровень' (Group child) = GROUP SUM 1 IF isParent(child, Group parent);

// числа Фибоначчи, свойство высчитывает все числа Фибоначи до значения to, (после будет возвращать null)
fib(i, to) = RECURSION 1 IF (i==0 OR i==1) AND to IS INTEGER STEP 1 IF (i==$i+1 OR i==$i+2) AND i<to CYCLES IMPOSSIBLE;

Заметим, что числа Фибоначчи можно реализовать без добавления параметра to:

fib(i) = RECURSION 1 IF (i==0 OR i==1) STEP 1 IF (i==$i+1 OR i==$i+2);

Но в текущей реализации оптимизатор платформы в меньшей степени ориентирован на работу с числами, поэтому пока не может определить, что функция шага возрастающая, и сам остановить рекурсию, искусственно создав соответствующие условие, как это сделано в верхнем примере. Еще больше вопросов возникает, когда это свойство необходимо отображать в динамическом списке (а в статическом списке это невозможно сделать, так как количество не NULL значений бесконечно). В этом случае необходимо также учитывать текущей порядок в этом списке, и также проталкивать его внутрь запроса. Эти ограничения будут устранены в будущих версиях, но в текущей версии их рекомендуется учитывать.