2 0 0 0 OA 階層グラフ書換えモデルに基づく統合プログラミング言語LMNtal
- 著者
- 乾 敦行 工藤 晋太郎 原 耕司 水野 謙 加藤 紀夫 上田 和紀
- 出版者
- 日本ソフトウェア科学会
- 雑誌
- コンピュータ ソフトウェア (ISSN:02896540)
- 巻号頁・発行日
- vol.25, no.1, pp.1_124-1_150, 2008 (Released:2008-02-29)
LMNtalは階層グラフ書換えに基づく単純な言語モデルであり,接続構造の表現に論理変数を,階層構造の表現に膜を用いることを特徴としている.LMNtalは,多重集合や並行処理やモビリティなどの概念を持つさまざまな計算モデルの統合を目指すと同時に,階層グラフ書換えに基づく実用的なプログラミング言語を提供してその有用性を示すことを重要な目標としている.本論文の目的は,プログラミング言語としてのLMNtalの諸機能を紹介し,その記述力を多くの例題を用いて示すことである.我々は,算術,ルール適用制御,モジュール,他言語インタフェースなどの重要機能を階層グラフ書換えモデルの中に組み込む方法を設計し実装した.記述力の検証のためにλ計算,π計算,ambient計算,CHRなどの代表的な関連計算モデルのエンコーディングを行い,それらを実際に処理系上で動作させることに成功した.
1 0 0 0 OA 階層グラフ書換え言語LMNtalの処理系
- 著者
- 村山 敬 工藤 晋太郎 櫻井 健 水野 謙 加藤 紀夫 上田 和紀
- 出版者
- 日本ソフトウェア科学会
- 雑誌
- コンピュータ ソフトウェア (ISSN:02896540)
- 巻号頁・発行日
- vol.25, no.2, pp.2_47-2_77, 2008 (Released:2008-06-30)
LMNtalは階層グラフ書換えに基づく言語モデルであり,リンク構造による接続構造と膜による階層構造の表現・操作機能によって,動的データ構造や多重集合書換えを扱うプログラムを簡潔に記述することができる.LMNtalは書換え規則の適用を単位とする細粒度の並行性をもっており,正しく効率的な実装方式は自明でない.そこで言語処理系をJavaを用いて開発し,効率をできるだけ犠牲にせずに正しく動作する実装方式を確立した.処理系は中間命令列へのコンパイラ,その解釈実行系及びJavaソースへのトランスレータからなり,他言語インタフェースをはじめとするさまざまな有用な機能を備えている.複数の膜を貫くリンク構造を正しくつなぎかえるための処理や,複数の膜にある書換え規則を正しく非同期実行させるための工夫も行っている.本論文では,処理系開発において主要な技術的課題となった階層グラフ構造の保持方法,中間命令体系,安全な非同期実行方式等を中心として,公開中のLMNtal処理系の設計と実装について論じる.
1 0 0 0 OA LMNtal処理系におけるグラフ構造の複製・破棄および比較機能の設計と実装
- 著者
- 工藤 晋太郎
- 出版者
- Waseda University
- 巻号頁・発行日
- 2004
上田研究室により提案された言語モデルLMNtalは, 階層的グラフ構造の書き換えに基づく言語モデルである. LMNtalでは, プロセス構造を容易に図で表現できるように設計されている. しかし, 不特定構造の複製や破棄, 比較といった機能が欠けていた. 探索問題において, バックトラックではなく, 探索木の分岐に応じて状態を複製していくという解き方があるが, これをLMNtalで書くにはそれらの機能が必要である. 本研究ではこれを補うものとして, ``非線形プロセス文脈''および``基底項プロセス''という概念を実装した. これによって, 従来のLMNtalではできなかった計算モデルの表現ができるようになった. これら二つの機能を用いたLMNtalプログラム例として, 本研究の動機でもある, 状態の複製を用いて探索問題を解くプログラムを記述した. そのモデル化方法とLMNtalプログラムでのアルゴリズムの表現を解説し, また, この方法の応用を考察する.