Loading...
Please wait, while we are loading the content...
Similar Documents
Type Inference and Principal Typings for Symmetric Record Concatenation and Mixin Modules
| Content Provider | Semantic Scholar |
|---|---|
| Author | Makholm, Henning Wells, J. B. |
| Copyright Year | 2005 |
| Abstract | The obvious simple type system for a λ-calculus extended with record concatenation has a typability problem that was believed to be expensive, a nd which we prove NP-complete. Some previous approaches to this problem employ subtyping polymorphism. We present Bowtie, a system ofsimple typesfor record concatenationwhich hasprincipal typings, no subtyping, and a clean separation between unification-based type inference with type and row variab les nd constraint solving for safety of concatenation and field selection. Becau s Bowtie has no subtyping, we s쳮ded in straightforwardly generalizing it to a s imilar type system, Martini, for mixin modules . The type inference complexity for both systems isO(n2), or O(n) given a bounded number of field labels. 1 We have implemented type inference for both type systems. Because they have pr incipal typings, extending either with Milner's let-polymorphism is straightforward. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.macs.hw.ac.uk/DART/reports/D5.2/MW05b.pdf |
| Alternate Webpage(s) | http://www.macs.hw.ac.uk/cs/techreps/docs/files/HW-MACS-TR-0030.pdf |
| Alternate Webpage(s) | http://www.macs.hw.ac.uk:8080/techreps/docs/files/HW-MACS-TR-0030.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
