(57)【特許請求の範囲】
【請求項１】
コンピュータの処理により、イテレータを用いて入力されたデータのデータ変換を記述可能なプログラミング言語を処理する方法であって、
前記プログラミング言語のイテレータのコードを、ジェネレータをオペレータとして含む中間言語上のジェネレータで記述されたコード（以下、ジェネレータ記述コードという）に変換するステップであって、前記イテレータのコード中の各ステートメントを読み出して、各ステートメントが所定のイテレータ部分式であることに応じて当該部分式を再帰的に処理してジェネレータ記述コードに変換し、当該再帰的に処理して変換された各ジェネレータ記述コードが１以上のｙｉｅｌｄ文を含むように、当該ｙｉｅｌｄ文を挿入するステップを含む、前記変換するステップと、
消費側のコードを読み込むステップと、
前記消費側のコードと前記ジェネレータ記述コードとの間でインライン置換によるコード書き換えを行うステップと
を含む、前記方法。
【請求項２】
前記イテレータを含むプログラミング言語においてオペレータが連結して書かれており、前記連結された一連のオペレータが前記インライン置換によって単一のコードにコンパイルされる、請求項１に記載の方法。
【請求項３】
前記コード書き換えから得られたプログラムの為のコンパイラを使用して前記コード書き換えから得られたプログラムをコンパイルするステップをさらに含む、請求項１又は２に記載の方法。
【請求項４】
前記イテレータを含むプログラミング言語がJaqlであり、
前記変換されたコードを更に、Javaバイトコードに変換するステップをさらに含む、請求項１〜３のいずれか一項に記載の方法。
【請求項５】
前記インライン置換によるコード書き換えを行うステップが、ジェネレータgがfor (x:g) {e}文の形で消費されるとき、gの定義中のyieldの出現をeで置き換えたもので、for (x:g) {e}自体を置き換えるステップを含む、請求項１〜４のいずれか一項に記載の方法。
【請求項６】
前記各ステップが、Hadoopフレームワークにおける、ジョブ・トラッカ又はタスク・トラッカで実行される、請求項１〜５のいずれか一項に記載の方法。
【請求項７】
コンピュータの処理により、イテレータを用いて入力されたデータのデータ変換を記述可能なプログラミング言語を処理するプログラムであって、前記コンピュータに、
前記プログラミング言語のイテレータのコードを、ジェネレータをオペレータとして含む中間言語上のジェネレータで記述されたコード（以下、ジェネレータ記述コードという）に変換するステップであって、前記イテレータのコード中の各ステートメントを読み出して、各ステートメントが所定のイテレータ部分式であることに応じて当該部分式を再帰的に処理してジェネレータ記述コードに変換し、当該再帰的に処理して変換された各ジェネレータ記述コードが１以上のｙｉｅｌｄ文を含むように、当該ｙｉｅｌｄ文を挿入するステップを含む、前記変換するステップと、
消費側のコードを読み込むステップと、
前記消費側のコードと前記ジェネレータ記述コードとの間でインライン置換によるコード書き換えを行うステップと
を実行させる、前記プログラム。
【請求項８】
前記イテレータを含むプログラミング言語においてオペレータが連結して書かれており、前記連結された一連のオペレータが前記インライン置換によって単一のコードにコンパイルされる、請求項７に記載のプログラム。
【請求項９】
前記コンピュータに、前記コード書き換えから得られたプログラムの為のコンパイラを使用して前記コード書き換えから得られたプログラムをコンパイルするステップをさらに実行させる、請求項７〜８のいずれか一項に記載のプログラム。
【請求項１０】
前記イテレータを含むプログラミング言語がJaqlであり、
前記コンピュータに、前記変換されたコードを更に、Javaバイトコードに変換するステップをさらに実行させる、請求項７〜９のいずれか一項に記載のプログラム。
【請求項１１】
前記インライン置換によるコード書き換えを行うステップが、ジェネレータgがfor (x:g) {e}文の形で消費されるとき、gの定義中のyieldの出現をeで置き換えたもので、for (x:g) {e}自体を置き換えるステップを含む、請求項７〜１０のいずれか一項に記載のプログラム。
【請求項１２】
前記各ステップが、Hadoopフレームワークにおける、ジョブ・トラッカ又はタスク・トラッカで実行される、請求項７〜１１のいずれか一項に記載のプログラム。
【請求項１３】
コンピュータの処理により、イテレータを用いて入力されたデータのデータ変換を記述可能なプログラミング言語を処理するシステムであって、
前記プログラミング言語のイテレータのコードを、ジェネレータをオペレータとして含む中間言語上のジェネレータで記述されたコード（以下、ジェネレータ記述コードという）に変換する手段であって、前記イテレータのコード中の各ステートメントを読み出して、各ステートメントが所定のイテレータ部分式であることに応じて当該部分式を再帰的に処理してジェネレータ記述コードに変換し、当該再帰的に処理して変換された各ジェネレータ記述コードが１以上のｙｉｅｌｄ文を含むように、当該ｙｉｅｌｄ文を挿入する、前記変換する手段と、
消費側のコードを読み込む手段と、
前記消費側のコードと前記ジェネレータ記述コードとの間でインライン置換によるコード書き換えを行う手段と
を備えている、前記システム。
【請求項１４】
前記イテレータを含むプログラミング言語においてオペレータが連結して書かれており、前記連結された一連のオペレータが前記インライン置換によって単一のコードにコンパイルされる、請求項１３に記載のシステム。
【請求項１５】
前記コード書き換えから得られたプログラムの為のコンパイラを使用して前記コード書き換えから得られたプログラムをコンパイルするコンパイル手段をさらに含む、請求項１３又は１４に記載のシステム。
【請求項１６】
前記イテレータを含むプログラミング言語がJaqlであり、
前記変換されたコードを更に、Javaバイトコードに変換する手段をさらに備えている、請求項１３〜１５のいずれか一項に記載のシステム。
【請求項１７】
前記インライン置換によるコード書き換えを行う手段が、ジェネレータgがfor (x:g) {e}文の形で消費されるとき、gの定義中のyieldの出現をeで置き換えたもので、for (x:g) {e}自体を置き換える手段を含む、請求項１３〜１５のいずれか一項に記載のシステム。
【請求項１８】
前記各ステップが、Hadoopフレームワークにおける、ジョブ・トラッカ又はタスク・トラッカで実行される、請求項１３〜１５のいずれか一項に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、１つのプログラミング言語で書かれたコードを別のプログラミング言語に変換することにより、実行速度を向上させるための技法に関するものである。
【背景技術】
【０００２】
プロセッサやディスク装置などのコンピュータのハードウェアが廉価になるにつれ、大量のデータをディスクに保存し、多数のコンピュータ・システム装置を互いに接続して、大量のデータを高速に処理する仕組みが提案されている。そのような仕組みの一つに、Google(R)が開発したMapReduceがある。
【０００３】
開発者は、MapReduceを利用することで、並列処理の難しい部分をMapReduceに任せることで、少ない労力で大規模な処理を実行できるようになる。
【０００４】
その後、MapReduceをオープンソースとして実装するものとして、Hadoop(商標)プロジェクトが立ち上げられた。
【０００５】
Hadoop(商標)MapReduce上で使用されるプログラミング言語として、Jaql、Pig、Hiveなどが開発されている。これらのプログラミング言語は、イテレータ(iterator)と呼ばれる、反復処理する仕組みをもつ。イテレータを用いると、大きなデータ全体をメモリに乗せずに処理することが可能であるため、データをイテレータによってアクセスし、データの変換をイテレータの変換として記述することが行われる。なお、Jaqlについては例えば、http://code.google.com/p/jaql/wiki/IOなどを参照されたい。また、Pigについてはhttp://pig.apache.org/を、Hiveについてはhttp://hive.apache.org/を参照されたい。
【０００６】
しかし、このような変換で得られたイテレータは複雑な制御や状態をもつことがあり、既存のJITコンパイラなどで容易に最適化できないことがある。
【０００７】
すなわち、既存のコンパイラは、制御フローグラフに基づいてプログラムの遷移を判断しながら、データフロー解析・最適化を行うが、イテレータの遷移はイテレータの内部状態で決定されるので、既存のコンパイラは正確なデータフローが判別しにくい。
【０００８】
例えば、iter->expand e式では、外部イテレータiterから得た各要素x0,x1,...について、内部イテレータの列e(x0),e(x1),...を計算し、それぞれの表現する列を連結するような結果イテレータを返す。この結果イテレータは、外部イテレータがもっていた状態に加えて、現在みている内部イテレータが何かという状態をもつ。
【０００９】
条件式if cond then iter1 else iter2では、condの評価結果を状態としてもつ。
【００１０】
定数サイズ配列式[e0,e1・・・.]から生成されるイテレータは内部に配列の添字を状態としてもつ。  これらのことが、複雑な制御や状態をもつことにつながる。
【００１１】
具体的に、$out = $in -> expand[$.a,$.b,$.c,$.d]
-> filter ($ > 0)
というJaqlのイテレータのステートメントによる処理において、結果イテレータ$outは、図１のような状態遷移図であらわされる。$out.next()は例えば、前回が$.bの読み出しで終われば、次の読み出しは$.cのところから再開する。このような処理は既存のコンパイラでは処理しにくい。というのは、$out.next()のコールサイトが、制御フローがジョインする場所になってしまうからである。
【００１２】
http://docs.oracle.com/javase/1.4.2/docs/api/org/xml/sax/package-summary.htmlに記述されている、XML SAX APIでは、イベント列として得られる入力が、イベントハンドラで処理される。しかし、この技法はJaqlに自明に適用することはできない。
【００１３】
尚、http://galax.sourceforge.net/compiler/にある、XQueryコンパイラのGalaxでも、イテレータによってマテリアライズされていないデータがアクセスされて、処理が複雑になることが知られている。より具体的に述べると、データのアクセスに複雑なイテレータ処理のコードが必要となりコンパイラ最適化がしづらいということがある。
【先行技術文献】
【非特許文献】
【００１４】
【非特許文献１】http://code.google.com/p/jaql/wiki/IO
【非特許文献２】http://pig.apache.org/
【非特許文献３】http://hive.apache.org/
【非特許文献４】http://docs.oracle.com/javase/1.4.2/docs/api/org/xml/sax/package-summary.html
【非特許文献５】http://galax.sourceforge.net/compiler/
【発明の概要】
【発明が解決しようとする課題】
【００１５】
この発明の目的は、プログラミング言語におけるイテレータの処理のコードの実行を高速化することにある。
【００１６】
この発明の他の目的は、イテレータの内部状態の増加を抑えて、最適な実行コードを生成する技法を提供することにある。
【課題を解決するための手段】
【００１７】
この発明は、イテレータの処理のコードを、ジェネレータをもつ中間言語上でデータ変換をジェネレータ変換で表現するように変換し、コンパイラにより最適化することによって上記課題を解決する。
【００１８】
すなわち、本発明に係る変換プログラムにより、データ変換をジェネレータ変換で表現する。例えば、入力イテレータinは for (x:in) {yield x} のようにジェネレータに変換される。
【００１９】
iter -> expand e は for (x:iter) {for (y : e (x)) {yield y}} のようにジェネレータ変換される。
【００２０】
条件式 if e then iter1 else iter2 は if e then for (x : iter1) {yield x} else for (y:iter2) {yield y} のように変換される。
【００２１】
配列式 [e0, e1, ..] は、yield e0; yield e1; … のようにジェネレータとして変換される。
【００２２】
次に本発明に係る変換プログラムは、さらに中間言語上でジェネレータのインライニング書き換えを適用する。ジェネレータのインライニングとは、ジェネレータgがfor (x:g) {e}文の形で消費されるとき、「g の定義中の yield の出現をeで置き換えたもの（消費側のコードを生成側のコードにインライン）」で「for (x:g) {e}」自体を置きかえる（生成側のコードを消費側のコードにインライン）ことで実現される。消費側が最終的に、for (x : g) { … } のようにイテレータを使用するコードであったなら、インラインにより結果コードはジェネレータをサポートしないランタイムでも処理できる通常コードになる。
【００２３】
イテレータの消費側のコードが得られないなどの理由により、イテレータとしての途中結果が必要になり、かつランタイムがジェネレータをサポートしない場合には、結果コードをもう一度イテレータに変換しなおす。この場合は、yield時のローカル変数フレームをセーブ・ロードする機構が必要になるが、なお各 yield の継続をそれぞれ別の関数のエントリとしてコンパイルすることで、元々のイテレータよりは簡単な制御構造を得ることができる。
【００２４】
Jaql の処理系では、消費側のfor (x:g) {e}文の形のコードが得られる。
【００２５】
本発明に係る変換プログラムは、ジェネレータとして変換され、さらにインライニング書き換えを適用された中間言語のコードを、その中間言語向けに作成したコンパイラで、実行可能コードに変換する。その際、コンパイラは、既存のコンパイラ最適化を適宜利用する。
【発明の効果】
【００２６】
この発明によれば、イテレータが持っていた状態は、ジェネレータ・インライン後のプログラムのプログラムポイントにマップされる。よって、制御フローグラフに基づく既存の最適化によって、各状態での処理をより精緻に最適化できるようになる。
【図面の簡単な説明】
【００２７】
【図１】従来技術におけるイテレータの処理を模式的に示す図である。
【図２】本発明を実施するためのHadoop(商標)に基づくハードウェア構成のブロック図である。
【図３】本発明を実施するための機能構成のブロック図である。
【図４】イテレータをジェネレータに変換する処理のフローチャートを示す図である。
【図５】イテレータをジェネレータに変換する処理を模式的に示す図である。
【図６】ジェネレータをもつ中間言語でのインライニング処理のフローチャートを示す図である。
【発明を実施するための形態】
【００２８】
以下、図面に従って、本発明の実施例を説明する。これらの実施例は、本発明の好適な態様を説明するためのものであり、発明の範囲をここで示すものに限定する意図はないことを理解されたい。また、以下の図を通して、特に断わらない限り、同一符号は、同一の対象を指すものとする。
【００２９】
図２は、本発明を実施するための一例のハードウェア構成を示すブロック図である。図２の構成は、本発明の実施はこれには限定されないが、Hadoop(商標)に従うものである。
【００３０】
図２において、Ｌ３スイッチ２０２には、Hadoop(商標)に特徴的なマスター・サーバである、ネーム・ノード(NameNode)２０４と、ジョブ・トラッカ(JobTracker)２０６が接続されている。Ｌ３スイッチ２０２は、ＯＳＩ参照モデルにおけるネットワーク層（レイヤ３）データの転送処理を担う。
【００３１】
Ｌ３スイッチ２０２にはまた、各々Ｌ２スイッチ２０８ａ、２０８ｂ、・・・、２０８ｎを介して、ラック型サーバ２１０ａ、２１０ｂ、・・・、２１０ｎが接続されている。ラック型サーバは、複数の薄型のサーバを積層した構造であり、Ｌ２スイッチは、その積層した各々のサーバの各々を、ルータとしてＬ３スイッチ２０２に接続する。Ｌ２スイッチは、スイッチング・ハブとも呼ばれ、データリンク層で動作する機器である。
【００３２】
ラック型サーバ２１０ａ、２１０ｂ、・・・、２１０ｎは、Hadoop(商標)のスレーブ・サーバ、すなわち、タスク・トラッカとデータ・ノードの役割を果たす。
【００３３】
Ｌ３スイッチ２０２にはさらに、マスター・サーバに処理リクエストを出す、クライアント・コンピュータ２１２が接続されている。ここでは一台のクライアント・コンピュータしか示されていないが、複数のクライアント・コンピュータを接続し、それらから処理リクエストを受け付けるようにしてもよい。
【００３４】
ネーム・ノード２０４は、ラック型サーバ２１０ａ、２１０ｂ、・・・、２１０ｎをデータ・ノード(DataNode)として、Hadoop分散ファイル・システム（ＨＤＦＳ）を管理する。
【００３５】
ジョブ・トラッカ２０６は、ＨＤＦＳ上で、ラック型サーバ２１０ａ、２１０ｂ、・・・、２１０ｎをタスク・トラッカ(TaskTracker)として、MapReduce処理を行う。
【００３６】
これには限定されないが、ネーム・ノード２０４とジョブ・トラッカ２０６の好適なコンピュータ・ハードウェア・システムとして、IBM(R) Power 780を使用することができる。また、ラック型サーバに積層される各サーバは、IBM(R) Power 710 Expressを使用することができる。
【００３７】
これらのサーバのハードディスク・ドライブに導入されるオペレーティング・システムは、好適にはLinux(R)であり、Linux(R)上でJava(R)実行環境を構成するように、Java(R)プログラムが導入されている。
【００３８】
ネーム・ノード２０４とジョブ・トラッカ２０６には、Hadoop(商標)のパッケージが導入されている。このとき導入されるHadoop(商標)のパッケージは、これには限定されないが、好適には、The IBM Distribution of Apache Hadoopである。
【００３９】
クライアント・コンピュータ２１２は、メモリとＣＰＵとハードディスク・ドライブと通信インターフェースをもつ通常のパーソナル・コンピュータでよい。クライアント・コンピュータ２１２のハードディスク・ドライブには、オペレーティング・システムとして、Linux(R)が導入され、さらに、Java(R)実行環境を構成するように、Java(R)プログラムが導入されている。
【００４０】
クライアント・コンピュータ２１２は、Hadoop(商標)において、ジョブ・クライアント(JobClient)の役割を果たす。すなわち、クライアント・コンピュータ２１２の役割には、ジョブ・トラッカ２０６にMapReduceのジョブを依頼することと、MapReduceジョブで処理するためのデータをＨＤＦＳに転送することが含まれる。
【００４１】
なお、ネーム・ノード２０４、ジョブ・トラッカ２０６、及びラック型サーバ２１０ａ、２１０ｂ、・・・、２１０ｎと、それらに導入されたHadoop(商標)のパッケージからなる構成は、Hadoop(商標)フレームワークとも呼ばれる。
【００４２】
図２の構成は、Hadoop(商標)の一般的な構成であり、ジョブ・トラッカ２０６とは別にジョブ・クライアントの役割を果たすクライアント・コンピュータを設置するものであるが、本発明のより好適な実施例では、ジョブ・トラッカ２０６自身がジョブ・クライアントの役割を果たすようになされる。
【００４３】
図３は、ジョブ・トラッカ２０６において、ハードディスク・ドライブに保存された、ジョブ・クライアントの役割を果たす機能構成を示すブロック図である。図３において、メイン・プログラム３０２は、ジョブ・クライアントの処理を開始し、あるいは処理を制御する機能をもつ。
【００４４】
図示しないが、ジョブ・トラッカ２０６には、Jaqlの処理系が導入されている。Jaqlの処理系は、テキストエディタ、プログラム開発ツールなどにより作成された、Jaqlのソースコードを、MapReduce用のタスクそれぞれをあらわす小さいソースコードに分解して、主記憶に配置し、あるいはハードディスク・ドライブに保存する機能をもつ。
【００４５】
図３で示すソースコード３０４は、そのように分解されたJaqlのソースコードである。変換モジュール３０６は、ソースコード３０４を中間言語コード３０８に変換する機能をもつ。その変換機能は、(1) イテレータをジェネレータに変換した中間言語コードを生成する機能と、(2) 中間言語コード上でジェネレータのインライニング書き換えを行う機能をもつ。ここで中間言語コードは、既存のプログラミング言語である必要はなく、この処理のために特に設計されたものでよい。但し、この中間言語コードは、ジェネレータをサポートするものであることが必須である。
【００４６】
尚、ジェネレータとは、プログラミング言語の機構の一つであり、Python、C#、C++、XL、PHPなどのプログラミング言語でサポートされている。典型的には、ジェネレータを備えた言語は、yield文という、return文の親戚のような文をもつ。returnとyieldの違いは、returnでは状態は保存されないが、yieldは呼び出し側に戻っても状態がセーブされていて、次に呼ばれるときには、前回yieldした場所の次の場所から状態を再開できることである。この発明によれば、一旦ジェネレータをサポートする中間言語に変換するので、元の言語がジェネレータをサポートしていなくてもよい。
【００４７】
コンパイラ３１０は、変換モジュール３０６の変換結果としてハードディスク・ドライブに書き出された中間言語コード３０８をコンパイルして、Java(R)バイトコードまたは、Hadoop(商標)フレームワークが解釈して実行可能なバイナリコードである、実行可能コード３１２を一旦主記憶に配置し、あるいはハードディスク・ドライブに書き出す。
【００４８】
処理の流れは、次のようになる。すなわち、上記ジョブ・トラッカ２０６のジョブ・クライアントの役割を果たす部分がまず起動し、これがジョブ・トラッカ２０６にジョブを依頼する。その後ジョブ・トラッカ２０６におけるJaql処理系が、上述のように、Jaqlのソースコードを、MapReduce用のタスクそれぞれをあらわす小さいソースコードに分解して、主記憶に配置し、あるいはハードディスク・ドライブに保存する。
【００４９】
分解された各々の小さいソースコードは、一旦変換モジュール３０６によって中間言語コード３０８に変換されて、この中間言語コード３０８がコンパイラ３１０によって実行可能コードにコンパイルされる。それらの各々の実行可能コードは、ＨＤＦＳ上のデータを入力として使うものであった場合に、MapReduceジョブにおける、Map/Reduceそれぞれのタスクのための実行プログラムのフラグメントに対応する。
【００５０】
ジョブ・トラッカ２０６は、これらの実行可能コードのフラグメントを、分散処理のためのJaql処理系のコピーとともに、ラック型サーバ２１０ａ、２１０ｂ、・・・、２１０ｎである各タスク・トラッカに配る。各タスク・トラッカのノードでタスクが起動すると、処理系のコピーが起動され、タスク・トラッカは、配られた実行可能コードのフラグメントを実行する。図３では、このような処理を、Hadoop(商標）フレームワーク３１４上で実行するものとして示されている。
【００５１】
なお、ジョブ・トラッカ２０６で実行可能コードのフラグメントをコンパイルし、タスク・トラッカに転送する代わりに、タスク・トラッカの各々に変換モジュール３０６とコンパイラ３１０を導入しておき、ジョブ・トラッカ２０６が、分解されたJaqlソースコードのフラグメントと分散処理のためのJaql処理系のコピーをタスク・トラッカに転送し、タスク・トラッカ側でJaqlソースコードのフラグメントの中間言語コード３０８への変換、そしてそれに続くコンパイルと、結果の実行可能コードを実行するようにしてもよい。
【００５２】
ここで、本発明の実施例で使用される、Jaqlのイテレータを、中間言語のジェネレータに変換される規則について記述する。
【００５３】
入力イテレータ in ⇒ for (x : in) {yield x} 
iter -> transform e ⇒ for (x : iter) {yield e(x)}
iter -> expand e ⇒ for (x : iter) {for (y : e(x)) {yield y}}
iter -> filter e ⇒ for (x : iter) {if (e(x)) yield y}
iter -> union other ⇒ for (x : iter) {yield x}; for (x : other) {yield x}
iter -> group by key into agg ⇒ 
Map m;  
for (x : iter) {
if (m.contains(key(x)) {m.put(key(x), agg(m.get(key(x)), x))} 
else {m.put(key(x), x)}}
for ((k,v) : map) {yield v}
iter -> tee e ⇒ for (x : iter) {e(x); yield x}
iter -> top k ⇒ int c = 0; for (x : iter) {if (c++ >= k) return; yield  x}
if e then iter1 else iter2 ⇒
if e {for (x : iter1) {yield x}} else {for ( x: iter2) {yield x}}
[e0, e1, ..] ⇒ yield e0; yield e1; …
【００５４】
図４は、この規則を実装した、変換モジュール３０６における、イテレータをジェネレータに変換した中間言語コードを生成する処理のフローチャートを示す図である。この処理は、ステートメント（文）毎に呼び出されることを理解されたい。
【００５５】
図４において、変換モジュール３０６は、ステップ４０２で、ソースコード（プログラム）３０４の１つのステートメントを読み込む。
【００５６】
変換モジュール３０６は、ステップ４０４で、読み込んだステートメントがread()などの入力イテレータかどうか判断し、もしそうなら、ステップ４０６で、for (x:read()) {yield x}を生成して処理を終わる。
【００５７】
読み込んだステートメントがread()などの入力イテレータでないなら、変換モジュール３０６は、ステップ４０８で、読み込んだステートメントがiter->transform eかどうか判断し、もしそうなら、ステップ４１０で、部分式iterを再帰的に処理して、ステップ４１２で、for (x:iter) {yield e(x)}を生成して処理を終わる。
【００５８】
読み込んだステートメントがiter->transform eでないなら、変換モジュール３０６は、ステップ４１４で、読み込んだステートメントがiter->expand eかどうか判断し、もしそうなら、ステップ４１６で、部分式iterを再帰的に処理して、ステップ４１８で、for (x:iter) {for (y:e(x)) {yield y}を生成して処理を終わる。
【００５９】
読み込んだステートメントがiter->expand eでないなら、変換モジュール３０６は、ステップ４２０で、読み込んだステートメントがiter->filter eかどうか判断し、もしそうなら、ステップ４２２で、部分式iterを再帰的に処理して、ステップ４２４で、for (x:iter) {if (e(x)) {yield y}を生成して処理を終わる。
【００６０】
読み込んだステートメントがiter->filter eでないなら、変換モジュール３０６は、ステップ４２６で、読み込んだステートメントがiter1->union iter2かどうか判断し、もしそうなら、ステップ４２８で、部分式iter1,iter2を再帰的に処理して、ステップ４３０で、for (x:iter1) {yield x}; for (x:iter2) {yield x}を生成して処理を終わる。
【００６１】
読み込んだステートメントがiter1->union iter2でないなら、変換モジュール３０６は、ステップ４３２で、読み込んだステートメントがiter->group by key into eかどうか判断し、もしそうなら、ステップ４３４で、部分式iterを再帰的に処理して、ステップ４３６で、Map m; for (x:iter) {if m.contains(key(x)) m.put(key(x),a(m.get(key(x)),x)) else m.put(key(x),x)}; for ((k,v):map) {yield v}を生成して処理を終わる。
【００６２】
読み込んだステートメントがiter->group by key into eでないなら、変換モジュール３０６は、ステップ４３８で、読み込んだステートメントがiter->tee eかどうか判断し、もしそうなら、ステップ４４０で、部分式iterを再帰的に処理して、ステップ４４２で、for (x:iter) {e(x); yield e(x)}を生成して処理を終わる。
【００６３】
読み込んだステートメントがiter->tee eでないなら、変換モジュール３０６は、ステップ４４４で、読み込んだステートメントがiter->top kかどうか判断し、もしそうなら、ステップ４４６で、部分式iterを再帰的に処理して、ステップ４４８で、for (x:iter) {e(x); yield e(x)}を生成して処理を終わる。
【００６４】
読み込んだステートメントがiter->top kでないなら、変換モジュール３０６は、ステップ４５０で、読み込んだステートメントがif e then iter1 else iter2かどうか判断し、もしそうなら、ステップ４５２で、部分式iter1、iter2を再帰的に処理して、ステップ４５４で、if e {for (x:iter1) {yield x}} else {for (x:iter2) {yield x}}を生成して処理を終わる。
【００６５】
読み込んだステートメントがif e then iter1 else iter2でないなら、変換モジュール３０６は、ステップ４５６で、読み込んだステートメントが[e0,e1,...]かどうか判断し、もしそうなら、ステップ４５８で、yield e0; yield e1; ...を生成して処理を終わる。
【００６６】
読み込んだステートメントが[e0,e1,...]でないなら、変換モジュール３０６は、ステップ４６０で、変換しないでステートメントを出力して処理を終わる。
【００６７】
図５は、イテレータのジェネレータへの変換の具体例を示す図である。図５(a)に示すイテレータの処理におけるnext()は、以下のようなコードで記述される。
next() {
do { 
if (this.cur == null) {
this.cur = $in.next();
if (this.cur == null) return null;
this.index = 0;
}   
if (this.index == 0) x = this.cur.a;
if (this.index == 1) x = this.cur.b;
if (this.index == 2) x = this.cur.c;
if (this.index == 3) x = this.cur.d;
this.index++;
if (this.index == 4) {
this.cur = null;
}
} while(x > 0);
return x;
}
【００６８】
図４に示した、イテレータをジェネレータに変換する処理によれば、図５(a)に示すイテレータの処理が、図５(b)に示す、yieldが個々に挿入された、ジェネレータをもつコードに変換される。以下のようなコードで記述される。
for (cur in $in) {
if (cur.a > 0) yield cur.a;
if (cur.b > 0) yield cur.b;
if (cur.c > 0) yield cur.c;
if (cur.d > 0) yield cur.d;
}
【００６９】
次に、図６のフローチャートを参照して、変換モジュール３０６における、ジェネレータのインライニングの処理について説明する。
【００７０】
図６において、ステップ６０２で、変換モジュール３０６は、最適化対象のプログラムＰと、yieldに置換されるプログラムＱとを入力する。最適化対象のプログラムＰは、図４のフローチャートで示す処理の結果として用意されるものである。yieldに置換されるプログラムＱとは、コンシューマ(consumer)とも呼ばれる。本発明で想定するJaqlのプログラムは、オペレータを連結して書かれている。基本的には各オペレータが先行するオペレータのコンシューマとなる。本発明では連結された一連のオペレータをインライン最適化によって、単一のコードにコンパイルする。最終のコンシューマとなるオペレータにはいくつか種類がある。例えばprintであれば、標準出力へのストリーム出力がインラインされるコードとなり、それがMapReduceオペレータであればHadoop(商標)のOutputCollectorというAPI への出力がインラインされるコードとなる。各オペレータに対するこれらのコードはJaqlランタイムのソースから抽出する。
【００７１】
図６のフローチャートに戻って、変換モジュール３０６は、ステップ６０４で、プログラムＰの各文（ステートメント）を順次調べる。すなわち、ステップ６０６で、最適化の文がfor (x:g) {R}かどうか判断し、もしそうなら、ステップ６０８で、Rを再帰的に処理し、ステップ６１０で、ステップ６０８の結果を、yieldに置換されるプログラムQ'(x)としてgを再帰的に処理し、ステップ６１８に進んで、文がまだあるかどうか判断し、もうないなら処理を終わり、まだ文があるならステップ６０４に戻る。
【００７２】
ステップ６０６に戻って、最適化の文がfor (x:g) {R}でないなら、変換モジュール３０６は、ステップ６１２で最適化の文がyield eかどうか判断し、もしそうならQ(e)を出力し、ステップ６１４に進む。
【００７３】
ステップ６１４で最適化の文がyield eでないなら、変換モジュール３０６は、ステップ６１８で文をそのまま出力し、ステップ６１８に進む。
【００７４】
次に、この処理の具体例を示す。
先ず、イテレータをジェネレータに変換した次のようなコードがあるとする。
for (JsonValue x : in )  {
if ( toInt(x) > 0)  {
yield x;
yield x;
yield x;
}
}
return;
【００７５】
そして、コンシューマが次のコードだとする。
for (sonValue x : out )  {
println(x);
}
【００７６】
すると、ジェネレータをインライニングした結果は、下記のとおりとなる。
for (JsonValue x : in )  {
if ( toInt(x) > 0)  {
println(x);
println(x);
println(x);
}
}
return;
【００７７】
以上、本発明を、Jaql言語をHadoop(商標)フレームワークで使用する実施例に基づき説明してきたが、この発明は、Jaql言語には限定されず、Pig、Hiveなど、イテレータをもつ他のプログラミング言語にも適用可能である。
【００７８】
また、実装するプラットフォームは、Hadoop(商標)フレームワークに限定されず、通常のウェブ・サーバの環境や、スタンドアロンのシステム上でも実装可能である。オペレーティング・システムも、Linux(R)に限らず、マイクロソフト社のWindows(商標) 7、Windows XP(商標)、Windows(商標)2003サーバ、アップルコンピュータのMac OS(商標)などの、使用されるＣＰＵに適合する任意のものでよい。
【００７９】
さらに、イテレータをジェネレータに変換する処理と、中間言語のコンパイルの処理は、ジョブ・トラッカ上でなく、別のコンピュータ上で実行するようにしてもよい。
【００８０】
あるいは、スタンド・アロンのコンピュータ上でも、本願発明に従う、イテレータをジェネレータに変換する処理と、中間言語のコンパイルの処理は実施可能であることも理解されたい。
【符号の説明】
【００８１】
２０４  ネーム・ノード
２０６  ジョブ・トラッカ
２１０ａ、・・・、２１０ｎ  ラック型サーバ
２１２  クライアント・コンピュータ
３０４  ソースコード
３０６  変換モジュール
３０８  中間言語コード
３１０  コンパイラ
【図１】
0005936118.tif 000002
【図２】
0005936118.tif 000003
【図３】
0005936118.tif 000004
【図４】
0005936118.tif 000005
【図５】
0005936118.tif 000006
【図６】
0005936118.tif 000007