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.
Epigram is a dependently typed programming language and an interactive programming environment. Epigram has got a type system which is strong enough to express the behaviour of programs, the type checker then guarantees that the program is well behaved. However, you don't have to go as far, you can write ordinary programs and refactor them into more trustworthy, formally checked deliverables -- Epigram supports a pay as you go approach to formal methods. Epigram is freely available this page provides access to downloads of version 1 as source or binaries for the major platforms along with relevant documentation. Development on version 2 is under way we hope this will considerably improve on the first, and details of its current state are available, in the form of a developers' 'blog.
Metamorphic programming is an approach to extend the structured recursive programming discipline, which favors the use of fold operations over general recursion, to abstract data types. The key idea is to represent an ADT by two parts, a constructorand a destructor,which are essentially functions to/from a common representation. Then a fold can work on an ADT by applying parameter functions to values that are delivered by the ADT's own destructor. Fold operations that use as a parameter the constructor of another ADT, called ADT transformers,play an important role and offer a concise programming style. Several laws for ADT folds and transformers exist that can be used for program optimization and verification.
Interpreting types as abstract values [The Abstract of the lecture notes] We expound a view of type checking as evaluation with `abstract values'. Whereas dynamic semantics, evaluation, deals with (dynamic) values like 0, 1, etc., static semantics, type checking, deals with approximations like int. A type system is sound if it correctly approximates the dynamic behavior and predicts its outcome: if the static semantics predicts that a term has the type int, the dynamic evaluation of the term, if it terminates, will yield an integer. As object language, we use simply-typed and let-polymorphic lambda calculi with integers and integer operations as constants. We use Haskell as a metalanguage in which to write evaluators, type checkers, type reconstructors and inferencers for the object language.
I'm interested in the relative merits of ATS vs. Epigram which is a Pure Type System that seeks to unify types and terms, where ATS distinguishes the statics and dynamics of the language. What benefits and limitations do these approaches have on complexity for both developer and implementor? notes in atsVepig.txt
The goal of the Ynot project is to make programming with dependent types practical for a modern programming language. In particular, we are extending the Coq proof assistant to make it possible to write higher-order, imperative and concurrent programs (in the style of Haskell) through a shallow embedding of Hoare Type Theory (HTT). HTT provides a clean separation between pure and effectful computations, makes it possible to formally specify and reason about effects, and is fully compositional. more...
This book is about beliefs---how we get them and how we evaluate them. It takes the form of a fictional conversation makes the following points: 1) in analogy with robots, we humans know by the models we make of reality, 2) these models are always provisional and sometimes unreliable, 3) it is especially important to examine thoroughly those models upon which we base actions, and 4) the scientific method provides an excellent guide for such examination. The level of exposition is neither technical nor deeply philosophical
Jack W. Crenshaw wrote the Let's Build a Compiler article series from 1988 - 1995. This document is a formatted version of that excellent non-technical introduction to compiler construction. These web pages were created in 2005, and port Mr. Crenshaw's original Pascal code for the 68000 under SK*OS to the Forth language on a 80x86 CPU, under Windows XP. The text files were downloaded from http://compilers.iecc.com/crenshaw/. They are highly recommended. In this transcript I have assumed a 32-bit, byte-addressing Forth, with 8-bit characters. Division is symmetric, not floored, and two's complement is assumed throughout. iForth works splendidly for it, but other Forths can do it too.
jose emilio labra gayo This page collects my personal links in the field of Programming Languages. At first, it was devoted to functional programming. Now, I am very interested in the expressiveness of programming languages in general. With the term advanced I mean that it is oriented to researchers on programming languages .
Methods that are specialised on sub-classes introduce a number of well-known challenges for type systems: these challenges can now be met in a type system for the pattern calculus. The latter provides a foundation for computation based on pattern-matching in which different cases may have different specialisations of a default type. Supporting type specialisation by both type substitution and sub-typing makes it possible to type functions whose cases correspond to the different.