Wei KE et al. A graph-based generic type system for object-oriented programs 113
and the frame of a method consists of the parameters of the
method. These structures are also characterized in a type
graph. In fact, each type, static table or method frame of a
program is represented as a subgraph of the type graph of
the program. There is a designated node in such a subgraph,
called the root of the graph of the type, static table or method
frame. For a nominal type, the root of its graph is the name of
the type, while for a structural type, a static table or a method
frame, the root is anonymous. We call the root of a nomi-
nal type a nominal node and an anonymous root a structural
node.
We use D to denote the primitive type (data type) names
and U the class (user type) names, and C = D∪Uthe type
constants. Let X be the type variables. Thus, C∪Xis the set
of nominal nodes. Using S to denote the structural nodes and
assuming all these sets are mutually disjoint, we have the set
N = C∪X∪Sof nodes of type graphs.
For the labels of edges, let A be the set of the names of
variables, attributes, methods and parameters, which is dis-
joint with N. We introduce a special label “” for the class
inheritance relation, and another special symbol “σ” to label
an incoming edge to the root of a static table. If a class con-
tains a type variable α, the class is generic. A generic class
can be instantiated by mapping α to some actual type u.We
use an edge labeled by the type variable α and targeting u to
record the mapping α → u. We put such an edge to the static
table of each generic class and class instantiation, see Fig. 1.
Thus, A
+
= A∪X∪{,σ} is the set of all labels of edges.
Fig. 1 A type graph and the corresponding class declarations
Definition 1 (Type graph) A type graph is a directed and
labeled graph Γ=N, E,whereN ⊆Nis the set of nodes,
and E : N ×A
+
→ N is the set of edges.
Notice that E is a function implies that labels of the out-
going edges of a node are distinct. Thus the names of at-
tributes and methods of a class are different, and parameters
of a method are different. In particular, there is no multiple
inheritances allowed in this model.
Figure 1 shows a type graph and the corresponding class
declarations. In the graph, C is a generic class, with a type
variable β and a superclass D. Notice the β-labeled edge tar-
geting at the node β.Ifβ is instantiated to an actual type,
the β node is replaced by the node of the actual type. C has
two attributes a and b of types S and β, respectively, and a
method m
1
with a parameter x of type S. The type variable β
implementing class I has a method m
2
with two parameters
x and y both of type S, meaning that any replacement of β in
an instantiation of C must define such a method. D is a non-
generic class with an attribute i and two methods m
3
and m
4
,
where m
3
has a parameter x and m
4
has two parameters x and
y.
We use s
a
−→ t to represent an a-labeled edge from s to t,
and call s the source node and t the target node of the edge.
We use s
a
−→·to represent an a-labeled outgoing edge of s
and ·
a
−→ t an a-labeled incoming edge to t. For a given graph
Γ=N, E,weuseΓ.ns to denote the set N of nodes, and
Γ.es the set E of edges.
Apathp is a sequence of consecutive edges, denoted as
n
0
a
1
−→ n
1
···n
k−1
a
k
−→ n
k
or simply n
0
a
1
a
2
···a
k
−−−−−−→ n
k
, if we are not
concerned with its intermediate nodes. We also overload the
notation of set membership “∈”, using n ∈ Γ, e ∈ Γ and p ∈ Γ
to denote that a node n, an edge e and a path p are in graph Γ,
respectively.
For a path p,letsource (p)andtarget (p) be the starting
and ending node, respectively. We say that a node n
2
is reach-
able from a node n
1
, denoted as n
1
−→
∗
n
2
,ifthereisapath
from n
1
to n
2
.Apathn
1
a
−→ ···
a
−→ n
2
is simply denoted as
n
1
a
−→
∗
n
2
.
3.2 Rooted graphs
In the type graph Γ of a program, an individual type T,say
a class, is represented by a node r of Γ, the nodes reachable
from r and the edges between these nodes. These nodes and
edges form a subgraph of Γ with r being designated as the
root. This rooted graph represents the type T.
Definition 2 (Rooted graph) Given a node r of a graph Γ,
the rooting operation Γ r returns the subgraph G = N, E, r
of Γ such that
N = {n | r −→
∗
n ∈ Γ},
剩余25页未读，继续阅读
weixin_38657376
- 粉丝: 4
- 资源: 928
我的内容管理
展开
最新资源
- 多模态联合稀疏表示在视频目标跟踪中的应用
- Kubernetes资源管控与Gardener开源软件实践解析
- MPI集群监控与负载平衡策略
- 自动化PHP安全漏洞检测：静态代码分析与数据流方法
- 青苔数据CEO程永：技术生态与阿里云开放创新
- 制造业转型： HyperX引领企业上云策略
- 赵维五分享：航空工业电子采购上云实战与运维策略
- 单片机控制的LED点阵显示屏设计及其实现
- 驻云科技李俊涛：AI驱动的云上服务新趋势与挑战
- 6LoWPAN物联网边界路由器：设计与实现
- 猩便利工程师仲小玉：Terraform云资源管理最佳实践与团队协作
- 类差分度改进的互信息特征选择提升文本分类性能
- VERITAS与阿里云合作的混合云转型与数据保护方案
- 云制造中的生产线仿真模型设计与虚拟化研究
- 汪洋在PostgresChina2018分享：高可用 PostgreSQL 工具与架构设计
- 2018 PostgresChina大会：阿里云时空引擎Ganos在PostgreSQL中的创新应用与多模型存储
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
