未踏ソフトウェア創造事業 提案テーマ詳細説明 ---------------------------------------------------------------- 提案の目的、背景 コンピューティングの主流は、 単独のシステムから分散環境へと移行しつつある。 しかし、分散環境において複数のプロセスが協調しつつ並行に処理を 行なう分散アプリケーションの実装は、逐次アプリケーションの実装と 比較して非常に難しい。その理由は次の２つであると思われる。 a) １つ目は分散アルゴリズムに関する研究が逐次アルゴリズムほど 蓄積されていないことである。逐次ノイマン型を前提として蓄積さ れてきた従来のアルゴリズムを不用意に分散アプリケーションに適 用すると、かえって効率が落ちることがある。 b) ２つ目は分散プログラミングのための言語が未熟であることで ある。広く普及している手続き型言語の分散拡張は、分散のための 言語機能がネットワーク透過でない。 このため、逐次アプリケーションの分散化に伴って 論理セマンティクスが変わってしまい、 正当性が失われることがある。 本提案では b) の問題を解決することによって、a) の問題を解決す るための基盤を整備することを目指す。具体的には並行論理型言語 KL1の分散処理系の設計と実装を行ない、正しい分散 アプリケーションを容易に構築するための環境を整備する。 究極の目標 ネットワークに接続されたあらゆる機器が並行オブジェクトとしての インタフェイスを持ち、依頼に応じて固有の計算を提供するような 宣言型広域分散計算環境を目指す。 統一的な枠組を持つ宣言型広域分散計算環境を実現することによって、 正しいネットワークプログラミングを容易に行なえるようにする。 提案の背景 並行論理型言語は変数が単一代入であるという点において純関数型 言語に近く、静的解析に望ましい特徴を共有している。また、並行 論理型言語は関数型言語や手続き型言語の並行拡張と異なり、並列 ・分散を含む並行な計算モデルが言語自体に内包されている。この ため、プログラムの並列化・分散化に伴って論理セマンティクスが 変わることはない。ネットワーク透過な論理セマンティクスと 静的解析の容易さという特徴を持つ並行論理型言語は、 分散アプリケーションを記述するのに最適な言語であると思われる。 KLICはUnix上の並列KL1言語処理系である。 KL1言語は並行論理型言語の中でも最も単純で最も研究の蓄積された Flat GHCに基づいているため、並列化によって論理セマンティクスが 変わることはなく、静的解析による 最適化や自動デバッグなどの研究が行なわれている。 dklicは既存のKLIC処理系とその周辺処理系、 試作済みの分散ミドルウェアを組み合わせることによって 目標の達成を目指す。 従来の処理系や規格 Distributed Ozは並行オブジェクト指向言語である。 単一代入変数を用いる点において静的解析に望ましい特徴を持つが、 静的解析・検証という方向を目指していない。 Javaは分散アプリケーションの記述に広く用いられている。インタ ーネット上のWWWサービスと連動してバイトコードを輸送・実行する 機能を持つが、プリミティヴには逐次の手続き型言語であるため 並行アプリケーションの構築・解析は手間がかかる。 CORBAは分散オブジェクトのためのフレームワークである。 KL1のプロセスは並行オブジェクトと見なすことができ、 分散KL1をCORBAの枠組に適応させることも考えられる。 あるいは逆に、CORBAと等価な機能を KL1による分散計算環境に採り入れることを目指す。 ---------------------------------------------------------------- 提案の具体的内容 dklicは分散KL1言語処理系である。 Unixではデバイスやプロセスに 統一的なファイルのインタフェイスが与えられている。 また、Java言語ではグラフィクスやネットワークへの インタフェイスが提供されている。 dklicでは、これら様々なオブジェクトに統一的な 並行プロセスのインタフェイスを与えることによって、 分散プログラミングを容易にする。 並行プロセスと通信路の動的生成、 プロセス間通信や同期といった分散計算に本質的な 機能はKL1言語の核を成しているため、 正しい分散アプリケーションを容易に構築することができる。 開発するソフトウェアの内容と図 分散計算環境 | | クライアント サーバ クライアント／サーバ型のユーザアプリケーションは、 分散計算環境に計算を依頼することによって遠隔ホストに接続し、 接続後は通信相手の所在が同一ホストか、遠隔ホストかを意識しない。 API サーバ 提供されるサービス 特別なサーバ（計算サーバ） unify X=Y KL1データの単一化（代入・束縛・送受信）（KLIC） Localhost Goal 組み込み・ユーザ定義述語の起動（KLIC） Remotehost Goal@node(Remotehost) 遠隔述語の起動（試作あり） 基本サーバ（述語呼び出しによって起動される） merge ストリームのマージ（KLIC） unix bind,connect,stdin,stdout,stderr 組み込みサーバへの接続（KLIC） naming register,lookup ユーザ定義サーバの登録・接続（試作あり） 普通のサーバ（基本サーバのサービスを介して接続される） Socket accept（KLIC） File getc,putc,gett,putt 入出力（KLIC） exec 述語移送・実行（試作あり） sandbox 例外処理 agentspace エージェント : dklicの機能は全てサーバによって提供されるサービスである。 KLIC処理系によって単一計算機上で実現されていた機能は、 Localhostという計算サーバによって提供されるものと見なす。 また、遠隔述語呼び出しはRemotehostという計算サーバによって提供される。 サービスを受けるには、unixまたはnamingという基本サーバに 望みのサーバへの接続を依頼して通信路を確立し、 それからサーバへサービスを依頼する。 例外的に、特別なサーバと基本サーバへは直接サービスを依頼できる。 ユーザ定義サーバがサービスを提供するには、 naming基本サーバに自分を登録し、 基本サーバを介してクライアントとの通信路を確立する。 表に挙げたサーバは、 ユーザによる定義が難しい基本的なサービスを提供するものであり、 dklicが組み込みで提供すべきである。 しかし、sandboxやagentspaceなどは実装が難しいと予測できる。 表に挙げたサーバの順序は、 おおよそ基本的なものから高級で難しいものへと並べてあるため、 実装の優先度も表に挙げた順とする。 もっとも優先すべき単一化サービスは分散論理変数の実現と等価である。 分散論理変数の表現と操作を定めることによって、 任意のKL1データの移送プロトコルも定まる。 コードやプロセスの移送プロトコルも、 データ移送プロトコルを利用するサーバによって定義することができる。 構成要素 dklic実行系がホスト毎に1つ起動され、互いに適切な通信を行ないながら 同一ホスト内の要求に応答することによって（仮想）分散計算環境を成す。 dklic実行系は次の機能から成る。 ・遠隔サービスの起動（遠隔述語呼び出し） ・遠隔サーバへの接続（起動済みサーバへの通信路取得） ・サーバとサービスの登録（ネーミングサービス） ・サービスの検索（ネーミングサービス） ・故障検出機構（例外処理） これらの機能を実装する下位処理系として、 既存の並列KL1言語処理系KLICを利用する。 KLIC実行系をdklic実行系の一部として非分散機能を提供する。 また、dklic実行系の大部分をKLIC/KL1言語で記述し、 KLIC翻訳系によってKL1プログラムを機械語に翻訳する。 KLIC上のミドルウェアとしては次のような機能が試作済みである。 ・複数のKLIC実行系にまたがる遠隔述語呼び出し ・中間コードで表現された述語の移送と実行（遠隔述語呼び出し） ・サービスの名前による検索（ネーミングサービス） ・未定義引数のないプロセスのファイルへの退避と復元 また、実用性を考慮すると次のようなものが不足している。 ・例外処理機構、論理計算空間の動的管理 ・KL1コードから中間コードへの翻訳系 ・KL1言語およびKLIC処理系, dklic処理系についてのドキュメント ・組み込みプロセスへの完全なインタフェイス これらの機能の完成度を高め、 不足しているものを補うことによって目標の分散計算環境を実現する。 競合 既存の分散計算環境として分散OS, CORBA, COM, Java RMI, Jini などがあるが、これらは逐次の手続き型言語に基づくものであり、 分散アプリケーションの構築・解析は非常に難しい。 dklicは静的解析に望ましい特徴を持つKL1言語に基づいており、 分散アプリケーションの安全性を検証することが可能であると期待できる。 安全性の検証は、信頼性の低いモバイルコードを実行するために特に重要である。 MozartはDistributed Ozの実装であり、 並行制約に基づいている点で静的解析に期待が持てるが、 dklicに比べて短期的な実用性を重視している。 Javaのような既存言語と同レベルで共存または置換されることを 目指しており、高階・オブジェクト指向・ 完全な分散論理変数など重厚な機能を実装している。 完成度が高い反面、今以上の普及は見込めそうもない。 適用範囲（レベルは様々） inetd IPC, RPC, NFS, NIS LDAP (Lightweight Directory Access Protocol) ORB ping, chat agent IMAP, POP X chatアプリケーションの例 client :- true | naming(S), S = [lookup(window(WI)), lookup(window(WO)), lookup(chat(CI,CO))], io(WI, CO), io(CI, WO). io(I, O) :- true | I = [getl(L) | I1], O = [putl(L) | O1], io(I1, O1). server :- true | naming(S), S = [register(chat/2, Server)], generic:new(merge, Ls, L), chat(Server, Ls, L). chat(Server, Ls, L) :- Server = [chat(CO,CI) | Server1] | Ls = {L1, Ls1}, io(CI, L1), io(L, CO), chat(Server1, Ls1, L). alternatively. chat(Server, Ls, L) :- L = [_ | L1] | chat(Server, Ls, L1). ---------------------------------------------------------------- 期待される効果 短期的な効果 学部1年生のネットワークプログラミングに使うことができる。 統一的な枠組を持つ宣言型広域分散計算環境によって、 ネットワークや遠隔計算機は 並行プログラミングにおける通信路や他プロセスと 本質的に同じインタフェイスを与えられている。 プロセスと通信路の生成、プロセス間通信と同期は KL1言語によって自動透明に行なわれる。 これによって学生はネットワークプログラミング固有の詳細にとらわれずに 分散アルゴリズムを学ぶことができる。 また、正しく動く分散アプリケーションを書くのが難しくないこと、 それに対して、 正しく動く効率の良い分散アプリケーションを書くのが難しいこと を学ぶことができる。 提案が目指すもの dklicはMozartのように重厚な実装ではなく、軽く小さな実装を目指す。 Javaなどの既存言語に置換されることを目指すのではなく、 既存のオブジェクトに並行プロセスのインタフェイスを与えることによって、 性質の良い分散計算環境の基礎を成すことを目指す。 ユーザが独自のサーバを容易に定義し、 組み込みサーバと同じインタフェイスでアクセスできるため、 システム構成の動的変更を安全に行なえることが期待できる。 広がりと発展 構築や検証の困難な分散計算に対して包括的なインタフェイスを与える。 馴染みの薄い並行論理型言語のパラダイムを普及させる。 これによって、言語やパラダイムの間の健全な競争が期待できる。 他言語インタフェイス、例えばJavaへのインタフェイスは既に試作されている。 従って、CORBAへのインタフェイスも定義できるであろう。 データ移送プロトコルに従っていれば、 他言語によって記述されたアプリケーションもdklicに接続可能である。 ---------------------------------------------------------------- 開発の具体的な進め方 2001-07 概念設計 08 詳細設計 09 プロトタイプ構築 10 実装 11 評価 12 例題作り 2002-01 ドキュメント整備（外部仕様書、内部仕様書、意志決定資料） 02 成果報告 開発体制 開発チームは次の3人で構成する。 ・高木祐介 ・高山啓 ・松村量 各段階における成果をなるべく早く公開し、 外部からの指摘・報告・協力があれば採り入れることとしたい。 開発プラットフォームは主に Linux, FreeBSD, Solaris などのUnix系OS、 開発マシンはLANまたはダイアルアップIP接続された PCおよびSun Sparcとする。 開発設備や場所は、開発人員の所属する 上田研究室（所在地はテーマ申請書参照のこと）を利用する。 開発チーム3人の分担は次の通りである。 ・高木祐介 方針決定、概念設計、実行系の通信プロトコル ・高山啓 詳細設計、実装 ・松村量 ネーミングサービス、例外処理 しかし、一般のオープンソース開発における緩やかな組織化と異なり、 開発チームは同じ研究室で対面して連係をとりながら開発を進めるため、 分担は柔軟に変更することもあり得る。 開発計画 dklicは分散KL1言語処理系である。KLICを下位処理系とし、dklic 自身をKL1言語で記述することによって実装の容易さを重視している。 dklicの最終目標はネットワーク透過な宣言型広域分散コンピューティング 環境であり、その点ではCORBAに通じるものがある。既存分散環境と の最大の違いは、並行論理型言語の性質の良さを基礎に持つ点である。 分散環境では逐次・並列環境以上に通信の信頼性が低く、 外部から受け取ったデータや実行コードの正当性を検証するためには 静的解析の容易な並行論理型言語が有利である。 また、KL1の計算ノードの概念は計算機に限らず IPアドレスの振られた機器や計算機の部品（ストレージやビデオチップなど） のような広域分散環境に容易に敷衍することができる。 本提案では、既存の処理系や試作を組み合わせ、 より普遍的な宣言型広域分散計算環境の構築を目指す。 以下では、遠隔述語呼び出しの実装の改善、 ソケットインタフェイスの仕様と設計について順に述べる。 ●dklic試作処理系の改善 ・分散変数表の性能向上。 変数識別子の再利用を採り入れることによって変数表のワーキング セットが限定できることを期待し、データ構造をリストから配列へ 移行して定量比較実験を行なう。 ・遠隔述語呼び出しのための分散実行環境の改善。 現在の試作dklicは未定義変数同士を単一化して終了するプロセスを 検出できず、無駄な通信を行なってしまう。 未定義変数同士の単一化を検出し、 参照数を解析または検出することによって無駄な通信をなくす。 ・下位処理系をKLIC処理系だけでなくKLIJava処理系, KL1/J処理系へも対応する。 下位言語をUnix/CからJavaへ移行することによって、Windowsや Macintoshでも分散KL1プログラムが動作することを期待できる。 ●分散KL1におけるサーバとソケットのインタフェイスの再検討 非分散KL1サーバが併合器を用いて複数のクライアントに応対するのに対し、 分散KL1サーバはサーバソケットを用いる。 KL1の入出力ストリームに変数を含む項を流すことができない問題は 分散変数表の実現によって解消できた。しかし、信頼性の低い外部入出 力を内部通信と全く同じに扱うのは望ましくない。 ネットワーク透過な論理セマンティクスを持ちながら フォールトトレラントな外部入出力の仕様と設計を検討する。 Unixにおけるプロセス、ファイル、ストリーム、サーバ、ソケット 等の概念を分散KL1に敷衍する。 例えば、具体的には： ・Javaのイベントモデルに相当する制御用のストリームを同時に提供 し、入出力ストリームを論理的に制御できることを確かめる。 ・クライアント／サーバ型のアプリケーションを書き、 ソケットインタフェイスの改善度を定量比較する。 ・変数の束縛情報の流れを制御することによって ファイルのセーブ・ロードや接続の中断・再開などの 永続プロセスを可能にする。 ・Javaなど既存言語による分散アプリケーションの例題を分散KL1で記述し、 比較評価を行なう。 ---------------------------------------------------------------- 費用の概算 ---------------------------------------------------------------- 提案者の実績 ・ソフトウェア整備 KLIC処理系に対する修正の整備・公開, 2000-2001. http://www.ueda.info.waseda.ac.jp/~takagi/kl1/klic-3.003/fix.html ・プログラミング KL1, ネットワークプログラミング, 数百から千行 KL1, 並列プログラミング, 数十行 Java, ネットワークゲーム、アプレットなど, 数十から数百行 C, MIPSエミュレータなど, 数百から数千行 ・論文 高木祐介, dklic: KL1による分散KL1言語処理系の実装. In Proc. JSSST Workshop on Systems for Programming and Applications (SPA2001), 2001. 高木祐介, KL1による分散KL1言語処理系の実装. 早稲田大学理工学部情報学科卒業論文, 2000. 高山啓, 並行論理型言語KL1による分散KL1言語処理系の実装. 早稲田大学理工学部情報学科卒業論文, 2001. 松村量, 並行論理型言語KL1の分散拡張のための遠隔ノード管理の実装. 早稲田大学理工学部情報学科卒業論文, 2001. ----------------------------------------------------------------