Skip to main content

A Tale of Three Loops

This one has been cooking for a very long time. Like many professional programmers I have often wondered what is it about programming that is just hard. Too hard in fact.

My intuition has led me in the direction of turing completeness: as soon as a language becomes Turing complete it also gathers to itself a level of complexity and difficulty that results in crossed eyes. Still, it has been difficult to pin point exactly what is going on.

A Simple Loop

Imagine that your task is to add up a list of numbers. Simple enough.

If you are a hard boiled programmer, then you will write a loop that looks a bit like:

int total = 0;
for(Integer ix:table)
total += ix;

Simple, but full of pitfalls. For one thing we have a lot of extra detail in this code that represents additional commitment:

  • We have had to fix on the type of the number being totaled.

  • We have had to know about Java's boxed v.s. unboxed types.

  • We have had to sequentialize the process of adding up the numbers.

While one loop is not going to hurt anyone; real code is stuffed with them. There have been occasions (not many thankfully) where I have written loops nested to a depth of 7 or 8. Such code really does become impossible to follow; let alone to write.

A Functional Loop

In a functional programming language, there are two ways to accomplish the task. The apprentice's approach might be to write a recursion:

total(nil) is 0;
total(cons(E,L)) is total(L)+E;

While workman-like, for many instances a smarter way is to use a fold:


Apart from being more concise; the fold is higher-level: it abstracts away the machinery of the loop itself and it is also independent of the representation of the collection of numbers.

(That is assuming that you have a functional language with overloading).

What is really interesting in relation to my original thesis is that the fold expression is closer to a problem-solving representation of the task.

However, ask any functional programmer about their use of fold and you will likely encounter a fairly procedural interpretation of how it works and how it should be used. (Something about how it successively applies the + function to each element of the list accumulating the answer as it goes.)

I.e., fold is better than for; but is not good enough.

A Totalization Query

My third version of this would be familiar to any SQL programmer:

total X where X in L

I.e., if you want to add up the elements of the list, then say so!

This query — which is based on notation in the Star programming language — declaratively states what is required. Although it's form is a little too specific, a more realistic variant would be:

fold X with (+) where X in L

I argue that either of these queries is better than either of the previous solutions because it comes closest to the original description and makes the fewest assumptions about the nature of the collections or the arithmetic.

It is also much closer to a problem oriented way of thinking about the world. I would argue that more people — especially non-programmers — would be able to follow and even to write such a query than either of the earlier formulations.

Why is that?

The Homunculus

Traditional programming is often taught in terms of programs being sequences of steps that must be followed. What does that imply for the programmer? It means that the programmer has to be able to imagine what it is like to be a computer following instructions.

It is like imagining a little person — a homunculus — in the machine that is listing to your instructions and following them literally. You the programmer have to imagine yourself in the position of the homunculus if you want to write effective programs.

Not everyone finds such feats of imagination easy. It is certainly often tedious to do so.

Popular posts from this blog

Concept Oriented Markup

I have long been frustrated with all the different text mark up languages and word processors that I have used. There are many reasons for this; but the biggest issue is that markups (including very powerful ones like TeX) are not targeted at the kind of stuff I write.

Nowadays, it seems archaic to still be thinking in terms of sections and chapters. The world is linked and that applies to the kind of technical writing that I do.

I believe that the issue is fundamental. A concept like "section" is inherently about the structure of a document. But, what I want to focus on are concepts like "example", "definition", and "function type".

A second problem is that, in a complex environment, the range of documentation that is available to an individual reader is actually composed of multiple sources. Javadoc exemplifies this: an individual library may be documented using Javadoc into a single HTML tree. However, most programmers require access to multiple…

Existential Types are the flip side of generics

Generic types, as can now be seen in all the major programming languages have a flip side that has yet to be widely appreciated: existential types.

Variables whose types are generic may not be modified within a generic function (or class): they can be kept in variables, they can be passed to other functions (provided they too have been supplied to the generic function), but other than that they are opaque. Again, when a generic function (or class) is used, then the actual type binding for the generic must be provided – although that type may also be generic, in which case the enclosing entity must also be generic.

Existential types are often motivated by modules. A module can be seen to be equivalent to a record with its included functions: except that modules also typically encapsulate types too. Abstract data types are a closely related topic that also naturally connect to existential types (there is an old but still very relevant and readable article on the topic Abstract types have …

Robotic Wisdom

It seems to me that one of the basic questions that haunt AI researchers is 'what have we missed?' Assuming that the goal of AI is to create intelligence with similar performance to natural intelligence; what are the key ingredients to such a capability?

There is an old saw
It takes 10,000 hours to master a skill
There is a lot of truth to that; it effectively amounts to 10 years of more-or-less full-time focus. This has been demonstrated for many fields of activity from learning an instrument, learning a language or learning to program.

But it does not take 10,000 hours to figure out if it is raining outside, and to decide to carry an umbrella. What is the difference?

One informal way of distinguishing the two forms of learning is to categorize one as `muscle memory' and the other as 'declarative memory'. Typically, skills take a lot of practice to acquire, whereas declarative learning is instant. Skills are more permanent too: you tend not to forget a skill; but it is…