A General Theory of Program Dependencies in Imperative and Declarative Concurrent Programs and Its Applications

1.对程教授首次提出的命令式并发程序的两种表示形式--非确定并行控制流网和非确定并行定义使用网进行了扩展，使其可以用来表示声明式并发程序中的多个控制流和多个数据流。2.在并发逻辑程序中引入了三种主要的程序依赖：共享依赖、通信依赖和统一依赖，并给出了分析这些程序依赖的算法。我们还提出了一种新的并发逻辑程序表示方法，称为参数依赖网，它是一种弧分类有向图，用于显式地表示程序中的三种主要程序依赖。在参数依赖网的基础上，形式化地定义了并发逻辑程序切片的各种概念，并提出了计算并发逻辑程序切片的算法。3.提出了一种新的并发面向对象程序表示方法--系统依赖网，它是一种弧形分类有向图，用来显式地表示程序结构中的各种主要程序依赖关系以及程序中结构的结构，并证明了一旦一个并发面向对象程序用它的系统依赖网来表示，程序的切片就可以基于网作为一个简单的网络可达性问题来计算。4.我们提出了两种新的函数式程序表示法。命名为赋值顺序图和绑定赋值图，并展示了它们在函数式程序的理解、分析、测试、调试、维护和复杂性度量等方面的应用。我们正在开发一个工具，将一个函数式程序转换成它的求值顺序图和绑定求值图。

1.We extended the nondeterministic parallel control-flow net and nondeterministic parallel definition-use net, which are two representations for imperative concurrent programs originally introduced by Cheng, such that they cab be used to represent multiple control flows and multiple data flows in declarative concurrent programs.2.We introduced three new types of primary program dependencies between arguments in concurrent logic programs, named the sharing dependence, communication dependence, and unification dependence, and proposed algorithms to analyze these program dependences. We also proposed a new program representation for concurrent logic programs, named the argument dependence net, which is a kind of arc-classified digraph to explicitly represent the three types of primary program dependencies in the programs. Based on the argument dependence net, we formally defined various notions about slicing concurrent logic programs and also proposed algorithms to compute various slices in the programs.3.We proposed a new program representation for concurrent object-oriented programs, named the system dependence net, which is a kind of arc-classified digraph to explicitly represent various types of primary program dependencies in constructs and the structure of the constructs in the programs, and showed that once a concurrent object-oriented program is represented by its system dependence net, the slices of the program can be computed based on the net as a simple reachability problem in the net.4.We proposed two new program representations for functional programs, named the evaluation order graph and binding evaluation graph, and showed their applications including understanding, analysis, testing, debugging, maintenance, and complexity measurement of functional programs. We are developing a tool to transform a functional program into its evaluation order graph and binding evaluation graph.