Single Inheritance and Other Modeling Conundrums

Sometimes a restriction in a programming language makes sense and no sense at all — all at the same time.

Modeling the real world

Think about the Java restrictions on the modeling of classes: a given class can only have one supertype and a given object’s class is fixed for its lifetime.

From a programming language perspective these restrictions make a good deal of sense: all kinds of ambiguities are possible with multiple inheritance and the very idea of allowing an object to be ‘rebased’ fills the compiler writer with horror. (Though SmallTalk allows it.)

The problem is that, in real life, these things do happen. A ‘natural’ domain model is quite likely to come up with situations involving multiple inheritance and dynamic rebasing.

For example, a person can go from being a customer, to an employee, to a manager to being retired. A given person might be both an employee and a customer simultaneously (someone else may not be).

Given a domain that is as flexible as this one if forced to ‘simulate’ it in Java. I.e., one cannot use a Java class called Customer to represent a customer; because Java’s idea of class is not rich enough to model the domain.

At the same time, the modeling is not random and a good architect will try to ensure some discipline in the application.

The logical conclusion is that large applications tend to contain a variant of ‘the type system’ where the domain model is represented. Java is used to implement the meta model, not the domain model.

This dynamic type system may or may not be based on a well founded model (such as that of description logic); but in any case the programming language is not helping as much as it should.

What is a language to do?

On the face of it, it seems that the logical thing is to make a programming language’s type system sufficiently flexible to actually model real world scenarios.

However, there is a difficulty with that: it is not the case that any one modeling system is best suited to all applications. In addition, a modeling system that is well-suited to modeling domain knowledge is not guaranteed to be equally well suited to regular programming tasks.

A better approach is to embrace diversity. A combination of DSLs and libraries enable one to build out a particular modeling system and to support the programmer with direct appropriate syntax.

For example, this pseudo-code example:

  customer isa person
  customer has account
  ...
  person has name
  ...
  C instance of customer
  ...
  if overdrawn(C's account) then
    ...

shows one example of a modeled customer. The ‘actual’ code implied by this fragment might look like:

  C : object;
  ...
  if overdrawn(findAttribute(C,"account")) then
    ...

The principal point here is that the syntactic sugar offered by a DSL is not mere syntactic sugar: it can help the application programmer to use a language that is appropriate for her needs while at the same time enforcing sanity checks implied by the particular modeling language.

At the same time, there is no implied permanent commitment to one particular way of modeling with the host language.

Too Many Moving Parts

A common, if somewhat informal, observation about a large code base is that there are “too many moving parts” in it. In my experience, this is especially true for large Java systems but is probably universally true.

What do we mean by ‘too many moving parts’?

Simply put, there is always a significant semantic gap between a programming language and the program. The larger this gap, the more that has to be expressed in the language, as opposed to simply using it.

For example, consider the problem of traversing a recursive tree structure. In Java, we can iterate over an Iterable; structure using a loop, for example, to count elements:

int count = 0;
for(E el:tree)
{
  count++;
}

If the Tree class did not implement Iterable we would be forced to construct an explicit iterator (or worse, write a recursive one-off function):

int count = 0;
for(Iterator<E> it=tree.iterator(); it.hasNext();)
{
  E el = it.next();
  count++;
}

This version illustrates what happens when a programming language does not quite meet us halfway in our programming task. There is a lot of extra clutter (managing the iterator) that makes it hard to see what is really going on.

In this case, Java’s for notation makes it significantly easier to see the program. However, there are many cases where this is not true. For example, you cannot use a similar technique for reading files, searching or removing elements from a tree, etc. etc.

Language Extensions

One way of reducing clutter is to permit the programmer to extend the language. Of course, the designers of Java set their face against this — there is no macro facility in Java — for a reasonable if misguided reason: to prevent programmers lying to each other.

The Star language does permit language extensions to be introduced by the programmer. This has the effect of encapsulating not only data abstractions but also control abstractions.

For example, to count the elements of a tree in Star, we can do:

var count:=0;
for E in tree do
  count := count+1;

The program depends on the programmer implementing the type contract for _search and a macro expansion rule:

# for ?Ptn in ?Exp do ?Act ==>
  __search(Exp,procedure(X){ if X matches Ptn then Act})

No apologies for the macro definition itself, but the effect is that the language has been lifted into one that fits the requirements more closely. This, in turn, reduces the semantic gap between the language as used by the programmer and the application.

Of course, there is quite a bit more to reducing clutter than macro definitions. However, it should be an important goal of language design to ensure that programmers can express themselves with minimum extraneous concepts.

Late Binding in Programming Languages

Late binding is key to enhanced productivity in programming languages. I believe that this is the single most important reason why so-called dynamic typed languages are so popular.

This note is part of an ongoing ‘language design’ series which aims to look at some key aspects of programming language design.

What do we mean by late binding?

Simply put, a programmer should not have to say more than they mean at any particular time.

To see what I mean, consider a function that computes a person’s name from a first and last name. In Star, I can write this:

fullName(P) is P.firstName()++P.lastName()

This constitutes a complete definition of the function: there is no need to declare types; furthermore this function will work with any type that has a first and last name.

Contract this with a typical well-crafted Java solution:

boolean fullName(Person P){
  return P.firstName()+P.lastName();
}

Not so different one might argue.

Except that we have had to define a type Person; at best this is an interface and not a class. The Java fullName method will only work with objects of type Person.

In designing the Java version we have to find and/or create a type Person. In addition, we must make sure that all classes that we want to compute the full name of implement the Person type.

This last aspect can be a real productivity killer. Suppose that we want to be able to compute the full name of many different kinds of objects; then we must arrange them all to implement the Person type. This may not even be possible if the classes in question are from a library that you don’t have the source to.

Late Binding does not mean dynamic typing

One of the common perceptions is that you lose the safety of a type checker if you want to allow late binding. This is not true; at least, it is not true for Star.

Star is a statically typed language which supports a range of type constraints. In the case of the fullName function, the constraint is that the type of P has the firstName and lastName attributes. (The details of how this is done are too gory to go into here.)

These constraints can be checked; so, for example, every time the fullName function is used on an argument, the checker can verify that the type of the argument is consistent with having a first and last name. This check can be performed at compile-time.

It is even possible (necessary) to go one step further and allow generic functions to use the fullName function.

Other forms of Late Binding

Late binding shows up in other ways. For example, when specifying an imported library of some form or other, it should be possible to declare the requirement for a library in terms of what is needed, rather than the name of the library. I.e., instead of:

import java.util.List;
import java.util.ArrayList;

we should be able to say:

require List of integer;

or some such expression.

The difference is that the former says — in the source code — which package to import whereas the latter merely declares a contract requirement. How the contract is fulfilled is a separate step; one that a smart compiler system may even be able to automate.

(Some language do work this way. Typically LISP language systems organize their modules in terms of requires and provides.)

Take Away

It can be hard to know what features should go into a programming language. Having a few principles to guide us make the task of designing a language more tractable.

In this case, the message is that programmers should be able to program in terms of their requirements, not the compiler’s. This need not come at the expense of safety or of performance.

Productivity gains are permanent, Performance losses are temporary

This is the first in a short series of notes about language design. The goal is to identify what is truly important about programming language design.

It is all about productivity

There are ‘too many moving parts’ in a typical Java program.

Here is a simple straw-man example: iterating over a collection. Before Java 5, the paradigmatic way of iterating over a collection was to use a fragment like:

for(Iterator it=coll.iterator();it.hasNext();){
  SomeType el = (SomeType)it.next();
  ...
}

There is a lot of ‘clutter’ here; but worse, there are a lot of concepts that are not really that important to the problem at hand.

Compare that to the Java 5 version:

for(SomeType el:coll){
 ...
}

Here we can focus on exactly what is needed: the collection and the iteration.

This kind of example can be repeated fractally up the entire stack of abstractions: not just at this micro level but also at the level of using standard JDK class libraries on through to using features such as Spring/Hibernate or Wicket.

The elements of productivity

I believe that the list of requirements is not that long:

Digestibility

A programming language is an artifact, and needs to be understood in order to be effectively used. So, a language with a well crafted structure is going to be easier to learn and use than one with many ill fitting pieces.

Note that this does not mean a small number of pieces (or features). The classic example of this is natural languages (such as English or Spanish). There are at least 500,000 words in the English language. A daunting task for someone wishing to learn the language. But, the grammar of English is relatively simple compared to other languages (such as German or modern Greek). This has helped English to become the dominant second-language globally.

Semantic Lifting

Structure in software is evident at many levels: in the micro structure of individual fragments of code, to the organization of libraries to the ecosystem of multiple applications.

A powerful tool for managing this complexity is abstraction. Commonly abstraction is thought of as a technique that enables one to ignore inessential details.

But a better concept might be semantic lifting. Semantic lifting is a common technique in Mathematics. For example, vector geometry is layered over cartesian geometry but permits powerful statements to be expressed in a simple way.

A programming language that can support similar techniques for lifting the language — like the iteration example — enables higher productivity.

Late Binding

Programming languages are often quite fussy in character: requiring all kinds of details to be established quite early in the design process. For example, Java (like most languages) requires that all types have names.

This emphasis on detail makes a significant barrier to developing a program: the programmer is forced to focus on issues that she may not actually be ready or willing to.

A language that supports late binding allows programmers to delay such choices until they are needed.

For example, one reason that type inference is so powerful is that it permits a programmer to program in a ‘type-free’ way while knowing that the compiler will verify the type safety of the program. Establishing types of functions is a detail that can often be left to later. However, ultimately, type inference still ensures that the program is ‘correct’.

Declarative Semantics

This one is a hard one!

But the fundamental benefits of a declarative semantics arise from the tractability that follows. Having a declarative semantics makes program manipulation of all kinds more straightforward. That, in turn, means that some high-powered transformations — such as those required for scaling on parallel hardware — much easier to accomplish without requiring enormous input from the programmer.

What does the future language look like?

According to this thesis, a language based on these principles would have a sound semantic foundation, would be easy to understand and would not require more from the programmer than was required by the problem. And it would be easy to deploy on systems consisting of many cores.

What’s not to like? In the subsequent posts I will look at each of these principles in turn in a little greater depth.

(Software) Architecture = Policy + Mechanism

In the early 1980′s Bob Kowalski made famous an interesting equation: Program = Logic + Control. The idea of that equation was that programming was essentially a combination of logic — i.e., what you wanted done — with algorithm — how you wanted it done.

It is a fairly commonplace fact that any non-trivial program has a similar flavor to it: there is often a substantial amount of machinery that is used to deliver the value in the program; together with some form of policy statement/expression that governs the precise requirements for a particular execution of the program.

The larger the program, the more obvious it is that there is this layering into mechanisms and policies. For example, one could argue that a word processor’s mechanisms are all the pieces need to implement text editing, formatting and so on. If the word processor supports styles, especially named styles, then these styles are a simple form of policy.

At larger scales, when considering networked applications for example, there are often formal languages used to express the different kinds of policy that apply: security policies, management policies and so on.

So, my thesis of the day is that Architecture consists of the specification of the mechanisms together with the specification of the policies that may apply.

Is this useful? Being clear about the `natural divisions’ in a complex structure is the first step in making that structure tractable.

Sub-turing complete programming languages

Here is an interesting intuition: the key to liberating software development is to use programming languages that are not, by themselves, turing-complete.

That means no loops, no recursion ‘in-language’.

Why? Two reasons: any program that is subject to the halting problem is inherently unknowable: in general, the only way to know what a turing-complete program means is to run it. This puts very strong limitations on the combinatorics of turing-complete programs and also on the kinds of support tooling that can be provided: effectively, a debugger is about the best that you can do with any reasonable effort.

On the other hand, a sub-turing language is also ‘decidable’. That means it is possible to predict what it means; and paradoxically, a lot easier to provide a rich environment for it etc. etc. An interesting example of two languages on easier side of the turing fence are TeX and CSS. Both are designed for specifying the layout of text, TeX is turing complete and CSS is not.

CSS is still young but, for all its warts, an order of magnitude easier to work with than TeX. Further more, there is actually no much that TeX can do that CSS cannot; with the proviso that sometimes missing functionality must be ‘buried’ in the CSS language.

For example, TeX is powerful enough to implement an indexing scheme, CSS is not. It would be easy enough to extend a CSS engine to provide key indexing mechanisms.

I think that there are many fundamental merits to this approach to programming languages. The biggest is that a sub-turing complete language would (have to) be inherently more high-level than a turing-complete language. Secondly I believe (no evidence presented here) that such a language could be closer to the way people think about tasks than programming in Java (or even Haskell).

On programming languages and the Mac

Every so often I dig out my Xcode stuff and have a go at exploring developing an idea for Mac OS X. Everytime the same thing happens to me: Objective-C is such an offensive language to my sensibilities that I get diverted into doing something else.

All the lessons that we have learned the hard way over the years — the importance of strong static typing, the importance of tools for large scale programming — seem to have fallen on deaf ears in the Objective-C community. How long did it take to get garbage collection into the language? I also feel that some features of Objective-C represent an inherent security risk (in particular categories) that would make me very nervous to develop a serious application in it.

As it happens, I am currently developing a programming language for Complex Event Processing.
Almost every choice that I am making in that language is the opposite to the choice made for Objective-C — my language is strongly, statically typed; it is designed for parallel execution, it uses a functional programming foundation, it is symbolic in nature, designed to permit development of large programs, etc. etc.

Hence my allergic reaction and yet again I veer off into something that does not involve actually making a beautiful application for a platform that I much admire.

I have to also admit that I regret Apple’s choice to abandon Java development. I am not an apologist for Java, but it is significantly better for programming in than Objective-C.

I have heard that some of the features of Cocoa are impossible to do in Java. I have strong doubts about that.

I just wish that Apple’s sense of design extended to the underlying technologies as much as it does to user engineering.

About the right tools for the job

Some time ago I was involved in a running debate about whether we should be using Ruby on Rails rather than the Java stack (junkyard?) that we were using. At the time, I did not really participate in the discussion except to note that everything seemed to be at least 5 times too difficult. I had this strong intuition that there were so many moving parts that that was the problem. The application itself was not really that hard. My assertions really ticked some of my colleagues off; for which I apologize; sort of.

I guess that I come from a tradition of high-level programming languages, by high level, I would say that I would consider LISP to be a medium level language, and Prolog is slightly better. I would say that it is a pretty common theme of my career that I end up having to defend the position of using high-level tools. I have gotten a number of arguments, ranging from “it will not be efficient enough” to “how do you expect to find enough XX programmers?”. I used to try to answer these questions, because I thought that they are raised in good faith. Most of them, with the possible exception of the last, have all but been made moot by progress in silicon and compiler technology.

Anyway, afterwards, I decided to take a more serious look at RoR. I picked up a book on it, and followed along. At the end of three days, I had managed to replicate perhaps 60-70% of the functionality of the site I had been working on; and I became furious.

If we had used RoR at the beginning, I began to think, it is entirely possible that I would still have a share in a company that was going to go places. Not that RoR is perfect; far from it. For example, when something goes wrong with your Ruby program a neophyte has very little support. And Ruby is a pretty weird language. But, to replicate 60% of an application that had taken 5 man years of developer effort in two days really pissed me off.

You see, one key reason that everything fell apart was that we had a competitor; a competitor who got out into the market before we did. It is hard to be sure, but we did not get the feeling that they had started before us even. What they did do was use a much easier to get going technology (PHP). So, maybe PHP does not scale; but so what? The first to market can gain enough time to re-implement should the idea prove sufficiently interesting.

So, the next time someone says that they can’t find programmers, or some other reason for not using advanced techniques; my response is likely to be more robust. If we need to train people, then so be it. Using technology that lets you get going quickly can make the difference between life or death for a startup.

I may even start pushing some of the languages that I have been involved in developing…

Another thought about Turing and Brooks

Rodney Brooks once wrote that robots would be human when treating them as though they were human was the most efficient way of interacting with them. (Not a precise quote.)

This is an interesting variation on the Turing test. It assumes that we decide the smartness of machines in the context of frequent interactions with them. It also builds on an interesting idea: that in order to deal with another entity, be it human, animal or mineral, we naturally build an internal model of the entity: how it behaves, what it can do, how it is likely to react to stimuli etc. That model exists for all entities that we interact with; a rock is not likely to kick you back, your word processor will likely crash before you can save the document etc.

When the most effective way to predict the behavior of a machine is to assume that it has similar internal structure to ourselves, then it will, for all intents and purposes, be human.

So, here is another thought: how do we know that another human is human? Although this sounds flippant, there are many instances where we forget that another person is a real person: soldiers must do this in order to carry out their job; terrorists must de-humanize their enemy in order to justify their atrocities.

I think that we only really recognize another person as human when we can relate personally to them. In most cases, what that means, is recognizing the other person’s behavior as symptomatic of something that we ourselves have experienced. In effect, the model building process consists largely of seeing someone’s reaction to an event and relating it to something that we ourselves have experienced. (An aside: how often, when told of some event or situation as it affects someone we know, do we react by quoting something from our own past/situation that somehow is analogous?)

At the heart of this phenomenon is something curious: conventionally, the Turing test is phrased in such a way as to decide whether the other entity is human or not. However, it may be more accurate to say that what we do everyday is try to decide if we ourselves could somehow be that other person (or entity) we are interacting with? Furthermore, it may be, that this emphasizing is only possible because fundamentally, we are all clones to 99.99%: we are all running the same operating system in our mind as it were. We can predict the other person’s responses because they could be our responses also.

What does this mean? Well, perhaps we need a new formulation of Turing’s test: an entity can be considered human if we believed that we would react the way that the entity reacts had we been that entity. Another consequence may be that machines may be smart and intelligent etc. but not human simply because the code that they run is not our code. A cultural difference between people and machines if you will.

Turning Turing upside down

I am probably not alone in visualizing Turing’s Universal Machine as a little animacule walking over a linear landscape of ones and zeros:

The great innovation of thinkers such as Turing and others was to reduce the complex world of algorithms and functions into something simple and elemental: all computable functions can be thought of as state machines operating over a large collection of ones and zeros, presence and absence.

There are arguably many differences between a Turing Universal Machine and a modern browser (quite apart from the fact that, being a Javascript interpreter makes a browser a TUM). But for me, one of the most striking differences is that where a TUM is an animacule in a universe of one and zeroes, the browser is an animacule in a universe of HTML, CSS, HTTP and so on.

The browser understands a different world than Turing’s computer. Were we to draw a browser as an animacule, it should look like:

There are similarities, and if you were to look at it from the perspective of a binary TUM, you would be hard put to see a significant difference between a browser and a regular TUM. But that would be missing an essential difference.

The browser understands a different world than the TUM because the concepts that underlie its state machine are concepts from the world of the web, not the world of ones and zeros. Its semantic engagement with the world is different; arguably higher level than the binary TUM. The browser stands on the shoulders of the binary TUM, but nevertheless reaches higher.

What, one may ask, would the level above the browser’s level look like? And is there an infinite stack of levels waiting for our discovery?