XSLで再帰処理を効果的に使用する

XSLの再帰処理の概要と、XSLで再帰処理を効果的に使用するためのテクニック

XSLTを効果的に使用するには、関数型言語としてのXSLの記述方法を習得する必要があります。これはつまり、再帰処理について理解する必要があるという意味です。この記事では、再帰処理の基本的な考え方を取り上げ、XSLで再帰処理を使用するためのテクニックを紹介します。また、XML変換を最適化してエラーを回避するためのテクニックについても見ていきます。概念についてもテクニックについてもサンプル・コードを付けましたので、合わせて参考にしてください。

Jared Jackson, Research Associate, IBM

Jared JacksonJared Jacksonは、IBM Almaden Research Centerのリサーチ提携者であり、Harvey Mudd大学でコンピューター・サイエンス学位を取得した新卒者です。



2002年 10月 01日

XSLがW3Cの標準規格として登場したころを振り返ると、XSLは関数型言語ではないという見方が、開発者たちの間では一般的でした。現に、SAXONというXSLインプリメンテーションの開発者であり、Wrox社から出版されている「XSLTProgrammer's Reference」(邦訳はインプレス社の「XSLTバイブル-プログラマーズリファレンス」)の著者でもあるMichaelKay氏は、「XSLTはどのような言語か」というdeveloperWorksの記事でこう書いています。「XSLTは、関数型プログラミングの着想に基づいていますが、関数を第1クラスのデータ型として扱う機能が欠けているため、まだ関数型プログラミング言語ではありません。」

しかし、最近では、テクニカルライターでありXSL開発者でもあるDimitre Novatchev氏が、XML名前空間をうまく使えば、データ型として関数 (XSLのテンプレート) を受け渡すことが可能であるという趣旨の記事を書いています。だからといって、テンプレートを第1クラスのデータ型と見なすかどうかについては、意見が分かれるかもしれませんが、少なくとも、Novatchev氏の手法によって明らかになったとおり、ゆるやかな型指定のある関数型言語としてXSLを利用できるのは間違いありません。

Michael Kay氏とDimitri Novatchev氏の記事については、参考文献の中にリンクがあります。

現在のプログラミングの世界は、命令型のプログラミング言語に支配されていると言えます。Java、各種のC言語、Visual Basicなど、現在の主流になっているプログラミング言語の基本的な考え方はすべて同じです。要するに、変数を設定し、変数を変更する関数や操作を呼び出し、結果を返す、というわけです。もちろん、これが強力なプログラミング手法であるのは間違いありませんが、だからといって、これがすべてではありません。

このような手続き型の言語よりはなじみが薄いものの、少なくとも機能の面ではまったく引けを取らないプログラミング言語があります。それが関数型または宣言型の言語です。この種の言語で書いたプログラムでは、変数を1度宣言することができますが、その変数に格納した値を変更することはまったくできません。プログラミング言語としてのXSLは、宣言型であり関数型です。したがって、JavaやCでコードを書くことに慣れている開発者がXSLの高度な機能を使おうとすると、多少なリとも違和感を持ってしまうのは当然と言えます。

XMLによるアプリケーション開発やWeb開発の重要性も、それに関連したXSLテクノロジーの重要性も高まっている中で、XSLTの効果的な使用を避けて通ることはできません。したがって、宣言型のプログラミングを学ぶということがどうしても必要になります。これはつまり、再帰処理に習熟しなければならないという意味です。再帰処理の基本的な考え方を理解し、当面の問題を解決するために再帰処理を効果的に使用するテクニックをマスターしなければなりません。

実例で学ぶ再帰処理

宣言型の言語は、再帰的関数によって、命令型の言語と同等の機能性を用意しています。これは、命令型の言語で再帰処理を利用できないという意味ではありません。ほとんどの命令型言語では、現に再帰処理を利用できます。しかし、宣言型言語では、操作の主な手段として再帰処理を利用するのに対し、命令型言語では、再帰処理が機能の1つという位置付けになっているわけです。

ここで、正の整数の階乗を計算する関数を取り上げてみましょう。ちなみに、階乗とは、1からnまでの自然数の積であり、4の階乗 (4! と表記する) は、4 * 3 * 2 * 1 = 24となります。リスト1 は、Javaコードでこの関数を記述する一例です。

リスト1. ループ処理を使って階乗を記述したJavaコード
public int factorial(int number) {
    if (number <= 1) return 1;
    int result = 1;
    for (int i=1; i <= number; i++) {
        result *= i;
    }
    return result;
}

このコードのロジックは完ぺきですが、変数の値を代入し直せるというJavaの機能に頼っているのもまた事実です。そのような機能を使わないで階乗の関数を記述するには、リスト2 のようにします。

リスト2. 再帰処理を使って階乗を記述したJavaコード
public int factorial(int number) {
    if (number <= 1) return 1;
    return number * factorial(number-1);
}

このように、階乗の関数を記述したコードが2種類できましたが、どちらを呼び出しても結果は同じです。2番目のコードでは、関数の本体の中でfactorial() を再び呼び出すので、再帰処理を利用していることになります。このテクニックは、階段のような形で図式化できます。要するに、この関数は、自らを呼び出して結果 (状態情報) を格納するという処理を繰り返しながら、終結条件を満たすまで「階段」を下りていき、一番下にたどり着いたら、今度は「階段」を上に向かいながら、各呼び出しの結果 (状態情報) を乗算して最終結果を導き出すわけです。この階乗関数の流れを図式化したのが図1 です。

図1. 階段状の再帰処理
図1

基本的に、再帰的関数を記述するには、終結条件、演算コード、関数自体の再帰的な呼び出しという3つの要素が必要です。この階乗関数の場合は、nの階乗を求めるために、終結条件である1に達するまで、n-1、n-2、n-3といった具合にそれぞれの階乗を再帰的に計算していくわけです。

この説明では再帰処理の考え方をはっきりつかめないという方は、参考文献で紹介している再帰処理関連のリンクを参照するか、自分でとりあえず関数を書いてみることをお勧めします(フィボナッチ数列のn番目の数を計算する関数などがよいかもしれません)。


XSLの再帰処理の基本的な用例

XSLで再帰処理を利用する状況としては、次の2つが考えられます。

  • 同じ種類の値が繰り返し記述されているソースXMLを変換し、そのような値の合計などを示す場合。たとえば、商品カタログのXMLを変換し、各商品の価格と合計金額を一緒に示すには、再帰的なテンプレートを使って合計金額を計算する必要があります。
  • タグに数値 (x) が入っているソースXML(<countTo number="5"/> など) を変換するときに、何かの情報をそのn回だけ繰り返して示す必要がある場合。階乗の問題は、このような状況のごく小さな例ですが、もう少し複雑な例をあとから取り上げます。

この両方の状況について、XSLで再帰処理を利用する方法をこれから見ていきますが、まずは先ほどのような階乗の計算をXSLで記述する方法を見てみましょう (リスト3)。

リスト3. 再帰処理を使って階乗を記述したXSL
<xsl:template name="factorial">
  <xsl:param name="number" select="1"/>
  <xsl:choose>
    <xsl:when test="$number <= 1">
      <xsl:value-of select="1"/>
    </xsl:when>
    <xsl:otherwise>
      <xsl:variable name="recursive_result">
        <xsl:call-template name="factorial">
          <xsl:with-param name="number" select="$number - 1"/>
        </xsl:call-template>
      </xsl:variable>
      <xsl:value-of select="$number * $recursive_result"/>
    </xsl:otherwise>
  </xsl:choose>
</xsl:template>

このテンプレートには、先ほどJavaコードで見たのと同じ3つの要素が含まれています。まず、終結条件 (1未満の値) が記述されています。次に、この終結条件が満たされていない場合に実行する関数の再帰的呼び出しが記述されています(結果はrecursive_result 変数に格納されます)。最後に、元の値と再帰処理で得られた値とを乗算して最終結果を導き出す演算が記述されています。ちなみに、このコードを書くには、かなりの入力作業が必要です。ほかの言語に比べて、XSLのコードが長くなってしまうのは、XMLに準拠した変換用言語のありがたくない一面と言えます。

再帰処理の用例1: 各要素の合計

リスト3 の階乗の例と同じテクニックを使って、XMLの商品カタログに出てくる商品価格の合計値を計算できます。基本的な考え方は階乗の場合と同じですが、乗算の代わりに加算を使う点と、入力として数値の代わりにノード・セットを使うという点が違っています。

ここで、リスト4 のようなXMLがあるとしましょう(このコードは単なる断片ですが、参考文献で紹介しているリンクからは、完全なXMLコードやXSLコードなど、さまざまなコードをダウンロードできます)。

リスト4. XMLの商品カタログのサンプル
<Products>
  <Product>
    <Name>Gadget</Name>
    <Price>$10.00</Price>
  </Product>
  <Product>
    <Name>Gizmo</Name>
    <Price>$7.50</Price>
  </Product>
  ...
 </Products>

ここで実行したいと思っているのは、商品リストの最初の価格と、その他の価格の合計とを加算するという処理を最後の価格まで繰り返していくことです。そのためには、リスト5 のようなXSLを使用できます。

リスト5. 簡単な再帰処理を使ってノードをトラバーサルするXSL
<xsl:template name="priceSum">
  <xsl:param name="productList"/>
    <xsl:choose>
      <xsl:when test="$productList">
        <xsl:variable name="recursive_result">
          <xsl:call-template name="priceSum">
            <xsl:with-param name="productList"
              select="$productList[position() > 1]"/>
          </xsl:call-template>
        </xsl:variable>
        <xsl:value-of
          select="number(substring-after($productList[1]/Price,'$'))
                  + $recursive_result"/>
      </xsl:when>
      <xsl:otherwise><xsl:value-of select="0"/></xsl:otherwise>
  </xsl:choose>
</xsl:template>

このコードでは、リスト内の最初の商品価格と、その他の全商品に対する再帰的呼び出しの結果とを加算しながら、関数を繰り返し呼び出していくうちに、リストがだんだん小さくなり、最後にリストが空になって終結条件が満たされた時点で、結果にゼロを加算するようにしています (つまり、最終結果がそのまま残ります)。このように、ノード・リストをだんだん小さくしていく再帰処理のテクニックは、いろいろな状況に応用できます。

再帰処理の用例2: 数値に基づく反復処理

ソースXMLの何かのコンテキストに数値が指定されていて、XSLプログラマーがその回数だけ処理を反復しなければならないような場合に、2番目の状況が発生します。たとえば、行/列形式の表の情報が含まれているXMLを変換し、HTMLなどの形式でその表をビジュアルに書き出さなければならないような状況がそれに当たります。

そのような場合、再帰処理に習熟していない開発者であれば、XMLを解析して各行/列に対応する要素をXMLに付け加えるためのプログラムを書こうとするかもしれません。確かに、その作業が済んでしまえば、テンプレートや再帰処理を使わなくても、簡単な<xsl:for-each> 要素で問題を解決できますが、この方法には欠点もあります。つまり、最終的な変換結果を得るための作業負荷がほとんど倍になってしまうということです。特に、サーバーから送ってもらったXMLとXSLを使ってクライアントで変換を実行するというクライアント/サーバー型のモデルでは、この欠点が大きく出てしまいます。サーバーがせっかく効率的な処理をしていても、XMLに要素を付け加える段階でその効率が一挙に落ちてしまうわけです。

したがって、再帰処理を記述したテンプレートを使って、変換時にすべてを実行してしまうほうが優れています。ここでは、九九 (掛け算) の表を記述したXML要素をHTMLに変換してみましょう。入力としては、次の行を使います。

<MultiplicationTable Rows="6" Columns="6"/>

この行をHTMLに変換して、次のような表を生成してみましょう。

123456
1123456
224681012
3369121518
44812162024
551015202530
661218243036

この場合は、最初の2つの例よりも処理がかなり複雑になります。つまり、関数の結果を返すだけで問題が解決されるわけではなく、むしろ、再帰処理を実行しながらHTMLを書き出していかなければなりませんし、行に関する再帰処理を記述したテンプレートと、列に関する再帰処理を記述したテンプレートを2つ組み合わせることも必要になります。

参考文献で紹介しているこの記事のダウンロード・サイトに、このあたりの処理をすべてまとめたmult_table.xslファイルを用意しておきましたので、参考にしてみてください。リスト6 は、そのファイルからの抜粋です。

リスト6. 簡単な再帰処理を使って数値に基づく反復処理を記述したXSL
<xsl:template name="drawRow">
  <xsl:param name="currentRow"/>
  <xsl:param name="totalRows"/>
  <xsl:param name="totalCols"/>
  <xsl:if test="$currentRow <= $totalRows">
    <tr>
      <xsl:call-template name="drawCell">
        <xsl:with-param name="currentRow" select="$currentRow"/>
        <xsl:with-param name="currentCol" select="0"/>
        <xsl:with-param name="totalCols" select="$totalCols"/>
      </xsl:call-template>
    </tr>
    <xsl:call-template name="drawRow">
      <xsl:with-param name="currentRow" select="$currentRow  + 1"/>
      <xsl:with-param name="totalRows" select="$totalRows"/>
      <xsl:with-param name="totalCols" select="$totalCols"/>
    </xsl:call-template>
  </xsl:if>
</xsl:template>
<xsl:template name="drawCell">
  <xsl:param name="currentRow"/>
  <xsl:param name="currentCol"/>
  <xsl:param name="totalCols"/>
  <xsl:if test="$currentCol <= $totalCols">
    <xsl:variable name="bgColor">...</xsl:variable>
    <xsl:variable name="value">...</xsl:variable>
    <td bgcolor="{$bgColor}" align="center" valign="top">
      <xsl:value-of select="$value"/>
    </td>
    <xsl:call-template name="drawCell">
      <xsl:with-param name="currentRow" select="$currentRow"/>
      <xsl:with-param name="currentCol" select="$currentCol + 1"/>
      <xsl:with-param name="totalCols" select="$totalCols"/>
    </xsl:call-template>
  </xsl:if>
</xsl:template>

このコードでは、再帰処理を記述した2つのテンプレートを使っています。最初のテンプレートが表の行を1つずつ再帰的に作っていき、終結条件が満たされた時点で、2番目のテンプレートを使って、各行の各列のセルを1つずつ完成していくわけです。この種のテクニックは、多次元データ処理のほとんどのケースに応用できます。


XSLの再帰処理のパターンを最適化する

再帰処理には、残念ながら大きな欠点もあります。つまり、XSLエンジンで大きなデータ・セットに対して再帰処理を実行しようとすると、失敗に終わる場合が少なくないということです。再帰処理が10,000回を超えるようになれば、「スタック・オーバーフロー」とか「メモリー不足」という例外が出る可能性がきわめて高くなります。たとえば、商品カタログの合計金額を計算するときに、商品の数が10,000個を超えていれば、エラーになる場合が多いというわけです。

そのような場合でも、再帰的関数の処理を最適化する方法がいくつかあります。つまり、テンプレートで実行する再帰処理の深さを限定したり、まったくゼロにしたりする方法です。ここからは、再帰処理を記述したXSLを最適化するための4つの方法を見ていきましょう。

再帰処理を一切使わずに、<for-each> 要素でXML文書内の全ノードをループ処理するというテクニックが、いろいろなWebサイトで紹介されています。つまり、再帰的変数を使う代わりに、各ノードのposition() 値を使って数値を反復処理するというわけです。このテクニックをさらに洗練させると、大きなノード・セットについては、XMLデータ・ソースではなく、XMLスタイルシート文書を処理できるとまで言われています。

しかし、このテクニックは、汚い「裏技」にすぎません。サイズの制約があるので、使用には危険が伴いますし、再帰処理に比べて速度がかなり落ちてしまいます。この種のテクニックを使うよりも、この記事で取り上げている最適化のテクニックを学ぶほうが、いろいろな面で役立つと思います。

再帰処理の最適化1: 1項目単位の分割

最初のサンプルでは、XMLの商品カタログに載っている商品の合計金額を計算しました。まずは、カタログに載っている最初の商品の金額と、その他の全商品の合計金額を加算し、カタログ全体を処理するまで、その計算を再帰的に繰り返していくわけです。この場合、再帰処理の深さは、カタログ内の商品の数と等しくなります。そこで、方法を少し変えて、再帰処理のレベルをそれほど深くしないで、同じ結果を得るようにしたいと思います。

どのように変えるかと言えば、まずカタログを小さく分割する処理を再帰的に繰り返し、最終的には各部分を1つの商品だけにしてしまうわけです。そのための一番シンプルな考え方は、各部分を半分に切って、それぞれに対して別々に再帰的呼び出しを実行し、最初の半分についての作業を完了してから、次の半分の作業に取り掛かるということを繰り返していく流れです。最初に取り上げた方法は、線形 (階段状) の処理ですが、この場合は、ツリー状の処理と言えます。図2 は、この再帰処理のツリー構造を示したものです。

図2. 再帰処理のツリー構造
図2

このような「1項目単位の分割」方式を使う場合は、加算の演算処理の回数が少なくなるわけではありませんが、再帰処理のスタックにすべての数値が格納されるまで加算の演算を延期する必要がないという点にメリットがあります。この点を示したのが、リスト7 のXSLコードです。

リスト7. 「1項目単位の分割」方式でノードをトラバーサルするコード
<xsl:template name="priceSumDivideAndConquer">
  <xsl:param name="productList"/>
    <xsl:choose>
      <xsl:when test="count($productList) = 1">
        <xsl:value-of
          select="number(substring-after($productList[1]/Price,'$'))"/>
      </xsl:when>
      <xsl:when test="$productList">
        <xsl:variable name="halfIndex"
          select="floor(count($productList) div 2)"/>
        <xsl:variable name="recursive_result1">
          <xsl:call-template name="priceSumDivideAndConquer">
            <xsl:with-param name="productList"
              select="$productList[position() <= $halfIndex]"/>
          </xsl:call-template>
        </xsl:variable>
        <xsl:variable name="recursive_result2">
          <xsl:call-template name="priceSumDivideAndConquer">
            <xsl:with-param name="productList"
              select="$productList[position() > $halfIndex]"/>
          </xsl:call-template>
        </xsl:variable>
      <xsl:value-of select="$recursive_result1 + $recursive_result2"/>
    </xsl:when>
    <xsl:otherwise><xsl:value-of select="0"/></xsl:otherwise>
  </xsl:choose>
</xsl:template>

加算の演算は、項目の数が1 (終結条件) になった時点で行われ、片方の処理が終わったら、もう片方の処理に進むということを繰り返していきます。このテクニックを使えば、再帰処理の深さがリスト内の項目数のlog2 を超えることはないので、当然のことながら、計算できる商品価格の数が指数関数的に増えることになります。

再帰処理の最適化2: サイズを指定した分割

「1項目単位の分割」方式の場合は、再帰処理の深さを限定するという点で大きなメリットがありますが、残念ながらデメリットもあります。つまり、項目の数が2の累乗になっていない場合は、再帰処理の末尾で不要なオーバーヘッドが発生してしまうということです。

しかし、再帰処理の深さを限定するという発想は同じでも、項目数が1になるまでリストを半分に切っていく処理を繰り返す代わりに、ノードのサイズとして一定の項目数を指定して分割を行えば、そのあたりのデメリットをカバーできます。この方法は、基本的な再帰処理のテクニックをベースにしていますが、分割を管理するためのテンプレートをさらに用意する必要があります。

この分割管理用のテンプレートの役割は、メモリー不足の問題が起きないように分割を行い、小さく分割した作業の結果を取り込みながら、すべてがそろった時点で必要な演算処理を実行するということです。

この「サイズを指定した分割」方式を使ったテンプレートのサンプルが、リスト8 です。このテンプレートは、ノード・リストと分割サイズの値に基づいて分割を行い、元の合計金額計算用のテンプレートを使って、それぞれの分割部分に対して演算処理を実行します。

リスト8. 「サイズを指定した分割」方式でノードをトラバーサルするコード
<xsl:template name="priceSumSegmented">
  <xsl:param name="productList"/>
  <xsl:param name="segmentLength" select="5"/>
  <xsl:choose>
    <xsl:when test="count($productList) > 0">
      <xsl:variable name="recursive_result1">
        <xsl:call-template name="priceSum">
          <xsl:with-param name="productList"
            select="$productList[position() <= $segmentLength]"/>
        </xsl:call-template>
      </xsl:variable>
      <xsl:variable name="recursive_result2">
        <xsl:call-template name="priceSumSegmented">
          <xsl:with-param name="productList"
            select="$productList[position() > $segmentLength]"/>
        </xsl:call-template>
      </xsl:variable>
      <xsl:value-of select="$recursive_result1 + $recursive_result2"/>
    </xsl:when>
    <xsl:otherwise><xsl:value-of select="0"/></xsl:otherwise>
  </xsl:choose>	
</xsl:template>

「1項目単位の分割」方式の代わりに「サイズを指定した分割」方式を使えば、ほとんどの場合にオーバーヘッドが減少しますが、再帰処理の深さを限定するという点では、「1項目単位の分割」方式に遠く及びません。どちらの方式が適しているのかは、それぞれの状況に大きく左右されます。では、どうしたらよいかと言えば、答えは「併用する」ということです。その方式を次に取り上げましょう。

再帰処理の最適化3:「1項目単位の分割」方式と「サイズを指定した分割」方式の併用

「1項目単位の分割」方式と「サイズを指定した分割」方式を併用すると、次のようなメリットがあります。

  • 再帰処理の深さとそれぞれの加算レベルのオーバーヘッドを最小限に抑え込める
  • 再帰処理のツリー構造の末端で発生するオーバーヘッドを回避できる

この方式では、再帰処理のテンプレートに、どちらを使うかの分岐点を示した値とノード・リスト(または他の処理対象データ) を渡し、「1項目単位の分割」方式の修正版によって分割を管理します。リストの実際のサイズがその分岐点の値よりも大きい場合は、リストを半分に切って、それぞれに再帰的呼び出しを実行するという処理を繰り返し、そうでない場合は、基本的な再帰処理のテンプレートを使って、「サイズを指定した分割」方式で結果を計算します。

この方式を記述したXSLテンプレートのサンプルが、リスト9 です。

リスト9. 「1項目単位の分割」方式と「サイズを指定した分割」方式を併用してノードをトラバーサルするコード
<xsl:template name="priceSumCombination">
  <xsl:param name="productList"/>
  <xsl:param name="threshold" select="5"/>
  <xsl:choose>
    <xsl:when test="count($productList) > $threshold">
      <xsl:variable name="halfIndex"
        select="floor(count($productList) div 2)"/>
      <xsl:variable name="recursive_result1">
        <xsl:call-template name="priceSumCombination">
          <xsl:with-param name="productList"
            select="$productList[position() <= $halfIndex]"/>
        </xsl:call-template>
      </xsl:variable>
      <xsl:variable name="recursive_result2">
        <xsl:call-template name="priceSumCombination">
          <xsl:with-param name="productList"
            select="$productList[position() > $halfIndex]"/>
        </xsl:call-template>
      </xsl:variable>
      <xsl:value-of select="$recursive_result1 + $recursive_result2"/>
    </xsl:when>
    <xsl:otherwise>
      <xsl:call-template name="priceSum">
        <xsl:with-param name="productList" select="$productList"/>
      </xsl:call-template>
    </xsl:otherwise>
  </xsl:choose>
</xsl:template>

再帰処理の最適化4: 末尾再帰処理

再帰処理についてある程度習熟している読者であれば、最適化のテクニックとして最初に思い付くのは、この「末尾再帰処理」だと思います。確かに、再帰処理の深さがゼロになりますし、オーバーヘッドらしきものもほとんどありません。しかし、いろいろなメリットがあるのは事実ですが、XSLコードの中でこのテクニックを使っても、変換用のXSLエンジンがそれを認識し、その記述に合わせて動作を変更しなければ、まったく意味がありません。実は、このテクニックに対応しているXSLエンジンは、ほとんど存在しないというのが現状です。

しかし、ビジネスと研究の両方の分野でXSLが完全に定着していることからすれば、このような状況も遠からず解決されると見てよさそうです。したがって、メモリーの問題を解消し、パフォーマンスの問題もほとんどないテクニックがここにある以上、開発者がこの末尾再帰処理のしくみを理解しておくのは、とても重要だということになります。

末尾再帰処理の基本的な考え方は、再帰処理の各段階で状態情報を格納しないということです。各段階で必要なすべての情報を高いレベルで再帰処理のスタックに格納する代わりに、パラメーターとして関数に渡すようにするので、XSLエンジンは、再帰的関数を手続き型言語の反復ループと同じようにして処理できるわけです。

合計価格を計算するサンプルを末尾再帰処理の形で書き直したのが、リスト10 です。

リスト10. 末尾再帰処理を使ってノードをトラバーサルするコード
<xsl:template name="priceSumTail">
  <xsl:param name="productList"/>
  <xsl:param name="result" select="0"/>
  <xsl:choose>
    <xsl:when test="$productList">
      <xsl:call-template name="priceSumTail">
        <xsl:with-param name="productList"
          select="$productList[position() > 1]"/>
        <xsl:with-param name="result"
          select="$result + number(substring-after($productList[1]/Price,'$'))"/>
      </xsl:call-template>
    </xsl:when>
    <xsl:otherwise><xsl:value-of select="$result"/></xsl:otherwise>
  </xsl:choose>
</xsl:template>

このコードの違いは、途中結果を格納する変数を追加しているという点に尽きます。再帰処理の各段階で加算する数値をスタックに格納する代わりに、加算を各段階で実行し、それぞれの途中結果を再帰処理の次の段階にパラメーターとして渡していきます。高性能なXSLエンジンであれば、ちょうどJavaやCのコードで変数の値を上書きするのと同じ要領で、再帰的な呼び出しのたびに、途中結果の値を格納しているメモリー領域を上書きしていくわけです。まさに、プログラミング言語としてのXSLTの特徴をそのまま残しながら、宣言型の言語と命令型の言語の両方の機能を活用するためのテクニックと言えます。


結論

再帰処理の使い方をマスターしてしまえば、XSLの宣言型のプログラミング・スタイルは、邪魔物どころか、XML変換の機能を拡張するための効率的な方法だということになります。あとは、それぞれの状況に合わせて、どのタイプの再帰処理を選ぶかという問題に帰着します。

一般論として、小さなデータ・セットが相手であれば、ここで取り上げたような最適化のテクニックは必要ありません。しかし、データ・セットが小さいという保証がない場合は、変換のためにどのテクノロジーを使うかによって、選択肢が限定されてきます。XSLエンジンが末尾再帰処理に対応しているのであれば、それが一番です。末尾再帰処理に対応していない場合は、基本的に併用方式が望ましいと言えます。その場合の分岐点の値は、状況にもよりますが、5~30が妥当でしょう。

再帰処理の考え方は、最初は理解しにくいかもしれませんが、使い込むにつれて、それがいかに便利で、いかにきれいな処理になるかがわかるはずです。


おまけ: ハノイの塔

情報科学の分野で、「ハノイの塔」というゲームは有名です。3本の棒 (塔) があって、そのうちの1本に何枚かの円盤が差し込まれています。要は、すべての円盤を別の棒に移すということですが、それにはルールがあります。まず、円盤は1枚ずつしか動かせません。また、円盤の大きさはそれぞれ違っていて、大きいほうの円盤が常に下になるようにしなければなりません。再帰処理の考え方を応用すると、この答えを簡単に導き出せます。

この「ハノイの塔」の解答が、今回の再帰処理を記述したXSLの最後のサンプルです。まず、冒頭で指定する円盤の数に基づいて、1つ1つの動きを記述したXMLファイルを用意しました。また、この解答をSVGのグラフィック表現に変換するためのXSLファイルを別に用意しました(SVG対応のプラグインを搭載したWebブラウザーがあれば、そのSVGを表示できます)。その2つのXSLファイルは、この記事で取り上げたXSLの再帰処理の2つの用例のサンプルになっています。この記事のコードにその2つのファイルも入れておきましたので、参考にしてみてください (参考文献を参照)。円盤の数を3に指定して実行した場合の出力をGIF形式に変換したのが、図3 です。ゲームでちょっと息抜きするのは、いかがでしょうか。

図3. 「ハノイの塔」の解答
図3

参考文献

  • この記事に関係するコードすべてを収めたzipファイルをダウンロードしてください (使用上の注意については、READMEファイルをご覧ください)。
  • 優れたXML/XSLインプリメンテーションが必要なら、Apache XML Project から、Xerces (XMLパーサー/DOMインプリメンテーション) と、Xalan (XSL変換プログラム) をダウンロードできます。
  • XML/XSLについては、次の記事をお勧めします。
関数型言語としてのXSLT

コメント

developerWorks: サイン・イン

必須フィールドは(*)で示されます。


IBM ID が必要ですか?
IBM IDをお忘れですか?


パスワードをお忘れですか?
パスワードの変更

「送信する」をクリックすることにより、お客様は developerWorks のご使用条件に同意したことになります。 ご使用条件を読む

 


お客様が developerWorks に初めてサインインすると、お客様のプロフィールが作成されます。会社名を非表示とする選択を行わない限り、プロフィール内の情報(名前、国/地域や会社名)は公開され、投稿するコンテンツと一緒に表示されますが、いつでもこれらの情報を更新できます。

送信されたすべての情報は安全です。

ディスプレイ・ネームを選択してください



developerWorks に初めてサインインするとプロフィールが作成されますので、その際にディスプレイ・ネームを選択する必要があります。ディスプレイ・ネームは、お客様が developerWorks に投稿するコンテンツと一緒に表示されます。

ディスプレイ・ネームは、3文字から31文字の範囲で指定し、かつ developerWorks コミュニティーでユニークである必要があります。また、プライバシー上の理由でお客様の電子メール・アドレスは使用しないでください。

必須フィールドは(*)で示されます。

3文字から31文字の範囲で指定し

「送信する」をクリックすることにより、お客様は developerWorks のご使用条件に同意したことになります。 ご使用条件を読む

 


送信されたすべての情報は安全です。


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=60
Zone=XML
ArticleID=243377
ArticleTitle=XSLで再帰処理を効果的に使用する
publish-date=10012002