The Curry-Howard correspondence is a mapping between logic and type systems. On the one hand you have logic systems with propositions and proofs. On the other hand you have type systems with types and programs (or functions). As it turns out these two very different things have very similar rules. This article will explore the Curry-Howard correspondence by constructing a proof system using the Haskell type system (how appropriate since Haskell is named after Haskell Curry, the "Curry" in "Curry-Howard"). We'll set up the rules of logic using Haskell types and programs. Then we'll use these rules as an abstract interface to perform some logic profs.
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