Tag Archives: tda

Variance expression in functional programming

This time we’re going to explore how functional programs express variance. We’ll consider the same case as we did for TDA – getting a stored value from a Map, and storing a new value in a Map.

Retrieval

lookup :: Ord k => k -> Map k a -> Maybe a

In Haskell, the variance is expressed in the return type.

data Maybe a = Nothing
             | Just a

We might express this as follows:

variance ⊂ return type

Storage

We want to put a new value into the map.

Once again, the entropy of this function is two, see the previous variance post for further discussion.

Here’s the comprehensive version:

insertLookupWithKey :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> (Maybe a, Map k a)

This function actually allows the caller to do more than our original requirement, so a little explanation of that type signature is perhaps necessary.

(k -> a -> a -> a)

The caller passes in this function, which takes the key, the new value and the old value and produces the value that will be stored (most implementations will simply return the new value, rather than performing a calculation, mind).

Data.Map will only call this function if a value is already present – this information is present in the last part of the type signature:

k -> a -> Map k a -> (Maybe a, Map k a)

This is the part we’re going to focus on. Here we pass the key, new value, and the map to operate on. Note that the return type contains both the possibility of an old value (the presence of which tells us our value transforming function was called) and the new map.

Diversion one: encapsulation in FP

It’s starting to look as though functional programs eschew encapsulation in favour of type signature totality (definitely a thing). This is not true.

  • What if Maybe didn’t export its two constructors?

I fear the answer for some may be “huh”? So, a brief explanation of how this might work.

Haskell makes it relatively simple to obscure your implementation details. At the moment, we know that:

Maybe a = Just a
        | Nothing

In fact though, we only get to know this because the original author allowed those constructors out to play. It would be just as valid to export two functions that did the same but obscure the constructors, like so:

module Maybe (Maybe,just,nothing) where

data Maybe a = Just a
             | Nothing

just :: a -> Maybe a
just = Just
nothing :: Maybe a
nothing = Nothing

instance Functor Maybe where
fmap f (Just a) = Just $ f a
fmap _ Nothing = Nothing

Now, at the point of invocation, we can’t pattern match any more. We have to use the fact that Maybe is an instance of Functor in order to do anything with the value inside; there’s no way at all for us to get it out.

Example: reversing the value, if it exists.

fmap reverse $ lookup "key" map

So, it looks like the core of the FP world; Functors and Monads are very interested in not letting us execute a function on a value directly; you pass the function you would like executed to the enclosing context, and it can choose (based on the value inside) how to execute it.

In particular in Haskell, syntactic sugar (do,<-, etc) is provided to make it appear to the eye that this is not the case. That’s only for humans, though; in reality the value never escapes.

Uh, so what now?

We used the term “return type” on the assumption that it is the last thing we see in the type signature of a function. This is either almost true or almost completely false.

Tony Morris tells us that all Haskell functions take one argument, and, once you’ve read that link, I’ll hope you’ll agree he is right.

This means that for a function which appears to take n arguments there are in fact n - 1 return types. Or, perhaps, they have one return type, and it’s everything we see after the first ->.

We’ll stick with:

variance ⊂ return type

Totalitarianism, dogma and consequences

That’s enough pretentious subheadings -Ed

Just as we distilled OOP into a very dogmatic TDA, we’ve taken a very dogmatic view of what FP is. Effects are delayed until the last possible moment, and mutable state is excised.

Oddly, unlike in the TDA case, our chosen implementation language, Haskell, is very keen on enforcing this dogma. Attempting to perform calculations or effects outside of a function’s type signature is* a compile error.

From here on out, we’ll assume dogmatic FP === FP and that non dogmatic usages of FP languages are charlatanic. This isn’t necessarily true, but it will save us a few words here and there.

(*almost always is. There is always Debug.trace)

Diversion 2: A mirror image

Cast your mind back to our purified TDA map insert. What would it look like if we translate it to Haskell?

put :: (Ord k) => Map k a -> k -> a -> (a -> IO()) -> IO() -> IO()

You can think of a -> IO() as being a bit like Consumer and IO() as being like Runnable. Haskell’s lazy predisposition allows us to pass around putStrLn "nothing here" as an expression without executing it.

Let’s rename that, and fiddle with argument order:

tda_insert :: (Ord k) => k -> a -> Map k a -> (a -> IO()) -> IO() -> IO()

Let’s also consider the core of the FP signature:

fp_insert :: (Ord k) => k -> a -> Map k a -> (Maybe a, Map k a)

Now, recall our stricter, non pattern matching Maybe implementation from earlier. This told us that Maybe is actually a context for executing functions that take an a. It also provides the following:

maybe :: b -> (a -> b) -> Maybe a -> b

If we just plug b = IO() into that, we get:

maybe :: IO() -> (a -> IO()) -> Maybe a -> IO()

and with some further shuffling, it becomes this:

maybe_ish :: Maybe a -> IO() -> (a -> IO()) -> IO()

Now, if we elide Map k a from fp_insert (thus making the state change implicit)

fp_insert_ish :: (Ord k) => k -> a -> Map k a -> Maybe a

…and now, we almost have

tda_insert = maybe_ish . fp_insert_ish

This is very interesting! It feels like we’ve come across a little piece of symmetry between the two approaches.

One way to think of this, perhaps, is that our TDA insert has inlined Maybe. It acts both as an associative container and as a context for function execution. The only difference (mind out though, it’s a big one) is that fp_insert is far stricter about what those functions are allowed to do.

We perhaps shouldn’t be surprised at this; what we’ve really found is an artifact of tight encapsulation, which we introduced by definition in both cases.

Why compose isn’t quite working

fp_insert_ish, as far as . is concerned, has type

fp_insert_ish :: (Ord k) => k -> (a -> Map k a -> Maybe a)

and maybe_ish is really wanting a Maybe a to start with. One can bind enough of fp_insert_ish‘s parameters to get this to work; we’ll not spend the time doing that here.

Having found some symmetry (admittedly with a little bit of hand waving), let’s consider a less friendly asymmetry.

Interactions between FP and OOP

A lot of hot air has been generated about the exciting possibility of combining the powers of OOP and FP approaches, as if they are some sort of transformer robots that get a attack bonus, amazing music and lens flares whenever they touch.

It’s not particularly clear whether this is true. We won’t try to answer this question here at all. All we can do here is look at TDA‘s interaction with FP.

  • Can FP code call TDA code?

No

The TDA approach deliberately obscures some variance in its type signatures. You’d have to do some serious gymnastics to express the same thing in Haskell, and, once the core is infected with mutability, the IO() virus spreads inexorably outwards.

  • Can TDA code call FP code?

Just about.

One can start to preach the church of return type in the core of an application and gently push it outwards (TDA style callers can update a mutable reference to the newly returned FP core, then send out the (also returned) events).

This will cause some dissonance, but, and this is the very important point, only at changeover points. Purity, unlike mutability, isn’t upwardly mobile.

Diversion 3: Not today…

Whether this has any bearing on OOP / FP interweaving is left temporarily as an exercise to the reader.

Serendipitously, Eric Meijer just wrote something excellent on the wider question of hybrid OOP/FP approaches.

Conclusion

We found a tiny Maybe hidden in our TDA code; a symmetry due to the encapsulation shared between our two approaches.

One wonders if other exercises TDAing the living daylights out of other data structures would uncover any other fundamental types.

We found also one asymmetry between TDA and FP; implicit mutation simply isn’t permitted in FP, so we can nest the approaches in one direction only.

Extremely satisfying summary

Once we start to mutate, anyone above must mutate with us.

So: Pick the point of no return very carefully.

Next time

A selection from:

  • Do our truths about TDA tell us anything about OOP?
  • Does our TDA world bring us any new problems?
  • Does our TDA world bring us any benefits?
  • Will we ever get to talking about the Actor model?

Post script

There may be a small hiatus over the next couple of months while I develop related material into a workshop for 2014’s SPA Conference ( This session is mine ).

Variance expression in tell don’t ask programs

This time we’re going to explore how tell don’t ask (TDA) programs express variance, and hopefully come across an interesting corollary of our TDA definition.

We’ll consider two ubiquitous operations: getting and storing a value into a map. In both cases we’ll discuss the standard Java implementation before creating a speculative TDA version.

Example one: value retrieval

We want to lookup the value associated with a particular key.

This operation has entropy two. Either the map contains the value or it does not.

java.util.Map

V get(Object key);

Here the returned value is either:

  • null to signify absence
  • the present value

Amusingly nothing prevents us from storing a null value other than some very hopeful javadoc.

Clearly this interface violates our TDA definition.

  • Should we be perturbed by this?

If such a core library concept is against us, perhaps we’ve chosen a poor language as for TDA implementation; Java, after all, is frequently mocked for not being a tremendous OO language.

What about a lauded OO language, like Smalltalk? Well, Smalltalk’s dictionary class still provides value access via at:, which generates an error if a value isn’t present.

Even the more robust accessor

at: key ifAbsent: action

still returns the present value, rather than forwarding a message to it.

Let’s continue to persist with our TDA approach and see what happens.

TDA like we mean it

void forward(final K key, final Consumer<V> onPresent, final Runnable onAbsent);

Now we obey our TDA definition and end up passing in two more objects.

There’s that number two again! It sounds like we’ve expressed the variance in function parameters – we’ve given the map two functions that it could call depending on whether a value is present or not, and we trust it to call only one of them.

Perhaps we could express the TDA variance as follows:

variance ⊂ downstream call graph

Example two: Storage

Now we want to put a new value into the map.

Once again, the entropy of this function sounds like it might be two:

  • There could be a value already present for that key; we overwrite it
  • There is no existing value and we just add the new key value pair.

In both cases the state of the map changes.

Java standard

V put(K key, V value)

Once again, not quite tell don’t ask compliant.

Side note: If one looks at the javadoc on java.util.Map, one notices that with the addition of exceptions and the possibilities of null the entropy is now far higher than two.

TDA like we mean it

void put(K key, V value, Consumer<V> oldValueExisted, Runnable noExistingValue);

Here again we have two extra parameters.

  • Does this new definition express the complete variance?

N.B We could argue that oldValueExisted and thereWasNoExistingValue don’t have access to the new key and value. Nothing in the TDA definition prevents us from binding this information into the implementations at construction time, though.

What’s really missing is the variance in the map’s state. This is left implicit – the caller still has a reference to the (now mutated) map, and the old version is gone, forever!

What if we wanted to use an immutable map in this style? A naive first attempt might look something like this:

Map<K,V> put(K key, V value, Consumer<V> onOldValue, Runnable noExistingValue);

The map decides which function to call next, but must also provide a new map to pass back to the original caller. This violates our TDA definition, however, and if either of the two callbacks want to play this game, we’re suddenly in trouble (they could be longer lived objects than a simple closure – how do we update their callers with their new values?).

It’s hard to see how we can scale this approach.

Conjecture: TDA mutation expression

What a pretentious subheading.

void put(K key, V value, Consumer<V> onOldValue, 
         Runnable noExistingValue, Consumer<Map<K,V>> onNewMap);

Now we’re fully tell don’t ask compliant, but what are we going to do with that new map?

Well, temporarily ignoring TDA, a caller could pass themselves as onNewMap. It could then tell its callers that it has changed, and so on, up the stack.

  • Can we do that and keep to the TDA definition?

We need the traditional extra layer of indirection.

Messages outgoing from our object can no longer be delivered directly, but will need to be captured/dispatched by some piece of architecture that knows where messages should be routed to and delivers them appropriately.

What’s the tapping noise I hear? Ye gods, we’ve just dug up the foundations of the actor model.

So, we have two choices:

  • Keep direct dispatch, but leave state change implicit
  • Abandon direct dispatch and build towards an actor like model.

Very important scoping note

In order to achieve TDA certification with the actor model, we’ll actually need to abandon synchronous dispatch (and qualify the TDA definition slightly).

Precisely why this is necessary is left (for now) as an exercise for the reader. We’ll spend the rest of this post discussing simple, direct dispatch TDA, and leave discussion of the actor model for another day.

The Consequences Of Implicit Mutation

This really ought to be the name of the next Blotted Science album.

We have roughly agreed that in TDA world:

variance ⊂ downstream call graph + (implicitly) mutable object state

This is perhaps more elegantly expressed as:

variance ⊂ downstream call graph for current method invocation +
           downstream call graph of future method invocations

That sounds quite worrying, no? We could see the variance of a call at the point of any future invocation. That’s a helluva lot of variance!

That is true, but our insistence on TDA at least allows each object to know precisely what messages it might get passed (and thus the possible states it can get into).

This fits with my experience in this area; as soon as we disregard TDA, understanding (and changing) code becomes extremely difficult.

On the up side

We do gain some immutability elsewhere. A large chunk of our object graph often is fixed at start time (spot the final fields of a given object).

For example, anyone using our TDA map could hold on to it for the entire program runtime, even though its contents (and thus behaviour) will evolve over time. The TDA map feels more like a subscription registry.

Conclusion

Caveat implementor!

TDA as we have defined it leads inexorably to mutable objects.

The only way to be sane (citation needed) in a mutable world is to encapsulate decisions made about state to the places where the state is. In a way, TDA is both the cause and solution of all of our problems.

Coming up

We are yet to discover the limits of TDA, and we haven’t really explored the effects of TDA at anything other than the unit level.

If TDA is such a good idea:

  • Why don’t library classes (like Map) obey our definition?
  • What effect does their lawlessness have on code that wants to be good?

We’ll try to make some headway on this soon.

In addition, we also need to cover:

  1. Variance expression and encapsulation in functional programs (FP).

    This should lead to a nice lemma on nesting FP in TDA (and vice versa). We’ll probably go here next, as a brief diversion (not least because I just extracted most of it from this post).

  2. The actor model