Monday, April 20, 2009

Towards Combinator based API design

I was listening to the presentation by Alex Payne, the Twitter API lead, that he delivered at Stanford very recently. A nice presentation that sums up the philosophies and practices that they followed in the evolution of APIs for Twitter. In case you are interested in API design, Josh Bloch also has a great video up as part of a Javapolis interview that discusses in details all the nuances of designing good and robust APIs.

These days, we are getting more and more used to interesting programming languages, which, apart from being powerful themselves, also mostly happen to share the wonderful ecosystem of common runtimes. As Ola Bini noted sometime back on his blog, it is a time when we can design the various architectural layers of our application in different languages, depending on the mix of robustness, type-safety and expressiveness that each of them demands. Client facing APIs can be focused more towards expressiveness, being more humane in nature, a pleasure to use, while at the same time offering modest error handling and recovery abilities. But whatever the layer, APIs need to be consistent, both in signature and in return values.

One of the very important aspects of API design is the level of abstraction that it should offer to the user. The ideal level comes out only after a series of exploratory evolutions, refactorings and user implementations, and can often lead to loss of backward compatibility within the existing user community.

One of the very powerful ways of API design that many of today's languages offer is the use of combinators. I have blogged on uses of combinator in concatenative languages like Joy - it is truly a great experience as a user to use such compositional API s as part of your application design. Here is one from my earlier post on Joy combinators. It finds the arithmetic mean of a list of numbers ..

dup  0  [+]  fold  swap  size  /


The API is beautiful in the sense that it evolves the intention ground up and makes use of smaller combinators in building up the whole. This is beautiful composition.

In one of the comments to my earlier post, James Iry mentioned "I remain unconvinced that concatenative languages are really buying much over applicative languages, as interesting as they are". Since then I have been dabbling a bit with Haskell, a pure functional language that does many things right with the notion of static typing, offering powerful point free capabilities along with rich combinator composition ..

A simple pointfree sum ..

sum = foldr (+) 0


and a more complex map fusion ..

foldr f e . map g == foldr (. g) e


The main point is to seek the beauty of API design in expressiveness of the contract through effective composition of smaller combinators. The biggest advantage of combinators is that they offer composability i.e. the value of a bigger abstraction is given by combining the values of its sub-abstractions. And the power of composability comes from the world of higher order functions and their ability to combine them in your programming language, just as you would do the same in mathematics.

Object orientation is not so blessed in this respect. Composition in OOP is mostly confined to designing fluent interfaces that make expressive APIs but can be made useful only in a limited context and of course, without the purity that functional abstractions espouse. The Builder design pattern is possibly the most famous compositional construct in object oriented languages, and often lead to sleak APIs. Here is a great example from Google Collections MapMaker API ..

ConcurrentMap<Key, Graph> graphs = 
  new MapMaker()
    .concurrencyLevel(32)
    .softKeys()
    .weakValues()
    .expiration(30, TimeUnit.MINUTES)
    .makeComputingMap(
      new Function<Key, Graph>() {
        public Graph apply(Key key) {
          return createExpensiveGraph(key);
        }
      }
    );



But Java, being a language that is not known to offer the best of functional features, it is often quite clumsy to compose abstractions in a fluent way that can offer consistent, rich and robust APIs that match the elegance of functional combinators.

Scala is not a particularly rich language for pointfree programming. But Scala offers great library support for combinators. Of course the secret sauce to all these is the rich support of functional programming that Scala offers. Parser combinators that come with Scala standard library help design external DSL s with enough ease and convenience. Quite some time back I had blogged on designing a combinator based DSL for trading systems using Scala parser combinators.

The main power of combinators come from the fact that they are compositional, and it is the presence of non composable features that make combinators hard in some languages. And one of them is shared mutable state. Paul Johnson had it absolutely right when he said "Mutable state is actually another form of manual memory management: every time you over-write a value you are making a decision that the old value is now garbage, regardless of what other part of the program might have been using it". Languages like Erlang enforces confinement of mutable state within individual processes, Scala encourages the same through programming practices, while Haskell, Clojure etc. offer managed environments for manipulating shared state. Hence we have composability in these languages that encourage combinator based API design.

Combinator based API design is nothing new. It has been quite a common practice in the worlds of Haskell and other functional languages for quite some time. Simon Peyton Jones described his experience in ICFP 2000 in applying combinator based API design while implementing a financial system for derivative trading. It was one of those trend setter applications in the sense that "the ability to define new combinators, and use them just as if they were built in, is quite routine for functional programmers, but not for financial engineers".

1 comment:

Jon Harrop said...

"Mutable state is actually another form of manual memory management: every time you over-write a value you are making a decision that the old value is now garbage, regardless of what other part of the program might have been using it"Representing a matrix as a mutable array of floats is an obvious counter example. That is not manual memory management because floats are value types.

In reality, that quote is only arguably true for non-null mutable reference types.