On Type Definitions with Parameters

Abstract

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.