Complexity redux: Best Coding Practice

As a new year marches in, a young minimalist’s mind turns to complexity.  In interesting comments on this earlier post, Alex and Tim assured me that CS does not involve itself with the kinds of complexity concerns I outlined. I am not in a position to contest this (hopefully very soon those more expert in these matters will weigh in. Believe me I am encouraging them to do so). However, I thought that a brief Wikipedia check would be worthwhile and I think that I have found a branch of computation that thinks about similar issues in a similarly qualitative way.  It appears that there are few theorems in this domain of computational thinking, but there are many recommended “good practices” that have the right kind of minimalist flavor.  I want to review a couple of these and illustrate their oomph by elaborating on David Adger’s comment on the same earlier post.

Wikipedia has an interesting entry on best coding practices for software development.  The entry makes the following general pronouncement:

Best coding practices for software development can be broken into many levels based on the coding language, the platform, the target environment and so forth. Using best practices for a given situation greatly reduces the probability of introducing errors into your applications, regardless of which software development model is being used to create that application.

I like this little paragraph: note the indicated sensitivity to the details of the coding language, the platform and the target environment.  The interactions of all three are relevant if one’s aim is to “reduce the probability of introducing errors” into the desired applications, error reduction being a highly valued design feature.  Though this is not discussed, I assume that some designs are better than others for reasons other than error minimization, e.g. they run faster on this platform, they make important calculations easier etc.  Such concerns, if not identical, at least rhyme with the point I tried to make in the earlier post.  Here’s a tendentious translation from Minimalism into software-develomentalese: Relativized Minimality is a nice design feature for a “coding language” that represents dependencies on a “platform” endowed with a bounded content addressable memory. Or, Relativized Minimality is a Minimalist Best Practice given the general architectural features of human memory and attention.

The Wikipedia article goes on to expand on these “minimalist” themes. It vigorously urges keeping one’s code “simple.” It emphasizes that choosing a good code is intimately connected to “what the code block must perform.”  The entry admonishes the erstwhile developer that the choice of architecture is “key” and that “without a good design you are going to be sunk.” It further warns against falling “into the trap… of over-designing the application”. 

These injunctions are very suggestive if one’s goal is to reverse engineer a cognitive  “application,” say an FL for example. As in the case of developing new software, it’s a good idea to be cognizant of what the code is used to represent and what the platform that will use the code looks like. These kinds of local complexity issues matter a lot, at least in this computational, even though they generally invoke rules of thumb and best practice suggestions rather than general proofs.  Moreover, this is roughly what we should expect. Here’s why.

For a proof to be useful it needs to be general. Generality goes hand in hand with abstraction.  As noted before (see again Berwick and Weinberg 1982) proofs that deal with problem complexity are intended to hold regardless of the details of machine architecture, including type of memory, size of CPU, details of data storage etc.  But, if one is interested in why FL/UG looks as it does we don’t want to abstract from these details.  We are interested in how FL/UG fits with this particular machine (our brain/mind) with these particular interfaces and memory/attention architectures.  Thus, the kinds of proofs we often see in CS complexity theory will quite often be unenlightening.  Indeed, it is interesting that the Wikipedia post does not list a bunch of software development theorems to guide in construction of new applications. It deals in fuzzy rules of thumb and best practice suggestions.  And it is none the worse for that!  ‘Simple,’ ‘elegant,’ ‘complex,’ have meaning in specific contexts even if there are no general proofs.  Indeed, given what we know about general proofs and the abstractions required to get them, we should not expect them to be terrifically useful.  This should not be taken as a categorical statement, just an observation. However, even if there are no proofs, it does not mean that everything one says is poodle poop.  Best practice guidelines can be very useful and very enlightening, as much in theoretical syntax as in software engineering.

Ok, enough pulpit thumping.  Let’s consider a little illustration (details from here). Arabic (Hindu/Indian actually) numerals than Roman numerals. Tru’dat!  In fact, my Wikipedia browsings have taught me that when Roman numerals were the numera franca,  calculations were done by translating to an abacus-representation of the number, doing the calculation and then retranslating the result to the relevant roman numeral (we’ll see why in a moment).  A big advantage of the Hindu-Arabic system is that this is not required for it is straightforward to manipulate these numerals arithmetically, in fact easy enough to teach grade school children to do it proficiently.  At any rate, there is quite an interesting literature on numeral systems that is worth dipping into.  So let’s dip.

Numeral systems are evaluated on several dimensions. Here are three that the Wikipedia entry notes. We want systems that

1.        Represent a useful set of numbers (e.g. all integers, or rational numbers)

2.        Give every number represented a unique representation (or at least a standard representation)

3.         Reflect the algebraic and arithmetic structure of the numbers.

The system of Roman numerals does well enough with (1) and (2) but rather miserably with (3).  It also has another inelegance: a nice feature of numeral systems is if they represent bigger numbers as “longer” so that relative size is easy to detect.  On this criteria, ‘IV’ is a “bad” numeral given that it is bigger than ‘V’ though 4<5. 

Another useful property is that it be easy to use.  Tally systems are the most basic kind of numerals.  Each number being represented by a mark, e.g. ‘/’. Two on this system is ‘//’, five is ‘/////’. Note that bigger numbers are longer using this numeral notation, but when numbers get a little bigger it’s hard to tell them apart: ‘////////////’ vs ‘/////////////’. The problem here is that for humans this gets confusing very fast (likely because for creatures like us with memory/attention structures like ours, these are easily confused?). Which is bigger? They are even hard to count, let alone inspect for the answer. Here out system of numerals with ten distinctive digits works very well. But this is for us. Tally systems are perfectly ok and (apparently) they are still used in CS (something called ‘Elias gamma coding’). But for us, they get very confusing very fast. It’s easy to determine at a glance that the number represented by ‘13’ is bigger than the one represented by ’12.’  However, even for our numeral system, things can get hairy when the numbers get very large: 1000000000000 vs 10000000000000. To address these problems we start putting in commas, or more perspicuously still, we code things with superscripts: 10¹² vs 10¹³.

The system we use has another virtue: it makes everyday arithmetic calculations pretty easy. It is a “positional” or “place value” notation, “where the position of the digit is used to signify the power of 10 that the digit is to be multiplied with, as in 304=3x10², 0x10¹ and 4x10⁰. Here ‘0’ becomes very important. It makes using the system a whole lot easier. Ineed, one (e.g. moi) is tempted to say that it increases to efficiency of the positional numeral system. Historically, introducing ‘0’ was a real big deal and if you look at what ‘304’ means you can see why (hint: look at the 10¹ place). At any rate, arithmetical calculations are easily done here as what you learn to do in the 10⁰ place applies again and again from right to left.  The Addition, multiplication, etc. algorithms that are used to compute the value in the 10⁰ place is the same as that in the 10ⁿ place.  The Romans (in a sense) knew this as that’s the way an abacus works, it’s essentially a positional machine. So because Roman numerals are not positional systems, calculation bypassed them by translating their values into abacus notation (which is essentially positional) and after the calculating was done the answer was retranslated into Roman numeral terms.  Some might be tempted to say (moi again) that cutting out the translations from Roman to Abacus and back to Roman made the calculation simpler/less complex and that in a non-trivial sense positional numerical systems are more efficient with respect to these kinds of calculations than are Roman numerals.

Let’s take one more step.  Our system is a base 10 system, the positions representing different powers of 10.  We find these pretty easy to use (can anyone guess what the standard speculation as to why this is? Hint: ‘digits’).  But they are no better than other positional systems and they are not, for example, the system of choice for electronic computers.  Here, as we all know from grade school, the favored base is 2. Why? Well because numbers can then be represented as series of on/off switches.  Electrically based systems easily discriminate on and off.  Current flowing or not.  Base 2 is well suited to a digital computer.  The platform makes a big difference: humans base 10, computers base 2.  Interestingly, we can have our cake and eat it by doing what the Romans did: translate base 10 numerals to base 2, have our silicon friends very very quickly calculate in base 2 and then translate this back into base 10 notation.  The “right” numeral notation cares about the physical characteristics of the user (carbon-human-10, silicon-computer-2).

These cursory considerations concerning different numeral systems invoke many of the design issues we mentioned above. Different numerical codings of the numbers come with different virtues. However, they are not virtues tout court. They are virtues only when considered from the perspective of the “platform” that uses them (10 fingered, low discrimination for frequent repetition) and the “algorithms” they run with them (e.g. arithmetical operations).  When these are considered it is pretty clear that some codings are superior to others in these contexts.  They fit better with the “interfaces,” play more nicely with the different “architectures” and are more congenial to different “algorithms.”  On a case by case basis, the superiority is obvious and it is these kinds of notions of complexity, efficiency and optimal design that Minimalists should be trying to flesh out for FL/UG. This may not be complexity as CS departments understand it, but it is an interesting, viable and linguistically useful notion nonetheless.

Oh yes: Happy New Year!