Friday, April 4, 2014

Scalable program architectures

Haskell design patterns differ from mainstream design patterns in one important way:

  • Conventional architecture: Combine a several components together of type A to generate a "network" or "topology" of type B

  • Haskell architecture: Combine several components together of type A to generate a new component of the same type A, indistinguishable in character from its substituent parts

This distinction affects how the two architectural styles evolve as code bases grow.

The conventional architecture requires layering abstraction on top of abstraction:

Oh no, these Bs are not connectable, so let's make a network of Bs and call that a C.

Well, I want to assemble several Cs, so let's make a network of Cs and call that a D

...

Wash, rinse, and repeat until you have an unmanageable tower of abstractions.

With a Haskell-style architecture, you don't need to keep layering on abstractions to preserve combinability. When you combine things together the result is still itself combinable. You don't distinguish between components and networks of components.

In fact, this principle should be familiar to anybody who knows basic arithmetic. When you combine a bunch of numbers together you get back a number:

3 + 4 + 9 = 16

Zero or more numbers go in and exactly one number comes out. The resulting number is itself combinable. You don't have to learn about "web"s of numbers or "web"s of "web"s of numbers.

If elementary school children can master this principle, then perhaps we can, too. How can we make programming more like addition?

Well, addition is simple because we have (+) and 0. (+) ensures that we can always convert more than one number into exactly number:

(+) :: Int -> Int -> Int

... and 0 ensures that we can always convert less than one number into exactly one number by providing a suitable default:

0 :: Int

This will look familiar to Haskell programmers: these type signatures resemble the methods of the Monoid type class:

class Monoid m where
    -- `mappend` is analogous to `(+)`
    mappend :: m -> m -> m

    -- `mempty` is analogous to `0`
    mempty  :: m

In other words, the Monoid type class is the canonical example of this Haskell architectural style. We use mappend and mempty to combine 0 or more ms into exactly 1 m. The resulting m is still combinable.

Not every Haskell abstraction implements Monoid, nor do they have to because category theory takes this basic Monoid idea and generalizes it to more powerful domains. Each generalization retains the same basic principle of preserving combinability.

For example, a Category is just a typed monoid, where not all combinations type-check:

class Category cat where
    -- `(.)` is analogous to `(+)`
    (.) :: cat b c -> cat a b -> cat a c

    -- `id` is analogous to `0`
    id  :: cat a a

... a Monad is like a monoid where we combine functors "vertically":

-- Slightly modified from the original type class
class Functor m => Monad m where
    -- `join` is analogous to `(+)`
    join :: m (m a) -> m a

    -- `return` is analogous to `0`
    return :: a -> m a

... and an Applicative is like a monoid where we combine functors "horizontally":

-- Greatly modified, but equivalent to, the original type class
class Functor f => Applicative f where
    -- `mult` is is analogous to `(+)`
    mult :: f a -> f b -> f (a, b)

    -- `unit` is analogous to `0`
    unit :: f ()

Category theory is full of generalized patterns like these, all of which try to preserve that basic intuition we had for addition. We convert more than one thing into exactly one thing using something that resembles addition and we convert less than one thing into exactly one thing using something that resembles zero. Once you learn to think in terms of these patterns, programming becomes as simple as basic arithmetic: combinable components go in and exactly one combinable component comes out.

These abstractions scale limitlessly because they always preserve combinability, therefore we never need to layer further abstractions on top. This is one reason why you should learn Haskell: you learn how to build flat architectures.

34 comments:

  1. Great read (as always).

    But I am missing a real (world) example that explains this concept. To me it is not clear how I would take the step from Monoids and Functors (which I understand in terms of data) to parts of a program.

    ReplyDelete
    Replies
    1. Just take any aspect of your program and start asking yourself if you can make it "addable". For example, if your program has plugins, ask if you can add plugins together to make a new plugin. If your program has event sources, ask yourself if you can add event sources together to create a new event source. If your program interacts with clusters, ask if you can add multiple clusters together to make a new cluster. The more you do this exercise the more you will start seeing these patterns.

      Delete
    2. This reply gave me my EUREKA. Thank you!

      Delete
    3. Parser combinators are a good real world example of such combinability.

      Delete
  2. Isn't a bit weird to present category as a typed monoid ? As it is usually the notion of monoid that is derived from the category theory. I can see that the Haskell definition of it matches a monoid though.

    ReplyDelete
    Replies
    1. I also prefer to think of a Monoid as a special case of a category but I was just experimenting with teaching the idea in reverse for this post.

      Delete
    2. On the contrary; I usually think of a monoid as a set with a not-necessarily-invertible binary operation (eg, addition of natural numbers), and it just so happens that there's a funny trick for realizing these structures as categories. (As a category with a single object and a bunch of arrows which become the 'elements' of the monoid, under the operation of function composition.) This has almost nothing to do with how category theory is normally actually used, though: one-object categories are a pretty degenerate case.

      In Sage (sagemath.org) we have a notion of category explicitly because we're building, well, actual categories. The great thing about categories is that they also contain information about the mappings between objects, which is structure not encompassed by the usual object-oriented programming paradigm. That and, yeah, functors.

      Sage is written mainly in Python, but, like Haskell, makes functions first-class objects. Good ideas deserve to spread!

      Delete
  3. In Java 8, the "thenComparing" method of java.util.Comparator is an example of the "monoidal" design pattern.

    ReplyDelete
  4. I love the way you've oversimplified Category Theory just to the point of understandability. :-) A great read.

    ReplyDelete
  5. Interesting! I think there is a typo in Monad (you named it Functor)

    ReplyDelete
    Replies
    1. That's a class constraint. It is more clear if you parenthesize it:

      class (Functor m) => Monad m where ...

      That means that anything that anything that implements `Monad` must also implement `Functor`. The real `Monad` class does not have this constraint, but it should and it will be added soon (indirectly, via an `Applicative` constraint, which is even more useful).

      Delete
  6. There is nothing Haskell specific about the ideas you are presenting, and it's pretty misleading to call this a 'Haskell architecture'. Haskell certainly does not have a monopoly on the concept of a type which is closed under a set of operations.

    ReplyDelete
    Replies
    1. For all practical purposes Haskell does have a monopoly on this in the programming world. Haskell is the only language where this style of programming is idiomatic.

      Delete
    2. I don't know. Regular OO languages allow this as well. In fact some patterns are even more natural in that setting. You can put various combinator methods in a superclass and then have subclasses implement their own special versions of those methods while still remaining in the same class hierarchy.

      Delete
    3. If you insert enough weasel words, "for all practical purposes", "idiomatic", etc, then I can't exactly disprove what you're saying, but I don't agree with your characterization, and I know a lot of functional programmers in other languages would also take issue with it.

      I am happy that you have discovered good programming ideas via Haskell and like blogging about them, but please don't assume Haskell has a monopoly on these ideas. It really doesn't, and if it think so, I'd say you have not spent enough time in other language communities. IMO, posts like this contribute to unhelpful language tribalism that I'd really like to see go away.

      Delete
    4. Compositional programming (in the category sense of the word composition) still feels like a second class citizen in other programming languages, including other functional languages. When I say second-class I mean that you have to justify its use because there is another prevailing way to solve the problem (typically involving objects or mutation). I don't enjoy having to justify this compositional style to others so I would prefer to advocate stridently for a language where this style is the default and pragmatic choice.

      Delete
    5. You probably should't generalize in this way about language communities you aren't actively involved with.

      Your comment about having to justify FP in other languages is not relevant. Even if that were so (which it's not in general), that doesn't make functors, categories, monoids, and other aspects of FP Haskell-specific concepts. Is a 'functor' or monoid a Haskell concept? An Idris concept? An Agda concept? None of the above! Just say that the concepts are useful / important for writing software, and use Haskell or as the vehicle for communicating that. Pretending that a general concept is Haskell-specific is not the way to advocate for Haskell, if that's what you're trying to do!

      Delete
    6. Alright, I'll try not to beat the Haskell-specific drum when talking about theory so much.

      Delete
    7. Clearly many "Haskell concepts" would apply to languages like Agda and Idris, since those languages are heavily influenced by (and implemented in) Haskell, so it would be more justified to call them "FP concepts".

      However, Haskell's laziness and typeclasses ('being lazy with class') make some idioms particularly suitable which may be regarded as 'advanced topics' or 'second-class citizens' in other FP languages (eg. ML, Scheme or Scala).

      Monads spring to mind as as such a "Haskell concept"; even though they're now spreading into other languages, they were brought into programming specifically to model lazy IO, and were implemented as a typeclass in Haskell. The same can be said of Applicative and Arrow. Using these concepts in other languages could arguably be called 'writing Haskell-style code'.

      Of course there are languages like Clean, Curry and Idris which are, or can be, 'lazy with class', but Haskell's age and popularity will make it the posterchild of this feature-set for some time to come. Hence it's fine for introductory, thought-provoking articles like this to focus on it. Those of us who care about languages like Agda and Idris, or even know that they exist, are not the intended audience.

      Delete
    8. I have to come to Gabriel's defense. I am deeply embedded in the C++ community and I can testify to how difficult it is to express and justify certain ideas about composability in that language. I keep pointing out these patterns, like monoid or monad, but since there is not generic workable expression for them in C++, it just sounds like abstract nonsense. And if you try to abstract them, you run into template hell and/or performance issues. In Haskell these ideas are first class citizens at the level of typeclasses. Haskell programmers think in terms of monads. C++ programmers don't recognize a monad when it hits them in the head (the std::future monad being a recent example I had to justify to the C++ Standard Committee).

      Delete
  7. errata (duplicated words):
    several components together of type A *together* to generate
    layering *on* abstraction on top of abstraction
    you learn *to* how to build

    ReplyDelete
  8. I don't get what you mean by "Functor" and combine horizontally vs. vertically, or how this applies to architecture. I'd love to see this line of thought expanded.

    ReplyDelete
    Replies
    1. Yeah, the terms are a bit vague and I was hoping the type signatures would clear things up.

      Monads let you combine nested functors, like this

      m (m (m (m x))) -> m x

      Applicatives let you combine tuples of functors like this:

      (f a, f b, f c, f d) -> f (a, b, c, d)

      Does that help?

      Delete
  9. This is a very nice observation (and explanation). Actually it makes a lot of sense even outside of the Haskell world. Thanks for sharing!

    ReplyDelete
    Replies
    1. You're welcome!

      You're right that this is not Haskell-specific. I didn't mean to imply that only Haskell programmers can do this.

      Delete
  10. To me, it seems that this composability of what you call Haskell design patterns stems (at least also) from its algebraic types and how easily (in terms of syntax and memory management) one value is transformed into another.

    ReplyDelete
    Replies
    1. Yes, that definitely helps, too.

      An example I love to use is concurrent streams. Suppose we model a concurrent stream of `a`s as:

      Input a

      Then let's assume that `Input a` forms a `Monoid` where mappend interleaves two streams and mempty is the empty stream. Now we can combine multiple streams of the same type of value.

      Now suppose we want to combine two streams of different types of values:

      sA :: Input A
      sB :: Input B

      We can do this if `Input` is a `Functor`, too:

      sBoth :: Input (Either A B)
      sBoth = mappend (fmap Left sA) (fmap Right sB)

      This shows how algebraic data types and functors make it easy to get things to agree on a common type so that you can combine them.

      Delete
  11. This comment has been removed by the author.

    ReplyDelete
  12. Following the addition intuition. When you add some numbers you can’t go back to the addends.

    Do you know of any situation where this is not desirable, i.e., where a “foldable/unfoldable” (sorry for the sloppy terminology) structure is needed?

    ReplyDelete
    Replies
    1. Sorry for the late reply. So if I have a function of the shape:

      f :: A -> A -> B

      ... what I will usually do is see if I can decompose `f` into two functions, like this:

      g :: A -> B

      h :: B -> B -> B

      f a1 a2 = h (g a1) (g a2)

      Delete
  13. So you decompose `f` in order to preserve the scalability property with `h`, correct?

    Even so, I can’t apply this decomposition to my original question. What am I missing?

    ReplyDelete
    Replies
    1. It's hard for me to say without knowing more about your code.

      Delete