Typing ZINC Machine with Generalized Algebraic Data Types

Kwanghoon CHOI  Seog PARK  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E94-D   No.6   pp.1190-1200
Publication Date: 2011/06/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E94.D.1190
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Software System
Keyword: 
type system,  ZINC machine,  generalized algebraic data type,  functional language,  

Full Text: PDF(1MB)
>>Buy this Article


Summary: 
The Krivine-style evaluation mechanism is well-known in the implementation of higher-order functions, allowing to avoid some useless closure building. There have been a few type systems that can verify the safety of the mechanism. The incorporation of the proposed ideas into an existing compiler, however, would require significant changes in the type system of the compiler due to the use of some dedicated form of types and typing rules in the proposals. This limitation motivates us to propose an alternative light-weight Krivine typing mechanism that does not need to extend any existing type system significantly. This paper shows how GADTs (Generalized algebraic data types) can be used for typing a ZINC machine following the Krivine-style evaluation mechanism. This idea is new as far as we know. Some existing typed compilers like GHC (Glasgow Haskell compiler) already support GADTs; they can benefit from the Krivine-style evaluation mechanism in the operational semantics with no particular extension in their type systems for the safety. We show the GHC type checker allows to prove mechanically that ZINC instructions are well-typed, which highlights the effectiveness of GADTs.