On Type Definitions with Parameters
DOI:
https://doi.org/10.7146/dpb.v4i54.6473Abstract
This paper analyzes some of the consequences of allowing the definition of parameterized data types in programming languages. A typical use of such types is:
type queue(x) = struct (x, ref (queue (x))),
intqueue = queue(int).
It is shown that the addition of parameters permits the definition of new types not definable without parameters. In particular, the types definable with parameters are closely related to the deterministic context-free languages, whereas the author has previously shown that the types definable without parameters are characterized by the regular (i.e. finite state) languages.
An important consequence of this fact is that the type equivalence problem, which is easily solvable in the absence of parameters, becomes equivalent to the (currently open) equivalence problem for deterministic pushdown automata.
Downloads
Published
How to Cite
Issue
Section
License
Articles published in DAIMI PB are licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.