A functional programming language with context free grammars as data types
Syrotiuk, Violet Rose · Open Collections · 2010
Specifying data structures is important in programming languages. One approach uses initial algebras, but constructing specifications using them is difficult and hampered by restrictions. The recursive term algebra approach, uses recursive definition along with basic operations implied by the definition itself to induce an algebra of terms. Such a recursive definition may be transformed into an unambiguous context free grammar. These grammars are used to define data structures in a functional programming language named Kaviar. Provisions are made for non-context free data structures as well. This approach avoids the difficulties encountered in using the initial algebra method.