Designing a Module for Combinatory Logic in Haskell

4/09/2010

Like the Lambda Calculus (on which Lisp is based), Combinatory Logic is a formal system that can be used to model and study computation. What makes it fascinating is that it is as powerful as the (already simple) lambda calculus, but has no need for the variables that LC requires to perform substitution!

Here I show how we can use Haskell’s type classes and other language features to model the Combinator Calculus. The goals of this module were:

  1. don’t force any one evaluation strategy
  2. allow users to define new combinators without exposing the implementation
  3. allow new combinators to be defined in terms of other already-defined combinators.
  4. discourage creation of non-sensical combinator expressions, or possible mis-use of the module
  5. hide existential types and anything else exotic

If you want to play with it, you can do a:

$> darcs get http://coder.bsimmons.name/code/CombinatorCalculus

Read the rest of this article »

1 Comment

The Gift of Inconsistency

22/07/2010

Computer science is a fascinating and maddening thing. Even the most seemingly-esoteric topics turn out to be fundamental. Go out to the fringes of CS and you find yourself smack in the middle of Philosophy. You try to understand a single point and you suddenly find yourself embracing everything.

So this post comes from that infinitely-recursive rabbit hole of wikipedia topics I’ve been falling down for the last few weeks, and you can probably expect a few more like this one; I’ll try to keep focused.

We begin (as do All Good Things) with the Untyped Lambda Calculus:
Read the rest of this article »

No Comments

Befunge-93 Interpreter on Hackage

20/05/2010

I’ve fixed a bug related to upgrading GHC to version 6.12 (thanks to Cale and the folks on haskell-cafe who helped me with the issue) and got my Befunge-93 interpreter up on hackage. The program is written in haskell (as usual). You should be able to get it soon with a:

$> cabal install Befunge93

If you want to read about how I designed it you can check out the source above, or take a look at my previous blog post.

Please report any bugs to me, and I’m also very interested in patches or suggestions for performance improvements if anyone ends up being interested in this program.

EDIT: Here is the package page: http://hackage.haskell.org/package/Befunge93

No Comments