通信プロトコルを実装する場合,主として(1)プロトコルの規定するメッセージ形式に従ったパケットのデコード/エンコードと(2)プロトコルの通信手順に沿ったメッセージの送受信との2つを扱う必要がある.通信プロトコルの実装にはC言語を用いることが多いが,複雑なメッセージ形式のエンコードやデコードをCで記述するのは,困難ではないにしても退屈な作業である.また,アプリケーションが不必要にブロックすることなく,メッセージ送受信を処理するためには,多重化I/Oや非同期I/Oなど,オペレーティングシステムが提供する様々なI/O機構を適切に使用する必要がある.これらの要因により,通信プロトコルの実装には高度な知識とプログラミング技術が要求され,出来上がるプログラムも複雑なものとなる場合が多い.今日では,ウェブブラウザやメッセンジャをはじめとして,多くの興味深いソフトウェアは,何らかの通信プロトコルにしたがってネットワーク上の他のノードと通信しあうネットワークアプリケーションであり,これらを簡潔に実装するためのプログラミング言語が求められている.

本論文では,通信プロトコルの実装を支援するための言語機構として,関数呼び出しスタイルによる暗黙的な並行プロセスの起動,同期メッセージパッシングの上での透過的なI/Oチャネル,そして,通信プロトコルのメッセージ形式にあわせた拡張正規表現とそのパターンマッチを提案する.さらに本研究では,これらの機能を備えたプログラミング言語Preccsを設計し,PreccsのソースプログラムからC言語のコードを生成するコンパイラを開発した.

通信プロトコルは本質的に並行性を備えており,その実装には並行プログラミングが適している.Preccsでは,全てのプロセスは並行に動作することが前提であり,runやspawnなどによる明示的なプロセス生成の指示は必要ない.これにより並行プロセス主体のより柔軟なプログラミングスタイルを促進する.各プロセスはPreccsのランタイムによりユーザレベルでスケジューリングされ非常に軽量であるから,プログラマはプロセスによるオーバヘッドを気にする必要はない.透過的なI/Oチャネルは,メッセージの送受信をPreccsのプロセス間の通信と同様に記述することを可能にする.さらに,複数のI/Oを扱うためのselectやpollといった多重化I/Oは,チャネル間の選択実行(choice)に自然にマッピングされる.通信プロトコルのメッセージ形式は,TLV形式とよばれる可変長のフィールドを含んだデータ構造が用いられることが多いが,通常の正規表現ではこのようなデータ構造を記述することはできない.本研究では,TLV形式を直接的に扱えるように正規表現を拡張する.さらに拡張正規表現パターンマッチの機構によって,受信メッセージのデコードを宣言的に記述することが可能である.

本論文ではさらに,拡張正規表現のパターンマッチを高速に行なうための2つの手法を提案する.1つは決定性カウンタオートマトン(DCA)によるパターンマッチである.TLV形式のために拡張した正規表現では,可変長フィールドの記述をサポートするため,一般の決定性有限オートマトン(DFA)によるパターンマッチは不可能である.本研究では,可変長フィールドを認識するためのDCAを定義し,拡張正規表現から決定性カウンタオートマトンを構成するアルゴリズムを開発した.もう1つはパターンマッチのスキップである.ある正規表現とマッチしたメッセージに対して,さらに狭いパターンと再度マッチングを行う場合,既にマッチ済みの事実を利用して,2回目のマッチング処理の一部を省略することが可能になる.通信プロトコルで用いられる典型的なメッセージ形式を対象として,パターンマッチにかかる処理時間を計測した結果,これらの手法が有効であることを確認した.

本研究では,いくつかの典型的な通信プロトコルをPreccsによって実装し,記述性や性能の評価を行なった.その結果,我々の提案する機構によって,実際の通信プロトコルが簡潔に記述できることを確認できた.また,性能面に関しては,CPU使用率において改善の余地があるものの,プロトコルの処理速度については十分実用的な性能に到達することが確認された.

本論文は全部で8章から構成されている.第1章は,本論文の背景と目的についての記述である.通信プロトコルの実装で困難な点の1つは,複雑なメッセージ形式の解析と,非同期に発生するイベントや複数のI/Oを適切に処理することであるということを,具体的な例を挙げて説明している.そして,本論文の目的は,並行性と正規表現をサポートするプログラミング言語を利用することによって,通信プロトコルの実装を簡潔にすることであるとしている.

第2章では,通信プロトコルの一般的な構造について述べるとともに,通信アプリケーションにおけるいくつかの典型的なモデルについて説明している.また,それらを実装する際に選択肢となりうる複数のI/O方式や実装スタイルを解説している.

第3章では,新しいプログラミング言語であるPreccsを導入している.Preccsは,プロセスとチャネルにもとづく並行プログラミング言語であり,同期メッセージパッシングモデルを採用している.本章では,Preccsの基本的な言語機能を豊富なプログラム例を示しながら解説している.また,Preccsを用いた典型的なプログラミング技法とスタイルをいくつか紹介している.

第4章では,本論文で提案する言語機構であるI/Oチャネルと拡張正規表現型について述べている.I/Oチャネルはソケットやファイルなどのディスクリプタと関連付けられた特別なチャネルであり,プログラマはネットワークやファイルに対する入出力処理を,I/Oチャネルに対するデータの送受信として透過的に記述することが可能となる.通信プロトコルにおいては,TLV(Type-Length-Value)形式と呼ばれる可変長のデータ構造を含んだメッセージ形式が用いられることが多い.拡張正規表現はTLV形式を直接的に記述できるように正規表現を独自に拡張したものである.Preccsは型システムの一部として,拡張正規表現を組み込んでいる.本章では,複雑なメッセージ形式も,拡張正規表現型によって簡潔かつ宣言的に定義することが可能であり,また,拡張正規表現型によるパターンマッチによって受信メッセージの種類による処理の振り分けが明確に記述できることを示している.

第5章では,前章で提案した手法の一つである拡張正規表現について,高速なパターンマッチを実現するための手法を提案している.拡張正規表現はフィールドの値を参照することによる繰返しの表現を含むため,通常の決定性有限オートマトン(DFA)を用いたパターンマッチは不可能である.そこで,本論文では,オートマトンにカウンタを追加し,状態遷移に際してカウンタに対するいくつかの操作を許したカウンタオートマトンを導入する.このカウンタオートマトンは拡張正規表現を判別することが可能である.そして,拡張正規表現から対応する決定性カウンタオートマトンを構成する手法を開発する.また,スキップ処理を導入することで,部分型関係を持つような正規表現型のパターンマッチを高速化する手法についても述べている.そして,いくつかのパターンマッチにおける処理時間を計測した実験によって,これらの提案手法が有効であることを示した.

第6章では,Preccs言語処理系の実装について説明している.Preccsプロセスはコンパイラによって複数のクロージャに変換され,それらを実行時ライブラリのディスパッチャが一つ一つ実行していくことによって,軽量なプロセスを実現している.I/Oチャネルに対する値の送受信は,実行時ライブラリによる非同期I/O要求を発行することで処理される.これにより,Preccsプログラム全体の実行は,途中のI/O処理に対しても不必要にブロックされることなく円滑に進められる.正規表現型のデータ表現は,文字列型と互換性を保つように巧妙に設計されており,これによって正規表現型のデータをそのまま文字列として扱うことを可能にしている.

第7章では,いくつかの典型的な通信プロトコルに対して,Preccsを用いた実装を行い,評価を行なっている.本論文で提案する拡張正規表現によって,実際の通信プロトコルのメッセージ形式が簡潔に記述できることを,また,プロセスとI/Oチャネルを用いることで,様々なタイプの通信プロトコル手順を柔軟に記述できることを,具体的なPreccsプログラムとともに示している.さらに,HTTPサーバとiSCSIターゲットにおいては,C言語によって実装された代表的なソフトウェアとの性能比較を行ない,その結果,十分に実用的な性能で処理できることが示されている.

第8章では,本論文の貢献をまとめ,Preccsにおける例外処理の扱いなどの残された課題について議論し,今後の研究の方向性について述べている.

本論文では,通信プロトコルの実装を簡潔に記述するための言語機構として,I/Oチャネルと拡張正規表現型という二つの新しい機構を提案した.さらに,これらの機構を実現するためのプログラミング言語Preccsを新たに設計し,その処理系を実際に開発した.実際の通信プロトコルに対するPreccsの適用実験の結果から,提案する機構が有効なことを確認した.

以上のように,本論文は.内容の新規性とともに.情報理工学における創造的実践に関して高い価値が認められる.よって,本論文は博士(情報理工学)の学位請求論文として合格と認められる.