Haskell is a strongly typed language. In fact, the type system in Haskell is both stricter and more
expressive than any type system I’ve seen for any non-functional language. The moment we get beyond
writing trivial integer-based functions, the type system inevitably becomes visible, so we need to
take the time now to talk about it a little bit, in order to understand how it works.
I’m sure that in the friday pathological programming languages, I have a fondness for languages
that make your code beautiful: languages like [SNUSP][snusp], [Befunge][befunge], [Piet][piet], and such. Those languages all you two-dimensional layouts for their programs.
[snusp]: http://scienceblogs.com/goodmath/2006/08/beautiful_insanity_pathologica.php
[befunge]: http://scienceblogs.com/goodmath/2006/07/friday_pathological_programmin.php
[piet]: http://scienceblogs.com/goodmath/2006/11/programming_in_color_fixed.php
Among the nutters that make up the community of folks interested in this kind of thing, looking
at these languages led to a theoretical question, which was named *”the wire-crossing problem”*. The
basic question was:
>Is it possible to define a two-dimensional flow-based language which does *not* ever need
>one execution path to *cross* another execution path?
Alternatively:
>Is it possible to express every computable function as a two-dimensional graph
>where no edges ever cross?
This question raged for quite a while without an answer. Todays pathological language is
a very simple language designed for the sole purpose of demonstrating, once and for all, that
*yes*, you can write every computable function with no wire-crossing.
I wasn’t really sure of quite how to start this off. I finally decided to just dive right in with a simple function definition, and then give you a bit of a tour of how Haskell works by showing the different ways of implementing it.
Before getting to the meat of the tutorial, I thought it would be good to provide some setup
information in a distinct, easy to find place. This short post will tell you where to find
a Haskell implementation and related tools.
I’m testing my examples for these articles using two different Haskell implementations:
ghci which is included in its distribution. It’s also good to have some extra tool support for Haskell programming. A lot of editors, such as
emacs, vim, and textmate provide Haskell tooling. The best tooling that I’ve seen is the EclipseFP feature for the Eclipse programming environment. Admittedly, I’m a bit biased here;
I’ve used to lead an Eclipse-based research project, so I’m a huge Eclipse fan. But the Eclipse
Haskell support really is very nice, and it’s very easy to set up. Installing Eclipse involves
nothing more than downloading it – it runs very smoothly in-place with no setup; and installing
EclipseFP can be done inside of Eclipse using the update manager – there’s a complete step by step
explanation at the EclipseFP homepage linked above.
If you’re a visual studio user, there’s a Haskell package called Visual Haskell. I’ve never used it (I’m not
a windows guy; I use MacOS and Linux.), but I’ve heard quite good things about it.
If you prefer just using a simple text editor, vim includes the Haskell package; for emacs, you
can get a Haskell mode here. For TextMate, you can get
the Haskell bundle via the normal bundle installation route.
For understanding the execution of Haskell programs, particularly when the laziness gets a bit
confusing, being able to generate an execution trace can be a huge help. There’s a tool called Hat which can generate very nice, easy to follow traces for
GHC programs.
You can write fancy documentation for Haskell programs using a tool called Haddock. Haddock is something like Javadoc for
Haskell. It piggybacks on a “literate” syntax mode built-in to both GHC and Hugs, so
at least primitive support for Haddock is included in all of the Haskell tools; many also
provide additional Haddock support.
The capital of the online Haskell world is the Haskell.org site. It has links to numerous other tutorials, the language spec, implementations, events, etc.
There’s a Haskell blog called The Complete Sequence, which includes a weekly Haskell news update, as well as other interesting articles and links. There’s another Haskell blog called Planet Haskell which also has some good material.
In algebraic topology, one of the most basic ideas is *the fundamental group* of a point in the space. The fundamental group tells you a lot about the basic structure or shape of the group in a reasonably simple way. The easiest way to understand the fundamental group is to think of it as the answer to the question: “What kinds of different ways can I circle around part of the space?”
Before diving in and starting to explain Haskell, I thought it would be good to take a moment and answer the most important question before we start:
**Why should you want to learn Haskell?**
It’s always surprised me how many people *don’t* ask questions like that.
Haskell is a valuable language for a lot of different reasons, but the most important one is that *it
changes the way that you think about programming*. Haskell does things in a very different way from the imperative languages that most of us are familiar with. And it’s an extremely well-designed language, so there isn’t a ton of crap standing between you and the concepts that you can learn from it.
As you may have noticed, lately, I’ve been fascinated by Haskell. I haven’t done anything much in it until quite recently; it’s been sitting in my to-do queue for a long time. This weekend, I was hacking away on a Haskell implementation of an interesting (but currently unimplemented) language from the Esolang wiki. For the most part, it went astonishingly smoothly, until I got to the point of putting things together, when I ran into a problem combining two monads, which is one of the typically difficult problems in real Haskell programming.
What surprised me a bit when I hit this is how hard it is to find an approachable source for the more advanced issues. If it’s hard on a language geek like me, it’s bound to be as bad or worse for a lot of other
people who might be interested in Haskell.
So the thought hit me. If enough readers are interested, I can write an intermittent series of articles
to teach Haskell, starting from the very early basics, all the way through to the messiest issues of monad transformers.
Are you interested? Interested enough that you’d be willing to accept a bit of a slowdown of the (already slow) topology posts to give me time to write it?
Let me know what you think, either in the comments below, or through email to markcc@gmail.com.
*Ok, folks, I get the hint, you can stop emailing me! :-)*
*Since posting the question on a holiday weekend saturday night, I’ve gotten 50 responses, and they’re unanimously in favor. I **will** start working on it, and the first parts should appear on the blog later this week.*
Todays tidbit of torture is a simple little language called [Leszek][leszek], with an implementation available [here][leszek-impl]. Leszek is based on the idea of *iterative string rewriting*, which is actually a useful and valuable concept. Of course, Leszek takes it to an extreme of insanity which takes a perfectly good idea, and turns it into a horror. But thats what makes it fun!
[leszek]: http://www.esolangs.org/wiki/Leszek
[leszek-impl]: http://students.mimuw.edu.pl/~js248325/zsyp/leszek.tar.gz
In Lezsek, there are no variables; no loops; no state. A program is just a string with
a collection of embedded rewriting operators. The way that things work is, the interpreter looks
at the string. It finds all of the rewriting commands in the string, and executes them, concatenating the *results* of those commands. When it’s done all of
the rewrites in the entire program, it takes the *resulting* program string, and executes *that*. It keeps going until there is no possibility of any more rewrites generating output, and then it halts.
One of my fellow ScienceBloggers, [Karmen at Chaotic Utopia](http://scienceblogs.com/chaoticutopia/2006/11/puzzling_at_a_simpleminded_cre.php) pointed out a spectacularly stupid statement in [Casey Luskin’s critique of Carl Zimmer][lutkin] (*another* fellow SBer) at the Discovery Institutes “Center for Science and Culture”. Now normally, I might not pile on to tear-down of Casey (not because he doesn’t deserve it, but because often my SciBlings do such a good job that I have nothing to add); but this time, he’s crossed much too far into *my* territory, and I can’t let that pass without at least a brief comment.
[lutkin]: http://www.evolutionnews.org/2006/11/evolution_nat_geo_1.html
So, here’s the dumb statement:
>The article called evolution a “simple” process. In our experience, does a “simple” process generate
>the type of vast complexity found throughout biology?
Yes, one of the leading IDist writers on the net believes that in reality, simple processes don’t generate complex results.
Karmen pointed out fractals as a beautiful example of the generation of complexity from simplicity. I’d like to point out something that, while lacking the artistic beauty of a well-chosen fractal, is an *even simpler* and possibly more profound example.
Due to work stuff, I’m very busy this week, and I don’t have time to write a detailed
pathological language post, so I chose something that doesn’t take a lot of explanation, but
which is delightfully twisted. It’s a language called [Muriel](http://web.archive.org/web/20021205092706/http://demo.raww.net/muriel/), aka
the *”Monumentally Useless ReIterative Execution Language”.
Muriel is based on the idea of [*quines*](http://www.nyx.net/~gthompso/quine.htm). A quine for a programming language is a program in that language which produces itself as output. Quines are
considered interesting puzzles in some circles, which has led to generation of huge collections of quines in just about every imaginable programming language. Follow the link above to see one such collection. Muriel takes things a step further: instead of quines being an interesting (if pointless) challenge, in
Muriel, they’re an essential part of the language!