Logic, Complexity, and Programming Languages

点击翻译按钮获取中文摘要

This project consists of a program of research into logical and complexity theoretic aspects of programming languages. It continues an ongoing commitment to the study of type inference for functional programming languages, together with a variety of associated topics spanning research questions in deductive database theory, program transformation methodology, unification, and type systems for records, objects and linear programs. The research program is founded on the belief that this study of type inference will give deeper understanding of the computational costs of embedding such mechanisms in a compiler, thus providing some guidance to language designers as to what is computationally feasible. The program is motivated as well by the belief that the complexity of type inference provides a precise computational measure of the expressiveness of programming languages.