The interfaces of libraries in functional programming

When I started learning functional programming I asked myself what was considered a good API for a functional programming library. Recently, some newcomers asked me the same question.

So, I thought that it was a good idea to try to articulate an answer in a blog post.

What is functional programming about ?

The first question that people are asking themselve is really what is functional programming about. So, they read stuff about immutability, about functions as first class values ... But, I think it is missing the point.

For me functional programming is about composability. Let's take a very simple (and very artificial) example:

a + b

The + operator for integer as implemented in your hardware is perfectly understood. You know it is commutative. You know what is happening when you add 1 to the maximum representable positive integer etc ...

And yet, in spite of the fact that you perfectly understand this operator, you can't answer simple questions like:

f(x) + g(x) = g(x) + f(x) ? 
f(x) + f(x) = 2 * f(x) ?

It may be true or wrong. You need to look at the code of f and g to be sure. And this is due to side effects in general (IO; shared state ...)

Side effects are making programming anti modular unless they are controlled and do not break composability. What composability means is that you can understand the meaning of your complex expression from the meaning of its parts. And so, you can progressively build more and more complex expressions and increase the level of abstraction and reuse. Because the semantic of the expression remain understandable and manageable due to its composable nature.

In a functional program what is finally important is that it is a value oriented language. Your f(x) is not executed to produce side effects and eventually a result. Your f(x) is a complex expression which denotes a value. Like 4-4, 5-5 are different ways to write 0. A value just is. It can't be changed. It has no side effect. It can only be combined with other values to produce other values. A value is the expression that you can't simplify any further. 4-4 is not considered a value and can be simplified into the expression 0. This simplification process is generally called evaluation (but note that it is more subtle that you may think from this post)

Of course, functional programming gets its name from the fact that one category of values is made of functions and functions are values like any other values : they can be created as result of evaluation. They can be used as argument of other functions. They can be used in data structure.

But there are several other types of values available. Some values could even represent side effects (without doing the side effect themselves).

What is an API for a library ?

So, what is the relation with the API of a functional program ?

The problem is that composability is not the goal of traditional languages. First on a semantic level they don't really do any effort for ensuring the composability. It is far too easy to shoot yourself in the foot because of uncontrolled side effects.

Then, technically they don't really help by not supporting algebraic types (or discriminated union). Let's look at the simple example of composition:

f(g(x))

So, in C you may have:

err=f(&result);

which is breaking composability.

You could try to use a struct to package the error and result (and a tag to distinguish the cases). But, in any case what is needed is the possibility of returning different results. And what we have is only the possibility of returning all results and use a tag to select one of them hoping we will never make a mistake and select the wrong one.

Or you could use a hierarchy of classes in OO and use the dynamic type to distinguish between error or result objects. And you may have to do dynamic casts.

So, although it is possible to write things so that they can be syntactically composed, it is generally verbose and can easily introduce additional mistakes. This added to the fact that on a semantic level side effects can easily break everything then we can conclude that composability is not really favored in most languages.

But, if composability was just about the composition of two functions it would be rather limited. Thank to the fact that functions are values like any other ones then there is even more flexibility.

You can build new abstractions and combine the functions in different ways :

f . g 
f >>= g 
f `myOperator` g 

So, what we start to see is that functional programming is favoring the writing of complex expressions not only from standard values like integer and strings (the nouns) but also from functions (the verbs). But it is also helping us define new ways for combining and glue all those elements together. So, what we are building are sentences made from different values and higher order functions.

The types and higher order values are defining the grammar of those sentences.

It leads to the conclusion that a good API for a functional program is a domain specific language.

If there is no composability in the interface then you should think about it more. Perhaps it is normal but most of the time it means the added value of functional programming has not been used to its full potential.

So, a good API is a domain specific language. You think I am crazy ? Let's look at a simple example. For the lists, the usual functions of an API could be:

empty :: [a]
cons :: a -> [a] -> [a]
append :: [a] -> [a] -> [a]

In that case, the DSL has an interesting property : you're never getting out of the type [a] which is always the type of the result. This API is an example of universal algebra and we can replace this API with an algebraic data type.

data MyList a =  Empty 
              |  Cons a (MyList a)
              |  Append (MyList a) (MyList a)

The functions can then be implemented as

myEmpty = Empty
myCons = Cons 
myAppend = Append 

Those functions are indeed doing nothing more than building an element of the type.

Then we could have:

eval :: MyList a -> [a]
eval Empty = []
eval (Cons a l) = a:eval l 
eval (Append a b) = eval a ++ eval b 

This clearly shows that the API can be seen as a little language since the syntax and semantic have been separated through the use of an algebraic data type.

And it is exactly what a good API should be in the functional programming world : the definition of a language.

Functional programming is of course not the only category of languages focusing on composability. Concatenative languages also have this focus.

blog comments powered by Disqus