ヒント: XSLT での再帰によるループ

XSLT の機能を拡張するテクニック

Comments

XSLT はチューリング完備です。つまり、十分なメモリーさえあれば、XSLT は他のチューリング完備言語 (C++など) で計算できるものなら何でも計算できます。これは、より伝統的な言語に慣れているプログラマーにとって、ちょっとした驚きです。結局、XSLT には、ループや mutable 変数も含めて、多くのアルゴリズムにとって重要ないくつかの機能が欠けています。

: XSLT で変数と呼ばれるものは、他のほとんどの言語では定数と呼ばれています。従来のプログラミングでの変数よりは代数変数に近いものです。

関数型プログラミング

先ほど述べた欠落は、過失によるものではありません。XSLT は、手続き型言語ではなく関数型言語です。C や Pascal などの手続き型言語では、プログラムは一連のステップとして定義され、それらを指定された順序で実行することによって、シーケンスの最終ステップとして最終結果が生成されます。関数型言語では、プログラムは他の関数から成る関数として定義され、それらを評価することで最終結果が導き出されます。関数型言語の大きな利点は、実行の順序は問題ではないということです。単純な例として、次のような 2 つの (代数) 関数を考えてみましょう。

f(x) = 2*x
g(x) = x - 3

関数 h(x) は f と g の合成であるとします。

h(x) = f(g(x))

この関数は、g を先に評価してもかまいませんし、

h(x) = f(x - 3) = 2 * (x - 3) = 2x - 6

f を先に評価してもかまいません。

h(x) = 2 * g(x) = 2 * (x - 3) = 2x - 6

どちらも同じ答えになります。言語の関数性は、言語を並列処理になじみやすくします。どの部分を他の部分より先に評価するか気にせずに、プログラムの複数の部分を同時に評価できるからです。当然、スレッドセーフです。

関数型言語は、XSLT も含めて、従来のループを含むことができません。ループには時間的な前後関係があるからです。すなわち、典型的なループは、i==1 が i==2 よりも前に起こるように作成され、コンパイルされます。もちろん、ループを前方ではなく後方に実行したり、ループ・カウンターを 1 以外の値で増分したり、あるいは、while 文のようにループ・カウンターを完全になくすこともできます。しかし、ループの種類に関係なく、実行の順序が重要であり、この点が関数型プログラミングとは対照的です。

再帰

関数型言語では、従来の言語ではループで行われているタスクのほとんどが、代わりに再帰によって行われます。パラメーターが変数の代わりです。たとえば、最近、私は、コンパイル時には個数がわからないが、一定の数のドット (ピリオド) をプリントする方法を尋ねられました。これは、たとえばレストランのメニューを書式化するときに便利です。メニューでは、料理名と価格の間のドットの数を料理によって変えなければならないことが多いからです。

Crawfish Etoufee.......$9.95
Fried Chicken..........$6.95

C では、次のような単純な関数を使います。

void printDots(int n) {

  int i;

  for (i = 0; i < n; i++) {
    printf(".");
  }
  
}

しかし、これが問題を解決する唯一の方法ではありません。ループの代わりに、次のような再帰を使うこともできます。

void printDotsRecursively(int n) {

  if (n > 0) {
    printf(".");
    printDots(n-1);
  }
  
}

これは C では珍しいやり方かもしれません。しかし、XSLT では、再帰が唯一の選択肢です。

次のテンプレートは、count パラメーターの値として渡された正確な数のドットを生成します。ロジックは簡単です。$count の値がゼロより大きければ、ピリオドを出力し、count パラメーターを 1 だけ減らして、関数を再び呼び出します。そうでない場合は何もしません。これは基本的に、printDotsRecursively 関数で使用されているのと同じアルゴリズムであり、C ではなく XSLT で実装されているだけのことです。

<xsl:template name="dots">
  
      <xsl:param name="count" select="1"/>

      <xsl:if test="$count > 0">
        <xsl:text>.</xsl:text>
        <xsl:call-template name="dots">
          <xsl:with-param name="count" select="$count - 1"/>
        </xsl:call-template>
      </xsl:if>
      
  </xsl:template>

たとえば、ドットを 100 個プリントするには、count パラメーターの値として 100 を指定してテンプレートを呼び出します。

    <xsl:call-template name="dots">
      <xsl:with-param name="count" select="100"/>
    </xsl:call-template>

定数値を渡す代わりに、プリントするドットの数を何か他の値に基づいて計算することもできます。たとえば、次の命令は、価格と料理名の長さ (より具体的に言うと、コンテキスト・ノードの price および entree 子要素の文字列値の長さ) を除いて、メニューの 1 行 80 文字を埋めるのに必要な数のドットをプリントします。

    <xsl:call-template name="dots">
      <xsl:with-param name="count" 
                select="80 - string-length(entree) - string-length(price)"/>
    </xsl:call-template>

まとめ

ループを再帰に置き換えるには、C、XSLT、または Scheme のいずれでも、ある程度の慣れが必要です。しかし、このテクニックにはエレガンスさがあります。XSLT で頻繁に使用する必要があるわけではありませんが、標準の XSLT では他に方法がない厄介なタスクを成し遂げることができます。


ダウンロード可能なリソース


関連トピック

  • Wikipedia にある、関数型プログラミングに関する記事を読んでください。ここでは、チューリング完備に関しても学ぶことができます。
  • Michael Kay 著による XSLT への標準的な入門記事、XSLT Programmer's Referenceを読んでください。彼は developerWorks にも XSLT に関する 2 本の記事、「XSLT はどのような言語か」 (2005 年 4 月) と「Saxon: XSLT プロセッサーの解体新書」 (2005 年 4 月) を書いています。
  • XML テンプレートの基礎を解説した Elliotte Harold の著書、Processing XML with Java の Chapter 17 で、再帰について詳しく学んでください。
  • W3C の XSLT 2.0 仕様を読むと、この記事で XSLT 1.0 での再帰を使って行ったタスクを、もっと容易に行う方法が他にも幾つかあることが分かります。しかし XSLT 2.0 は、XSLT の基本的な機能は変えていません。ですから多くのタスクでは、やはり再帰が必要になります。
  • ここで議論したメニューの問題を解決するために、EXSLT のパディング機能を試してみてください。ただしこれは、一つのことしかできない代物で、再帰によって解決できるような他の多くの問題には対応していません。EXSLT パディング機能の純粋な XSLT 実装では、この記事で紹介した、もう少し効率的な再帰アルゴリズムを使用しています。
  • developerWorks の XML ゾーンでは、XML に関する資料が他にも豊富に用意されています。
  • XML および関連技術において IBM 認証開発者になる方法については こちら を参照してください。

コメント

コメントを登録するにはサインインあるいは登録してください。

static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=60
Zone=XML
ArticleID=242460
ArticleTitle=ヒント: XSLT での再帰によるループ
publish-date=06292005