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
In a declarative programming language, we might identify a subprogram which we can namef((a + b) / 2,(a + b) / 2)
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.let average = (a + b) / 2 in f(average,average)
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
uses a recurring calling pattern to the functionf(a,a+b) + f(a,a+c) + f(a,a+d)
f. This pattern is easily captured by a subprogram that we can call
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 variablelet f2(x) = f(a,a+x) in f2(b) + f2(c) + f2(d)
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.
Or we might declare the combinatorwithinParentheses(p) = token('(') >>> p >>> token(')')
many(p), which forms a parser which accepts whatever p accepts, zero or more times in a sequence (this is often written
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.many(p) = (p >>> many(p)) ||| epsilon