Monday 9 November 2015

Understanding composition

"Composition over inheritance" - I think I've heard this for the first time around 2006 when programming in Java 5 with generics was still a luxury and everything was literally "an Object". I remember an enormous shock after reading "Head First design patterns" when my mind started understanding a difference between OOP and procedural programming. This was a shock because as a Junior I had to work with large classes (with over 1000 lines per method) called SomethingManager or SomethingHelper - and then "the book" stated "well... this is wrong.. it's not Object Oriented Programming"

A decade later - we can hear that another approach called Functional Programming promises better composition that anything you tried before. Normally we would write couple "hello worlds" to gain better intuition, gradually gather new knowledge and make some judgement.

Yet... with FP something magical is hidden underneath - something marginalized yet very powerful, something scary yet very helpful and finally something which is denied but exists everywhere.

But let start with something simple...

What does it mean "to compose" ?

Literally "Composition" can be understood as an usage of N simple elements to create more complex construction. For example a tap below is a composition of some elements, It is technically working, passed acceptance criteria and is a good metaphor of many IT project which I saw in my life.

Of course we have an intuition that although this mechanism is working something is wrong with it. So let's think a little bit about composition in generally - can we answer a question about when things are easy to compose and how FP can help us with it. Writing finally some code - if for example I have a function in Java.

Function<Integer, Integer> f1 = i -> i + 1;

I have an Integer as an input and Integer as an output. So we could use this function with anything what ends with Integer or starts with Integer like this

Function<Integer, String> f2 = i -> "composition is beautiful : " + i;
Function<Integer, String> composed = f1.andThen(f2);

Or we could literally call this operation a composition

Function<Integer, String> alsoComposed = f2.compose(f1);
System.out.println(composed.apply(1));          //composition is beautiful : 2
System.out.println(alsoComposed.apply(1));      //composition is beautiful : 2

Before Java8 when there was no concept of a function as a value we would have to treat them like standard methods and invocation would look like this :

Integer result1 = f1.apply(1);
String finalResult = f2.apply(result1);

It is still a form of composition but we can feel that more work is needed here. This was Java - now let's do the same in Scala which is more expressive

val f1:Int=>Int= i=>i+1
val f2:Int=>String = i=> "composition is beautiful : " + i

val composed=f2 compose f1
composed(1) // res0: String = composition is beautiful : 2

It looks nice with simple numbers but to gain better intuition let's simulate more real life example.

More real life example

type Money=Double //yes it's very bad and evil
type DataBase = Map[Int,User]
case class User(val name:String,val salaryNet:Money)

This will be our model with very unprofessional usage of Double as Money. Let's create mock database with some records of keys and users

val database:DataBase=Map(
  1->User("Stefan",10.0),
  2->User("Zdzislawa",15.0),
  3->User("Boromir",20.0)
)

And finally actors of this spectacle - three simple functions which we are going to compose together:

val lookup:DataBase=>Int=>User = db=>key => db(key)
val salary:User=>Money= _.salaryNet
val net:Money=>Money= _ * 1.23

Perfect World Style

//perfect word style
val composedLogic: (Int) => Money =net compose salary compose lookup(database)
composedLogic(1)
composedLogic(2)
composedLogic(3)
//res1: Money = 12.3
//res2: Money = 18.45
//res3: Money = 24.6

Isn't it beautiful and simple? We took all parts and now we have fully functional program... but really have we? What if reality hit us with inpurity?

//problem
//composedLogic(4)
/// java.util.NoSuchElementException: key not found: 4

Most likely we had this problem at some point in our professional life - it's time to use the infamous "If" solution

When composition is difficult - the "dark ages" approach

Let's handle missing case in a classical DAO style

val lookupDarkAges:DataBase=>Int=>User = db=>key =>
  if(db.contains(key)) db(key) else null

For now looks fine. Let's do the composition :

val composedLogicDark: (Int) => Money =net compose salary compose lookupDarkAges(database)

It compiles... can it be IT? Well no, of course not ->

//composedLogicDark(4)
//composedLogicDark: Int => Money = <function1>
//AND the Stack Trace is SWEET
//java.lang.NullPointerException
//at pl.pawelwlodarski.fp.math.one.A$A109$A$A109$$anonfun$salary$1.apply(CompositionScala.sc0.tmp:19)

Now let understand why this don't compose. To safely use lookup function in Dark Ages style we need to adapt usage of another function by manually checking for null value and in real life this is how the arrow code is created

val lookupResult = lookupDarkAges(database)(4)
if(lookupResult!=null){
  val salaryResult=salary(lookupResult)
  if(salaryResult!=null){
    net(salaryResult)
  }
}

But now with full power of FP we can use another approach

the Scary "M" approach - "ehhh another Option example..."

//scary "M" style
val lookupScaryM:DataBase=>Int=>Option[User] = db=>key =>
  if(db.contains(key)) Some(db(key)) else None
//or just db.get(key) but let's keep it similar to previous examples

There are thousands of code examples on internet about Option construct but let's explain this for people who may don't know. Our methods now returns a wrapper which can be modified by special mechanism which receives some lambda/function as an argument. That's why we can call it high order function and from version 8 it can be also used in Java.

It allow us to use functional composition in context of real world problems like missing values and it protects us from null checks and arrow code.

val stillPerfectComposition: (User) => Money =net compose salary
val composedScaryM :Int => Option[Money]=
  key => lookupScaryM(database)(key) map stillPerfectComposition

composedScaryM(1)
//res4: Option[Money] = Some(12.3)
composedScaryM(4)
//res5: Option[Money] = None

And now we can contact real world somewhere over there

//Leave mathematical world
case class HttpMessage(code:Int,bod:String)
val error=HttpMessage(404,"<div>I'm so sorry for this error</div>")
val success=(salary:Money)=>HttpMessage(200,s"<div> salaray : $salary</div>")

val httpMessage = result.fold(error)(success)
// HttpMessage(200,<div> salaray : 12.3</div>)

Java example

For Java fans

Map<Integer, User> database = new HashMap<>();

database.put(1, new User("Stefan", 10.0));
database.put(2, new User("Zdzislawa", 15.0));

Function<Map<Integer, User>, Function<Integer, Optional<User>>> lookup = db -> key -> {
            User u = db.get(key);
            return Optional.ofNullable(u);
};

Function<User, Double> salary = User::getSalaryNet;

Function<Double, Double> gross = money -> money * 1.23;

Function<User, Double> perfectComposition = gross.compose(salary);

Function<Integer,Optional<Double>> program =key -> lookup.apply(database).apply(key).map(perfectComposition);

System.out.println(program.apply(1));
System.out.println(program.apply(4));
//Optional[12.3]
//Optional.empty

Ok but I promised something powerful. Option is very useful but it is only part of something bigger, a lot bigger...

The "F" word and another scary "M" word

There is something scary hidden under THIS MYSTERIOUS LINK. Just a moment ago I stated that Option is just a wrapper - I lied (to some point). "A wrapper" is an old way of thinking - we can look at it from a very different perspective and see that we actually used power of Type System to signalize possibility of a missing value.

If you entered the mysterious link you saw a page which looks maybe scary but for sure is not "cool". It leads to a wiki page about Functor and open gates to another scary concept denied by most of programmers something called... Mathematics

It may look scary but you have already used it - yes by using Option. My interpretation may not be accepted by mathematician but generally we can see there that Functor changes something like this X => Y into F(X) => F(Y). In our example it changed USER=>MONEY into OPTION(USER) => OPTION(MONEY)

And this is what map method on Option does. Imagine it as a standalone function: map(A=>B): Option[A] => Option[B]. Ok great, but does it have any practical value? You know in every scala presentation everyone carefully states "you don't need to know category theory". But when you write program how do you know you are doing it "correctly" ?

"CUSTOM" Driven Development

Once upon a time a guy lived in Scotland and his philosophy became one of the most important though movements in history - this guy was David Hume and according to his words people in generally organize their lives around set of Customs. "I don't have proof that tomorrow sun will rise but it happened 10000 times before so what the hell - I will assume that tomorrow situation will repeat".

I'm wondering if we are not doing the same thing with Computer Science which in most areas is not science anymore but became a "set of principles created by few and adapted by many". Look - OOP is not a science - even Alan Kay who created this term doesn't have strict definition ---> http://userpage.fu-berlin.de/~ram/pub/pub_jf47ht81Ht/doc_kay_oop_en

Most discussion about OOP which my inexperienced eyes saw and most discussion which may novice ears heard happened according to schema : My Opinion vs. your Opinion. This maybe convenient for drinking beer but maybe not so useful for engineering science. At the same time mentioned Functor is a part of bigger theory and it has some formal laws - yes, formal laws. Moreover "Scalaz" - a Functional library for scala - is shipped with prepared automated tests in scalacheck to check if your implementation of Functor from your domain is correct according to thoseformal laws!

This is really very new approach. After decade of "Opinion based development" this is something really new for me. It seems very promising but we are living in strange times when "being a programmer" is very blurry concept. For some you are an artist and for some you are just a fucking resource.

But let's return to something more pelasent

Functional purity - Haskell Kindergarden

This is as far as I can get with Haskell today but using a pure functional language where you can not cheat is a very interesting exercise. As a warm up let's do a simple composition. in Haskell you are composing by "dot" - -->.<-- (by "dot"? This is stupid! - In Java your are calling method by "dot"... -Ok.. continue)

Prelude> let f1 i =i+1
Prelude> let f2 i= "composition is beautiful : " ++ show i
Prelude> let f3= f2 . f1
Prelude> f3 1
"composition is beautiful : 2"

You can declare type aliases similarly to the way we are doing it in Scala (or in the other way - I believe Haskell was first)

Prelude> type Money=Double
Prelude> data User = User {name :: String, salaryNet :: Money} deriving (Show)

Prelude> import qualified Data.Map as Map
Prelude Map> type DataBase = Map Int User
Prelude Map> let database = fromList [(1,User "Stefan" 10.0),(2,User "Zdzislawa" 15.0)]

First Interesting this is that I was unable to create "Dark Ages" example in Haskell because... there is no null. (there is a function called "null" which checks if list is empty). And Option in Haskell is called "Maybe" and it has two values "Nothing" and "Just"

let ourLookup database key = Map.lookup key database
Prelude Map> :t ourLookup
ourLookup :: Ord k => Map k a -> k -> Maybe a

SalaryNet was generated automatically when we declared User structure

:t salaryNet 
salaryNet :: User -> Money

And finally our composition

let grossValue money = money * 1.23

let perfectComposition = grossValue . salaryNet 
Prelude Data.Map Map> :t perfectComposition 
perfectComposition :: User -> Money

And "scaryM" approach usage

let lookupScaryM key  = fmap perfectComposition (ourLookup database key)

lookupScaryM 1
Just 12.3

lookupScaryM 4
Nothing

What is fmap? This is wonderful moment because this is the place where practice meets formal theory (hint: word "FUNCTOR"...)

Prelude Map> :t fmap
fmap :: Functor f => (a -> b) -> f a -> f b

Now let's return to Scala and see some more powerful functional composition mechanisms

Even more composition - summon the Dragon

Let's recall last example of our Scala composition

val stillPerfectComposition: (User) => Money =net compose salary
val composedScaryM :Int => Option[Money]=
  key => lookupScaryM(database)(key) map stillPerfectComposition

We can summon the dragon

import scalaz._
import Scalaz._

And use something called Kleisli Composition

val findUser=(database:DataBase)=>Kleisli.kleisli[Option, Int, User] {
  (key:Int) => lookupScaryM(database)(key)
}

//HERE IS THIS BETTER COMPOSITION
val program=findUser(database) map stillPerfectComposition
program.run(1)
//res6: Option[Money] = Some(12.3)
program.run(4)
//res7: Option[Money] = None

We can even eliminate "database" parameter from composition generating functional dependency injection mechanism

val dependencyInjection = findUser andThen(_ map stillPerfectComposition)
val result=dependencyInjection(database)(1)
// res8: Option[Money] = Some(12.3)

dependencyInjection(database)(4)
//res9: Option[Money] = None

In 2004 there was a movie - The village. If I remember correctly it was about a group of people who was cheated that there is still XIX century while it really really XXI. I had the same feeling three years ago when I left "Java comfort zone". There are some very powerful languages over there with syntax a lot different than Java (which syntax was borrowed C++ which syntax was borrowed from C . Haskell has underscores, OCaml has underscores so maybe it's really worth to learn new way of thinking even if syntax is not from Java.