• 検索結果がありません。

階層グラフ書換え言語における並行プロセスの型推論

N/A
N/A
Protected

Academic year: 2021

シェア "階層グラフ書換え言語における並行プロセスの型推論"

Copied!
1
0
0

読み込み中.... (全文を見る)

全文

(1)Vol. 46. No. SIG 1(PRO 24). Jan. 2005. 情報処理学会論文誌:プログラミング. 発表概要. 階層グラフ書換え言語における並行プロセスの型推論 加. 藤. 紀. 夫†. 上. 田. 和. 紀†. 階層的グラフ構造の書換えに基づく並行言語において,プロセスが形作る構造に関する静的な性質 を表現し,解析する新しい枠組みを提案する.本発表では,階層グラフ書換え言語として LMNtal を 例に取り,この言語に型体系を導入する具体的な方法を示す.LMNtal はグラフのノードとしてアト ムを持ち,アトム間を結ぶ 1 対 1 のリンクを持つ.さらにアトムは膜と呼ばれる構文で階層化され, 各膜がその膜内に対して局所的に適用される書換えルールを持つ.グラフ書き換え言語をプログラミ ング言語として見たときには,プログラムの書き方や処理系の最適化に関する指針に関する研究が求 められる.しかし,従来の並行グラフ書換え言語は,LMNtal と違って一般のグラフ書き換えを実用 に供するプログラミング言語にするというアプローチの研究が不足しているため,一般のプログラム に対して上述の指針を与えるために役に立つ解析技術はあまり存在しない.本発表で提案する型体系 は,はじめにアトムをアクティブなものと,非アクティブなものに分類し,アクティブアトムにつな がる可能性のあるプロセスやデータを解析することに基づいた強い型をプログラムに導入する.この 型体系は,並行論理型言語のうえでの強モード体系を LMNtal に応用したものであるが,膜に関す る性質を扱う点で新しい.本発表では,型体系の型安全性を証明する.. Type Inference of Concurrent Processes in Hierarchical Graph Rewriting Languages Norio Kato† and Kazunori Ueda† We propose a new framework for formalizing and analyzing static properties on the shapes of processes in concurrent languages based on hierarchical graph rewriting. We take LMNtal as an example language and show a concrete method to introduce a type system to this language. LMNtal has atoms as graph nodes and one-to-one links that connect together atoms. Moreover, atoms are hierarchized with membranes and each membrane has rewriting rules local to itself. Viewed as programming languages, graph rewriting languages ask for research on how to write programs and how to optimize the runtime system. However, since the graph rewriting languages so far have lacked in research towards making themselves practical programming languages, few analysis techniques exist that can be used for solving the above issues. Our type system firstly classifies atoms into active ones and passive ones, and then introduces to the program strong types based on which processes as well as data can be connected to active atoms. The type system has been obtained by applying the strong mode system of concurrent logic languages to LMNtal, but is new in that it can deal with properties on membranes. The proof of the type safety will be shown.. (平成 16 年 7 月 30 日発表). † 早稲田大学理工学部 School of Science and Engineering, Waseda University. 155.

(2)

参照

関連したドキュメント

Then, an algorithm is established as the way of transformation of so called associated matrices, formed as a result of local inspection of patterns, into invariant ones which

The main purpose of this survey is to identify and highlight the discrete inequalities that are connected with (CBS)− inequality and provide refinements and reverse results as well

Instead an elementary random occurrence will be denoted by the variable (though unpredictable) element x of the (now Cartesian) sample space, and a general random variable will

In this paper, we have analyzed the semilocal convergence for a fifth-order iter- ative method in Banach spaces by using recurrence relations, giving the existence and

As Riemann and Klein knew and as was proved rigorously by Weyl, there exist many non-constant meromorphic functions on every abstract connected Rie- mann surface and the compact

Theorem 3.5 can be applied to determine the Poincar´ e-Liapunov first integral, Reeb inverse integrating factor and Liapunov constants for the case when the polynomial

Then, after clarifying the behavior of the maximum degree of the colored Jones polynomial for cables of certain knots in Propo- sition 3.2, we record an explicit proof of the

solenoids, which are the nonsimple noncommutative solenoids, and the only ones of type I, and are fully described as bundles of matrices over a solenoid group; irrational