(more to come)
Revision as of 04:16, 2 November 2006
Curry-Howard Isomorphism is an isomorphism between types (in programming languages) and propositions (in logic). Interestingly, the isomorphism maps programs (functions in Haskell) to (constructive) proofs (and vice versa).
1 The Answer
As is well established by now,
theAnswer :: Integer theAnswer = 42
2 InferenceA (non-trivial) Haskell function takes maps a value (of type
toInteger :: Boolean -> Integer inZ_2 False = 0 inZ_2 True = 1
Of course, atomic propositions contribute little towards knowledge, and the Haskell type system incorporates the logical connectives and , though heavily disguised. Haskell handles conjuction in the manner described by Intuitionistic Logic. When a program has type , the value returned itself indicates its type.
4 Theorems for free!
Things get interesting when polymorphism comes in. The composition operator in Haskell proves a very simple theorem.
(.) :: (a -> b) -> (b -> c) -> (a -> c) (.) f g x = f (g x)