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 →

Creationists on Gene Variation

Leave a reply

Fellow [SBer Tara from Aetiology][tara] pointed me at [this bit of inanity][loonytune], which I can’t resist mocking:
[tara]: http://www.scienceblogs.com/aetiology
[loonytune]: http://www.wdcmedia.com/newsArticle.php?ID=2306
>The mystery of the human genome has come into clearer focus as scientists have discovered that each
>individual person is at least ten times more different than another person than scientists
>previously thought, discounting even further the theory of evolution so widely taught around the
>world. A group of scientists from 13 different research centers in the United States and Britain
>published their findings in scientific journals earlier this week. The results: previous concepts
>that all humans were 99.9% alike were blown apart by the research conducted on 270 people of various
>races that confirmed that 2,900 genes could vary within people, making over a million combinations
>possible.
>
>This discovery means that of the nearly 30,000 genes in the human genome that can consist of nearly
>three billion genetic “letters,” 10 percent of those genes can be multiplied in each different
>individual. Instead of being 99.9% alike, humans are more than ten times different from one another
>genetically. Instead of having two copies of each gene–one from each parent–humans have some genes
>that are multiplied several times. Scientists are excited about this discovery, which they say is
>the most revealing since Gregor Mendel’s initial work with the genetic code in the 1860’s.
>Scientists believe it will help them bring about curing individuals who have devastating diseases by
>using their own genetics.
Now, I admittedly have a bit of a hard time parsing this (I guess these creationists are illiterate as well as innumerate). But after correcting for grammar as well as I can, what I end up with is,
to put it mildly, pathetically stupid. Alas, they don’t provide *any* link to a *source* for this, so I can’t be sure of just what the heck they’re talking about, so I can’t completely correct their math. (You need *data* to do accurate math!) But I’ll do what I can. Read on, beneath the fold.

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.

Walking in Circles: Fundamental Groups

Leave a reply

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?”

Continue reading →

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

The End of PEAR

Leave a reply

PEAR is gone. Yes, I know I’m late with this news; folks like [PZ](http://scienceblogs.com/pharyngula/2006/11/shhhdont_tell_deepak.php), [Orac](http://scienceblogs.com/insolence/2006/11/news_too_good_to_confine_to_just_one_sci.php) and [Jeff Shallit](http://recursed.blogspot.com/2006/11/pear-has-finally-rotted.html) reported this
great news days ago. But I wanted to add my two bits, by explaining just why this is good news. So I’m going to take this news as an opportunity to remind you just what PEAR was, what they did, and why it’s so good that they’re gone.

Continue reading →

Friday Random Ten, Nov 24

Leave a reply

1. **Kate Bush, “Pi”**. I’ve been waiting for this to show up in my shuffle for the FRT! Kate Bush, singing the digits of π!
2. **Suzanne Vega, “Knight Moves”**. This is an old favorite of mine. The lyrics have some
personal significance, but it’s a lovely song.
3. **Explosions in the Sky, “Have You Passed Through This Night?”**. Post rock, very much in the
vein of “Godspeed You Black Emperor”. Not as good as Godspeed, but still pretty good.
4. **New Grange, “Weetabix”**. Very nice bluegrass tune performed by a supergroup of sorts. For the
anniversary of the founding of Compass Records, they put together this band of the top Compass
artists. It’s quite a lineup. Allison Brown on banjo (of course; AB is the founder of Compass);
Tim O’Brien playing a guitar-style Bouzouki (a bouzouki is strung like a mandolin – four pairs of strings tuned in fifths), but it’s much lower, in the same range as the guitar); Mike Marshall
playing Mandolin; Darol Anger playing fiddle; Todd Phillips on bass; and Phillip Aaberg playing piano.
5. **Rachel’s, “Artemisia”**. Yet more post-rock, this time from the more classical side. Rachel’s is one of my favorite groups, just overall amazing, wonderful composers and performers. Listening to
Rachel’s is a little slice of heaven.
6. **Hugh Blumenfeld, “Longhaired Radical Socialist Jew”**. The only gospel song that I like! Hugh is a great singer/songwriter and english professor. This is a hysterically funny song. To give you a sense of what it’s like, here’s the first verse: “Well, Jesus was a homeless lad/With an unwed mother and an absent dad/And I really don’t think he would have gotten that far/If Newt, Pat and Jesse had followed that star/So let’s all sing out praises to/That longhaired radical socialist Jew.”
7. **Solas, “The Wiggly Jigs”**. Solas is a great traditional Irish band, led by an unbelievable multi-instrumentalist named Seamus Egan.
8. **Flook, “Asturian Way”**. A great tune from my favorite trad Irish band.
9. **Dirty Three, “Stellar”**. Another really wonderful classical-leaning post-rock band.
10. **King Crimson, “Eyes Wide Open”**. A brilliant piece off of Crimson’s latest.

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 →