Universal domains for sequential computation

Classical recursion theory asserts that all conventional programming languages are equally expressive because they can define all partial recursive functions over the natural numbers. However, most real programming languages support some form of higher-order data such as potentially infinite streams, lazy trees, and functions. Since these objects do not have finite canonical representations, computations over these objects cannot be accurately modeled as ordinary computations over the natural numbers. In my thesis, I develop a theory of higher order computability based on a new formulation of domain theory. This new formulation interprets elements of any data domain as lazy trees. Like classical domain theory, it provides a universal domain T and a universal language KL. A rich class of domains called observably sequential domains can be specified in T with functions definable in KL. Such an embedding of a data domain enables the operations on the domain to be defined in the universal language. Unlike embeddings in classical domain theory, embeddings in T retain enough computational information to separate terminating and non-terminating computations. An important practical consequence of this embedding is the fact that the definitions of program operations are effective, implying that denotational language definitions expressed in this framework are effective interpreters.

Name thesis:degree_name

Doctor of Philosophy

Level thesis:degree_level

Doctoral

Discipline thesis:degree_discipline

Engineering

Grantor

Rice University

Year dc:date.issued

1995

Author dc:creator

• Kanneganti, Ramarao

Advisor dc:contributor.advisor

• Cartwright, Robert S.

• Computer science

Statement dc:rights

• Copyright is held by the author, unless otherwise indicated. Permission to reuse, publish, or reproduce the work beyond the bounds of fair use or other exemptions to copyright law must be obtained from the copyright holder.

Language dc:language.iso

eng

Handle dc:identifier.uri

https://hdl.handle.net/1911/16836

OAI identifier oai:identifier

oai:repository.rice.edu:1911/16836