Tuesday, December 05, 2006

Generalised Haskell

In the past few days I've been working on a generalised version of Haskell, designed for program optimisation and transformation. I've also implemented the start of a Haskell optimiser, but in about 100 lines of Haskell, using this generalised form of Haskell.

Generalised Haskell is very much like a normal Haskell Core language, with less restrictions in pattern matching. In normal Haskell you would write "map" as:

> map f [] = []
> map f (x:xs) = f x : map f xs

Which would be compiled into:

> map f x = case x of
> ____ [] -> []
> ____ (x:xs) -> f x : map f xs

The rule for pattern matching is that you take the first rule that matches. Generalised Haskell relaxes this slightly to take any one rule that matches, but not necessarily in order. The second relaxation is that when pattern matching on the left hand side, functions can appear as patterns.

For example, you can now define:

> map id x = x
> map f x= case x of
> ____ [] -> []
> ____ (x:xs) -> f x : map f xs

Note that the "map id" case looks very much like GHC's Rules feature. The advantage for optimisation is that many activities can be encoding using these pattern matches - arity raising, specialisation, deforestation.

I am still working on a tool that uses this technique for optimisation, but initial results look quite promising, while the code remains impressively short.

4 comments:

Anonymous said...

Calling a pattern-matching extension "Generalized Haskell" implies that Haskell is a pattern-matching syntax for some underlying theoretical language -- probably a combination of Squiggol and combinatory logic.

Is *that* what you're saying?

Anonymous said...

No, thats definately not what I'm saying! I'm just saying its more general than Haskell for pattern matches - i.e. Haskell's behaviour is a subset of this language.

-- Neil

Anonymous said...

Now this looks interesting (not that everything on this blog isn't interesting :)).

I am having trouble coming up with a specific question, but I would love more details on this.

Anonymous said...

I'm still trying to figure out the details, still working on it. I hope to have an optimiser based on this in a few days time.