Tech Reports Home Contact
Technical Report Series
Submit Report
Browse Reports
Information for Authors
Contact Details

Technical Report HW-MACS-TR-0030

TitleType Inference and Principal Typings for Symmetric Record Concatenation and Mixin Modules
AuthorsHenning Makholm, J.B. Wells
AbstractThe obvious simple type system for a lambda-calculus extended with record concatenation has a typability problem that was believed to be expensive, and which we prove NP-complete. Some previous approaches to this problem employ subtyping polymorphism. We present Bowtie, a system of simple types for record concatenation which has principal typings, no subtyping, and a clean separation between unification-based type inference with type and row variables and constraint solving for safety of concatenation and field selection. Because Bowtie has no subtyping, we succeeded in straightforwardly generalizing it to a similar type system, Martini, for mixin modules. The type inference complexity for both systems is O(nČ), or O(n) given a bounded number of field labels. We have implemented type inference for both type systems. Because they have principal typings, extending either with Milner's let-polymorphism is straightforward.


Email Technical Report's Administrator
|MACS Home| Top of the Page

Department of Computer Science, Heriot-Watt University, Riccarton, Edinburgh, EH14 4AS, +44 (0) 131 4514152

Last Updated: 02 September 2003 © Copyright Heriot-Watt University, Disclaimer