Categorising the Complexities in Programming

Trying to understand what makes programming hard.

As you could tell from my previous post on teaching the basics of programming, I am struggling to understand how what I want domain experts to do with DSLs is different from what we all know as programming. Sure, the obvious one is that one is domain-specific, whereas the other is not, and that the DSLs have more domain-specific concepts and notations. That does make things easier to learn and understand for domain experts.

But are there more fundamental differences? In the introduction to the Programming Basics tutorial I wrote that I don’t want domain experts to have to build their own abstractions — they are expected to use existing ones. That’s of course not really true, because an insurance contract described with a DSL is an abstraction. But it’s not a reusable abstraction.

So, in this post I try to classify different approaches to programming according to the complexities, or challenges in learning, they incur. This is of course just a (hopefully reasonably argued) proposal, there are many other dimensions according to which the space can be structured. An obvious one is size: the bigger a program gets, the harder it is to understand.

Please comment where you agree or disagree.

Workbooks

The simplest form of programming is what I call creating a workbook. Workbooks are characterised by the fact that the program logic and all relevant data is “on the same page”. The obvious example of this approach are spreadsheets, they are essentially 2-dimensional workbooks where every value is addressable by its coordinates. But there are other document-like interfaces, for example, Mathematica Notebooks or IPython/Jupiter Notebooks. They are essentially glorified REPLs where you alternate inputs and outputs, and you can refer to earlier outputs in downstream input expressions.

If your language is functional (which is true for spreadsheets and also most Mathematica Notebooks) then you can re-evaluate every input over and over again, and the outputs update accordingly. So the state of the program is right there on the page (in the cells or the outputs). This is really simple, because everything is right there on the page.

One could also imagine workbooks that organise there state as a tree, and you address parts of the state via path expressions.

An important ingredient to this style of “programming” is the fact that you see the output immediately (“live”). So there is no edit-compile-run cycle. Instead you change functionality or data, and the workbook immediately and automatically updates.

(A comment: I could argue why this style is very simple because it doesn’t have all kinds of complexities. However, I won’t, because the following sections introduce each of those complexities step by step — I don’t want to say everything twice).

Purely Functional Program

So, is a workbook actually a program? I think one could argue either way. But the fact that all relevant data is on the same page (i.e., part of the “program”) makes it a kind of simplistic, degenerated form of a program (which is why I mentioned it first in this categorisation). A “real” program does not know all of the data it might work with at the time of writing the program. This, of course, makes writing such a program harder: the programmer has to anticipate the possible input data, and ensure that the program works correctly for all possible inputs. To express for which data the program is valid, the programmer uses typed arguments. I think creating things that can be parametrised, i.e., things that have some kind of interface, is where programming really starts.

More generally, there is this separation between writing the program and running it. This separation is not there in a workbook, a workbook always runs (or never, depending on your perspective). Which is why using Excel or using Mathematica is often not called programming.

In contrast, in a functional program, the programmer has to abstract from specific inputs. To ensure correctness for all possible inputs, a program must be tested. Here, the programmer supplies (exemplary) data, that (hopefully) covers all corner cases of the program. Again, this requires imagining how the program will run once it is used. You don’t really have to test a workbook — you probably want to check the outputs for plausibility, but testing, in the sense of exploring the input space, is not necessary.

Very often, the person who writes the program (or function, or whatever the granularity is) will be a different person from the person who uses it. Again, this is not the case for creating a workbook.

Imagine structured workbooks, i.e., workbooks with a schema, where users can fill in data into the “holes” of the schema. Like spreadsheets with predefined formulas and certain marked-up cells where users insert values. Then the act of creating such a schema is essentially a functional programming.

State and Time

In both, functional programs and (functional) workbooks, the complete computation can be represented as a single, immutable, never-changing state. In a linear notebook, the state is the outputs. The inputs are essentially step-by-step transformations of the state. Similarly for a functional program: for any given executions (with a set of inputs), you can represent the program execution as a tree of intermediate results; again, the program “is”, it doesn’t “run”. You can debug a functional program through a post-mortem tree of intermediate results.

Enter effects. You get changeable data, i.e., variables in the classical sense. The distance between a program (as source text) and its execution grows. In fact, now you actually do run the program, running means changing the values of variables change over time (as well producing other effects). Representing all values (of variables) of a program execution becomes visually challenging, at the very least you need some kind of time-travel slider thingy. Practically, you now need an actual debugger or various other means of program animation.

Note that this the notion of time I mention here concerns the execution of the program, not time as part of the program data. You can perfectly well write a functional program that performs computations on time values. We have at least two projects that deal with time as part of the domain.

(Re-)Assembling Programs

(The title of this one sucks, I know. I couldn’t find a better one). In the interest of avoiding duplication and “complexity”, we split a program into various parts: we decompose into functions that build on each other, we build hierarchical component structures, we separate concerns, we use extension/ specialisation/inheritance to separate the more general from the more specific.

All of this clearly helps to avoid repetition, and it also makes code easier to test because the individual parts are smaller and better isolated through an interface. The flipside, of course, is that it is now much harder to understand the overall behavior of a program, because you have understand how all these previously separated things fit together and/or interact, intentionally or unintentionally.

It really is a conundrum, isn’t it? We can either keep everything in one place, then there’s no assembly, but the program is a mess, not reusable, and untestable. Or we can separate things, but then it is harder to understand the big picture and be sure that everything works together well. It is not a coincidence that a lot of innovation in programming languages is about solving exactly this challenge.

Operational Concerns

As a software engineer, we don’t just care about implementing an algorithm. We want it to be fast, and scalable, and robust, and secure, and whatever else. It is obvious that this makes things harder, because we have to keep more concerns in our heads when writing the program: not just how data changes, but also how long it takes to change, how this time becomes longer as we add more or bigger inputs, how much memory it will use, what other, unintended (and potentially exploitable) behaviours the program might have, how to recover from (partial) failures, and so on.

And when trying to write a program this way, we usually have to change the original algorithm. Think about sorting: sorting a list naively is easy to do, and a program that does that is easy to understand. Once you make it fast using quicksort, it’s a different story. It takes a while to understand the algorithm, and when looking at a quicksort implementation, it’s not at all obvious that this program sorts a list!

So if you want write code that takes these non-functional concerns into account, this adds another dimension of complexity that was not there before.

Building Abstractions

In some sense, every function is an abstraction. So building abstractions already starts when one writes a functional program. And in fact, this is why functional programming is harder than creating a workbook. But as we all know, building “real” abstractions starts with libraries and frameworks (and, ultimately, languages of course). The reason why this is hard is that you have to abstract to a much higher degree than when writing a plain function.

And often, abstractions are stacked: you build an abstraction and then you use it to build further abstractions. And you potentially use more and more advanced features of your programming language (think: higher-order functions, generic types, or type reflection). Obviously, this is a whole order of magnitude more complex than what we have discussed so far. Because of the much larger input space, testing also become much harder.

So, what can we learn for DSLs?

Of course I have to bring this around to DSLs, right :-) ? Let us see what we can learn from this categorisation for the design of DSLs. And when I say DSLs, I mean DSLs targeted at domain-experts, not DSLs that programmers use to optimise matrix computations.

Workbooks: For the vast majority of DSLs, at least those that we build, the workbook style is not enough. It is necessary that the program will run with different sets of input data. But maybe we could provide a workbook-style interface for testing? Users could define functions and other abstractions and directly test them in the workbook. But then these functions can also be run separately. And we should definitely make sure that programs can be run immediately, at least on example/test data. And there is clearly a use for a Workbook-style DSL for engineering, as Mathematica proves.

Functional: If at all possible, we should design our DSLs in a way where the domain expert only writes functional code. That code calculates values, makes decisions, or, in order to manage state, returns deltas or commands. This functional code is driven by an engine that handles state. Many DSLs fit very well into this schema.

State and Time: If our domain requires stateful programs then make sure that tool support makes the passage of time explicit. Build animators that show how values change over time, build UIs that simulate the resulting program with which users can play, maybe use an immutable persistent data structure to represent the complete state and allow users to go back and forth on the time axis.

(Re-)Assembling Programs: This one is hard. We really got stuck a number of times with domain users when we tried to explain inheritance or, worse, aspects or something. One approach that has worked was to build tool support that allows users to see the assembled version of the separated program. And immediate execution and animation also helps. But only to a point. In the end, the modularization/re-assembly conundrum limits the size and complexity of the kinds of DSLs and/or programs you can expect domain experts to be able to deal with, at least without significant training.

Operational Concerns: Separate them out. Your domain experts should never see any of this in their programs. Of course this is easier said than done, because, for example for performance, you have to build optimising code generators. Or for scalability, you might have to execute the (generated) program reactively or incrementally, so you re-run only as little as possible as some of the inputs change. All of this might have an impact on the language design, the programs have to be written to, for example, support reactive execution.

Building Abstractions: Well, just don’t :-) Put the abstractions relevant to the domain into the language as first-class citizens. And when new abstractions are needed, evolve or extend the DSL. Or at the very least, separate library programmers from library users.

And a note on Excel: we often complain about it being more of a problem than a solution. The reason for this is not that it is a spreadsheet/workbook. The problem is that it is general-purpose. There is no actual DSL involved. And very often, spreadsheets are intended to have a schema (predefined, read-only formulas, plus well-defined places where people can enter values), but Excel (and its users) aren’t good at enforcing one. This is why the use of Excel & Co often ends up in chaos.

Conclusions

If your DSL represents the domain well, then steps one and two (Workbook and Functional Programs) are very much feasible to master for most domain experts I have worked with, especially if you educate and train them a bit (for example, with this tutorial :-)). If it is a good fit, and supported by tools, State and Time also works. But everything beyond this generally belongs to software engineers, and not into DSLs targeted at end users.