Think Before Coding

To content | To menu | To search

Friday, April 11, 2014

Monoidal Event Sourcing

I Could not sleep… 3am and this idea…

 

Event sourcing is about fold but there is no monoid around !

 

What’s a monoid ?

 

First, for those that didn’t had a chance to see Cyrille Martaire’s  fabulous explanation with beer glasses, or read the great series of post on F# for fun and profit, here is a quick recap:

 

We need a set.

Let’s take a simple one, positive integers.

 

And an operation, let say + which takes two positive integers.

 

It returns… a positive integer. The operation is said to be closed on the set.

 

Something interesting is that 3 + 8 + 2 = 13 = (3 + 8) + 2 = 3 + (8 + 2).

This is associativity: (x + y) + z = x + (y + z)

 

Le last interesting thing is 0, the neutral element:

x + 0 = 0 + x = x

 

(N,+,0) is a monoid.

 

Let say it again:

(S, *, ø) is a monoid if

  • * is closed on S  (* : S –> S > S)
  • * is associative ( (x * y) * z = x * (y * z) )
  • ø is the neutral element of * ( x * ø = ø * x = x )

warning: it doesn’t need to be commutative so x * y can be different from y * x !

 

Some famous monoids:

(int, +, 0)

(int, *, 1)

(lists, concat, empty list)

(strings, concat, empty string)

 

The link with Event Sourcing

 

Event sourcing is based on an application function apply : State –> Event –> State, which returns the new state based on previous state and an event.

 

Current state is then:

fold apply emptyState events

 

(for those using C# Linq, fold is the same as .Aggregate)

 

Which is great because higher level functions and all…

 

But fold is event more powerful with monoids ! For integers, fold is called sum, and the cool thing is that it’s associative !

 

With a monoid you can fold subsets, then combine them together after (still in the right order). This is what give the full power of map reduce: move code to the data. Combine in place, then combine results. As long as you have monoids, it works.

 

But apply will not be part of a monoid. It’s not closed on a set.

 

To make it closed on a set it should have the following signature:

 

apply: State –> State –> State, so we should maybe rename the function combine.

 

Let’s dream

 

Let’s imagine we have a combine operation closed on State.

 

Now, event sourcing goes from:

 

decide: Command –> State –> Event list

apply: State –> Event –> State

 

to:

decide: Command –> State –> Event list

convert: Event –> State

combine: State –> State –> State

 

the previous apply function is then just:

apply state event = combine state (convert event)

 

and fold distribution gives:

 

fold apply emptyState events = fold combine emptyState (map convert events) 

 

(where map applies the convert fonction to each item of the events list, as does .Select in Linq)

 

The great advantage here is that we map then fold which is another name for reduce !

 

Application of events can be done in parallel by chuncks and then combined !

 

Is it just a dream ?

 

Surely not.

 

Most of the tricky decisions have been taken in the decide function which didn’t change. The apply function usually just set state members to values present in the event, or increment/decrement values, or add items to a list… No business decision is taken in the apply function, and most of the primitive types in state members are already monoids under there usual operations…

 

And a group (tuple, list..) of monoid is also a monoid under a simple composition:

if (N1,*,n1) and (N2,¤,n2) are monoids then N1 * N2 is a monoid with an operator <*> ( (x1,x2) <*> (y1,y2) = (x1*y1, x2¤y2)) and a neutral element (n1,n2)…

 

To view it more easily, the convert fonction converts an event to a Delta, a difference of the State.

 

Those delta can then be aggregated/folded to make a bigger delta.

It can then be applied to a initial value to get the result !

 

 

The idea seams quite interesting and I never read anything about this.. If anyone knows prior study of the subject, I’m interested.

 

Next time we’ll see how to make monoids for some common patterns we can find in the apply function, to use them in the convert function.

Thursday, April 4, 2013

C# Static interfaces - Take 3

You may believe it or not, but the post that drains most of the traffic of this blog, is the one about C# static interfaces !

 

In october 2009, I simply tried to imagine where the idea of C# static interfaces could lead us, and, since then, I have more viewed pages (> 15%) on this post than on my home page !

 

And since then, nothing moved in this area in the C# langage, and I don’t expect it to happen soon.

 

But some other thing happened…

 

F#

 

Yes F# is out and running on almost all platforms, and it can do what I described in the previous post.

 

The thing is called Statically Resolved Type Parameters and is closer to C++ templates than from C# generics.

 

The trick is that you can define an inline function with statically resolved types, denoted by a ^ prefix. The usage of defined methods on the type is not given here by an interface, but by a constraint on the resolved type :

let inline count (counter: ^T) =
    let value = (^T: (member Count : int) counter) 
    value

here , the count function takes a counter of type ^T (statically resolved).

The second line express that ^T actually should have a member Count of type int, and that it will call it on counter to get the result value !

 

Magic !

 

Now, we can call count on various types that have a Count member property like :

type FakeCounter() =
    member this.Count = 42;

or

type ImmutableCounter(count: int) =
    member this.Count = count;
    member this.Next() = ImmutableCounter(count + 1)

or

type MutableCounter(count: int) =
    let mutable count = 0
    member this.Count = count;
    member this.Next() = count <- count + 1

without needing an interface !

For instance :

let c = count (new FakeCounter())

True, this is compile time duck typing !

 

And it works with methods :

let inline quack (duck: ^T) =
    let value = (^T: (member Quack : int -> string) (duck, 3))  
    value

This will call a Quack method that takes int and returns string with the value 3 on any object passed to it that has a method corresponding to the constraint.

And magically enough, you can do it with static methods :

let inline nextThenstaticCount (counter: ^T) =
    (^T: (member Next : unit -> unit) counter)
    let value = (^T: (static member Count : int) ()) 
    value

this function calls an instance method called Next, then gets the value of a static property called Count and returns the value !

It also works with operators :

let inline mac acc x y = acc + x * y

notice the signature of this function :

acc: ^a -> x: ^c -> y: ^d ->  ^e
    when ( ^a or  ^b) : (static member ( + ) :  ^a *  ^b ->  ^e) and
         ( ^c or  ^d) : (static member ( * ) :  ^c *  ^d ->  ^b)

It accepts any types as long as they provide expected + and * operators.

 

The only thing is that a specific implementation of the function will be compiled for each type on which it’s called. That’s why it called statically resolved.

 

You can use this kind of method from F# code but not from C#.

 

Anyway…

No need for static interfaces in C#, use F# !