C∀ Type System Implementation

programming languages;type inference;C language;polymorphism;generic types;expression resolution;type environment;union-find;name overloading;compiler construction;C∀

Moss, Aaronadvisor:Buhr, Peter ; affiliation1:Faculty of Mathematics ; Buhr, Peter ;

University of Waterloo

关键词: generic types;    type environment;    union-find;    expression resolution;    compiler construction;    polymorphism;    programming languages;    C language;    name overloading;    C∀;    Doctoral Thesis;    type inference;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/14584/1/Moss_Aaron.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

The C programming language has been an important software development tool for decades. C∀ is a new programming language designed with strong backwards-compatibility to take advantage of widely distributed C programming expertise and the large deployed base of C code, paired with modern language features to improve developer productivity.This thesis presents a number of improvements to C∀. The author has developed one major new language feature, generic types, in a way that integrates naturally with both the existing polymorphism features of C∀ and the translation-unit-based encapsulation model of C. This thesis also presents a number of smaller refinements to the C∀ overload resolution rules, each of which improves the expressivity or intuitive nature of the language.This thesis also includes a number of practical improvements to C∀ compilation performance, focused on the expression resolution pass, which is the main bottleneck. These include better algorithms for argument-parameter matching and type assertion satisfaction, as well as a new type-environment data-structure based on a novel variant of union-find. The compilation performance improvements have all been experimentally validated with a new prototype system that encapsulates the key aspects of the C∀ language; this prototype is a promising basis for future research and a technical contribution of this work.C∀, extended and refined in this thesis, presents both an independently interesting combination of language features and a comprehensive approach to the modernization of C. This work demonstrates the hitherto unproven compiler-implementation viability of the C∀ language design, and provides a number of useful tools to implementors of other languages.