Term graph

A term graph is a representation of an expression in a formal language as a generalized graph whose vertices are terms^[clarify].^[1] Term graphs are a more powerful form of representation than expression trees because they can represent not only common subexpressions (i.e. they can take the structure of a directed acyclic graph) but also cyclic/recursive subexpressions (cyclic digraphs).

Abstract syntax trees cannot represent shared subexpressions since each tree node can only have one parent; this simplicity comes at the cost of efficiency due to redundant duplicate computations of identical terms. For this reason term graphs are often used as an intermediate language at a subsequent compilation stage to abstract syntax tree construction via parsing.

The phrase "term graph rewriting" is often used when discussing graph rewriting methods for transforming expressions in formal languages.^[2] Considered from the point of view of graph grammars, term graphs are not regular graphs, but hypergraphs where an n-ary word will have a particular subgraph in first place, another in second place, and so on, a distinction that does not exist in the usual undirected graphs studied in graph theory.

Term graphs are a prominent topic in programming language research since term graph rewriting rules can formally expressing a compiler's operational semantics. Term graphs are also used as abstract machines capable of modelling chemical and biological computations as well as graphical calculi such as concurrency models. Term graphs can perform automated verification and logical programming since they are well-suited to representing quantified statements in first order logic. Symbolic programming software is another application for term graphs, which are capable of representing and performing computation with abstract algebraic structures such as groups, fields and rings.

The TERMGRAPH conference ^[3] focuses entirely on research into term graph rewriting and its applications.

Term graphs are also used in type inference, where the graph structure aids in implementing type unification.^[4]

References

^ Plump D. (Hartmut Ehrig, G. Engels, Grzegorz Rozenberg, eds) (1999). Handbook of Graph Grammars and Computing by Graph Transformation: applications, languages and tools. Vol. 2. World Scientific. pp. 9–13. ISBN 9789810228842.{{cite book}}: CS1 maint: multiple names: authors list (link)
^ Barendregt; van Eekelen; Glauert; Kennaway; Plasmeijer; Sleep (1987). "Term graph rewriting". PARLE Parallel Architectures and Languages Europe (Lecture Notes in Computer Science). Lecture Notes in Computer Science. 259: 141–158. doi:10.1007/3-540-17945-3_8. ISBN 978-3-540-17945-0.
^ "TERMGRAPH 2013".
^ Fritz Henglein (1988). Type inference and semi-unification. In Proc. 1988 ACM conference on LISP and functional programming, pp. 184-197. doi:10.1145/62678.62701

This formal methods-related article is a stub. You can help Wikipedia by expanding it.

[Plump1999-1] Plump D. (Hartmut Ehrig, G. Engels, Grzegorz Rozenberg, eds) (1999). Handbook of Graph Grammars and Computing by Graph Transformation: applications, languages and tools. Vol. 2. World Scientific. pp. 9–13. ISBN 9789810228842.{{cite book}}: CS1 maint: multiple names: authors list (link)

[Barendregt1987-2] Barendregt; van Eekelen; Glauert; Kennaway; Plasmeijer; Sleep (1987). "Term graph rewriting". PARLE Parallel Architectures and Languages Europe (Lecture Notes in Computer Science). Lecture Notes in Computer Science. 259: 141–158. doi:10.1007/3-540-17945-3_8. ISBN 978-3-540-17945-0.

[3] "TERMGRAPH 2013".

[4] Fritz Henglein (1988). Type inference and semi-unification. In Proc. 1988 ACM conference on LISP and functional programming, pp. 184-197. doi:10.1145/62678.62701

[1]

[2]

[3]

[4]

See also

References