A Functional Reformulation of UnCAL Graph-Transformations Or, Graph Transformation as Graph Reduction

This paper proposes FUnCAL, a functional redesign of the graph transformation language UnCAL. A large amount of graph-structured data are widely used, including biological database, XML with IDREFs, WWW, and UML diagrams in software engineering. UnCAL is a language designed for graph transformations, i.e., extracting a subpart of a graph data and converting it to a suitable form, as what XQuery does for XMLs. A distinguished feature of UnCAL is its semantics that respects bisimulation on graphs; this enables us to reason about UnCAL graph transformations as recursive functions, which is useful for reasoning as well as optimization. However, there is still a gap to apply the program-manipulation techniques studied in the programming language literature directly to UnCAL programs, due to some special features in UnCAL, especially markers. In this paper, following the observation that markers can be emulated by tuples and lambda- abstractions, we transform UnCAL programs to a restricted class of usual (thus, marker-free) functional ones. By this translation, we can reason, analyze or optimize UnCAL programs as usual functional programs. Moreover, we introduce a type system for showing that a small modification to the usual lazy semantics is enough to run well-typed functional programs as finite-graph transformations in a terminating way.