Derivation and inference of higher-order strictness types

• Published in: Computer languages, systems & structures systems & structures, 2015-12, Vol.44, p.166-180
• Main Authors: Smetsers, Sjaak, van Eekelen, Marko
• Format: Article
• Language: English
• Subjects: Aids; Algorithms; Automated theorem proving; Derivation; Design engineering; Inference; Lambda calculus; Operational semantics; Proving; Semantics; Strictness analysis; Theorem proving; Typing
• ISSN: 1477-8424; 1873-6866
• DOI: 10.1016/j.cl.2015.07.004

We extend an existing first-order typing system for strictness analysis to the fully higher-order case, covering both the derivation system and the inference algorithm. The resulting strictness typing system has expressive capabilities far beyond that of traditional strictness analysis systems. This extension is developed with the explicit aim of formally proving soundness of higher-order strictness typing with respect to a natural operational semantics. A key aspect of our approach is the introduction of a proof assistant at an early stage, namely during development of the proof. As such, the theorem prover aids the design of the language theoretic concepts. The new results in combination with their formal proof can be seen as a case study towards the achievement of the long term PoplMark Challenge. The proof framework developed for this case study can furthermore be used in other typing system case studies. •We introduce syntax and semantics of a basic programming language.•We define derivation rules for a higher-order strictness typing system.•We proof soundness of our system with respect to the semantics.•The proof is formalized by using a theorem prover.•In inference algorithm is specified which infers principal strictness types.•An extension of our system with recursive data types is given.