Learning to Program Without Writing the Usual Sort of Code

There's much anecdotal evidence, from teachers of beginning programming classes, that many people can't come to grips with how to program. Sticking points can be as fundamental as not being able to break a problem down into a series of statements executed one after another, or struggling with how variables are updated and have different values at different points in the program.

I don't think it's quite as straightforward as that, because there are real life analogs for both of these sticking points. Clearly you have to go into the restaurant before you can sit at the table, then you order, eat, pay the bill, and leave. Everyone gets that (and knows why you don't sit at the table before going to the restaurant). When you pay for the meal, the money you have is decreased, and it stays that way afterward. The difference with code is that it's much more fine-grained, much more particular, and it's not nearly so easy to think about.

If you think that I'm oversimplifying, here's a little problem for you to code up: Write a program that, given an unordered array, finds the second largest value.

(I'll wait for you to finish.)

You could loop through the array and see if each element is greater than Largest. If that's true, then set NextLargest to Largest, and Largest to the current element. Easy. Except that this doesn't work if you find a value smaller than Largest but greater than NextLargest. You need another check for that (did you get that right?). I'm not saying this is a hard problem, just a little tricky, and a hard one for beginners to think about. Even in the first, simple case you have to get the two assignments in the right order, or both variables end up with the same value.

Set aside that kind of programming for a bit, and let's look at other ways of solving the "second largest" problem. Remember, nowhere in the description does it say anything about performance, so that's not a concern.

Here's the easiest solution: Sort the array from largest to smallest and take the second element.

There's a little extra housekeeping for this to be completely correct (what if the length of the array is 1?), but the solution is still trivial to think about. It's two steps. No looping. No variables. Of course you don't write the sort function; that's assumed to exist.

If you're not buying the sort, here's another: Find the largest value in the array, remove it, then find the largest value in the updated array. This sounds like looping and comparisons (even though finding the largest element is an easier problem than the second largest), but think about it in terms of primitive operations that should already exist: (1) finding the largest value in an array, and (2) deleting a value from an array. You could adjust those so you're getting the index of the largest value and deleting the element at an index, but the naive version is perfectly fine.

What I'm getting at is that thinking about problems given a robust set of primitives to work with is significantly easier than the procedural coding needed to write those primitives in the first place. Yet introductions to programming are focused almost exclusively on the latter.

As much as I like functional programming, I don't think it gets this right. The primitives in most functional languages are based around maps and folds and zip-withs, all of which require writing small, anonymous functions as parameters. Now if a fold that adds up all the integers in an array is named "sum" (as in at least Haskell and Erlang), then that's a solid, non-abstract primitive to think about and work with.

Long-time readers will expect me to talk about array languages like J at this point, and I won't disappoint. The entire history of array languages has been about finding a robust and flexible set of primitives for manipulating data, especially lists of numbers. To be completely fair, J falls down in cases that don't fit that model, but it's a beautiful system for not writing code. Instead you interactively experiment with a large set of pre-written verbs (to use Ken Iverson's term).

J or not, this kind of working exclusively with primitives may be a good precursor to traditional programming.

(If you liked this, you might enjoy Explaining Functional Programming to Eight-Year-Olds.)

permalink November 21, 2016

previously