On Complexity: The So-Called Irreducible Evil

Modern software systems are veritable Ruby Goldberg contraptions.  Layers upon layers upon layers of code, libraries, and frameworks, thousands of modules, components, and containers, all working in an impressive orchestrated symphony of... mostly delivering trivial things like "take my credit card" or "here's another picture of a cute cat".

The jarring disconnect between ever-increasing complexity of hidden technological plumbing and the mundanity of what that plumbing does for the users begs the $64 trillion question: where all that complexity comes from and can something be done to control it?

Back in 1986 Fred Brooks in his classic No Silver Bullet introduced the notions of essential and accidental complexity arguing that essential complexity - i.e. complexity inherent in the nature of the problem being solved itself - is irreducible while accidental complexity can be reduced with better and more careful design.   On it's own, this statement is nearly tautological (a careful reader may note that the very definition of "essential" implied in the distinction is circular - what we cannot reduce must be essential).

Like many novel takes in the computer science, this one got its cult following with the cultish aspect of embracing the argument is overinterpretation it to mean simply that complexity is irreducible and can only be moved from one place to another. This implies that modern software tooling already eliminated most accidental complexity by providing programmers with abstracted building blocks.

This view is the starting point of the rather insightful essay by Ivan Turkovic: Complexity Is Never Eliminated. It Is Only Relocated.

This view is also simply wrong.

Firstly, this treats complexity as a single large lump, whereby in reality a large system composed of multiple well-delineated and conceptually simple modules is much easier to expand, debug, and maintain than a monolithic bezoar, even if combined code size is the same.  Modularization is the mainstay of engineering.

The general error of considering complexity as an objective metric is in the fact that human ability to understand complex concepts is severely limited.  It is not complexity defined in some way mathematically which matters: what matters is human ability to gain useful understanding of the concepts and implementation.  This ability declines sharply and non-linearly with growing size of the module.

There is a useful definition of essential (objective) complexity which is not circular: it is called Kolmogorov complexity (aka algorithmic complexity) defined simply as the length of the shortest program of all programs equivalent to one being analyzed. As any mathematical abstraction, this is only good for dealing with spherical cows in vacuum.  The real-world program quality cannot be reduced only to size of the code, and other criteria (such as speed of execution, memory required, fault tolerance, etc, etc) are more important.  This means that essential complexity is not limited to the code itself - it depends on the computer and the performance requirements.

This said, Kolmogorov complexity still offers some insight on the nature of essential complexity in real-life systems: you can see reducing accidental complexity as an optimization problem.  However a procedure for finding algorithmic complexity in general is uncomputable.   This means that it is impossible (in general case) to determine how much of our program's complexity is accidental and how much is irreducibly essential, and even trying all possible programs up to the length of the one we are trying to analyze on all possible inputs won't give us an answer.

Another interesting feature of algorithmic complexity is its subadditivity: algorithmic complexity of a combination of two programs does not exceed the sum of complexities of these programs alone. (Informally, this is easy to understand by observing that optimizing two programs together can eliminate redundancies like code common between these programs.)  This means that essential complexity of a monolithic program is not larger (and usually less) than essential complexity of a modularized program - which flies completely in face of the actual engineering experience.

Therefore this artificial division between essential and accidental complexity is rather useless as a guide to understanding the complexity of real-life software systems.  What we need to consider instead is perceived complexity which is objective complexity of some sort adjusted by non-linear and rapidly increasing to infinity function which quantifies amount of effort needed to comprehend a program with given objective complexity (let's call it a cognitive effort function CE(oc)).

A perceived complexity of a program decomposed into modules will be

     PC = sum(CE(oc_i)) + CE(oc_glue)

where oc_i is objective complexity of module i and oc_glue is objective complexity of glue code combining the modules.   Note that this definition can be used recursively if we decompose modules even further.

This approach matches reality much better: a program of objective complexity in the region where CE is rapidly raising (or infinite - i.e. beyond human capacity to comprehend) when decomposed into simpler modules will have much lower PC.  That said, slicing it too much increases complexity of glue, so there is an optimal size of the modules.  A good decomposition also reduces cross-dependencies and links between modules thus simplifying the glue.

To paraphrase: good architecture decreases perceived complexity.  This is not new and has been a generally accepted engineering principle for a century now.

The second problem with the idea of somehow irreducible complexity is duplication.  You cannot reduce complexity only if your program does not need to use same functionality in more than one place.  If it can, you can abstract that functionality into a procedure or module, thus eliminating the complexity of duplicating parts of code at the cost of adding complexity of abstracting.

The elephant in the room, however, is duplication across different programs.  The reason why libraries and compilers are so effective in reducing perceived complexity of the systems is because they eliminate duplication of cognitive effort.  The burden of complexity of development tool chain is amortized across all users of that tool chain.  Given the large population of programmers, the cost of complexity of a compiler to a developer is rather minimal (and comes mostly as the cost of learning how to use the tool chain).

Thus, the diagnosis of the complexity issue as inability to eliminate the essential complexity is wrong, and so is the contention that software tools now successfully control accidental complexity down to manageable levels.

While we have some notable successes (such as use of high-level languages and reuse of libraries), the actual programs are still full of boilerplate and repetitive (maybe with some variations) code.  It gets even worse across different software projects - it seems that every project reimplements the same set of functions not provided by the technology stack of the day.

The low level of reuse results from the phenomenon of abstraction level ceiling as we discussed here.

The rest of the Ivan Turkovic's essay is right on the spot.  The real reason why we do not see much of programming productivity increase with the use of LLMs to generate code is that LLMs do not (and cannot) increase the abstraction level.  They generate code (which still needs to be reviewed by humans)  at the same level of abstraction as the traditional development tool chains.  LLMs do not reduce cognitive load - you still need to understand what the code it generated does simply because LLMs are by their very nature probabilistic - they are statistical predictors, not logical machines - and will generate buggy code no matter what.

LLMs are not a silver bullet.  Νέμεσις is undefeated (and not even fazed much).

And if we look at the software industry as a whole, wide adoption of LLMs will simply increase overall complexity with randomly varied repetitions of the same patterns - generated at industrial scale, and with very lax supervision.  Prepare for the brown wave of even shittier software, folks.

The Teetering Towers of Abstraction

Here's another take on the issue of innate differences between mathematical and engineering abstractions (which we discussed before): The Teetering Towers of Abstraction by Brian Hayes.

No Silver Bullet

I will leave this rather prescient essay (from 1986!) without comment:

http://worrydream.com/refs/Brooks-NoSilverBullet.pdf

Generic Programming, a half-step forward

The key to the continuing popularity of C++ (the decidedly ugly, complex, dangerous, and hard-to-learn programming language) is its support for generic programming in the core language and the generic libraries available to C++ programmers (such as Standard Template Library (STL) and Boost).  The ability to use existing and define new generic templates saves programmers quite a lot of time and effort (a practical example is an execution platform of a database engine which needs efficient implementation of operators for all kinds of types of values such as numbers of various precision: writing these without templates would result in close to million lines of code, with templatized version being just tens of thousands LOC).

Conceptually, generic programming is quite simple: instead of requiring specific types of function parameters and the type of its result, it allows the types to be left unspecified, so that when this generic function is used the types of specific parameter values are inserted at compile time and the machine code for this specific combination of types of parameters is generated (this process is known as instantiation of the function template).  The second part of generic programming is allowing the compound types (i.e. arrays, structures, or classes) to be similarly parametrized, so a whole family of similar types differing only by types of its members could be created on as-needed basis (this also serves to parametrize methods (aka member functions) of templatized classes).

This is all very useful, but what makes generic programming interesting is that it does not rely on type theory (which is problematic as foundation for practical programming, as we discussed before), the fact explicitly acknowledged by the creator of STL, Alexander Stepanov:  "Generic programming... gets its inspiration from Knuth and not from type theory."  The basic mathematical theories which became the foundation for STL (and generic programming as we know it) are abstract algebra (particularly group theory) and number theory (I would highly recommend the book by A.Stepanov and D.Rose From Mathematics to Generic Programming for the in-depth discussion).

This said, generic programming as implemented in C++ is still terribly flawed (other languages such as Java, Ada, Eiffel, ML, D, and others offer severely limited variants or near clones of C++ support for generic programming).  As it is it fails to fulfill its objective of hiding inner workings of abstract generic algorithms even in trivial cases, as is illustrated in the following example:

Let's say we have two integer values and want to have a generic function which divides one value by another.  C++ code would be:

template <typename T>
T divide(T x, T y)
{
   return x / y;
}

Sounds simple, right?  However,  divide(3, 2) returns 1, while divide(3., 2.) returns 1.5.  It is easy to understand why is it so in this simple example, but the point is: you cannot even write a simple generic numeric division consisting of a single operation within which would produce consistent results for numerically equal inputs!

Now, we could write something like

template <typename T>
double divide(T x, T y)
{
   return double(x) / double(y);
}

This kind of works for both integers and floating point numbers, but now it fails to be "generic" for anything else (for example if T is a representation of a polynomial function or a complex number).

You cannot just assume that "divide" divides, you have to look inside the implementation to understand its properties.  The abstraction is no longer usefully abstract.

Now, since this kind of nonsense is annoying and actively dangerous and defeats the purpose of having generic programming capabilities in the first place, the practical language added a bunch of workarounds.  For example, we could address the issue above by using template specialization:

template <typename T>
T divide(T x, T y)
{
   return x / y;
} 

template <>
double divide<long>(long x, long y)
{
   return double(x) / double(y);
}

This seems to be better (though now we have two replicas of the "generic" algorithm) - though it still fails miserably on unsigned integers and "long long" integers.  The problem with full or partial template specializations is that they need matching to specific types, and there could be many of them (this problem gets especially annoying when arguments have independent types... we end up with combinatorial explosion of specialized variants if we want to write a generic function which is reliably correct).  We also cannot reliably support types we're going to create in the future.

Finally, the modern variants of C++ (which grow ever more and more complicated) provide something called type traits which, combined with a happy accident of C++ template semantics called SFINAE allows to arrive to a horribly hacky but kind-of-correct implementation of "divide":

#include <type_traits>

template <typename T>
std::enable_if<!std::is_integral<T>::value, T>::type divide(T x, T y)
{
   return x / y;
} 

template <typename T> 
std::enable_if<std::is_integral<T>::value, double>::type divide(T x, T y)
{
   return double(x) / double(y);
}

This still subtly fails for long long arguments (owing to loss of precision in cast to double) and does not handle arguments of different types, but this is enough to demonstrate the frustrating nature of writing generic code in C++.  And this is an example of only one of the "gotchas", examples like the one above are dime a dozen.

The interesting question is why this situation is so bad. To answer it we need to take a look at the mathematical foundation of the generic programming: the abstract algebra.  The most fundamental concept in abstract algebra is homomorphism: mapping between two algebraic structures such that all formulae from one structure will be just as true in another structure if we replace all elements from the first structure with corresponding elements from the second structure (the map establishes the correspondence).  The notion of homomorphism essentially is the same as the notion of mathematical abstraction (which is not the same as operation of abstraction in λ-calculus).

Thus, when we see an operation in algebra (such as operation of division in the example above) we expect that it will behave the same way in all algebraic structures homomorphic to the one we consider.  Unfortunately for an aspiring C++ template programmer the elementary, baked-in, operation of the language doesn't work this way! Real numbers form a division ring while integers don't (rational numbers do), they are not homomorphic, and our best bet is to treat integers as a subring of real or rational numbers (but not an ideal of the division ring).  I.e. we'd want integer division to produce rational (or real if rationals are not supported) result, and have the "integer division" to be a separate operation complementary to remainder operation, so that if d=⌊a/b⌋ and r=a%b then a=d*b+r (this would work for both integer and real a and b!).

This is just one example of how underlying basic language (in this case C++ without templates) is not homomorphism-safe, which makes abstract algebraic features such as generic templates on top of it awkward and hard to construct.

This point also happens to illustrate another deficiency of C++: while type traits are supported (to a some extent) there is no way to discover operator or function traits, and thus no way to check for them in a generic code.

However, all these details are minor annoyances compared to the real elephant in the C++ shop: template instantiation is controlled solely by the local information.  There is absolutely no way to create conditions for selecting specialized templates based on how the object of the given generic type is used in all its invocations: i.e. it is impossible to write a template which would implement a collection of objects differently depending on which access and modification operations are used! This impossibility is the result of the insistence on separate compilation - something which made a lot of sense back when computers had small RAM and slow CPU, so that compiler couldn't process a big program at once.  This insistence becomes ridiculous in the age of CPUs with dozens of cores and terabytes of DRAM.

And, of course, there is no way to communicate information about side effects.  The abstraction level ceiling is still firmly in place with C++-style generic programming, just moved a little bit higher.

C++ style generic programming is definitely a step in the right direction, but it falls far from the goal of achieving true generic programming capabilities, something Alexander Stepanov candidly acknowledged:  [Generic programming's] goal is the incremental construction of systematic catalogs of useful, efficient and abstract algorithms and data structures. Such an undertaking is still a dream.

It seems likely that this dream is similar to the dream of free flight before invention of flight control by means of changing wing geometry - and before internal combustion engines became light and powerful enough.  We have powerful engines now, let's see if we can add the correct set of controls to the process of compilation.

How life is doing it

The biological life on Earth is astonishing.  It's full of living organisms of incredible complexity and robustness (just some numbers: on average a human body contains 30 trillion cells (gut flora adds 40T cells more), 86 billion of which are neurons forming 150 trillion connections; besides humans there is estimated 1 trillion species currently living on Earth, not counting not-exactly-living things like virii).  The living organisms are constantly defending themselves from both directed attacks (by pathogens, predators, and such) and impressive levels of damage caused by environmental factors and by-products of biochemical machinery.

What is truly impressive is that all that panoply is encoded in essentially the same programming language, aka DNA/RNA code. Even more impressive is that this programming language is both very low-level (it is basically a biochemical machine code) and very compact: a full human genome contains about 3.08 billion base pairs (each encoding 2 bits, or 717 MiB total - yes, it fits on a CD-ROM!).  Of that only 2% of human DNA actually encodes proteins, the rest is non-coding DNA which is about half junk (such as remnants of retrovirii and transposons).  Other ncDNA usually has some biological function, mostly as modifiers to expression of coding regions, but the information density in non-coding regions is not large: genetic code of multi-cellular organisms compresses by about 75% by the lossless compressors (and by 99% by lossy probabilistic compressors such as GReEn).

Back-of-envelope estimate of the useful information content of human DNA would be about 20-25 MiB, and the total number of human genes is about 20000, at about 1KiB on average per gene. Conventional computer programming languages like C++ average about 30 bytes per line of code, so that would be equivalent to about 700-800 KLOCs, something a smallish group of programmers can write in a few years.  And that relatively small amount of code is sufficient to encode not only a versatile organism which is well-equipped for both obtaining and digesting wide variety of foods, defending itself from nearly infinite variety of pathogens, parasites, and predators, but also has general intelligence sufficient to sustain the secondary memetic evolution.

Impressive, isn't it?  There are certainly lessons to be learned from Mother Nature.

Now, just to get it out up front, there are significant differences between solid-state semiconductor and water-based biochemical computers.   The most important is the degree of physical randomness inherent in the operation of circuits vs signal transduction pathways.  The machines are designed to have very low error rates in their signal circuits, while molecular interactions in biology are driven by mechanical collisions of rather floppy protein molecules pushed around by Brownian motion of water molecules.  A degree of reliability in biological signal transduction is achieved mostly by averaging over huge numbers of molecules involved (the averaging is impossible when relevant molecules are singular per cell (such as DNA in chromosomes) - the evolution created rather elaborate error correction and repair mechanisms for these).  If anything, this makes programming biochemical machinery much more challenging.

The structure of biological programs is also very different: they are the products of evolution, and the outputs of evolutionary algorithms are notoriously incomprehensible, noisy, and unstructured. Everything designed by humans is much more structured and hierarchial by necessity, owing to the limitations of human cognition which we discussed before.  That said, it is well known that it is quite possible to write functionally identical programs in a variety of styles from "clean" and easy to understand to "hacky" and obfuscated; so we could hope that architectural lessons from evolved systems could be transferred to designed systems, stylistic differences notwithstanding.

So, how does life do it?  (We will only look at multicellular eucaryotes just to avoid the discussion of differences between these and other taxa).

The first observation is that biological programs do not provide exact plans for the organisms they encode.  Instead they are generative: they provide a set of rules (encoded in signal transduction pathways) which tell cells how to specialize and migrate to the correct places after dividing.  This process starts after the first division of a zygote into blastomere cells and uses various chemical gradients as a kind of coordinate system during early embryonic development, followed by use of paracrine and juxstacrine inter-cell signaling to guide the detailed development of organs.

The lesson here is that to implement functional generative system one needs a way to propagate information about "what" and "where" between the components being generated.  Just specifying the interfaces is not enough.  The process of generation is not one-shot, but rather iterative, with increasing degrees of differentiation (or decrease of cell potency levels in biological lingo).

The process of generating an organism also involves a lot of programmed cell deaths - apoptosis. The closest equivalent in computer programming would be dead code elimination combined with other optimization techniques.  The take-away here is that it is a very good idea to perform optimization as integral part of generation, interleaving optimization with specialization.

A significant portion of genes encode the components for the basic biochemical machinery necessary for the individual cells to function, this machinery is basically the same for all plants and animals; a (possibly hyperbolic) claim by Prof. Steve Jones is that humans and bananas have 50% of their genes in common.  These common genes are important because their breakage usually results in unviable or seriously crippled organisms, and so changes in these genes are strongly selected against.  The closest analog in computer programming is low-level libraries (libc and such) - a small change in semantics or interfaces of functions provided by these libraries (for example swapping source and destination arguments of strcpy is likely to break pretty much every program in an operating system).

The genes encoding higher-order features (such as additional signal transduction pathways and receptors) which generate complex body plans during development and are necessary for operating complex organs are much more variant between species.  Another trend is increased role of regulation of gene expression in more complex species - i.e. proteins are increasingly "standardized" while controls which affect production rate of specific proteins depending on environment and internal state of the cell grow in importance.

These observations certainly match what we see in the software: the low-level libraries quickly ossify, and any change in them has to be very carefully considered.  The higher-level functions are more mutable, and a successful software product often sees quite a lot of changes there.  What is missing in software is an equivalent of the expression regulation (there are some crude techniques which could be used to get some of that in computer code - we will discuss generic programming in the next post).   What biology has and computer programming has not is the way to control the use of basic blocks in complex ways, depending on the local environment and interactions of the block with other blocks.

Another interesting aspect of generating a functioning cellular machinery from genes is how much the information from the genes gets transformed during the gene expression (by necessity, the outline here is significantly simplified).  First, the expression of different parts of DNA is promoted or repressed by a variety of mechanisms: the fact that the gene is here doesn't mean it's going to be expressed at all!  These mechanisms are controlled by intracellular signals through signal transduction pathways.  The result of DNA transcription is short-ish RNA strands, containing a copy of information from the transcribed parts of DNA.

The second step is RNA processing, which sees the RNA strands being modified. The most important of these modification is splicing which generally removes parts of the genes (known as introns) and discards them and then joins the remaining parts (aka exons) into an edited whole.   The interesting part is that RNA splicing is not necessarily fixed, and different alternate parts of RNA could be excised during splicing thus producing different proteins in the end (this is known as alternative splicing).  Just like transcription, the process of splicing can be controlled by biochemical signals.

The resulting RNA needs to be transported from the nucleus to the proper place in the cell;  this process can be controlled by tags specifying the destination present on the RNA.

The next major step is translation, which reads the linear genetic code from mRNA and builds a linear chain of amino acids (the 64-entry translation table is fixed) by reading groups of 3 RNA bases (codons) to select the proper amino acid to be attached to the end of the chain.   The resulting proteins are still non-functional, because the function of a protein depends on the way it is folded into a three-dimensional blob.  This process (called protein folding) is driven by the chain seeking a local minimum in its energy; however an energy landscape is non-trivial and to help the proteins to find the right minimum (and thus fold in a proper way) the external help is often needed, this help is provided by specialized proteins called chaperones.  The abundance of chaperone proteins may control the rate of production of functional proteins (and the abundance of chaperones can be in turn controlled by environmental factors; for example many chaperones are classified as heat shock proteins which are produced by cells in response to stressful conditions).

The number of possible configurations of even modestly-sized amino acid chains is astronomical, so no full search for the energetically optimal configurations is possible as it would take longer than the age of the Universe - while in reality it happens in micro or milliseconds (this is known as Levinthal's paradox).  Note how similar is this to the search in very high-dimensional spaces commonly used in the modern machine learning;  while the ML practitioners can try a large variety of heuristic optimization algorithms, the protein sequences are selected by the evolution so that their energy landscapes form funnels quickly guiding the folding to the desired outcome (see Anfinsen's dogma).

Finally, the proteins need to be transported to their proper places via protein transport  and translocation directed by signal peptides tacked to the N-terminus of amino acid chains.  This process can be modified through a variety of mechanisms chemically altering the signal peptide.

The main lesson here is that the end product of gene expression (the functional protein located at a proper place in the cell) is vastly different from the original gene, and the "code" for the proteins is a subject of significant transformation.  The multi-stage expression process is controlled or influenced by a panoply of biochemical signals coming off the complex signal transduction pathways.  The process is controlled and modified by external signals at all stages (however, it appears that the most controls are at the earliest stage).   Some parts of the expression process are computationally intensive, and so the "design" by evolution favored structures which are amenable to simple simulated-annealing like search.

So far, the mechanisms described above are sufficient for building an organism which can grow from a single cell and have some fixed instinctive behaviors and react to environmental circumstances in a "pre-programmed" manner. However, in a real life each organism is also forced to defend itself from a nearly infinite variety of pathogens.  Because the pathogens are extraneous to the organisms (and most of them can mutate and evolve quickly) there is no way to pre-program effective defenses against most of them (the generic innate immunity defenses such as inflammation can only go so far). The organism needs to somehow learn what pathogens are attacking it, and learn how to recognize them (or cells infected by them) efficiently.  This is done by an ingenuous mechanism called adaptive immune system.

The adaptive immunity needs some way to create biochemical sensors (receptors) which have very high specificity to particular species or strains of pathogens - at a molecular level (i.e. inaccessible to neural learning).  These sensors are known as antibodies, and basically are Y-shaped protein complexes which may have a nearly infinite variety of mechanical configurations at their antigen-binding sites.  In effect, these act like locks "opened" by molecules specific to pathogens (similar to malware signatures in computer anti-virus software).  The challenge is how to produce this variety from a rather small number of genes, and how to keep only those antibodies which are effective.

The high variety of antibodies is generated by the genetic mechanism called V(D)J recombination of genes encoding immunoglobulins.  The parts of these genes are randomly permuted and excised within individual somatic cells (additional randomness is thrown in by the abnormally high mutation rates at some parts of these genes, a phenomenon known as somatic hypermutation).  This creates a population of functionally similar cells (such as T-lymphocytes) which secrete variety of antibodies. The population of these cells is pruned against "self" antigens in thymus, thus ensuring that the immune system doesn't attack the organism itself.  Then the T-lymphocytes which encountered the antigens they recognize activate (and proliferate) while those which are dormant die (so this works is an evolution inside the individual organism, a process known as clonal selection).  After the infection is cleared, some T cells with the antibodies recognizing the pathogen remain, to speed up immune response, a phenomenon we know as acquired immunity.

So here we have yet another lesson: if the system needs to adapt to unpredictable requirements, it may make sense to generate parts of it randomly, and select the best combination.

Surprisingly, quite a lot of how life works has analogies in how software tool chains work. Optimizing compilers certainly perform non-trivial code transformations, etc.  The major difference is that biological "programs" are mostly not descriptions of what to build, but rather descriptions of how to build.  These descriptions make use of complex controls on expression of genes and subsequent transformations. The cells (which start with the same genome) are driven to specialize to fit the specific needs.  The detailed plan of the organism is not something fixed by the "programmer" but rather a result of code generators (stem cells) reacting to both outside stimuli and relations to other generators.   The transformation from code in genes to the actual "implementation" involves search in huge multidimensional landscapes, and sometimes use randomness and evolutionary algorithm to find the needed solution.   The most striking aspect of biology is that there just isn't any clear-cut "universal" method for generating organisms from their genetic descriptions (nothing like use of β-reduction for abstraction unwrapping in programming), and that huge diversity of domain-specific methods is used to solve specific problems.

The tools we use for creating software are much more restrictive, possibly due to the misguided pursuit of "cleanliness", and emphasis on precise control of the resulting machine code.  There are some relatively recent advances in the direction of generative programming (notably generic programming in C++), but these fall way short of what is needed for releasing programmers from the tyranny of details.  (Generic programming and its limitations will be the topic of the next post).

The Spherical Cow in Vacuum, Part 2 - Type Theory

By the beginning of 20th century mathematicians found that they have a yuuge problem: the attempt to rigorously formulate the fundamentals of mathematics failed miserably.  The very concept of sets (in the so-called naive set theory) was found to be self-contradictory, as is demonstrated by Bertrand Russel's paradox.  The problem comes from the way sets were defined: as collections of objects satisfying some conditions (usually using set builder notation), and these conditions could be self-referential to the set being defined. Obviously, the way the concept of sets was defined needed some change to make it more restrictive in order to avoid variants of Russel's and other paradoxes.

One (but not the only one) approach was to coerce mathematical objects into hierarchies (i.e. we may have boojums, set of boojums, set of sets of boojums, set of pairs of boojums, etc) thus preventing self-referentiality.  The mathematical formulation of this became known as type theory.

The type theory turned out to be a nice fit for λ-calculus; and so it was only natural to design programming languages to incorporate it as the basic programming concept: something we now call "records", "objects", "struct-s", or "classes".  (The more modern object-oriented formulations also throw in some syntactic sugar in form of member methods).

It is important to understand that the purpose of type theory is to eliminate paradoxes arising when we're overly clever with the way we specify predicates in our set builders.  The use of the notion of types along the lines of type theory has nothing do with that:  when writing programs we are not at all concerned with correctness of all possible programs (i.e. that all programs produce a result instead of some of them looping indefinitely).

We cannot even say that the types we use in programming are not self-referential: there are common use cases when we have to have circular dependencies between types.  That's why we have forward declarations.

So why the type-theoretical view of types is being used so widely in the practical programming?

For one, the constructive notion of types (when we construct higher-level types from collections of elements of lower-level types) is quite easy to learn and understand, and is quite intuitive.  Secondly, the conventional type systems do offer some degree of information hiding and abstraction.   And last (and in the author's opinion not least) is horrible inertia:  the choice of the the readily available mathematical concept was quite reasonable when the computing pioneers were inventing first programming languages.  Since then the short-comings of that choice became painfully obvious, to the point that some programming language designers have chosen to dismiss the whole idea of static typing completely, notably in the so-called scripting languages which recently became the most popular kind of programming languages. (This was facilitated by the tremendous growth of the computing power which masks many programming sins these languages positively encourage).

The type theory-inspired type systems in conventional programming is the second most important mechanism for expressing engineering abstraction after the notion of subroutines (inspired by  λ-calculus).  And, just like the case of λ-calculus, the type theory provides the conceptual framework not matching the reality of programming.  We're again in the spherical cow territory.

The use of types in programming is not remotely as neat as the theory and common programming languages conflate several very different concepts, whereby types are used to represent implementation of the value storage and methods of accessing and modifying the value, the constraints on the value usage, the parametrization for polymorphism, and the semasiology (i.e. meaning to the programmer) of these values (this somewhat obscure term is chosen to explicitly distinguish notion of meaning of a value from the notion of its semantics as used in computer science: i.e. limited to the computation process itself).

The implementation aspect of a type in programming languages is the declaration made by the programmer to the effect that a specific hardware-supported encoding should be used to store and manipulate these values.  That's what all those char, int, long, double, etc declarations are.  It quickly became apparent that it would be completely impractical to explicitly specify types of all values, and so all existing high-level programming languages rely on automatic type derivation for intermediate values.  The declarations of compound types (arrays, structures, etc) also mandate presence (and in some languages, specific order) of all their elementary or compound fields in memory - the ordering and placement of the fields may have a dramatic effect on the program's performance because of data caching by CPUs.  The implementation specifiers in the types are also used to control where in RAM the value will be stored - be it heap, stack, or statically mapped data segment.

So far so good, it all makes a lot of practical sense, but has no relationship whatsoever to the type theory.  The implementation aspect of types in programming languages was historically first, with type composition coming only later.

The second important practical aspect of types in programming languages is checking constraints on individual values they place, and using these constraints to optimize code.  The most common constraint is on the kind of values a variable can contain: integer numbers, Boolean values, strings, etc. The second is range specification (usually implicit, though some languages like Pascal allow explicit range specifications).  Additionally, the constraints may include access controls (i.e. public vs private members of classes) and whether the value is a constant or can be changed run-time.  For array types constraints may include dimensionality and dimension sizes, and for structures they may manifest as requiring type identifier match and satisfying parent-child relationship predicates in case of type inheritance.

The constraint checking is important for detecting programming errors, essentially allowing users of abstract interfaces to spend less mental efforts an time on making sure that uses of interface match the interface definition.  This, however, is undermined by the inflexibility of the compositional construction of the types in modern programming languages usually forcing the interface designers to compromise between usability and type safety.

Having constraints on the possible types of values a variable or argument to a subroutine may have allows disambiguating between alternative implementations of a subroutine, so instead of having the subroutine name reflect the type of arguments, we can have polymorphic subroutines selected based on their signatures (which combine name and argument type constraints).  (The next step after subroutine polymorphism is generic programming with templates, but this is a topic for a future post).

Finally, programmers use types (particularly type names) to indicate what values mean to the programmer.  From a computer's point of view, number of apples is integer and number of oranges is integer, and you can add them with abandon.  For a programmer doing so would in many cases be an error.  With some degree of syntactic ugliness and verbosity we could define classes Apples and Oranges which contain the integer counters, define arithmetical operations on these classes, and achieve the detection of apple plus orange kind of programming errors for these classes.  Doing so is usually so burdensome for simple values that nobody bothers, leaving the program correctness to luck and prayer.  The structures and classes, however, are already named, so this is often used to enforce semasiologic correctness: if routine placeCall takes an AddressBook as an argument, and we're trying to pass it value of type BankAccount the compiler will rightfully complain.

This type-based support for semasiological constraint checking is quite limited: it mainly works with simple hierarchy-based ontologies, and any attempt to represent a less trivial relationship between types again requires non-trivial hackery.  It falls to the programmer to keep track of the meaning of the values to ensure that the program does what is intended by the programmer.

The boundary between semasiological meaning and program semantics is somewhat blurry, and some aspects of value types, traditionally considered as outside of scope of the programming language do affect computation.  For example, transposing a large matrix in memory is an expensive operation, so we may want the compiler to perform transposition elimination by changing iteration order in downstream matrix operations.  Another example is sorted-ness of an array (complicated by the fact that order is always associated with a specific predicate).  There is no natural way to express something like "this array of integers is sorted in ascending order" in a conventional programming language, so nobody does that, preferring to keep that information in one's head (and, depending on professionalism of the coder, comments).

The conflation of completely different aspects of types is one of the reasons why modern programming seems to be stuck at a rather low abstraction ceiling. The existence of this problem is recognized, but fixing it within a singular type systems seems to be elusive - to the point that there are proposals (notably by Gilad Bracha) to ditch the built-in rigid type system and replace it with optional, pluggable domain-specific type systems.

It may be more fruitful to stop treating types as strictly composable objects, type theory-style, and start looking at them as arbitrary annotations representing constraints which can be (at least partially) computed at compile time. We will return to this in the future posts, after the discussion of generic programming provides some background.

The Spherical Cow in Vacuum, Part 1 - Lambda Calculus

There is an old joke about a farmer who figured out that egghead boffins who can split an atom could surely figure out a way to get his cows to produce more milk.  So he contacted the physics department in the famous university and sweet-talked them into agreeing to consider his problem. The intrepid team of scientists eagerly took on the challenge and spent countless hours arguing, writing equations on chalk boards, and publishing papers. Days passed, then months, and then the team announced the break-through - they made huge progress!  When the farmer heard about it, he promptly inquired so as to what the solution is and how can he make use of it at his farm.  "Not so fast..." replied boffins "Our solution only applies to spherical cows in vacuum."

As the joke goes, it's only partially a joke.  One of the pitfalls of doing science is that you could build a nice theory which seems to fit your problem quite well... all the simple problems have solutions, but when you get to interesting ones, it all breaks down.  Pesky details ignored by the theory suddenly become major issues, and the nice theoretical framework now gets in the way of finding a right way of thinking about the problem at hand.

The most fundamental mathematical theory to the practical computing is lambda calculus (often written as "λ-calculus").   It was created in 1930 by Alonzo Church as part of his life-long work on foundations of mathematical logic (specifically, he came up with it in order to show that Entscheidungsproblem is not solvable).  It has an enormous influence on computer science and programming practice, from the first programming languages of late 1950s, and all the way to the contemporary fad of functional programming (which can be described as a thin veneer of syntactic sugar on top of λ-calculus).  It is beautiful, and some expressions have even gained cult status among the cognoscentes (see Y combinator).

It is also the biggest spherical cow in vacuum one could find. Let me explain.

The central concept of λ-calculus is abstraction (denoted by letter λ).  It is easily recognizable in a notion of subroutine in pretty much every general-purpose programming language. The abstraction contains the body (a formula) it wraps, and bound named variable(s) used in the formula and exposed by the abstraction as arguments (in programming parlance this would be formal parameter(s) of the subroutine).

Specific values of parameters can be applied to an abstraction, using an operation called β-reduction which basically replaces every mention of a bound variable (parameter) with the formula of the specific value.  (There are some other details - such as dealing with renaming of variables to avoid name conflicts, these are not important for the purpose of this discussion).

These λ-calculus operations of abstraction and application are directly reproduced in pretty much every conventional programming language and serve as the primary mechanism for abstraction (which corresponds to a subroutine declaration) and abstraction unwrapping (I deliberately use non-standard term here to avoid more specific connotations) - which corresponds to either subroutine call or subroutine code in-lining (the semantics is the same, but these choices offer different trade-offs between executable code size and performance).  For brevity, I'll omit closures - they are just syntactic sugar over plain old calling of subroutines by pointers.

In  λ-calculus, expressions have no side effects and are pure:  they only produce result value when evaluated,  and that value will be the same when all variable values are the same.  And this is here where the nice theoretical construct starts to clash with the reality.

Execution of any computer code has side effects.  Let it sink.

Some of these side effects are intrinsic: they change the state of the computer in ways directly accessible to the program (functional programming style attempts to minimize these), but more interesting side effects are extrinsic: the time it takes to run the code, the amount of heat generated by the computation, data being stored in and evicted from cache, network packets being sent, changes in pixel luminosity on displays, etc, etc.   Because programs run strictly within confines of CPU and RAM - which are not directly accessible from outside, a program without extrinsic side effects would be a null operation.  The sole purpose of running programs on computers is to generate extrinsic side effects.

The problem is: λ-calculus (and operations of subroutine declaration and calling in programming languages) do not admit existence of side effects.  It is not possible to describe side effects or do anything about them within this formalism.  (Of course,  λ-calculus is Turing-complete and so any kind of non-interactive program can be converted into it - but this is a ridiculously low bar for fitness for any practical purpose, as anybody who ever tried to write a slightly non-trivial program for Turing machine or played with Church numerals surely knows.)

From the point of view of programming ideal abstract machines there is no difference, for example, between bubble sort and quicksort.  They are equivalent.  On real computers, of course, there's a world of difference.

There's another name for the side effects which are not formally representable in the language: abstraction leaks.  And they are the root of the problem with modern software development, as we discussed in the previous post.

So here we have it: by using a seemingly perfect theoretical concept to represent abstraction and abstraction unwrapping in our programming languages we got ourselves into the corner - because that particular theoretical concept does not fit the reality of computation using physical computers. Part of this is confusion between mathematical and engineering abstraction, part of it is inertia and lack of reflection on the basic tenets of the discipline.

We obviously need to find a way to represent side effects (both intrinsic and extrinsic) within a programming language if we ever going to overcome the abstraction level ceiling. Prof. Gregor Kiczales offered an outline of a design attempting to do just that in his 1992 article, but no practical implementation or design proposal ever came out of it.

The question is what the right mathematical structure and corresponding practical representation for the engineering abstraction would be?  Stay tuned.  We're not done with sacred spherical bovines yet (see Part 2).

The Tale of Two Abstractions

Observing the software industry for a few decades from the inside is both depressing and instructive: what never ceases to astonish is how little actual progress is made by the efforts of huge numbers of really smart and talented people.  Especially jarring is the contrast with the progress in hardware: most people now carry small devices which have more computing power than supercomputers of 1980s  (and an array of sensors, an impressively detailed and bright display, and always-on radio data connection with more bandwidth than trunk links of biggest Internet backbones of mid-1990s). But the software which runs on it is seriously unimpressive.  In fact, compared with the feats of software engineering of 1970s - like landing on the Moon under guidance of 16-bit 1MHz computer with 19 instructions and 4KiB of magnetic core RAM - or designing software for Air Traffic Control which is still running the critical infrastructure on computers so old that finding parts for repair is a huge challenge - it seems that we've got a serious case of regression.  It's not really a regression in skills, just an effect of being able to get away with crappy software design because hardware is so powerful and reliable - and result of our inability to cope with ever-increasing complexity.

Complexity is Νέμεσις.  It's programmer's enemy № 1.  Human ability to deal with complexity is quite limited, both in terms of ability to understand non-spatial structures (an attempt to mentally visualize simple tesseract (not a projection, but the tesseract as it is, with equal-length straight edges and 90° angles) is going to be futile) - leave alone structures without any notion of continuous space such as computer programs - and in terms of very limited short-term/active memory (4±1 units). Meanwhile, software is the most complex of all human artifacts, by far.  How do we manage to build it at all?

The key to creating large and complex systems is abstraction: when we can think of a complex system as containing blocks which may be complex inside, but which perform conceptually simple functions and have relatively simple interfaces, we can focus our limited attention and memory on the currently relevant block at the abstraction level we're working at.  Splitting the design into blocks also allows to divide the labor of designing these blocks among many people.  This is daily bread for a software architect.  The principles of good software architecture are well understood (though often ignored), but the real issue is the gap.

Architecture is informal and somewhat nebulous (and when trying to steer system design towards sounder architecture the author of this post had been told to stop wasting time on philosophy by the lets-get-hacking geeks - on many occasions).  The code, however, is very specific.  This does not make architectural decisions any less consequential: it's just there's that gap between intention and implementation, and the more complex the system is, the wider is the gap.  So far attempts to close or at least reduce that gap were unsuccessful (the dismal failure of CASE is a topic worthy of separate discussion).  We just don't seem to be able to raise the level of abstraction of our programming systems to the place where intentions of a software architect could be trivially converted into a working code for any project of a meaningful size.  When creating software we are still mired in the tar pit of details.  It's as if there's an impenetrable abstraction level ceiling in our software development environments.  To understand how that ceiling came to be we'll need to re-examine our notion of abstraction.

To start with, there are two not very subtly different notions of abstraction: the first one is mathematical and another is common in engineering.  Abstraction in mathematics is, basically, stripping details of objects in order to arrive to a structure which has interesting set of algebraic properties.  The most familiar example of this is natural numbers (the set of natural numbers is usually designated as ℕ).  The notion of natural numbers abstracts away all properties of discrete natural objects (such as apples or oranges) to leave only their countability, which doesn't seem much, but gives raise to arithmetic.  The arithmetic is very useful in practice, its power coming from the ability to use the results of abstract calculations to predict results of manipulating any countable objects. Adding one apple to three apples gives four apples.  Adding one orange to three oranges gives four oranges, etc.  Note, however, that arithmetic fails when other properties are mixed in: adding one apple to three oranges gives us neither four apples nor four oranges.  A major part of mathematical reasoning is figuring out when a specific abstraction is applicable, and when it no longer gives meaningful answers.

The engineering abstraction is also about stripping details, but it aims to facilitate approximate, imprecise reasoning about larger blocks of the system.  It's a cognitive aid, not a search for algebraic structures.  No engineer ever believes that details are irrelevant, it's just that he chooses to defer thinking about them in order to avoid being cognitively overwhelmed by the complexity.

All software objects are engineering abstractions, they run on physical computers (rather than mathematical abstractions like Turing machine), and because of physical laws (such as the limit on the speed of light) they have physical properties, too: the real programs take time to execute, the side effects of their execution is release of heat (for both technological and fundamental reasons), they always have non-zero error and failure rates, etc, etc, etc.  These physical properties combine to create properties of higher-level software objects, and those are not trivial.

These abstracted-out properties are not inconsequential, the problem first described by Prof. Gregor Kiczales, and then formulated by Joel Spolsky as the Law of Leaky Abstractions: All non-trivial abstractions, to some degree, are leaky.  Spolsky seems to consider the leakiness to be the emergent property of complex software.  It is not:  it is the inescapable consequence of the nature of engineering abstractions. The very same phenomenon is found in every engineering discipline, although it is much less pronounced (but we still have to test designs of all complex machinery to detect overlooked "reality leaks").

The only reason this law comes as a surprise to software engineers is because they (and the practitioners of the discipline of Computer Science in general) tend to think of software in terms of mathematical objects, thus conflating two very different notions of abstraction.  This confusion exists at the very core of how we write programs: the mathematical idea of abstraction is fundamental to all existing programming languages.

The law of leaky abstractions also has a non-trivial consequence: imagine that we're building software running directly on a physical computer.  We have a pretty good idea of how it works, and thus we can select algorithms and data structures to make our program efficient on this computer.  Now, let's abstract common operations such as reading and writing disk blocks, adding some cache and a file system on top.  Now the application programmer can use these more abstract operations (instead of figuring our specifics of a particular disk controller) - but we also introduced new non-trivial details (cache behavior, file fragmentation, etc).  Then we write a database - which by necessity will be aware of these details.  And then one nice day we get a shiny new SSD - which, while offering the same "abstract" I/O, has radically different performance characteristics (and wants to be explicitly told when information is no longer needed, aka trim command).   Some database queries are much faster, some are just as slow as they were before.  We can not just blindly put more load on the application just because we made storage faster.  Instead, we have a huge amount of work to adapt the whole stack to make advantage of the new technology.  It may actually be simpler to rewrite everything from scratch.  Here comes the new "framework" doing pretty much the same work as the old one, but quite different, so all users now need to rewrite their applications.

The problem with abstraction leaks is that they are kept within the mind of a programmer: there is no way to write code which would adapt to the changing leaks.  Pile more layers on top, and the whole becomes intractably rigid, unable to cope with changes in a reasonable manner.

This phenomenon of specific "values" of abstraction leaks being baked into successive layers of software is the reason why we can't work up to high abstraction levels.  And we have to bake in these values when we write software because there's no way to express or handle the leaks explicitly (that's why they are "leaks").  Let's call it the Law of Abstraction Level Ceiling:

Abstraction leaks create abstraction level ceiling.

The situation looks fairly hopeless... we need engineering abstractions to cope with cognitive overload, and this results in the upper limit on the abstraction level at which we could program.
Fortunately there is an escape:  the whole mess with leaky abstractions is created by the use of the mathematical concepts which are inappropriate for dealing with engineering abstractions precisely because they were developed for dealing with ideal abstract machines.  The physical reality of engineering abstractions seems to be also amenable to mathematical description - it's just the description matching the reality may not be the same as the nice theory we have in our minds. Planets are not moving in perfect circles, but the real law governing their motion is not that complicated either, and in vast majority of cases we could get by with astonishingly simple approximation.

What exactly we got wrong half of the century ago, and what can we do about it will be the subject of further discussion in our future posts concerning spherical bovines in evacuated spaces.

Programming like it is still Middle Ages, Part 2 - Software Factory Pipe Dreams

Keeping in mind the discussion of modes of production (in part 1) we're going to take a closer look at the poster child of post-industrialism: modern software development.

It is hardly a secret that the shiny facade of high technology hides some truly ugly problems: first of all, the success rate of software projects is abysmally low: a relatively recent study found that as many as 68% of all software/IT projects fail.  The quality of software (although much harder to quantify) is universally poor, especially where security is concerned.  The incredible growth of CPU performance and amounts of memory and data storage are not matched by visible improvements in software responsiveness and usability. To top it off, a significant part of software developers cannot even be described as competent programmers despite being able to negotiate rather impressive wages, indicating both the increasingly dire shortage of software developers and fundamental brokenness of the hiring and management practices.

To get some insight into the nature of the problem  (the necessary first step in being able to come up with a serviceable solution to it) we need to take a closer look at how software is produced.  At a risk of sounding like Captain Obvious I would like to state that each mode of production has its own best methods of organizing it.  These methods are evolved products of selective pressures (those which worked were imitated, these which didn't failed and disappeared).  Being confused about which mode of production is involved leads to the failed attempts to organize and manage production is ways which will be consistently deleterious or even catastrophic.

The common wisdom is that high-tech in general and software development in particular are a shiny new production mode: the wonderfully vague "post-industrial".  This unfortunately yields no practical insight into what it is: what is the relation of labor, capital, and inputs in this mode of production?  Let's try to characterize these based on what we see in reality.

We need to keep in mind that production cycle in software is rather long (many months or years), and this somewhat complicates teasing out which factors are capital and which are inputs.  The depreciation time of some nominally capital factors (such as computers) is close enough to the length of the production cycle to consider them consumable inputs instead.

Labor: Software development is very labor-intensive, and budgets of high-tech companies are dominated by labor costs.  A modern software project could easily be from 100K to 10M lines of code (however flawed this metric is, it at least offers some way of coming up with order-of-magnitude estimates).  A recent estimate of an average software developer's productivity  comes up to something like 325 to 750 lines of code per month (Jones, Capers and Bonsignour, Olivier. The Economics of Software Quality.).  For a small 2-year 100K LOC project it implies staff of 6-12 developers, for a 10-year 10M LOC project the estimate would be around 300 developers (in reality the headcount will be much more because productivity rapidly falls with increasing complexity, the staff of 1500-3000 engineers for a project on this scale would be closer to reality).

Besides hours spent, labor in high-tech contributes personal knowledge and experience, which are costly to acquire.  I.e. the "talent" contributes capital in addition to labor, which is tacitly recognized by the structure of compensation in the high-tech industry which commonly gives equity in the business (in form of stock options) to the engineers as a part of the package in order to create incentive for the "human capital" to stay longer with the company.

Capital: The capital goods used in production of software are mostly in the form of the office buildings, institutional knowledge, and acquired intellectual property (IP).  Offices used in software development are not any different from pretty much any other office space, which is practically a commodity; most software businesses rent.  Of course, a start-up company needs financial capital in order to pay labor and other costs before it becomes profitable, but mature software companies do not need outside financial capital to sustain their production.

Acquired IP is not as important as it is appears to be because the code itself is not of much practical use without people who understand it.  Gaining understanding of somebody else's code to the point of being able to significantly modify and successfully maintain it long-term requires efforts comparable to writing the code from scratch (especially if code quality isn't great and supporting documentation is lacking). As it happens, IP critical for the actual software development is mostly in public domain and/or free. (Why is this so is outside of scope of this post).

The only really important capital good necessary for software development is knowledge created in-house, usually as a byproduct of creating the software.  Unfortunately, most companies are not good in promoting accumulation and preservation of this knowledge, and often create perverse incentives which inhibit knowledge transcription and sharing (again, this is a separate discussion) - the situation eerily resembling the reluctance of medieval artisans to share their knowledge.

Inputs: the inputs in software development (besides trifles such as coffee and electricity to run computers in the office) are quickly depreciating computer hardware, licensed IP, on-line product service fees, and rental office space.  These are relatively minor lines in the budgets.

The final observation about production of software is that while software costs next to nothing to replicate, producing it is always custom work.  Where production is concerned, all software is bespoke - no two items are the same.  In fact, there's not much standardization in software engineering: there are some standards for programming languages and network protocols, but the practical implementations are never 100% compliant, and a common practice among the vendors is to deliberately break compatibility by creatively "extending" the standards for the purpose of customer lock-in.

Just like there is notable paucity of software object standardization, there is also notable lack of standards for professional qualification.  This leads to the strange spectacle of academia churning out massive numbers of "computer science" graduates who lack the skills and knowledge to program in the real world.  This knowledge is then acquired through on-the-job training, which ranges from autodidact learning to apprenticeship.

All of the above strongly matches the artisanal mode of production: the most advanced and complex artifacts of human civilization are, in fact, produced in the way not much different from the artisans of old firing clay pots and smiting horseshoes.  In no way it is "industrial", leave alone "post-industrial".  We program like it's still Middle Ages.

This, however, does not stop the business people to try to impose management methods developed for industrial production (after all, this is what they are taught in the business schools) onto software development, with little success.  No amount of wishful thinking could make an occupation requiring advanced abstract reasoning into blue-collar work. The "software factory" is still a pipe dream, by now becoming firmly associated with outsourced production of junk software on the cheap. It may actually be better to re-create the social structures which evolved during Middle Ages to support the artisanal production.  Yes, guilds (a historical tidbit: guilds created modern academia by establishing the early secular universities).

Another feature of artisanal production is its unpredictability: the lack of standards and high variance in professional quality (at least guilds provided some guarantees about performance of their members) makes planning of software development an exercise in futility and outright fraud: quite a lot of software engineering projects are delivered "on-time" by means of cutting corners, changing the definition of what is going to be delivered, and compromising on quality and future maintainability of the delivered code.

The problem with the artisanal mode of production is that it does not scale well, and no management fads are going to change this basic fact.  We cannot deal with the crisis in software production without changing the nature of software development by figuring out why our attempts to mechanize software production and to standardize software objects were such abject failures (and not for the lack of trying by very smart people) and finding ways to overcome this obstacle.  This will be the main theme of many future posts in this blog.

Programming like it is still Middle Ages, Part 1 - Modes of Production

Human economic activity generally revolves around production: nearly all what we consume has to be produced first.  Production of anything requires inputs, labor, and capital.  Inputs are goods which are consumed in production of the output goods: as parts, as materials used in production, as other necessities such as electricity for lighting shops, etc.  Labor is provided by people (and only by people - robots are tools), and capital is the set of durable goods (tools, machines, buildings, etc) needed to production but which is not consumed as a part of production.  Of course, to produce something one need to know how to produce it: the knowledge is clearly the crucial part of production, but it is not consumed during production (if anything, more knowledge is gained in the course of production). Knowledge is costly to acquire and thus is properly categorized as a form of capital.

Sometimes it is hard to tell which is which (for example clearly capital goods like tools and buildings are also consumed, although slowly: they depreciate with time and use).  It is also hard to disentangle labor from knowledge, especially in the white-collar occupations.  Let's just say that some factors of production may to a some extent belong to multiple categories.

Historically, the human society progressed through a series of production modes (although any society normally has multiple production modes co-existing), which can be roughly classified as following:

• Hunter-gatherer mode: there is not much capital involved, and all inputs occur naturally. Finding and taking them is all labor, and no attempts are made to codify or preserve knowledge.  This mode of production was prevalent in primitive societies and its productivity is only sufficient for sustenance-level living.  This mode of production does not actually require sentience: the instincts are sufficient, and animals are hunting and gathering nearly as well as humans can.
• Agrarian mode: the capital is overwhelmingly in a form of naturally occurring things: land and livestock, and all inputs (rain, sun, etc) are natural.  Like hunter-gatherer mode, it is labor intensive, but does not require advanced knowledge (the oral tradition is sufficient to pass the knowledge on); however this mode is also more productive than previous which allowed agrarian societies to produce surplus product, and enabled accumulation of capital and knowledge needed for creating civilization.  Pretty much any able-bodied man can be an agrarian worker with only a little instruction.  Agrarian mode of production was dominant from antiquity and until the modern industrial era.
• Artisanal mode: the production is characterized by increasing division of labor and introduction of the supply chain: the inputs of artisans are often intermediate goods produced by agrarians or other artisans. Artisanship also requires specialized knowledge and more capital (mostly in form of buildings and specialized hand tools).  The specialized knowledge is passed down by guilds in master-apprentice arrangements, but there is not much knowledge exchange between guilds.  Artisanship is still labor-intensive, and every product is unique because there are no widely accepted standards or best practices (and, in fact, guilds considered keeping their unique knowledge to themselves as something desirable and a way to limit competition).  The uniqueness could be desirable (as in art), but for most goods it is deleterious.  Within their broad specializations artisans are expected to be capable of doing pretty much any task.  The artisanal mode of production coexisted (and was supported) by agrarian mode, and reached its peak during late Middle Ages.
• Industrial mode: the supply chains become very complex and hierarchical, and the production is capital-intensive because tools and machines become complex and even more specialized. The industrial production involves two very distinct kinds of labor: the manual (aka blue-collar) labor, basically using people to perform routine and repetitive actions for which there are no adequate machines (or when it is cheaper to use labor) and the white-collar labor of managers and engineers who create plans and instructions for the production.  The blue-collar workers are expected to follow these instructions precisely, in a machine-like fashion.  The knowledge needed for the production becomes so complicated that industrial production is impossible without shared written records (in textbooks, industry publications, etc) and specialized training by educational institutions.  Because more and more operations involved in production are performed by machines, the output of industrial production is by necessity more standardized than output of artisans.  The industrial mode of production also requires the supply chain of capital goods which often involves even more complex and knowledge-intensive production.  Most modern production (including agriculture) is industrial.

The common trends in this progression are increasing capitalization and reduced labor-intensity (which allows for dramatic gains in productivity per worker), with increasing complexity of supply chains and the knowledge required for production.  Basically, to achieve higher productivity more capital and knowledge are required.  (The productivity per worker is important because it directly translates into how much goods is available for consumption per person: i.e. it defines the welfare of the society).

Relatively recently (see Prof. Daniel Bell's book The Coming of Post-Industrial Society: A Venture in Social Forecasting, 1973) it became fashionable to postulate the fifth mode of production: post-industrial, or knowledge-based economy increasingly defined by production of the so-called Intellectual Property (IP for short).  This notion is vague and conflates knowledge and information: knowledge is something residing in a brain, while information (in a narrow meaning as an economic good) is something existing outside of a person.  The post-industrial mode of production is supposed to reduce both capital requirements and labor and is supposed to displace the industrial production, while being dependent on computers and information technology.

This notion of the fifth production mode is arguably dubious, because it cannot exist without industrial production going on elsewhere (people need to eat and dress, and computers need to be manufactured).  In fact, it is nothing more that a part of industrial mode of production: the part involving white-collar labor.  It is possible to have a society specializing in this, but only if it is integrated by global trade with industrial societies.

As I will argue in the second part of this post, the confusion surrounding the notion of post-industrial mode of production has served to cloud our thinking about the nature of software development.