Category Archives: Programming

Creating User-Defined Types in Haskell

  • (This is an edited repost of one of the posts from the earlier
    version of my Haskell tutorial.)
  • (This file is a literate haskell script. If you save it
    as a file whose name ends in “.lhs”, it’s actually loadable and
    runnable in GHCI or Hugs.)

Like any other modern programming language, Haskell has excellent support
for building user-defined data types. In fact, even though Haskell is very
much not object-oriented, most Haskell programs end up being centered
around the design and implementation of data structures, using constructions
called classes and instances.

In this post, we’re going to start looking at how you implement data types
in Haskell. What I’m going to do is start by showing you how to implement a
simple binary search tree. I’ll start with a very simple version, and then
build up from there.

Continue reading

Types in Haskell: Types are Propositions, Programs are Proofs

(This is a revised repost of an earlier part of my Haskell tutorial.)

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.

Continue reading

Writing Basic Functions in Haskell (edited repost)

(This is a heavily edited repost of the first article in my original
Haskell tutorial.)

(I’ve attempted o write this as a literate haskell program. What that
means is that if you just cut-and-paste the text of this post from your
browser into a file whose name ends with “.lhs”, you should be able to run it
through a Haskell compiler: only lines that start with “>” are treated as
code. The nice thing about this is that this blog post is itself a
compilable, loadable Haskell source file – so I’ve compiled and tested
all of the code in here in exactly this context.)

Continue reading

The Go I Forgot: Concurrency and Go-Routines

A couple of people pointed out that in my wednesday post about Go, I completely left out the concurrency stuff! That’s what I get for rushing the post – I managed to leave out one of the most interesting subjects! Go provides very strong support for communicating processes.

I haven’t done a lot of hacking with the concurrency stuff yet – so my impressions of it are still very preliminary. But my early impressions are very good.

Continue reading

Google's New Language: Go

I’ve been being peppered with questions about Go, the new programming language just released as open-source by Google. Yes, I know about it. And yes, I’ve used it. And yes, I’ve got some strong opinions about it.

Go is an interesting language. I think that there are many fantastic things about it. I also think that there are some really dreadful things about it.

A warning before I go on: this post is definitely a bit of a rush job. I wanted to get something out before my mailbox explodes :-). I’ll probably try to do a couple of more polished posts about Go later. But this should give you a first taste.

Continue reading

Philosophizing about Programming; or "Why I'm learning to love functional programming"

Way back, about three years ago, I started writing a Haskell tutorial as a series of posts on this blog. After getting to monads, I moved on to other things. But based on some recent philosophizing, I think I’m going to come back to it. I’ll start by explaining why, and then over the next few days, I’ll re-run revised versions of old tutorial posts, and then start new material dealing with the more advanced topics that I didn’t get to before.

To start with, why am I coming back to Haskell? What changed since the last time I wrote about it?

Continue reading

Two Dimensional Pathological Beauty: SNUSP

I’m currently away on a family vacation, and as soon as vacation is over, I’m off on a business trip for a week. And along the way, I’ve got some deadlines for my book. So to fill in, I’m recycling some old posts. I decided that it’s been entirely too long since there was any pathological programming ’round these parts, so I’m going to repost some of my favorites.

Todays programming language insanity is a real delight – it’s one
of my all-time favorites. It’s a language
called SNUSP. You can find the language specification here,
a compiler, and
an interpreter embedded
in a web page
. It’s sort of like a cross between Befunge
and Brainfuck,
except that it also allows subroutines. (And in a variant, threads!) The
real beauty of SNUSP is its beauty: that is, programs in SNUSP are actually
really quite pretty, and watching them run can be positively entrancing.

Continue reading

Two-Dimensional Pathology: Befunge

I’m currently away on a family vacation, and as soon as vacation is
over, I’m off on a business trip for a week. And along the way, I’ve got some
deadlines for my book. So to fill in, I’m recycling some old posts. I decided
that it’s been entirely too long since there was any pathological programming
’round these parts, so I’m going to repost some of my favorites.

Today, we’re going to take a look at a brilliant language called Befunge.
Befunge is the work of an evil genius named Chris Pressey.

Normal programming languages are based on a basically one-dimensional
syntax; the program is a string, a sequence of characters, and it’s processed
by reading that string in a straight-ahead fashion. But that’s not Befunge!
It’s got a two-dimensional syntax. Befunge is something like a two-dimensional
turing machine: the program is written on a two dimensionaltorus called the playfield. Each
instruction in Befunge is a single character, and where it’s located on the
torus is crucial – control is going to move either up/down or left/right
on the torus. All of the control flow is expressed by just changing the direction that
the head moves over the torus.

(In case you’re not familiar with a torus, it’s what you get
if you take a very flexible sheet of paper, and roll it so that you connect
the top edge to the bottom, and then roll that tube so that you connect the
left edge to the right. You get a donut shape where moving up from what used
to be the top of the page puts you on the bottom of the page; moving left from
the left edge of the page puts you on the right.)

Continue reading

The One… The Only… Brainf*ck

I’m currently away on a family vacation, and as soon as vacation is over, I’m off on a business trip for a week. And along the way, I’ve got some deadlines for my book. So to fill in, I’m recycling some old posts. I decided that it’s been entirely too long since there was any pathological programming ’round these parts, so I’m going to repost some of my favorites.

As long-time readers know by now, in real life, I’m not a mathematician; I’m a computer scientist. I’m still a math geek, mind you, but what I really do is very much in the realm of applied math, working on building systems to help people build programs.

One of my pathological obsessions is programming languages. Since I first got exposed to TRS-80 Model 1 BASIC back in middle school, I’ve been absolutely┬á nuts programming languages. Last time I counted, I’d learned about 150 different languages; and I’ve picked up more since then. I’ve written programs most of them. Like I said, I’m nuts.

These pathological programming language posts are my way of inflicting my obsession on you in a (hopefully) amusing way. You see, in this screwed up world of ours, there are lots and lots of thoroughly crazy people out there. In the world of geekery, many of those crazy people like to invent programming languages. Some very small number of them try to design good languages and succeed; a much larger number try to design good languages and fail; and then there are ones whose work I’m writing about. The ones who deliberately set out to design strange, warped, twisted, and nearly unusable languages, and succeed brilliantly. Most of the people who design them call them “esoteric” programming languages. I call them evil.

Today, the beautiful grand-daddy of the esoteric language family: the one, the only, the truly and deservedly infamous: Brainfuck, designed by Urban M├╝ller. (There are a number of different implementations available; just follow the link.)

Only 8 commands – including input and output – all written using symbols. And yet it’s Turing complete. In fact, it’s one-up on just being Turing complete – it’s actually been formally specified with a complete formal theoretical design, called P”. And it’s even been implemented in hardware!.

Continue reading

Pathological Programming with Primes (REPOST)

I’m currently away on a family vacation, and as soon as vacation is over, I’m off on a business trip for a week. And along the way, I’ve got some deadlines for my book. So to fill in, I’m recycling some old posts. I decided that it’s been entirely too long since there was any pathological programming ’round these parts, so I’m going to repost some of my favorites.

Today’s pathological language is my personal all-time favorite pathological monstrosity. It’s an incredibly combination of perfect simplicity and complete incomprehensibility. It’s based on a piece of work called Fractran by John Conway of game theory fame. It’s a really fascinating bugger; absolutely insanely difficult to program in, but based on one of the most bizarrely elegant concepts of computation that I’ve ever seen. It’s amazing that this is Turing complete. It’s not a real programming language in the sense of being able to write practical programs; it’s more of a simple theoretical computational model which has been implemented as a
language.

Continue reading