Eric Normand Newsletter 468: Choice of abstraction matters

Reflections 🤔

Choice of abstraction matters

The purpose of abstracting is not to be vague, but to create a new semantic level in which one can be absolutely precise. -- Edsger Dijkstra

As usual, I've been thinking a lot about abstraction. While my book on the topic would be practical and skill-based, it's useful for me to explore the more abstract, theoretical ideas behind it. I think this is a safe place to do that.

I've rewatched a lecture by Dijkstra where he presents some river-crossing puzzles. One of the puzzles is the Wolf-Goat-Cabbage problem. You have a wolf, a goat, and a cabbage. You're trying to cross the river in a boat. Your boat is only big enough for you and one of your items. If you leave the wolf with the goat, the wolf will eat it. If you leave the goat with the cabbage, the goat will eat it. How do you get all three things across?

While you can easily do a case analysis to figure out the right move for every case (there are only 16 possible system states), Dijkstra introduces an abstraction that simplifies the problem. He shows that the wolf and the cabbage are equivalent in that neither can be alone with the goat. He calls both objects ɑ (and the two together ɑ^2). There are only 12 possible states with that abstraction since some concrete states map to the same abstract states. While it doesn't make the problem that much easier to solve, the point is clear: choice of abstraction does matter.

What Dijkstra doesn't talk about is how it relates to programming. Here's a problem when trying to program to this abstract form: If I know I need to move an ɑ, but I have to output my move in terms of "move cabbage" or "move wolf," how do I know which move is correct? I need to map ɑ back down to the concrete object to move. The operation needs to know what is on the current side of the river. It requires the current state. That need makes it much less convenient to write . It may even nullify the benefits of the abstraction.

Choosing an abstraction is only half of the job. The other half is encoding the abstract form into a convenient construct in your language. By convenient, I mean it has to be easy to write, read, and show the correctness of the operations. And it also has to be convenient (read: efficient) for the computer to execute the operations.

If I have :wolf, :goat, and :cabbage, I can easily represent the state as a set of zero or more of those keywords. If you count them, you'll see that there are 8 subsets. If I use :alpha and :goat, I can't keep two alphas in a set. Using a vector is inconvenient because searching it is hard, and also, order now matters ([:alpha :goat] vs. [:goat :alpha]). But I could use a map like {:alpha 2, :goat 1}. That does encode it, but am I opening up my system to errors where somehow I get {:alpha 3}? And what's the difference between {} and {:goat 0}? I need to be able to impose invariants.

I'm not trying to dismiss Dijkstra's abstraction. It's a brilliant example. Even though it's a puzzle, it captures a large part of what we do as programmers when deciding how to program a problem. Instead, I want to discover how to teach the skills this example reveals. How do we invent abstractions? How can we encode those abstract forms in code? How do the operations inform the encodings and influence the abstractions we choose?

Clojure Challenge 🤔

Last challenge

Issue 467 - Unfriendly neighors - Submissions

This week's challenge

Maxie and Minnie

The maxxie of a number n is the largest number you can achieve by swapping two of its digits (in decimal) (or choosing not to swap if it is already the largest possible). The minnie is the smallest with one swap (though you can't swap a zero digit into the most significant position).

Your task is to write a function that takes an integer and returns a tuple of the maxxie and minnie.

Examples

(swapmaxmin 213) ;=> [312, 123]
(swapmaxmin 12345) ;=> [52341, 12345] ;; the number was already the
smallest
(swapmaxmin 100) ;=> [100, 100] ;; no swap possible because of
zeroes

Notes

• Swap any two decimal digits
• No leading zeroes
• Don't swap if you can't make it bigger/smaller

Thanks to this site for the problem idea, where it is rated Expert in Ruby. The problem has been modified.

Please submit your solutions as comments on this gist.

Rock on!
Eric Normand