Implementing categorical programming languages
While the use of category theory in the specification and construction of programming languages is increasing, there is still a considerable gap between categorical definition and what is needed to specify and implement a programming language. A categorical framework is needed to organize different computational settings uniformly. This framework should facilitate the description and verification of their operational semantics and programming environment so that the correctness of their implementations can be verified.
This dissertation is designed to help fill this gap. It presents categorical combinator theories which provide a uniform and polymorphic method for specifying varieties of categories such as cartesian closed, distributive, and list arithmetic categories. Using these theories, we show how the combinator expressions can be type checked and reduced to a canonical form. Furthermore, simple abstract machines have been developed to facilitate the efficient implementation of these languages.
Thesis90b.C325.pdf
3.34 MB
Adobe PDF
5f2b55c4d93b09cae716e0cde819cb6d