Category Archives: Programming

Basics: The Halting Problem

Leave a reply

Many people would probably say that things like computability and the halting
program aren’t basics. But I disagree: many of our basic intuitions about numbers and
the things that we can do with them are actually deeply connected with the limits of
computation. This connection of intuition with computation is an extremely important
one, and so I think people should have at least a passing familiarity with it.

In addition to that, one of the recent trends in crappy arguments from creationists is to try to invoke ideas about computation in misleading ways – but if you’re familiar with what the terms they’re using really mean, you can see right through their
silly arguments.

And finally, it really isn’t that difficult to understand the basic idea.
Really getting it in all of its details is a bit harder, but just the basic idea that there are limits to computation, and to get a sense of just how amazingly common uncomputable things are, you don’t need to really understand the depths of it.

Continue reading →

Basics: The Turing Machine (with an interpreter!)

Leave a reply

As long as I’m doing all of these basics posts, I thought it would be worth
explaining just what a Turing machine is. I frequently talk about things
being Turing equivalent, and about effective computing systems, and similar things, which all assume you have some clue of what a Turing machine is. And as a bonus, I’m also going to give you a nifty little piece of Haskell source code that’s a very basic Turing machine interpreter. (It’s for a future entry in the Haskell posts, and it’s not entirely finished, but it does work!)

The Turing machine is a very simple kind of theoretical computing device. In
fact, it’s almost downright trivial. But according to everything that we know and understand about computation, this trivial device is capable of any computation that can be performed by any other computing device.

The basic idea of the Turing machine is very simple. It’s a machine that runs on
top of a tape, which is made up of a long series of little cells, each of which has a single character written on it. The machine is a read/write head that moves over the tape, and which can store a little bit of information. Each step, the
machine looks at the symbol on the cell under the tape head, and based on what
it sees there, and whatever little bit of information it has stored, it decides what to do. The things that it can do are change the information it has store, write a new symbol onto the current tape cell, and move one cell left or right.

That’s really it. People who like to make computing sound impressive often have
very complicated explanations of it – but really, that’s all there is to it. The point of it was to be simple – and simple it certainly is. And yet, it can do
anything that’s computable.

Continue reading →

Pathological Programming as Pathological Cooking

Leave a reply

I’ve had a long, difficult week, so I’ve decided to pick something pointlessly
pathological for today. It’s a remarkably goofy language called “Chef”, designed by David Morgan-Mar, in which programs are recipes. Since aside from being a programming language
nutjob, I’m also a pretty good chef, combining two of my favorite things naturally has
some appeal – particularly when done in a pointlessly twisted way.

Continue reading →

The Theory of Monads and the Monad Laws

Leave a reply

As promised, I’m finally going to get to the theory behind monads. As a quick review, the basic idea of the monad in Haskell is a hidden transition function – a monad is, basically, a state transition function.

The theory of monads comes from category theory. I’m going to assume you know a little bit about category theory – if you have trouble with it, go take a look at my introductory posts here.

Continue reading →

More Monads: Stateful Programming

Leave a reply

Time for more monads. In this article, I’m going to show you how to implement a very simple
state monad – it’s a trivial monad which allows you to use a mutable state
consisting of a single integer. Then we’ll expand it to allow a more interesting
notion of state.

Continue reading →

A Pathological Challenge: Prime Programming in NULL

Leave a reply

Todays pathological language is actually in the form of a challenge for you. (Isn’t that
exciting?) It’s a very clever numerical programming language in the vein of Conway’s Fractran,
called NULL. The author of NULL describes it
as a reaction to 2 and 3 dimensional languages in the Befunge tradition; NULL is a 0
dimensional language – a program is just a single point. It’s quite clever in its way; the only
problem is that is that there’s only one example program written in it. So the challenge is
to see if you can actually come up with some implementations of interesting programs.

Continue reading →

Haskell: A First Step Into Monads

Leave a reply

The biggest nightmare for most people learning Haskell is monads. Monads are the
key to how you can implement IO, state, parallelism, and sequencing (among numerous other things) in Haskell. The trick is wrapping your head around them.

Continue reading →

Hellish Programming: Malbolge

Leave a reply

I decided that for today, I’d show the most thoroughly evil programming language ever
devised. This is a language so thoroughly evil that it’s named Malbolge after a circle
of hell. It’s so evil that it’s own designer was not able to write a hello world program! In
fact, the only way that anyone managed to write a “Hello World” was by designing a genetic algorithm
to create one. This monstrosity is so thoroughly twisted that I decided to put it in the “Brain and Behavior” category on ScienceBlogs, because it’s a demonstration of what happens when you take a brain, and twist it until it breaks.

Continue reading →

Haskell: the Basics of Type Classes

Leave a reply

One thing that we’ve seen already in Haskell programs is type
classes. Today, we’re going to try to take our first look real look
at them in detail – both how to use them, and how to define them. This still isn’t the entire picture around type-classes; we’ll come back for another look at them later. But this is a beginning – enough to
really understand how to use them in basic Haskell programs, and enough to give us the background we’ll need to attack Monads, which are the next big topic.

Type classes are Haskell’s mechanism for managing parametric polymorphism. Parametric polymorphism
is a big fancy term for code that works with type parameters. The idea of type classes is to provide a
mechanism for building constrained polymorphic functions: that is, functions whose type involves a type parameter, but which needs some constraint to limit the types that can be used to instantiate it, to specify what properties its type parameter must have. In essence, it’s doing very much the same thing that parameter type declarations let us do for the code. Type declarations let us say “the value of this parameter can’t be just any value – it must be a value which is a member of this particular type”; type-class declarations let us say “the type parameter for instantiating this function can’t be just any type – it must be a type which is a member of this type-class.”

Continue reading →

Programs as Poetry: Fishy Programming in Homespring

Leave a reply

I’m hitting on something deeply twisted this week. It’s called homespring. Homespring is interesting for two reasons. First, it’s got a sort of reverse flavor to it: it consists of active agents in a passive structure. So, for example, you can’t do anything like control flow – that’s a dynamic change in the control flow of the program; in Homespring, you need to trick the agents into doing something using the static, unchanging structure of the program. And second, it challenges you to write your program in the form of a poem! And the icing on the cake? The agents are salmon,
and the passive structure is a network of streams.

Continue reading →