Технология XSLT — страница 55 из 66

Листинг 11.8. Шаблон, форматирующий дату
-
Jan
Feb
Mar
Apr
May
Jun
Jul
Aug
Sen
Oct
Nov
Dec
-
Рекурсия
Отсутствие в XSLT изменяемых переменных (оценим красоту этой тавтологии) как, впрочем, и многое другое, делает этот язык совершенно непохожим на многие классические языки программирования. В этом разделе мы опишем рекурсию [Кормен и др. 2000, Кнут 2000] — чрезвычайно простую, но в то же время исключительно мощную технику, которая в большинстве случаев компенсирует нехватку в XSLT переменных и других процедурных конструкций.
Не вдаваясь в строгие определения дискретной математики, можно сказать, что рекурсия это всего лишь описание объекта или вычисления в терминах самого себя. Пожалуй, самым простым примером рекурсии является факториал, функция, которая математически определяется как:
0!=1
n!=n×(n-1)!
Программа на процедурном языке (например, таком, как Java), вычисляющая факториал совершенно тривиальна:
int factorial(int n) {
 if (n == 0) return 1;
 else return n * factorial(n-1);
}
Попробуем запрограммировать факториал на XSLT. Мы уже научились создавать собственные функции (вернее, конструкции, похожие на них) с помощью одних только именованных шаблонов, значит написать функцию, которая бы вызывала сама себя, будет не так уж и сложно.
Листинг 11.9. Именованный шаблон, вычисляющий факториал
1
Вызвав этот шаблон с параметром 
n
 равным 
6
 следующим образом:
мы получим текстовый узел, значение которого будет равно "
720
".
Очевидным требованием к рекурсивным функциям является возможность выхода из рекурсии. Если бы в определении факториала не было указано, что 0!=1, вычисления так бы и продолжались без конца.
Главным минусом рекурсии является требовательность к ресурсам. Каждый раз, при вызове именованного шаблона, процессор должен будет каким-то образом сохранять в памяти передаваемые ему формальные параметры. Например, если мы попробуем сосчитать факториал от 170, процессору понадобится держать в памяти сразу 170 чисел. Безусловно, в случае с факториалом это не является большой проблемой — точность 64-битных чисел исчерпается гораздо раньше, чем закончится память, но в случае хранения в переменных действительно больших объемов информации (например, частей деревьев) такая угроза существует. Кроме того, рекурсивные решения, как правило, работают медленнее, чем решения, не использующие рекурсию.
Так в чем же смысл использования рекурсии? Дело в том, что вследствие определенных ограничений (связанных, в частности с неизменяемыми переменными) в XSLT существуют задачи, которые не могут быть реализованы иначе кроме как через рекурсию. Самым характерным примером такой задачи являются циклы.
Циклы
Цикл в общем смысле слова это повторение одних и тех же действий несколько раз. Если говорить об XSLT, то цикл это многократное выполнение одного и того же шаблона. Для подавляющего большинства случаев в преобразованиях достаточно бывает использовать такие элементы, как 
xsl:apply-templates
 и 
xsl:for-each
, которые заставляют процессор выполнять одни и те же действия несколько раз в контексте каждого из узлов определенного множества.
Весомым ограничением такого рода циклической обработки является невозможность генерировать множества узлов. В текущей версии языка никакой другой тип не может быть приведен ко множеству узлов, значит, в любое из них могут входить только те узлы, которые изначально присутствуют в одном из обрабатываемых документов. Это означает, что ни 
xsl:apply-templates
, ни 
xsl:for-each
 не могут быть использованы для того, чтобы реализовать простые 
while
- или 
for
-циклы для произвольных множеств.
Цикл while
Наиболее примитивной циклической конструкцией во многих языках программирования является цикл 
while
 (англ. пока). Цикл 
while
, как правило, имеет следующий вид:
пока
 верно условие
выполнять
действия
В качестве примера 
while
-цикла напишем на языке Java программу вычисления факториала в итеративном стиле:
int factorial(int n) {
 int i = n;
 int result = 1;
 while (i != 0) {
  result = result * i;
  i--;
 }
 return result;
}
В этой функции 
условием
 является отличие значения переменной 
i
 от 0, а действиями — умножение значения переменной 
result
 на значение переменной 
i
, и уменьшение значения этой переменной на 1.
Цикл 
while
 не может быть запрограммирован в XSLT итеративно потому как действия, как правило, изменяют значения переменных, в контексте которых вычисляется условие, определяющее, продолжать выполнение цикла или нет. Дадим другую общую запись цикла 
while
, выделив изменение переменных:
пока
 верно условие(x1,x2, ...,xn)
выполнить
 x1' := функция1(x1,x2,...,xn)
 х2' := функция2(x1,x2,...,xn)
 ...
 xn' := функцияn(x1,x2,...,xn)
 действия(x1,x2,...,хn)
 x1 := x1'
 x2 := x2'
 ...
 xn := xn'
иначе
 вернуть результат(x1,...,хn)
Переопределение значений переменных 
x
1, … , 
х
n в этом случае выполняют 
n
 функций: 
функция
1 …, 
функция
n. И если изменить значение переменной мы не могли, переопределить связанное с ней значение мы вполне в состоянии, добавив в контекст новый параметр или переменную с тем же именем.
Теперь мы можем записать весь цикл 
while
 как одну рекурсию:
while(x1, ..., xn) ::=
 если
  выполняется условие(x1, ..., xn)
 то
  действия(x1, ..., хn)
  while(функция1(x1, ..., хn),
   функция2(x1, ..., хn),
   ...,
   функцияn(x1, ..., xn))
 иначе
  результат(x1, ..., хn)
Теперь уже совершенно очевидно, как 
while
-цикл должен выглядеть в преобразовании.
Листинг 11.10. Шаблон цикла while в общем виде
В качестве примера приведем 
while
-цикл для программы, вычисляющей факториал. Java-код был следующим:
while (i != 0) {
 result = result * i;
 i--;
}
В этом цикле участвуют две переменные — 
i
 и 
result
. Функции, использующиеся в этом цикле, запишутся следующим образом:
условие($1, $result)      ::= ($i != 0)
функцияi($i, $result)     ::= ($i - 1)
функцияresult($i, $result) ::= ($i * $result)
результат($I, $result)    ::= ($result)
Именованный шаблон для этого случая будет иметь вид.
Листинг 11.11. Пример шаблона цикла while
Вызвать этот шаблон можно следующим образом:
Результатом будет, естественно, число 
720
.
Цикл for
Частным случаем цикла 
while
 является цикл 
for
. В разных языках программирования 
for
 имеет различную семантику; мы будем рассматривать циклы 
for
 вида
for (int i = 0; i < n; i++) { ... }
в языках Java и С или
for i := 0 to n-1 do begin ... end;
в Pascal. Иными словами, нас будет интересовать циклическое выполнение определенных действий при изменении значения некоторой переменной (называемой иногда индексом цикла) в интервале целых чисел от 0 до n включительно.
Цикл 
for
 может быть определен через 
while
 с использованием следующих условных и изменяющих функций:
условие($i, $n,$x1,...,$хk)      :: = ($i < $n)
функцияi($i, $n, $x1, ... , $xk) ::= ($i + 1)
функцияn($i, $n, $x1, ..., $xk)  :: = ($n)
Шаблон цикла 
for
 в общем виде будет выглядеть как.
Листинг 11.12. Шаблон цикла for в общем виде
функция1($i, $n, $x1, ..., $xk) "/>
В качестве примера цикла 
for
 приведем шаблон, вычисляющий 
n
 первых чисел Фибоначчи.
Числа Фибоначчи — это рекуррентная последовательность вида
1 1 2 3 5 8 13 21 ...
и так далее, где каждое последующее число определяется как сумма двух предыдущих.
Для вычисления 
n
 первых чисел Фибоначчи мы можем использовать две переменные 
current
 и 
last
, соответствующих текущему число и числу, полученному на предыдущем шаге соответственно. Функции, переопределяющие эти переменные, совершенно очевидны:
функцияlast($i, $n, $last, $current)   ::= ($current)
функцияcurrent($i, $n, $last, $current) ::= ($current + $last)
Поскольку в данном случае нам не нужно возвращать результат, нужно лишь циклически выводить очередное число Фибоначчи, шаблон 
for
 может быть немного упрощен использованием элемента 
xsl:if
 вместо 
xsl:choose
.
Листинг 11.13. Шаблон, вычисляющий числа Фибоначчи
/xsl:template>
Вызванный в основном шаблоне как:
этот шаблон создаст в выходящем документе последовательность:
1 1 2 3 5 8
Приведем еще более простой пример, в котором элемент 
option
 выводится заданное число раз.
Листинг 11.14. Вывод 10 элементов option
 version="1.0"
 xmlns:xsl="http://www.w3.org/1999/XSL/Transform'">



Листинг 11.15 Выходящий документ
Пожалуй, этим примером мы и закончим рассмотрение рекурсии. Осталось лишь добавить, что при всей своей простоте и вычислительной мощи, рекурсия является гораздо более требовательной к ресурсам техникой программирования, чем обычная итеративная обработка. Поэтому всегда следует тщательно оценивать, во что может вылиться использование рекурсии. В любом случае следует избегать глубоких рекурсий (функций, количество рекурсивных вызовов в которых может быть большим) и рекурсий, неэкономно использующих память.
Кроме того, большинство действий, выполнение которых в XSLT затруднено, в классических языках программирования выполняется, как правило, намного легче и эффективней. Поэтому, каждый раз, когда стоит вопрос об использовании рекурсии, наряду с ней следует рассматривать такую альтернативу, как использование расширений XSLT, написанных на обычном императивном языке.
Метод Пиза для for-цикла
Для простых 
for
-циклов, которые должны выполниться строго определенное число раз, вместо рекурсии можно использовать весьма остроумный метод, предложенный Венделлом Пизом (Wendell Piez, Mullberry Technologies, Inc). Суть метода состоит в том, что хоть мы и не можем сгенерировать множество узлов, выбрать множество с определенным количеством узлов нам вполне по силам.
Для начала выберем какое-нибудь множество узлов документа преобразования:
Затем для повторения определенных действий несколько раз используем конструкцию вида
где 
number
 указывает требуемое число итераций.
При использовании метода Пиза следует учитывать следующие особенности.
□ Множество узлов 
set
 не должно быть слишком большим — иначе его выбор будет неэффективным. 
□ Множество узлов 
set
 обязательно должно содержать число итераций (
number
) узлов.
В целом же метод Пиза — классический пример эффективного применения инструментов не по назначению.
Операции над множествами

Оглавление

К карточке книги