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.