双方向変換は,元のデータの一部を抽出し加工する順方向変換と,順方向変換で得られたデータに対する更新を元データに反映する逆方向変換の二つの変換から構成される.双方向変換を用いることで,XML文書の同期や相互変換を行える.さらには,双方向変換はプレゼンテーション指向の文書作成やソフトウェアエンジニアリングにも利用できる.しかし,順方向変換に対し,「振る舞いのよい」逆方向変換を与えるのは難しい.元データへの更新の反映は,たとえば「更新された元データにふたたび変換を適用すると更新を行った変換後のデータと等しい」,「変換後のデータの構築に関係ない部分を変更しない」などの順方向変換に対し何らかの整合性を保たなければならない.また,仮に逆方向変換が与えられたとしても,その動作が振る舞いのよいものであるかを確認するのも容易ではない.さらには,ある順方向変換に対して双方向に動作する逆方向変換は一つとは限らず,逆方向変換の中には,振る舞いはよいもののほとんどの更新を反映することができず効果的でない逆方向変換も含まれる.よって,順方向変換から,振る舞いがよく効果的な逆方向変換を求める手法が求められている.

近年,木構造データ上の双方向変換の重要性は増してきている.特に木構造データの一種であるXMLは広く普及しており,様々なアプリケーション間のデータ受け渡し用のデータの事実上標準となっている.それぞれのアプリケーションが異なる形式のXMLを要求していることも多いため,XMLを様々な形式に変換できると便利である.また,そういった場合に,変換後のデータの上でなされた更新を元のデータに反映することができればさらに便利である.

これまで,順方向変換に対し「補関数」という関数を与えることで,振る舞いのよい逆方向変換を定められることが知られていた.直観的には,補関数とは,「副作用のない」更新の反映を特徴付けるため導入された概念であり,元データのうち順方向変換の結果の構築に関係のない部分を全て抽出する関数である.よって,補関数値を不変に保つことで,変換結果に関係のない部分を変更することなく元データを更新することができる.しかし,数学的な関数としてではなく実行可能なプログラムとして補関数を求める議論は少ない.これまで,関係データベース上の問い合わせについて補関数を問い合わせの形で求める研究はあったものの,木構造データに対する変換プログラムに対する補関数プログラムの導出についての議論はなかった.また,補関数プログラムが仮に求まったとしても,数学的に逆方向変換関数を定義する場合とは違い,逆方向変換プログラムを求めるのは容易ではない.

本論文では,我々は特定のクラスの関数型言語で記述された木構造データ上の順方向変換プログラムから補関数プログラムを導出し,それに基づき逆方向変換プログラムを自動導出する「プログラムの双方向化」手法を提案する.提案手法は順方向変換の単射性に注目する.順方向変換プログラムは一般には単射ではないために,元データに変換結果の構築に関係ない部分が含まれる.補関数はこの変換結果の構築に関係ない部分を含まねばならないので,我々は,順方向変換プログラムにおける「プログラムが単射でなくなっている場所」において適切に情報を補うように順方向変換に対する補関数を構成する.

本研究の主な貢献は次の二点である.

一つ目の貢献は,順方向変換記述する言語を適切に制限することにより,プログラムを自動的に双方向化する手法を与えたことである.順方向変換記述言語はtreelessでaffineと制限されているものの,多くの基本的な変換を記述することができる.また,制限されているおかげでプログラムの単射性を効果的に解析することができる.プログラムの単射性を解析することにより我々は補関数が補うべき情報を適切に知ることができるため,より効果的な逆方向変換を定める補関数を導出することができる.さらに,制限により,得られた補関数プログラムから逆方向変換プログラムを導出するのも容易になっている.

二つ目の貢献は,XML上の双方向変換を記述できるように一つ目の貢献で述べた双方向化の手法を拡張したことである.確かに,treelessでaffineな言語で記述されたプログラムに対する双方向化の手法を,双方向結合子などの他の手法と組み合わせることで広範な順方向変換プログラムに適用することは可能である.しかし,そのようにして得られる逆方向変換はしばしば効果的ではない場合がある.XMLの変換においては,XMLの要素列の連接や変換結果の複製,そして元データの複数走査を順方向変換が含む場合に,素朴に導出した逆方向変換はあまり効果的でないものになることが多い.これらの問題箇所に対し,我々は,双方向化手法を拡張しまた適切に言語の補助を与えることにより,特定のクラスのXML変換プログラムに対しても効果的な逆方向変換を自動導出する手法を与えた.

以上が本論文の要旨である.

近年、木構造データ上の双方向変換の重要性が増してきている.とくに、木構造データの一種であるXML文書は広く普及しており、さまざまなアプリケーション間のデータ受渡しのためのデータ形式の標準となっている。しかし、それぞれのアプリケーションが異なる形式を要求していることも多く、XML文書をさまざまな形式に変換するための効率的な処理法が必要とされている。このような変換処理において、変換を施した後の文書の上でなされた更新を元の文書に反映させるという変換も頻繁に求められるものである。このような、木構造データ上で一対をなす順方向と逆方向の変換、すなわち双方向変換を統一的に捉える枠組みが注目されている。

本論文は「補関数によるプログラムの双方向化に関する研究」と題し、全9章から成る。本論文は、関数型言語で記述された木構造データ上の順方向変換プログラムから補関数プログラムを導出し、それに基づいて逆方向変換プログラムを自動導出するプログラムの双方向化の手法を論じたものである。本研究の主要な成果は、順方向変換の記述言語の機能を適切に制限することによりプログラムを自動的に双方向化する手法を与えたことと、XML文書上の双方向変換を記述できるようにその双方向化の手法を拡張したことである。

第1章「はじめに」では本論文の導入として、背景、目的、アプローチ、貢献等を簡単に要約し、論文の構成を示している。また、論文中を通して使う概念および記法を説明している.

第2章「関連研究」では、双方向変換分野における本論文に関係の深い研究を紹介している。また、双方向変換と関連の深い、単射関数から逆関数を導出するプログラム逆計算、単射関数とその逆関数を同時に記述する可逆計算、本論文で扱う双方向変換の前身であるビュー更新も紹介している。

第3章「補関数に基づく双方向化」は本論の準備にあたる章の一つである。この章では、双方向変換の定義、および本論文のプログラム双方向化手法の基礎となっている「補関数に基づく双方向化」(Bancilhon, Spyratos 1981)について述べている。ここでは、また、補関数に基づく双方向化により、双方向変換に要求される種々の振舞いのよさが達成されることを示している。

第4章「正規木文法と正規生垣文法」では前章と同様に本論の準備を行っている。この章では本論文で議論するプログラムの扱うデータ構造の木(tree)、およびXML文書の表現である生垣(hedge)について述べている。また、第5章および第8章におけるプログラムの双方向化で用いる木と生垣の集合を表現する正規木文法と正規生垣文法を紹介している。

第5章「プログラムの双方向化」では、本論文の成果であるプログラムの双方向化に関する基本的な考え方を示している。この章では、プログラム言語で記述された順方向変換から、自動的に振舞いのよい逆方向変換を導出する手法を提案している。それは、通常のプログラムで順方向の変換を記述する際に用いる言語の機能を適切に制限することにより逆方向変換の自動的な導出が可能であることによる。また、プログラムの単射性を解析することにより、振舞いがよいだけではなく効果的な逆方向変換を導出している。

第6章「XML上の順方向変換記述言語」と第7~8章は本論文のもう一つの主要な成果として、第5章の内容をXML文書の変換の双方向化に適用するための拡張について議論している。第6章では、双方向化の対象となるXML文書上の順方向変換を記述する言語を定め、単純な拡張における問題点について議論し、言語を適切に設計することにより、その問題点を回避できることを示している。

第7章「引数の型に基づく関数の特化」では双方向化のための前処理手法を述べている。第6章で定めた言語で記述された順方向変換に対して、後述の双方向化において効果的な逆方向変換を導出するために、引数の型に基づく関数の特化を行っている。

第8章「XML上の変換プログラムの双方向化」では、第5章の手法の拡張により、第6章の言語で記述された順方向変換に対して振舞いがよい効果的な逆方向変換を自動導出する手法を示している。第6章の言語で記述された変換に対して単射性を厳密に解析することは不可能であるが、適切な近似によって効果的に解析を行う方法を述べている。

第9章「まとめ」では以上の議論をとりまとめるとともに、今後の課題および展望を述べている。

以上を要するに、本論文はプログラムの双方向化に関して新たな方法論を理論的に展開するとともに、順方向変換から自動的に逆方向変換を導出する手法を提案してその有効性を示したもので、数理情報学、計算機科学の発展に寄与するところが大きい。よって本論文は博士(情報理工学)の学位請求論文として合格と認められる。