Category Archives: Programming

Pathological Programming: Do we need to have our wires crossed?

Leave a reply

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.

Continue reading →

Simple Functions in Haskell

Leave a reply

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.

Continue reading →

Haskell Preliminaries: Implementations and Tools

Leave a reply

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.

Haskell Implementations

I’m testing my examples for these articles using two different Haskell implementations:

Hugs
A very nice interactive Haskell interpreter. Hugs doesn’t quite implement
everything in the current Haskell specification, but it’s limits shouldn’t affect
anything I’ll cover in this tutorial, and probably won’t affect any moderate-to-large
size programs you want to write.
GHC
The Glasgow Haskell Compiler, a high performance optimizing Haskell compiler. GHC implements
every last bit of the Haskell spec, as well as a bunch of nifty extensions. It’s also
got an interactive mode, called ghci which is included in its distribution.
GHC is pretty much the gold standard in Haskell implementations.

Editors and Development Environments

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.

Miscellaneous Tools

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.

Other Documentation

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.

Why Haskell?

Leave a reply

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.

Continue reading →

Query for readers: Interested in Haskell?

Leave a reply

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.*

Pathological Programming by String Rewriting

Leave a reply

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.

Continue reading →

Complexity from Simplicity; or, Why Casey Luskin Needs a Math Class

Leave a reply

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.

Continue reading →

Friday Pathological Programming: Quine Madness with Muriel

Leave a reply

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!

Continue reading →

Friday Pathological Programming: Bad Actors in Cruise

Leave a reply

Today’s pathological language is a bit of a treat for me. I’m going to show you a twisted,
annoying, and thoroughly pointless language that *I* created.
The language is based on a model of computation called [Actors](http://en.wikipedia.org/wiki/Actor_model), which was originally proposed by Professor Gul Agha of UIUC. There’ve been some really nice languages built using ideas from Actors, but this is *not* one of them. And that’s exactly where the name comes from. What name comes to mind when you think of *really bad* actors with delusions of adequacy? For me, it’s “Cruise”.
You can get the code for Cruise on Google code, project “Cruise”, or you can grab a bundle containing the code, and a compiled binary in a jarfile [here](http://scienceblogs.com/goodmath/upload/2006/11/cruise.zip). To run it, just “java -jar Cruise.jar cruse-program-file”. Just so you know, the code *sucks*. It’s something I threw together in my spare time, so it’s sloppy, overcomplicated, probably buggy, and slow as a snail on tranquilizers.

Continue reading →

Programming in Color (fixed)

Leave a reply

Todays programming pathology is programs as art.
Start with a really simple stack based language, add in a crazy way of encoding instructions using color, and you end up with a masterpiece of beautiful insanity. It’s not too exciting from a purely computational point of view, but the programs are really great to look at. Yes, it’s a pathological language with truly beautiful source code!
*(The original version of this post had some trouble because I linked to the original images in-place,
which the owner of the Piet webpage had blocked. I didn’t realize he didn’t want links. I’ve since downloaded
the images, coverted them to jpegs, and posted them here. I initially thought that the problem with the images was formats, which is what I originally said in this explanation. It’s not the image format, but the linking; but converting the files to jpeg and uploading them removed the links that caused the problem.)*

Continue reading →