Dependent type systems, in which types can depend on values, admit detailed specifications of function behavior and data invariants. Programming languages based on System F do not have dependent types, and are therefore more limited in what structure or function invariants can be encoded in the type system. In this paper, we show how guarded algebraic datatypes can simulate dependent types. We formalize additions to a guarded-datatypes-enhanced System F that allow types to depend on values and discuss the programming style that results, which is similar to theorem proving. Our technique can be applied to multiple existing programming languages, including Haskell and C#. We also introduce an idiom for eliminating any execution cost from programming with simulated dependent types. We have developed a tool to automatically produce the boilerplate necessary for the simulation, and we have used it to enforce data structure invariants and to allow elision of run-time bounds checks.
Small TYPES workshop Curry-Howard Implementation Techniques/Connecting Humans and Type-checkers 2006 The CHIT Workshop discuss implementation issues.Keywords: * Terms and binders * Type inference, type constraints and unification * Reduction, evaluation and compilation * Proof refinement/Proof engine * State handling, library, modules, saving format * Coercions * Termination checking The CHAT workshop will focus on interaction between users and proof environments, graphical interfaces, and on network-based interaction. Keywords: * Declarative versus procedural proof styles (structured proofs, XML) * Web based interfaces (including cooperative environments) * Libraries and information retrieval (including search engines) * Proof documentation (literate proving) * Protocols for UI-interaction