- Stage 0: no functions, and thus, no abstraction
- Stage 1: functions, but no higher-order functions
- Stage 2: higher-order functions, combinator libraries
- Stage 3: typeclasses, abstracting over combinator libraries
- Stage 4: abstracting over typeclasses
Stage 3 is the generalization of combinator libraries - code that is generic across multiple such libraries - think of the generalized combinator library we obtain from a monad, or a traversable. This removes the duplication found due to common patterns in collections of higher-order functions. I wonder - was Haskell's type system and commitment to purity a prerequisite to developing this stage of programming? In principle stage 3 is possible in any dynamic language with first class modules and first class functions.
And stage 4... well, we're only starting to see what stage 4 looks like. In stage 3 programming, we can write code polymorphic to any instance of the typeclass, but there could be duplication in the implementations of different typeclass instances - for instance, you might create a data type that is essentially a list of trees, but in giving the
Applicativeinstance for your type, you start from scratch. In stage 4 programming, you'd assemble your type and appropriate typeclass implementations from combinators. This is done a little bit here and there in FP - you might compose Applicatives or take their product, but in stage 4 this style is pervasive and taken to its logical limit.
Stage 4 requires some serious rewiring of your programming brain. Forget concrete types or concrete type implementations. You don't implement a tree datatype. You assemble the type and all its useful functions from a catalog of typeclass combinators. Category theory would become an essential tool for programming in this style ("oh, there's a natural isomorphism between this type and blah, just gotta establish this isomorphism to get all that functionality"). Would we then see category theory and this style of programming taught as part of the standard computer science curriculum? Maybe...
I don't know of any any language that supports stage 4 programming adequately. It seems to require, among other things, first class and higher order modules. Probably more powerful type systems, too. Ed Kmett has an interesting language he's been working on, called Kata. Based on what he's told me about it, it looks specifically designed to make stage 4 programming easy. Interestingly, I think he's given up on static typing.
What do you think? Is stage 4 the future of (functional) programming?