More rambling

I'm going somewhere with this, I swear.

Primitive ontological abstraction gives us some objects we can play with, but it would be nice to be able to talk about them. Nominal abstraction allows us to assign a name to an object and to use the name to refer to the object. It's such a natural thing to do that you hardly notice it being done, but it is a tremendous source of power as well as confusion. I'm not going to explore this further right now.

So we have objects and names, and at this point we can construct a primitive programming language about on the level of assembly code. It isn't much, but it's better than toggle switches and hex codes. We need a few more abstractions. We'll need relational abstractions of some sort. I don't mean something as formal and heavyweight as a database relation, I mean some means of talking about two objects and how they relate to each other. An example would be a number and an array, and I might want to `put the number in the array'. And we'll want a way to refer to a quality that might be shared among several objects.

Now there are several ways we could go from here, but I was doing a bunch of thinking about procedural abstraction. (I was trying to figure out what sort of abstractions you needed in order to even make sense of procedural abstraction and I came up with the ones I just mentioned.) Procedural abstraction in some sense gives you the verbs you need in order to accomplish something with the objects. You don't strictly need them — very early computers didn't support subroutines, and there are a handful of computer languages that don't have the notion of a procedure. But the large majority of computer languages have a way of creating procedures (or methods, subroutines, functions, whatever you want to name them). Why is this?

One reason is that a function is a very well developed mathematical construct. Hundreds of years of thought have gone into formalizing what a function is. Another reason is that every theory of computability has ended up with modeling programs as the set of partial recursive functions. The final reason is that functions and procedures make extremely good abstraction barriers. A mathematical function is a perfect ‘black box’. It is characterized purely by the pairing up of what goes in and what comes out. Two mathematical functions are different if and only if there is an input-output pair for one that doesn't exist on the other. To a large extent, two computer programs are different if and only if there exists an input that produces different outcomes depending on the program. (There are caveats. Bubble sort and merge sort produce identical results, but whether we considered them the ‘same’ would depend on whether performance and resource use were taken into account.)