[ACM Press the 38th annual ACM SIGPLAN-SIGACT symposium - Austin, Texas, USA (2011.01.26-2011.01.28)] Proceedings of the 38th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '11 - Generative type abstraction and type-level computation

✍ Scribed by Weirich, Stephanie; Vytiniotis, Dimitrios; Peyton Jones, Simon; Zdancewic, Steve

• Book ID: 120709686
• Publisher: ACM Press
• Year: 2011
• Weight: 569 KB
• Category: Article
• ISBN: 1450304907
• DOI: 10.1145/1926385.1926411

✦ Synopsis

Modular languages support generative type abstraction, ensuring that an abstract type is distinct from its representation, except inside the implementation where the two are synonymous. We show that this well-established feature is in tension with the non-parametric features of newer type systems, such as indexed type families and GADTs. In this paper we solve the problem by using kinds to distinguish between parametric and non-parametric contexts. The result is directly applicable to Haskell, which is rapidly developing support for type-level computation, but the same issues should arise whenever generativity and non-parametric features are combined.