Primitives And Means Of Composition

A recurring pattern in many of the designs that can be considered masterpieces, and maybe one of the HigherOrderPatterns in good software design. It's also a good framework to apply against a design in order to decide how powerful or expressive it is.

The intuitive idea is that a good system should work like Lego. With just a few basic bricks and the means of connecting them, the users are empowered to develop the most unexpected constructions. So in constructing a system you focus your attention on the set of primitives (the bricks) and the means of composition (the way to connect them).

Primitives provide the most basic element that have a meaning in themselves. They're a given, provided by the system. For example in a programming language those would be the primitive types and operations on them. If you are not given integers and integer operation, it is impossible (or exceedingly difficult, inefficient, etc - which in software amounts to the same thing as impossible) to implement them. So if you need integers the system must provide them as primitives.
- Or, at least, the system needs to provide a standard 'view' of integers (e.g. Nat = succ(Nat)|zero) and guarantee an optimization that achieves the same effect. This approach is taken by many laboratory languages, but hasn't made it into the wild much.
Means of composition are the operations provided to the user (programmer) by the system by which you can take one or more existing elements and derive a new one. For example:
- EssExpressions as a notation for structured data needs exactly one composition operator CONS (or pair). Various implementations have more than CONS, but the classical Lisp notation had just CONS. Given two elements a b, you can create a pair (a . b). This can be used to compose structures of arbitrary complexity.
- Juxtaposition. The ForthLanguage relies on juxtaposition of two tokens to effect composition. Given two adjacent symbols A B, A operates on data first, producing output for consumption by B. Almost identical to Unix pipes without the explicit pipe character. It should be noted that any Forth environment may be constructed from a quite manageable core of about 27 to 43 primitive words, depending on what tradeoffs you make for performance. Apparently, some Forth systems have been implemented in as little as nine primitives (Frank Sargent's 3-instruction "Forth" isn't a Forth machine at all; it's just a monitor), but I'm forced to question whether the performance was usable for anything beyond a toy.
- In the RelationalModel, the means of composition are the relational operators (projection, selection, join, and set operations applied to relations as sets of tuples). This can be used to express transformations of arbitrary complexity.
- In SmalltalkLanguage, the main composition facility is the "message send". The primitives are the message sends that are natively implemented, plus the universe of primitive values - integers and the like. Actually, it could be the only means of composition because declaring a class is actually a message send. This can be used to define systems of arbitrary complexity.

If the two sets are carefully chosen, wonderful systems can occur. Examples of such systems are LispLanguage (as originally designed, or currently embodied in SchemeLanguage, because ANSI LISP has arguably departed from the original purity of the design), AlgolLanguage, the RelationalModel, SmalltalkLanguage, and Unix PipeAndFilters?.

There are a few qualitative aspects to be followed and recognized about PrimitivesAndMeansOfComposition design:

Economy. This is the whole point of this type of design. Often, a tiny set of primitives and means of composition can be more useful than a large set of non-composable features. An economical set of features is of great value for users, whose brains are freed to think about the problem domain rather than remember all the details of a vast collection of unrelated capabilities. The principle of economy drives the removal of redundant features so that the conceptual burden on the user can be reduced. It also drives the economy of implementation: if the implementer doesn't need to worry about a ton of features, more effort can be concentrated on quality of implementation.
Power This is what needs to be balanced against economy. The primitives and means of composition should be sufficiently powerful to cover all the targeted domains of the system. For example with just the CONS operation, EssExpressions can encode any data whatsoever.
Closure. For example, it is often said that the RelationalModel benefits from relational closure. That means any operation on relations yields another relation, which can be further combined with other relations and relational operators. In general, the composition operators should yield results that are subject to further composition. It is never helpful when a composition yields something with which it is "stuck" (i.e., can no longer be composed). Closure drives composability and therefore power.

In analysing a complex system/framework, it is good to look at it this way: What are the primitives and what are the means of composition? Then you can determine if these are economical, powerful and composable.

An edifying example

Unix structures almost everything around text files. In particular, the logging subsystem (/var/log) is simply text files. Through PipesAndFilters the text files can be operated upon with a variety of tools. Given a Unix system with enough logging, you can apply "tail -f" to monitor what's happening in real time, apply the powerful grep/egrep utility to filter what interests you, or cut, sort, etc., to extract information. For a skilled user, the sky is the limit.

In contrast, in Windows culture most applications are monolithic, store data in their proprietary format, couldn't care less about stdin, stdiout, stderr, and dump a fixed GUI on the poor user. This is relatively good for unsophisticated user, but guess what, GUIs are non-composable par excellence. So Windows comes with a proprietary log format, and a completely inept GUI attached to it (Log Viewer). The means of composition in Windows was not carefully chosen. COM/OLE are means of composition, but they're just too complex. They require access at least to a C compiler (with the expensive development process) and often to an IDE. Later on, Windows added Automation which is scriptable (easiest through WindowsScriptingHost or other facilities) but still far from the simple usability of Unix PipeAndFiltersArchitecture?. Similarly the Logs and LogViewer? have been finally exposed to composition through WMI API (Windows Management and Instrumentation) which offers a SQL query facility against the information in the logs. So you can put together a JScript or VBScript that throws a query at the log service. However, throw a few queries against a production system, or a moderately large log, and the response is painfully slow. In this case it is apparent that the means of compositions were too ambitious and put too much of a burden on implementers.

PrimitivesAndMeansOfComposition is also a very useful approach in teaching/documenting a software system. Often times you see software documentation/courses/tutorials that drive you to a baroque collection of individual use cases. They explain with a HowTo approach how you do this and that, and if you want to do something else you have to reverse engineer the PrimitivesAndMeansOfComposition structure of the system so that you can put them to work toward your goal.

This page expresses, in a far more precise way, what I alluded to in AllFeaturesShouldBeSimple. Well done.

The primitives of a powerful system may not be very simple to understand in and of themselves. But when they're decoupled from other primitives in a manner that allows composition, they're as simple as they can be while still providing the basis for expressive systems.

This is at the heart of my objections to the many popular 'object-only' approaches that seem popular nowadays. Most of these start with notions of objects and classes that conjoin concepts that are well-known traditional primitives of programming, making them unavailable for composition in other, useful ways. I'm thinking of concepts such as namespaces, access control, and closures.

As a practical matter, one may build complex constructs from such a system, and incorporate those constructs as new features of the system. This additive complexity does not detract from the elegance and power of the original system. (Thus object-oriented languages should preserve and make accessible the primitives that they build on.) For example, CommonLisp has for the most part not sacrificed the core elegance of its predecessors, but has mainly added new, pragmatic constructs that can be described in terms of the core concepts. (By some measures, there haven't been enough additions!) It thus gives an impression of more complexity than it actually has.

-- DanMuller

I received an observation by email that although nice this page contains only low-level examples, and I should have presented higher-level abstractions that follow this structure, and especially ObjectOriented examples.

Well, the observation is right, but I am in a dilemma. I don't believe that the OO tools of the trade, in the way they evolved, are very composable, although they do present themselves as powerful abstractions. You cannot take two objects, apply a universal operator and get a meaningful third one; you cannot take two classes, or a class and an object, or a class and a method and do something similar. Later, the orientation towards components made things a little bit more composable, but, for example, designs like EJBs were flawed from the start - see EjbFlaws, and now we have to wait to see how EJB3 will fare.

In comparison, FunctionalProgramming matches the idea of PrimitivesAndMeansOfComposition much better, because functions are inherently composable, and there are tons of operators: fold, map, reduce, automatic bind, and it's easy to create new HigherOrderFunctions that are the means of composition. See TheEvolutionOfaHaskellProgrammer, of course. :) Actually, some fine examples are in AlgebraOfProgramming. -- CostinCozianu

You cannot use the JavaLanguage to demonstrate limitations in ObjectOrientation. Java is only partly ObjectOriented: it's basically a procedural language with some ObjectOriented bits stuck on, That means it doesn't score well in the PrimitivesAndMeansOfComposition stakes: too many different kinds of primitives that don't compose well or even at all.

CategoryPattern