Paper: Computing with recursive types (at LICS 1989)
Authors: Cosmadakis, S.S.Abstract
A study is made of the complete adequacy for a λ-calculus with simple recursive types. The set of types is built using the standard domain-theoretic constructors, namely, function space, sum, cartesian and strict product, and lifting. The recursive types allow the author to solve arbitrary systems of mutually recursive domain equations. Thus, he can define in this calculus types of integers, Booleans, lists and streams over these, and so on. The author can also define numerals, Boolean constants, simple arithmetic versions, of pure untyped terms. A precise description is given of the author's calculus, as well as some examples illustrating its expressiveness. A complete adequacy result for the lattice semantics is presented. The problem of designing a completely adequate evaluator for the CPO semantics is also examined
BibTeX
@InProceedings{Cosmadakis-Computingwithrecurs,
author = {Cosmadakis, S.S.},
title = {Computing with recursive types},
booktitle = {Proceedings of the Fourth Annual IEEE Symp. on Logic in Computer Science, {LICS} 1989},
year = 1989,
editor = {Rohit Parikh},
month = {June},
pages = {24--38},
location = {Pacific Grove, CA, USA},
publisher = {IEEE Computer Society Press}
}