HtDP for the experienced programmer

I am a fan of Scheme (a programming language for the soul) and SICP "the greatest book on programming ever written", but my hat goes off to the creators of DrScheme, a great interactive environment for the beginner and experienced programmer alike.

The other night I swallowed my pride and started to work through HtDP (How to Design Programs), the PLT Scheme gang's reaction to the fact that SICP (which came from MIT) while great for the suitably talented individual does not by-and-large work for the mainstream. In this book they explicitly teach program design, a systematic approach to thinking and problem-solving that it seems only a few people get by the more traditional osmotic process.

HtDP is covers a great range. Although principally geared to college level, it can be taught in high schools (at a slower pace), and can teach most experienced practitioners more than a thing or two.

Additionally, the people on the PLT Scheme mailing list are incredibly friendly and supportive. Here's what Matthias Felleisen, first author of HtDP (among many other things) wrote when I mentioned that I was starting to work through HtDP, but was having difficulty restraining myself from skipping ahead:

If you are an experienced programmer, you should read HtDP like this:

• Read the sections whose title starts with "Designing ...."
• Also read the "iterative refinement" sections
• Pick five exercises in the preceding and/or follow-up section and solve them according to the recipe
  [my emphasis]
• Unless you're stuck move forward
• Try to understand the "symmetry" between data definitions and templates

I expect that somewhere around late part II, you will slow down. You may pick up real reading as of part III, though some may make it thru III and only "stutter" in IV.

Also:

• Use check-expect to express your examples/tests
• Avoid draw.ss exercises, replace them with world.ss but that's a non-trivial switch

And holler if you are having trouble -- Matthias

In short: Great tools, great teaching materials, supportive and experienced community.

Learning about (Computational) Monads

I am interested in acquiring programming idioms -- or if you like patterns -- that facilitate a clear and disciplined approach to organizing state. As applications grow large and certain operations transform state in a large-scale fashion, it becomes harder to understand and modify program behavior.

Perhaps monads offer a better way, but I don't really get them yet ...

What are Monads?

I think Leibniz invented the term monad to describe some kind of indivisible fundamental entity in his philosophy: Presumably the term atom was too Greek for him. Anyway: I do not mean philosophical monads, or biological monads, or mathematical -- category theory -- monads (although now we are getting warmer).

Right now I mean computational monads, the ones so beloved of Haskell programmers, but potentially of use elsewhere.

A monad is a family of types M t, based on a polymorphic type constructor M, with functions

return :: t -> M t
(>>=) :: M t -> (t -> M u) -> M u

satisfying

return a >>f = f a
m >>= return = m
m >>= (\a -> (f a) >>=g) = (m >>= f) >>= g

This definition gave me flashbacks to Pure Mathematics Honours (4th year University) where I encountered some classes so abstract as to seem totally detached from reality: "Hello Banach Spaces and Algrebras!"

How to get it

But having survived a mathematics education and having a ridiculously high sense of self-efficacy I know how to get through this kind of obstacle. There are two methods:

1. Abstractions first: Treat this as a game where the rules are given, and play with them until they become familiar and seem natural.
2. Empirical approach: Walk in the footsteps of the discoverers by building some practical experience first, so that the abstractions begin to make sense.

Better still, work from both ends. Anyway, both approaches require doing, as opposed to reading, and I am starting with the following tutorial:

You Could Have Invented Monads! (And Maybe You Already Have)

which seems to be helping, and belongs to the latter camp.

More later ...

Functional Programming Interest Group

An idea has been slowly germinating in my mind: Try to start a new special interest group (SIG) meeting in Melbourne once a month, but also with a virtual presence.

I have been working slowly through Abelman & Sussman's Structure and Interpretation of Computer Programming (SICP) and exercises, the MIT classic "introductory" text, but would like to share the experience. The great thing about SICP is that it is free online, as are accompanying video lectures -- the first was inspirational, but subsequently I have relied on the text. The tools are available online and free. The language used is Scheme (a teaching/research Lisp), but it's the ideas that come through.

There are other books out there which promise to capture exciting ideas using various f.p.-ish languages as vehicles:

• Hudak, The Haskell School of Expression
• Armstrong, Programming in Erlang
• Siebel, Practical Common Lisp (text available online)

I believe that languages such as these are worth studying for the ideas that they develop:

Haskell: Lazy evaluation, monadic computation, mathematical modelling, and more ...
Erlang: Practical, reliable, massive parallelism, ...
Lisps: Code-data duality

I am also interested in F# (as the .NET representative of the ML / OCAML) family, but am waiting on the publication and review of more books. [Forgive me for leaving Smalltalk, Forth, plus the various languages du jour off my list: There may well be too many already.]

Other probably books worth looking into:

• Graham, On Lisp
• Norvig et al, PAIP and AI: A modern approach
• Kiczales, The Art of the Meta-Object Protocol
• Sussman and Wisdom, Structure and Interpretation of Classical Mechanics (text available online)
• Doets and van Eijck, The Haskell Road to Logic, Maths and Programming
• Okasaki, Purely Functional Data Structures

Of course these are just some highly rated books, and not the literature, but my objective here is to survey some of the more mature parts of field; the leading edge can wait.

It's all about the joy of new and ongoing learning; with the bonus of becoming more skillful, productive, and having a chance of successfully working with the coming generation of massively multi-core machines.

I would be interested in hearing expressions of interest, suggestions for format plus any experiences and tips from anyone involved in such groups.

Let's Get Functional

Last week I watched Harold Abelson's introductory SICP lecture, courtesy of Google Video. SICP is short for Structure and Interpretation of Computer Programs, which is a much copied course given at MIT, and the title of Abelman and Sussman's now classic introductory text to Computer Science. Besides the video lectures, the complete text is available from the above link online. Thank-you!

Talk about insightful! This is what Computer Science is really about. Probably more advanced than most undergraduates can cope with, I am taking the time to look at these classic texts because I suspect that functional programming (FP) is about to become much more important.

Why? Besides the intrinsic pleasure in learning and extending oneself, multi-core CPUs are starting to go main-stream, and I believe that FP is our best hope to take advantage of a new age of parallel hardware.

So I plan to brush up by going through some / most of SICP (and doing the exercises), before moving on to one or more of Haskell (especially for monads), OCaml, and F#.

SICP is draws many examples from mathematics, so with my background it looks very inviting. Others may prefer How To Design Programs, another freely available text.

* * *

Abelson says that when you look into a computer language, you should ask:

• What are the primitives?
• What are the means of combination?
• What are the means of abstraction?
  

The primitives are the "building blocks"; the means of combination are the ways of putting the primitives together; and the means of abstraction are ways of building composites (out of primitives and other composites) when the primitives are insufficient. If the composites are then indistinguishable from the primitives, you have something truly powerful.

This prompted an interesting thought the following day:

Do these criteria also apply to computer applications?

More on this later ...

What Would a Functional Progammer Do?

As C# adopts features from functional programming languages it is becoming increasingly possible to program in an-least partially functional style as part of your day-job.

At time of writing I am using C# 2.0, which has reasonable support for lambda functions in the form of delegates, but they are ugly, because of the presence of strict-typing / absence of type-inference. You need to think things out functionally and then translate into the clunky C# 2.0 notation.

Things will get better with C# 3.0 and a host of functional-inspired features, including limited-type inference and cleaner notation to support LINQ.

Anyway, yesterday I was pairing with a colleague working on implementing some experimental enhancements to some core algorithms, and we were running into difficulties. Because the implementation was in C# we were thinking in an imperative way, and after running through a few options and hitting various dead-ends I asked Peter, "What would a functional programmer do?"

We were working on variations of an in-place algorithm, where a functional programmer would tend to write -- wait for it! -- a pure function. In our case a more functional approach was going to be a lot easier. Our context had blinkered us. And once you take a step back and put the functional hat on, other avenues open up.

So, here's a short list of things a functional programmer might do, and which are worth thinking about when you're trying to solve a programming problem:

1. In-place modification or pure function?
2. Higher-order functions: Does treating code as data lead to simplifications?
3. Can monads help?

Of course the amount that you can do may depend on language support that is present. Item 5 is a reminder to get on top of the monads concept: "If you can't understand it, you won't recognize when you can use it!"

All of this is in aid of the ideals of better abstractions, clearer and more understandable code, leading to higher quality and greater satisfaction and success.

There's a paradox that one may need greater understanding to express things more simply, and that for someone with less understanding the higher. clearer expression may be incomprehensible. But that's really old news: Look at the history of science and mathematics. Example: Want to know the area under a funny looking curve? Easy if you know calculus. Don't know calculus? A simple explanation may be hard to come by!

Now for the big question:

If Jesus were alive today, would he use a functional programming language? Who knows?

But Moses would, for sure.