Eric Normand Newsletter 467: Koppel's abstractions

Reflections 🤔

Koppel's abstractions

After publishing Issue 465, three different people asked me whether I had read an article by James Koppel on abstraction. Ironically, I did link to that article from within the essay. I had recently read it, and it inspired my piece. In this issue, thanks to the prompting of my readers, I want to address the essay's ideas directly. I want to focus on the ideas and not the delivery.

Koppel is right: The term abstraction is used inconsistently in the programming world. People use it in many different, often contradictory ways. A good definition should clarify, not confuse. I've been looking for a clarifying explanation of abstraction because it is one of the core skills in programming. Koppel's definition of abstraction is just what I wanted.

I've documented some meanings of abstraction that I like here:

I have found two definitions of abstraction that are precise enough to be useful:

  1. To name a thing so that you can refer to it later. (From SICP)
  2. To treat different things as if they were the same. (From Barbara Liskov)

Koppel uses a definition from Programming Language Theory (PLT): An abstraction is a mapping from a complex "concrete domain" to a simpler "abstract domain." In other words, we represent concrete things with abstract things (this is the mapping) to ignore unnecessary details and be more precise.

I like this definition because it captures the essence of what programmers do while connecting it to a broader field of study (math, etc.). I think Liskov was attempting to get at this same thing. However, phrasing it as a mapping (an actual operation) is more direct than the vague "treat things the same." "Treating different things the same" means mapping different things to the same abstract representation. I would replace definition #2 with Koppel's PLT definition.

I also appreciate that Koppel expounds on three different qualities of abstraction, namely soundness, precision, and size. We should separate the acts of identifying and creating abstractions from judging how good they are. We want to say, "that's an abstraction, and it's a bad one." Soundness means your mapping doesn't lose anything. Precision means your operations are still possible. Size is how many bits it takes. I want to explore these ideas in future issues.

I can't entirely agree with Koppel when he insists that the abstractions are not in the code. Indeed, neither the functions nor the classes that act on abstract representations are the abstractions themselves. However, we do build many mappings in software. It is a typical pattern to "lift" a value into a new representation where the problem is easier to solve, then "lower" it back into its original form. The lift and lower functions implement the bi-directional mapping that is the abstraction. We write these all the time in advanced functional programming. In the more extreme cases, we build an entire semantics and write a function to interpret something into that semantics. This function is known as an interpreter. I think this use of first-class abstractions needs exploration (or explaining why I am wrong).

Koppel explains a good definition of abstraction. It is valuable and precise. And it allows one to talk about abstractions that aren't good and explore why. Further, the definition has catalyzed new ideas for me. I hope to explore them here. One idea is that of writing the mappings as functions in your program. Another is a way to make the notions of soundness and precision practical as skills. If this idea is as powerful as it seems, why hasn't it caught on in the industry? I hope you can follow along as I develop these threads.

Programming Media 🍿

Explorations into modularity and abstraction? Yes, please! That's why I love listening to Barbara Liskov. Here is her 2007 ACM Turing Award Lecture.

Clojure Challenge 🤔

Last challenge

Issue 466 - Custom sort order - Submissions

This week's challenge

Unfriendly neighors

Let's say we have a sequence of integers:

[1 3 2 4 1]

There are 4 spots between numbers where we could insert a new number (represented by commas):

[1 ,, 3 ,, 2 ,, 4 ,, 1]
;; ^    ^    ^    ^
;; |    |    |    spot 3.5, between 3 and
;; |    |    spot 2.5, between 2 and 3
;; |    spot 1.5, between 1 and 2
;; spot 0.5, between 0 and 1

We can represent those spots as halves, such as 0.5.

We only want to insert numbers when they are "happy". Odd numbers are happy when we insert them next to at least one odd number. Even numbers are happy when we insert them next to at least one even number.

Write a function that takes a sequence of integers and an integer. It should return the happy spots and the unhappy spots.

(spots [1 1]     1) ;=> {:happy [0.5]                   }
(spots [1 1]     2) ;=> {                 :unhappy [0.5]}
(spots [1 1 2]   4) ;=> {:happy [1.5]     :unhappy [0.5]}
(spots [1 1 2 2] 3) ;=> {:happy [0.5 1.5] :unhappy [2.5]}

Note: Inserting a number may make pre-existing numbers unhappy. Ignore them!

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

Please submit your solutions as comments on this gist.

Rock on!
Eric Normand