论文标题
改进的GP 2编译器
The Improved GP 2 Compiler
论文作者
论文摘要
GP 2是基于图形转换规则的基于规则的编程语言，旨在促进程序分析和验证。用这种语言编写有效的程序很具有挑战性，因为图形匹配很昂贵。 GP 2通过提供植根规则来解决此问题，在温和条件下可以在恒定时间内匹配。最近，我们对Bak的GP 2到C编译器实施了许多更改，以加快图形程序。一个关键的改进是一种称为BigArray的动态阵列的新数据结构。这是对条目阵列的一系列指针，依次增加了一倍。为了证明新实现可实现的速度，我们提出了一个减少程序，用于识别以前在二次时期运行的二进制DAG，但现在在与新编译器编译时以线性时间运行。
GP 2 is a rule-based programming language based on graph transformation rules which aims to facilitate program analysis and verification. Writing efficient programs in such a language is challenging because graph matching is expensive. GP 2 addresses this problem by providing rooted rules which, under mild conditions, can be matched in constant time. Recently, we implemented a number of changes to Bak's GP 2-to-C compiler in order to speed up graph programs. One key improvement is a new data structure for dynamic arrays called BigArray. This is an array of pointers to arrays of entries, successively doubling in size. To demonstrate the speed-up achievable with the new implementation, we present a reduction program for recognising binary DAGs which previously ran in quadratic time but now runs in linear time when compiled with the new compiler.
