Definite Clause Translation Grammars & the Logical Specification of Data Types as Unambiguous Context Free Grammars

Data types may be considered as unambiguous context free grammars. The elements of such a data type are the derivation trees of sentences generated by the grammars. Furthermore, the generators and recognizers of non-terminals specified by such grammars provide the composition and decomposition operators which can be used to define functions or predicates over such data types. We present a modification of our Definite Clause Translation Grammars (Abramson 1984) which is used to logically specify data types as unambiguous context free grammars. For example, here is a grammatical specification of binary trees: leaf :tree ::=string. branch :tree ::=" (" , left :tree, " ," , right :tree," )".

The decomposition "operators", left, right, and (implicitly) string, are semantic attributes generated by the compiler which translates these grammar rules to Prolog clauses; these operators, together with the parser for $tree$s, and the predicates $leaf$ and $branch$, can be used to construct more complex predicates over the data type $tree$. We show how such grammars can be used to impose a typing system on logic programs; and indicate how such grammars can be used to implement Kaviar, a functional programming language based on data types as context tree grammars.