HacWrite - 1 Programming by combination

1 Programming by combination

This thesis is, to a large extent, oriented around programming by combination. By this, we mean the important programming method where you make programs by combining subprograms. The inner details of the subprograms can then be abstracted from, which makes it possible for the human brain to create and understand very complex programs. This methodology has, of course, been practised for many decades in various programming languages. However, it is a method that sometimes is forgotten, and often only used in parts of a program; for example, when doing tasks related to the operating system.

For programming by combination to be pervasive, it is important not only that we have access to a good library of subprograms, but the programming activity must also deal with forming new subprograms suitable for combination. Otherwise, the variety of programs we can write becomes limited because they get too complex. Therefore, programming by combination is also about forming new levels of subprograms.

One important aspect of programming is, of course, which programming language one uses. Different programming languages vary strongly in the support they give us when we want to program by combination. This is especially true when it comes to forming new subprograms. The authors have found that programming languages which are based on the declarative style are suitable in this respect. Declarative programming languages allow us to write programs in a mathematical style. For example, consider the expression

f((a + b) / 2,(a + b) / 2)

In a declarative programming language, we might identify a subprogram which we can name average.

let average = (a + b) / 2 

in f(average,average)

It is important that the activity of forming subprograms should be as easy as possible for the programmer. If the programmer is required to write many more characters than are shown in the previous example, another programming method might become more attractive, namely programming by copy and paste. This will soon result in programs which are complex to understand and maintain, but unfortunately, it is a too widely practised method.

The previous example did not actually introduce a subprogram. It could simply be seen as declaring a local variable. However, in declarative programming languages, we can use the same style when we want to form subprograms. The expression

f(a,a+b) + f(a,a+c) + f(a,a+d)

uses a recurring calling pattern to the function f. This pattern is easily captured by a subprogram that we can call f2.

let f2(x) = f(a,a+x)

in f2(b) + f2(c) + f2(d)

Forming a corresponding subprogram in the popular programming language C, for example, would be more involved. We would first need to declare a new top-level function, then make sure that its name did not collide with some other top-level function in the same source file, and finally, the function would need an extra parameter for the variable a. All parameters would need some type declaration.

As a more advanced example of programming by combination in declarative style, we might consider parsing combinators [Bur75][Wad85] (from now on, we will often talk about combinators when we mean subprograms which are designed for versatile combination). A large number of text parsers can be formed by four combinators:

token(c), which accepts the character c.
p ||| q, which forms an alternative: it either accepts whatever the parser p accepts, or it accepts whatever the parser q accepts.
p >>> q, which forms a sequence: it first accepts whatever p accepts, and then accepts whatever q accepts when given the rest of the text.
epsilon, which parses the empty string.

From these combinators, a programmer might build more useful combinators. Here is a combinator which can be used for parsing things within parentheses:

withinParentheses(p) = token('(') >>> p >>> token(')')

Or we might declare the combinator many(p), which forms a parser which accepts whatever p accepts, zero or more times in a sequence (this is often written p*):

many(p) = (p >>> many(p)) ||| epsilon

Note that in most of these combinators, we have used the possibility to parameterise over subprograms, which is another important feature that declarative programming languages naturally support.