About Mayakumar

I like reading books. This blog is a platform for me to write about the books I read across various disciplines like software, finance, psychology etc.

Streams

Introduction

In this blog post, we will look at the concept of Streams using the language of Scala as the vehicle.

Motivation

In Scala, a List can be expressed as data type parameterized on type A and contains 2 data constructors: Nil and Cons

Screen Shot 2018-04-13 at 8.33.04 PM

Cons data constructor is a recursive structure which takes an element A as head and another List as tail. The terminal element in the List is a Nil data constructor.

Screen Shot 2018-04-13 at 8.36.54 PM

Strict and non-strict functions

A function is non-strict, if it chooses not to evaluate one or more of its arguments, whereas a strict function always evaluates its arguments.

In the above example, Cons data constructor is strict in evaluating its arguments head and tail. For eg., Consider this example:

Screen Shot 2018-04-13 at 8.52.12 PM.png

In the above example, map(_ + 25) produces an intermediate list which is then filtered with a condition of (_ % 7), producing another list. Each transformation produces an intermediate list which is used as an input to the next transformation and then discarded to produce the final list. If we do it in an imperative way, we can do the above logic in one pass without creating any intermediate lists.

Screen Shot 2018-04-13 at 9.03.24 PM.png

In order to achieve similar behavior as the above using functional programming, we will use “non-strict” (or) “laziness” property of functions.

Thunked…

As explained before, non-strictness (or laziness) is a property of a function where a function may choose not to evaluate one or more of its arguments.

For eg:

Thunk

The parameters a and b are non-strict and they need to be invoked in the function body so as to get evaluated. In lazinessExAGetsEvaluated function, a gets evaluated and b is not evaluated whereas in lazinessExBGetsEvaluated function, b gets evaluated and a is not evaluated. The syntax () => A is called thunk.

The above syntax can be further simplified by removing () as below:

Screen Shot 2018-04-14 at 11.33.56 AM.png

With this new knowledge of creating thunks to make functions parameters non-strict, we will solve the problem of creating a non-strict version of List which we call it Streams.

Streams.png

In the above definition of Stream, similar to List we have a recursive data-structure in Cons. The key difference in this version of Cons is, both the head and tail are non-strict /lazy/thunks. Since they are non-strict, they are yet to be evaluated which is the fundamental difference compared to Cons data constructor of List data type. Note, for Streams we should be having smart constructors, which will make use of lazy val syntax to make sure head and tail thunks for Cons data constructor are being evaluated only once and the result is memoized but we will not cover this part in detail in this blog. 

For eg., if I need to construct a stream with 3 elements:

Screen Shot 2018-04-14 at 9.39.06 PM.png

The most important difference in this case is, we are utilizing non-strictness property of the Cons data constructor. head and tail of the first Cons data constructor are thunks. So in essence, non-strictness or laziness allows us to separate the description of an expression from the evaluation of that expression. This gives us a great ability to describe a larger expression than we need and then evaluate only a portion of it.

Ok, so we have separated program description from evaluation. How do we evaluate the stream? Streams will provide a toList function to actually evaluate the thunks that is captured in the stream.

toList.png

How do we evaluate only a small portion from a larger expression? foldRight is a primitive combinator for Streams using which we can traverse the stream. This gives us the ability to build a lot of derived functions or combinators on top of foldRight.

foldRight.png

The key point in definition of foldRight is function f which is non-strict in its 2nd argument. This gives function f, a chance to figure out whether it needs to evaluate its 2nd argument or not on the need basis. This gives the ability to only evaluate a smaller portion from a larger expression.

For eg., if we need an exists function to figure out whether an element e is present in the stream or not, we will do:

exists.png

Screen Shot 2018-04-15 at 10.52.29 AM.png

If we look at the above example, function to figure out element 2, will stop the execution of the tail 3 and 4 once it figures out element 2 is present in the stream. This gives the powerful ability to only evaluate a smaller portion from a larger expression.

Coming to the original problem of using Stream to avoid intermediate lists, we need to come up with the definition of map and filter for Streams. Both the derived combinators map and filter can be implemented using the primitive combinator foldRight.

Screen Shot 2018-04-16 at 10.24.31 AM

In the above function definition for map and filter, we can see that both are returning Streams. In Streams, we know that both head and tail are thunks where we only describe the expression. In the case of map, we return a Stream.cons(f(h),t)​ and in the case of filter, we either return Stream.cons(h, t) if f(h) is true else we return the tail t which is again a Stream. 

We have all the building blocks to provide the solution by avoiding intermediate data structure creation using Streams instead of Lists

Screen Shot 2018-04-16 at 9.57.23 PM.png

In the above example, toList triggers the computation of map​ to the first element 1. Applying map to element 1​ makes it 26. Now filter is applied to 26 which is not divisible by 7​ and is discarded. toList​ triggers the computation of map to the second element 2 and is then filtered and hence discarded. toList triggers computation of map and filter for element 3​., since element 28 is divisible by 7, element 28​ becomes the first element of the resultant List. toList triggers computation of map and filter for element 4 and then element 5 and both of them are discarded. In this above example, we did not fully instantiate the intermediate stream during map and filter. Also, we took an element and applied both map and filter to see if it’s eligible to make into the resultant List before moving on to the next element. It behaved very similar to the imperative way of solving using loops as shown before.

Conclusion

Streams are very powerful structures which exploit non-strictness or laziness property of the functions using which we can improve the efficiency and modularity of functional programs.

References

Advertisements

Tracking request in Node.js

Introduction

In this blog post, we will take a look at how we will be tracking request in Node.js.

Motivation (WHY?)

If we look at postal services like Fedex, UPS etc., they will provide us with a tracking number using which we can track the package status from their website.

Screen Shot 2017-11-04 at 5.41.27 PM

It is such an important functionality, using which each customer can track their package status at any time.

Similarly, in a Service Oriented Architecture, we will have a plethora of services talking to one another using HTTP protocol following REST(mostly) or SOAP architecture. When a client initiates a Web request using browser, request traverses through all these distributed services to fulfill a particular request. Diagrammatically it can be shown as below:

Screen Shot 2017-11-04 at 5.44.32 PM

Similar to how we track packages, we need to track what happened to a particular request r1 initiated by a client. Typically when the web application receives the request, it will generate a unique identifier called correlationId and track any information in its application logs by tagging this correlationId. Also when the web application makes any service calls it will pass along this correlationId as a Request HEADER key/value pair. Subsequently, those services will use the same correlationId while they log their information. This unique identifier is thus carry forward to all the services which are involved in fulfilling a single request r1.

Screen Shot 2017-11-04 at 5.56.46 PM

Passing along the same correlationId for a given request is very important for a variety of reasons:

  • When a given request fails, we can exactly know the reason why it failed and which service caused the failure.
  • We can tell how long a given request took and can measure exactly how long each services in turn took to process a given request
  • If we have all information logged for a given request r1 we can write aggregate queries to figure out:
    • How many request was served by a given endpoint in a min/hr/day range?
    • How many 2xx/4xx/5xx occurred for a given endpoint in a min/hr/day range?
    • What is the average/95th percentile response time taken for a given api to respond for a given request r1?
    • etc.,

It is very clear that tracking a given request r1 using correlationId in Service Oriented Architecture is critical to understand how our systems are behaving.

Implementation (HOW?)

Solution in JAVA

We will take a simple example of providing a stock price web application which retrieves stock price based on the company name. The flow is as follows:

  1. Client (Browser) makes a call by passing company name. for eg: Walmart
  2. Web application receives company name and then calls  StockService to retrieve the stock ticker symbol. (Walmart => WMT)
  3. Web application gets the stock price by passing stock ticker symbol to StockService and renders the webpage with the result. (WMT => price)

In the above example, we will focus how logging is implemented in the web application layer, since the process is the same across other layers in the stack.

UML diagram can be shown as follows:

Stock Price Sequence (2)

In this example, web application is written in Java and it includes WebController and StockBizImpl in the above diagram. We will not worry about the implementation of Stock Service(Separate Service).

To satisfy our logging requirements in JAVA web application we need to do:

  • Generate a unique correlationId which is tagged along in every log we generate in the web application
  • Pass this unique correlationId when we make 2 service calls. One to retrieve stock ticker symbol and the other to retrieve stock price.

Solution 1:

A quick solution would be to create a class called Context which will hold the generated correlationId. This object will be created by WebController and then each function which needs to either log or make a service call, will accept a new function parameter called context. For eg: public void process(String value, Context ctx, ...)​. This solution works but as we can see, the function signature gets tainted with Context ctx everywhere in the code and also we need to keep passing Context ctx wherever it’s required which is not elegant.

Solution 2:

How do we solve it in a way, that any portion of the code which is handling a given request somehow automatically gets the Context object without having to explicitly pass it as a parameter? THREADLOCAL to the rescue.

Java provides a ThreadLocal object using which you can set/get/remove thread scoped variables3 key functions:

  • set(T value) – It is generic over type T
  • get()
  • remove()

Assuming we are developing a J2EE web application running within Tomcat, blocked thread pool implementation., Tomcat will have a worker thread pool of size n and each thread will be allocated to handle a given request and once completed the thread goes back to the thread pool. Typically, we will register a filter which will create a Context object and set in ThreadLocal. This object can be accessed in the entire request lifecycle within the same thread and when the control comes back to filter, it will remove the context from ThreadLocal since threads will be reused by Tomcat as they go back to the thread pool. Solution is a Filter acting as a Decorator and ThreadLocal acting as the container of the object within the given thread of execution.

Stock_Price_Sequence__1__png_and_Stock_Price_Sequence.png

Solution in Node.js

We will take a simple example of generating a correlationId in one event loop and subsequently retrieve the previously set correlationId value in another event loop which is part of the same callback chain.

Solution 1:

Similar to Java solution 1, we can append the Context to request object under request.app.ctx with a new value for correlationId.  In the code wherever we need the correlationId from the Context object in the entire callback chain for a given request, we will simply use closure and close over the request object. Like in Java solution 1, it is not elegant as we have to close over the request object to access request.app.ctx wherever we need the ctx object in the request lifecycle.

Solution 2:

If we look at the above Java solution, the 3 key methods set(T value), get() and remove() do not have to pass in thread id to do CRUD on thread local objects. It is completely abstracted away by the implementation of ThreadLocal which makes the solution elegant. If we are looking at the signatures of set, get and remove from the lens of a functional programmer, we can clearly see that they are side-effecting operations. To me, both OOP and FP offer elegant solutions for various kinds of problems. In this use case, even though they are side-effecting operations, it does not clutter the code to pass the Context object all around and provides a very simple and elegant solution.

As we all know, Node.js is single threaded following Continuation-passing style.  How do we solve this problem in this environment?

We will look at a simple Node.js code to understand what we are trying to achieve:

Screen Shot 2017-11-07 at 8.24.55 AM

What we would like to achieve is set an object with key:value pair  and register some callback events using setTimeout for example in one event loop and then we should be able to retrieve the previous set value by passing  the key in the subsequent event loop when the callback actually gets fired.

We have taken the cue from the Java implementation. In the above Node.js implementation, we have come up with setters and getters using set(key, value) and get(key)​respectively and the object values stored using set should be  automatically made available to the entire callback chain in a transparent manner and should be able to be retrieved using getDecorator and ThreadLocal solution in Java becomes Monkey Patching and Use of Closures in Javascript.

What is MonkeyPatching ?

A monkey patch is a way for a program to extend or modify supporting system software locally (affecting only the running instance of the program).

A simple example of monkey patching setTimeout and the callback we pass to it can be shown as follows:

Screen Shot 2017-11-07 at 8.27.55 AM
As we can see above, both setTimeout and callback that we pass to it is being monkey patched. Since the client has already tied their code with setTimeout / callback the only way to augment the behavior of setTimeout / callback is by monkey patching.

Solution using Monkey patching and Closures

Screen_Shot_2017-11-05_at_10_12_19_PM

namespace.js

Screen_Shot_2017-11-05_at_10_17_14_PM

As we can see above, setTimeout and callback passed to it is monkey patched. In the patched setTimeout function, we are closing over the active context value at that point in time t. In the patched callback function, we are setting the closed active value what was at time t while entering, run the actual callback function, resetting the active to an empty object while exiting. We start everything off by running namespace.run(fn) where run function creates a brand new active object, sets the active object while entering, executes fn (in this case start) and then resets the active value while exiting.

Continuation Local Storage

An open sourced module called Continuation Local Storage solves the above problem for Node.js in a powerful and elegant way. You can go over the source code link to understand more about the module.

General code flow for passing around context in a generic way using Continuation Local Storage can be shown as below: (Took the below example from Continuation Local Storage )

Screen Shot 2017-11-06 at 10.28.56 AM

Continuation Local Storage  is a very powerful and complex module. Since in Node.js, IO are non-blocking operations, this effectively means Continuation Local Storage  module needs to apply monkey patching to a variety of functions. The module at a very high level does the following:

  • Handling variations of logic for different node versions
  • Monkey patch functions from the below objects:
    • net.Server.prototype
    • http.Agent.prototype
    • childProcess.ChildProcess.prototype
    • childProcess
    • process
    • global
    • dns
    • fs
    • zlib
    • crypto
    • Promise
    • etc…
  • Support CLS for EventEmitter
  • Handling error scenarios
  • Provides namespace using which we can start a new execution using run, and for read and write operation, we can use get and set respectively.

Modules

Screen Shot 2017-11-06 at 10.46.12 AM

Summary

Tracking a request in Node.js using correlationId is not very easy compared to how it can be implemented in a language like Java. Node.js asynchronous IO makes it very hard as the code structure becomes completely callback-driven.  Continuation Local Storage is one of the most powerful and complex modules which solves this problem in a very elegant way for Node js. Even if we are not planning to use this module in a real world application, just by looking at the source code implementation we can learn so much about the complexity involved in solving such a simple use case in Node js and the author’s brilliance in the way of its implementation.

Functional Programing in Javascript

Introduction

Recently I went through this fascinating article Professor Frisby’s mostly adequate guide to Functional Programming and would like to summarise my understanding in this post.

f(x)

In imperative programming, you get things done by giving the computer a sequence of tasks and then it executes them. While executing them, it can change state.  In purely functional programming you don’t tell the computer what to do as such but rather you tell it what stuff is.

// Imperative

var original = [1,2,3,4,5]
var squared = []

for(var i = 0; i < original.length; i++) {  
  var squaredNumber = original[i] * original[i]  
  squared.push(squaredNumber) 
} 

console.log(squared) //=> [1, 4, 9, 16, 25]
// Functional

var original = [1,2,3,4,5]

var squared = original.map(n => n * n);

console.log(squared) //=> [1, 4, 9, 16, 25]

Functions are first-class

In Javascript, functions are “first class”, we mean they are just like everyone else for example, like a Number, String etc.,

Functions are better if they are pure

A pure function is a function that, given the same input, 
will always return the same output and does not have any 
observable side effect.

Side effects may include but not limited to,

Changing the file system
Inserting/Updating/Deleting a record into a database
Making a http call
Mutations
Printing to the screen/logging
Obtaining User Input
Querying the DOM
Accessing system state

8th grade math

From mathisfun.com:

A function is a special relationship between values: 
Each of its input values gives back exactly one output value.

Take a function which calculates square

function square(x) {
  return x * x;
}

If function is just a special relationship between values as mentioned above, we can visualize the function as a simple table:

screen-shot-2017-01-10-at-10-54-08-amThere’s no need for implementation details if the input dictates the output. Pure functions are mathematical functions and they’re what functional programming is all about.

A pure function is:

  • Cacheable
  • Self Documenting
  • Testable
  • Reasonable (Referential transparent: A spot of code is referentially transparent when it can be substituted for its evaluated value without changing the behavior of the program.)
  • Can be made to execute in parallel

Curried Functions

The concept of curried functions is, you can call a function with fewer arguments than it expects. It returns a function that takes the remaining arguments.

For eg., a curried add function can be,

function add = a => b => {
    return a+b;
}

add(1)(2) // Result: 3

As explained earlier, a function is a special relationship between values: Each of its input values gives back exactly one output value. Using curried functions, we can make new, useful functions on the fly simply by passing in a few arguments and as a bonus, we’ve retained the mathematical function definition of each input mapping to exactly one output despite multiple arguments. This is the reason, why every function in Haskell officially only takes only one parameter. All the functions that accepted several parameters will be curried functions.

Composition – Holy Grail

compose function can be defined as:

var compose = function(f, g) {
  return function(x) {
    return f(g(x));
  };
};

f and g are functions and x is the value being piped through them.

The most important building block in FP is functions. Composition allows us to combine these smaller building blocks to build larger programs. If you look at the function definition, compose function takes 2 functions f and g and creates a brand new function which takes a value x calls g and then passes the result to function fand returns the result.

Functional composition is associative.

// associativity

var associative = 
compose(f, compose(g, h)) == compose(compose(f, g), h);

// true

This means that it doesn’t matter how we group our calls to compose, the result will be the same. This allows us to write a variadic compose (which is implemented in libraries like lodash, ramda etc.,).

The best analogy to think about the power of composition is UNIX pipes. 2 of the important points in Unix  philosophy are:

  1. Write programs that do one thing and do it well.
  2. Write programs to work together.

For eg;

find - walk a file hierarchy
cat - concatenate and print files
grep - file pattern searcher
xargs - construct argument list(s) and execute utility

Each program mentioned above exactly does one job very well. 
But when we combine/compose them together you get powerful programs.

find . -name "fp.txt" | xargs cat | grep "FP"

Find a file called "fp.txt" searching from the current directory
and pipe the contents to cat through xargs and then pipe the 
contents to grep to search for the text "FP"

In FP, we write pure functions that do one thing and do it well. We use composition to combine/compose functions so that they work together.

Hindley-Milner

In functional world, it won’t be long before we find ourself knee deep in type signatures. Types are the meta language that enables people from all different backgrounds to communicate succinctly and effectively. For the most part, they’re written with a system called “Hindley-Milner”.

Type signatures for the below functions are as follows:

:t capitalize
capitalize :: String -> String

:t strLength
strLength :: String -> Number

:t head
head :: [a] -> a

:t reverse
reverse :: [a] -> [a]

:t sort
sort :: Ord a => [a] -> [a]

:t foldl
foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b

Once a type variable is introduced, there emerges a curious property called parametricity. This property states that a function will act on all types in a uniform manner which makes the possible behavior of the function massively narrowed due to its polymorphic type.

Container/Box/Computational Context

We have seen how to apply functions to a value.

function addOne(x) {
  return x + 1;
}

var r = addOne(10) // r = 11

We will extend this idea by saying that any value can be in a context. For now we can think of this as a CONTAINER or BOX or COMPUTATIONAL CONTEXT. 

You can create this type with the following definition:

var Container = function(x) {
  this.__value = x;
}

Container.of = function(x) { return new Container(x); };

We will take a simple type called Maybewhich can be in 2 different states: One state containing a value and the other Nothing. In Haskell, this type is represented as

data Maybe a = Nothing | Just a

In Scala, this type is called Option, which will be in 2 different states: Some and None.

In Javascript, in the below example we will just define a  Maybe class which encapsulates both the states. In practice, we should mirror the Haskell or Scala or some other language have separate type constructors for each of the states.

var Maybe = function(x) {
  this.__value = x;
};

Maybe.of = function(x) {
  return new Maybe(x);
};

Maybe.prototype.isNothing = function() {
  return (this.__value === null || this.__value === undefined);
};

Maybe.of("JS rocks!!"); // State containing a value
Maybe.of(null); // State containing null

Functor

The definition of functor:

map :: Functor f => (a -> b) -> f a -> f b

From the signature, we can clearly see that Functor defines a map method and its implementors must provide an implementation to the map function. From the signature, we can see that map method allows us to do a data transformationof the value that is contained in the computational context. Another very important property of map function is it preserves structure.

A Functor is a type that implements map and obeys some laws

Maybe is a Functorand it provides a map implementation.

Maybe.prototype.map = function(f) {
  return this.isNothing() ? Maybe.of(null) : Maybe.of(f(this.__value));
};

Maybe.of('Mayakumar').map(match(/a/ig));
// => Maybe['a', 'a', 'a']

Functor Laws

// identity
map(id) === id;

// composition
compose(map(f), map(g)) === map(compose(f, g));

Diagrammatically, what happens under the hood of Functor's map method can be shown as below:

functor

Monad

Pointy Functor Factory

of method is to place values in what’s called a default minimal context part of an important interface called Pointed.

A pointed functor is a functor with an of method
Maybe.of(100).map(add(1));
// Maybe(101)

When the map function has a signature a => M[B] we will get nested container types. If we had to get to the value, we have to map as many times  as the wrapped container types which is not great from the caller perspective.

We somehow need to remove the extra container/box/computation context, M[M[a] to M[a]

var mmo = Maybe.of(Maybe.of('value'));
// Maybe(Maybe('value'))

mmo.join();
// Maybe('value')
Monads are pointed functors that can flatten

Any functor which defines a join method, has an of method, and obeys a few laws is a monad. Defining join is not too difficult so let’s do so for Maybe:

Maybe.prototype.join = function() {
  return this.isNothing() ? Maybe.of(null) : this.__value;
}

We can call join right after map which can be abstracted in a function called chain.

//  chain :: Monad m => (a -> m b) -> m a -> m b
var chain = curry(function(f, m){
  return m.map(f).join(); // or compose(join, map(f))(m)
});

For Maybe:

Maybe.prototype.chain = function(f) {
  return this.isNothing() ? Maybe.of(null) : this.map(f).join();
}

chain nests effects and we can capture both sequence and variable assignment in a purely functional way.

For eg:

var result = Maybe.of(3).chain(a => {
   return Maybe.of(30).chain(b => {
      return Maybe.of(300).chain(c => {
        return Maybe.of(3000).map(d => a + b + c + d);
      });
   })
});

// => 3333

Monad Laws

// associativity
compose(join, map(join)) == compose(join, join);

// identity for all (M a)
compose(join, of) === compose(join, map(of)) === id

var mcompose = function(f, g) {
  return compose(chain(f), g);
};

// left identity
mcompose(M, f) == f;

// right identity
mcompose(f, M) == f;

// associativity
mcompose(mcompose(f, g), h) === mcompose(f, mcompose(g, h));

Diagrammatically, what happens under the hood of Monad's chain method  can be shown as below:

function even(x) {
   if(x % 2 === 0) {
      return Maybe.of(x/2);
    } else {
      return Maybe.of(null);
    }
}

monad

Applicatives

Applicatives provide the ability to apply functors to each other.  We will take an example to understand better:

var add = a => b => {
 return a + b;
}

add(Maybe.of(2), Maybe.of(3));
// Not possible

var maybe_of_add_2 = map(add, Maybe.of(2));
// Maybe(add(2))

We have ourselves a Maybe with a partially applied function inside. More specifically, we have a Maybe(add(2)) and we’d like to apply its add(2) to the 3 in Maybe(3) to complete the call. In other words, we’d like to apply one functor to another.  We can achieve this using chain and map functions as defined below:

Maybe.of(2).chain(function(two) {
 return Maybe.of(3).map(add(two));
});

The issue here is that we are stuck in the sequential world of monads. We have ourselves two strong, independent values and we should think it unnecessary to delay the creation of Maybe(3) merely to satisfy the monad’s sequential demands. So applicatives provides the functionality where we need to apply functions within a computational context to values in a computational context but the values are independent and hence there is no need to sequence them. A good example to think of the use of Applicatives is when we do parallel independent asynchronous computations and apply the results of each to a function contained in a functor.

Maybe.prototype.ap = function(other_container) {
 return this.isNothing() ? this : other_container.map(this.__value);
}

Maybe.of(add).ap(Maybe.of(2)).ap(Maybe.of(3));
// Maybe 5
An applicative functor is a pointed functor with an ap method

Applicative Laws

// identity
A.of(id).ap(v) == v

// homomorphism
A.of(f).ap(A.of(x)) == A.of(f(x))

// interchange
v.ap(A.of(x)) == A.of(function(f) { return f(x) }).ap(v)

// composition
A.of(compose).ap(u).ap(v).ap(w) == u.ap(v.ap(w));

So a good use case for applicatives is when one has multiple functor arguments. They give us the ability to apply functions to arguments all within the functor world. Though we could already do so with monads, we should prefer applicative functors when we aren’t in need of monadic specific functionality.

Diagrammatically, what happens under the hood of Applicative's ap method  can be shown as below:

applicatives

map/of/chain/ap

We have explained the concepts behind Functor, Monad, Applicatives. There are so many structures that obey/satisfy the properties of being a functor, monad and applicative. From the above example we can see that Maybe is a Functor, Monad and Applicative. There are many structures that satisfy functor, monad, applicatives which include:

List
Maybe
IO
Task (https://github.com/folktale/data.task)
etc.,

If a type is a Monad it has to be both an Appliacative and a Functor. If a type is an Applicative it has to be a Functor.

Summary

Professor Frisby’s mostly adequate guide to Functional Programming is one of the best articles that I have read recently. From the article, the author wonderfully shows how powerful and deep functional programming constructs are and also explains how they can all be implemented with Javascript language.

References

  1. https://www.gitbook.com/book/drboolean/mostly-adequate-guide/details
  2. http://learnyouahaskell.com/
  3. http://adit.io/posts/2013-04-17-functors,_applicatives,_and_monads_in_pictures.html (The diagrammatic representation for Functor, Monad, Applicatives are inspired from this post).

Redux Middleware

Introduction

In this post, I will write about Redux Middleware by viewing it in 2 different angles, one from the Object Oriented way and the other from the functional way as how it is implemented in Redux source code.

Basics of Redux

The core function of Redux is:


dispatch(action)

When the client calls dispatch(action),  it internally calls the reducer function which is a pure function (a function which does not have any side effects) whose signature is (currentstate, action) => nextstate. The client can call getState to get the current state value any time.

Middleware

As stated earlier, dispatch(action) is the core function of Redux which does the next state calculation using the reducer function. What if an application wants to log the getState() function before and after the call to dispatch(action) (or) would like to know how long it took for dispatch(action) to finish completion (or)  would like to make an IO operation before calling the actual dispatch(action)?  How do we solve this problem? I was reminded of a famous quote,

History doesn’t repeat itself but it often rhymes

I have seen this similar problem in a couple of instances from the Object Oriented world.

  • Java Filters: A filter is an object that performs filtering tasks on either the request to a resource (a servlet or static content), or on the response from a resource, or both.
  • Java IO: InputStream is an abstract class. Most concrete implementations like BufferedInputStream, GzipInputStream, ObjectInputStream, etc. have a constructor that takes an instance of the same abstract class. That’s the recognition key of the decorator pattern (this also applies to constructors taking an instance of the same interface).

Both the above examples are typically solved by a popular Gang of Four Design Pattern: Decorator Design Pattern. The basic idea of Decorator Design pattern is to augment (or) decorate the behavior of the underlying base component without the need to change/extend the base component.

So the original problem of how to augment/decorate dispatch(action) perfectly fits the bill of GoF Decorator Design Pattern. GoF Decorator design pattern provides the solution in Object Oriented way, but the general abstract motivation of using Decorator Design pattern perfectly maps to how we will solve the problem of implementing Middlewares in Redux whether in Object Oriented Way (or) Functional way.

Square Calculator

To understand middleware, we will try to view it through the lens of a very simple example:Square calculator. If the input is x the output is x*x, which basically forms the pure reducer function. Redux stores the last computed square value as its state. Additionally we would like to do 3 middleware operations:

  1. Validate the input to make sure it is a number by calling a service (extremely hypothetical example), but in essence would like to sprinkle some impurity through an IO operation.
  2. Calculate the time taken to perform the original dispatch(action)
  3. Log the getState() before and after the original dispatch(action)

[If you look closely, not only 1 is impure because of an IO operation, even 2 and 3 are also impure since accessing the system clock to get the time and writing to the console are also impure operations.]

screen-shot-2016-12-27-at-1-56-48-pm

Implementation of Square Calculator – Object Oriented Way

As stated earlier, it is implemented using Decorator design pattern:Source Code in Java Using OO way

The UML diagram for the crux of the implementation can be shown as below:

screen-shot-2016-12-27-at-11-26-42-pm


Store globalStore;
globalStore = new Thunk(new TimerStore(new LoggingStore(baseStore)));

As shown above, we are adhering to an important principle, “Code to an interface rather than an implementation” and the client ties to the interface called Store and the implementation is a fully constructed chain of decorators wrapping the base Store and the client is not aware of any of the implementation details.

Implementation of Square Calculator – Functional Way

If we look at Redux source code, the implementation of middleware uses a lot of functional constructs. I have created a slimmed down version of it to implement the logic for Square Calculator. Source Code in Javascript Using Functional way

I would like to touch upon some of the important functional programming constructs that are being employed to construct the wiring for middleware.

If you look at the above source code you will see the following important properties being employed:

  1. In Functional Programming, functions are first class citizens. Meaning, functions can be stored in variables and can be passed around like numbers, strings etc.
  2. Use of Higher Order Functions – Functions can take functions as parameters and return functions as return values. A function that does either of those is called a higher order function. It turns out that if you want to define computations by defining what stuff is instead of defining steps that change some state and maybe looping them, higher order functions are indispensable. They’re a really powerful way of solving problems and thinking about programs.
  3. Currying –  Basically if you take a simple function like adding 2 numbers, its signature for being a curried function would be var add = a => b => a + b. The caller of this function would have to do,  add(1) (2) to get 3. A good analogy would be, “If I can give you a carrot for an apple and a banana, and you already gave me an apple, you just have to give me a banana and I’ll give you a carrot.” Translating to the add example, if we had called the function add with just 1 and stored the result like var addOne = add(1). Now if the client wants to add any number to one, they can simply just do addOne(2) , so If I can give you a 3 for 1 and 2 and you already gave me 1 you just have to give me 2 and I will give you 3
  4. Use of map function in the List – Usage of Functor
  5. Use of folds through reduce function – extremely powerful abstract API.
  6. Use of functional composition – In computer science, function composition (not to be confused with object composition) is an act or mechanism to combine simple functions to build more complicated ones. Like the usual composition of functions in mathematics, the result of each function is passed as the argument of the next, and the result of the last one is the result of the whole.

All the above 6 properties are used in just 30 lines of code 🙂

function compose(...funcs) {
  funcs = funcs.filter(func => typeof func === 'function')

  if (funcs.length === 0) {
    return arg => arg
  }

  if (funcs.length === 1) {
    return funcs[0]
  }

  return funcs.reduce((a, b) => (...args) => a(b(...args)))
}

function applyMiddleware(...middlewares) {
  return (createStore) => (reducer, preloadedState, enhancer) => {
    var store = createStore(reducer, preloadedState, enhancer)
    var dispatch = store.dispatch
    var chain = []

    var middlewareAPI = {
      getState: store.getState,
      dispatch: (action) => dispatch(action)
    }
    chain = middlewares.map(middleware => middleware(middlewareAPI))
    dispatch = compose(...chain)(store.dispatch)

    return {
      ...store,
      dispatch
    }
  }
}

Conclusion

As you can see, Redux Middleware is a very simple but powerful concept where the core idea of decorating the base behavior of dispatch(action)function with wrappers is seen in many other instances in the Object Oriented world as well.

Referential Transparency, Redux and React

Introduction

I started my career doing C/C++ programming for Embedded systems and then transitioned to do Java/J2EE for a very long time. For the last year or two, I have been exposed to the world of functional programming through Scala, and for the last couple of months I have been doing actively development in the front end stack using Node.js on the server side and Redux/React on the client side. It has been a great experience and would like to share the connections I can see between the concept of “referential transparency” in functional programming world to Redux/React.

Referential Transparency

[Source Used for reference: Functional programming in Scala book]

Functional programming (FP) is based on a simple premise that we construct our programs using only pure functions – functions that have no side effects. What are side effects? A function has a side effect if it does something other than simply return a result. For eg:

  • Modifying a variable
  • Throwing an exception or halting with error
  • Making IO operations

Functional programming provides many techniques to do the above set of operations as well without side effects. I have written about a couple of patterns here:

Kleisli Monad Transformer

Magic of State Monad

The key idea is that majority of logic that deals with side effects lives at the edges of the application, while the core remains pure. Why do we need to have “pure functions” in the first place? Well, the answer turns out to be simple: Pure functions are easier to reason about. A function f with input type A and output type B, function of type A => B, is a computation that relates every value a of type A to exactly one value b of type B such that b is determined solely by the value of a.

We can formalize this idea of pure functions using the concept of “referential transparency”(RT). This is a property of expressions in general and not just functions. For eg., if we have an expression 2 + 3 in different parts of the program; This expression has no side effect and evaluation of this expression results in the same value 5 every time. In fact, if we saw 2+3 in a program we could simply replace it with the value 5 and it would not change a thing about the meaning of the program. The above case is true for eg., if we have a function called add(int, int): int which takes 2 integers and returns an integer as a result. If we saw for example, add(2, 3) in different parts of the program we could again simply replace it with the value 5 and the meaning of the program stays the same.

Referential Transparency examples
String class and its methods in Java are examples of referential 
transparency, as they do not have any side effect.

String s1 = "Hello"
int length = s1.length() // always going to be 5

Non Referential Transparency examples
StringBuilder class and its methods in Java are examples of non referential
transparency as they have side effect.

StringBuilder s1 = new StringBuilder("Hello");
s1.append(" , World"); // side effecting operation

Pure functions as mentioned earlier are easier to reason about and also has an additional important property that they are inherently thread safe and are very easy to parallelize. In the above example, StringBuilder is not thread safe as it has side effecting operations.

Redux

Redux is a predictable state container for JavaScript apps. The core philosophy of Redux is to have a “single state tree” and they have a reducer function whose signature is (currentstate, action) => nextstate[ReduxSourceCode] and reducer has to be a “pure function”. This basically means, that reducer function is referentially transparent and where ever we see the reducer function call we can replace the function call with the result of making the call and the meaning of the program stays exactly the same.

In the case of UI, state comes from 2 sources:

  • State produced by making a backend service call, which is an IO operation which is solved by Thunk Middleware. Thunk Middleware makes side effects living at the edges of the program within redux, where as the reducer function within the core can remain pure.
  • UI state like checkbox selected, button clicked etc.,

Because of reducers being a pure function and thus referentially transparent, the UI application state has become so easy to reason about.

React

ReactJs, a javascript library for UI interfaces, follows declarative and component based approach. Since the browser DOM operations are impure and causes side effect, it makes reasoning extremely hard. React brings in a notion of virtual dom through “ReactElement” which is a light, stateless, immutable, virtual representation of a DOM Element. A React component is expected to have a render(props, state) function to describe its UI. The signature is not completely accurate, but it captures the essence of the render function. Props are read only and if we push state from the React component into Redux state tree, then the render function has become render(props) which is a pure function and it becomes referentially transparent. This is called “Stateless functional components” in React. So in essence we can have a referentially transparent react component render method using a referentially transparent redux reducer function.

React Redux , which provides react bindings for redux, provides a function called connect(mapStateToProps, mapDispatchToProps) which acts as a bridge connecting the redux state to the react component props and also dispatching actions from react component to trigger the next state calculation using reducer function thus making sure the React Component UI stays up-to-date when its relevant state changes.

The mental model of how React, Redux, React-Redux fits in can be shown as below:

ReactRedux

Conclusion

As we can see, how a core philosophy of “referential transparency” in the world of functional programming is being applied to client side programming using React/Redux which makes UI code very easy to reason about.

 

 

 

Kleisli Monad Transformer

Introduction

In Scalaz library, a wrapper exists for functions of type A => M[B] where M is a Monad called Kleisli. This blog post is an explanation about this wrapper.

Why need Kleisli?

As an example is always a great starting point to convey any concept, I will explain a simple use case where we can use Kleisli. As explained above, Kleisli is a wrapper for functions of type A => M[B] where M is a Monad. Imagine an enterprise application, which serves a REQUEST Url /foo/bar?a=1, and returns back response after talking to 3 Services S1, S2, S3 and performing 2 DB operations D1 and D2 in sequence. So we essentially do 5 IO operations to fulfill this client request. As you know, if a function has a side-effect it makes the function impure and makes it harder to compose. Functional composition is the core of doing functional programming. How do we get around this problem? Well the solution is to “Describe the IO Computation and then finally executing it”. We describe IO operations in an IO Monad[Yes, scalaz has an IO Monad type, by looking at the type, we know that there will be a side-effect], but the key take away is we just describe the IO computations and then combine/compose them and finally execute all of them at one shot using unsafePerformIO method on the IO Monad. Now coming back to the original problem, we are doing 5 IO operations in sequence, how do we compose/combine functions which take some input of type A and return IO[?]? Well, the answer is to use Kleisi as it is a wrapper for functions of type A => M[B]

Code Example

Below code sample shows a simple use case where, “Given employeeId Key we will get Employee details by making a database call”:

DAO

Screen Shot 2018-04-27 at 11.43.47 AM

Intermediate Layer accessing DAO

Screen Shot 2018-04-27 at 11.42.10 AM

Model

Screen Shot 2018-04-27 at 11.40.35 AMRunner – Main Application

Screen Shot 2018-04-27 at 11.44.25 AM

Magic of State Monad

Introduction

I have been doing Object Oriented Programming in Java for almost a decade. Recently for the past six months, I have been doing Functional Programming in Scala. This blog is about the reasoning behind why we need “State Monad”.

Modifying a variable – SIDE EFFECT

If “Design Patterns: Elements of Reusable Object-Oriented Software” is the bible for Object Oriented Design Patterns, I would say “Functional programming in Scala” book is the bible for learning Functional Programming.

“FP in scala” book starts by defining, “Functional Programming (FP) is based on a simple premise with far-reaching implications: we construct our programs using only pure functions – in other words, functions that have no side effects. What are side effects? A function has a side effect if it does something other than simply return a result, for example: Modifying a variable is a “SIDE EFFECT”.

When I first read that Modifying a variable is a “SIDE EFFECT”, I was completely surprised and puzzled, since we do it all the time in OOP. for eg., i++ is a side effecting operation. I was wondering how do we make state changes in FP? Well, the answer is State Monad.

State Monad

Chapter 6 “Purely functional state” in “FP in Scala” book, starts with the problem of Random number generation.

Random Number with Side effect:

Screen Shot 2018-04-27 at 11.26.51 AMEverytime you call nextInt function, it doles out a random value since rng has some internal state that gets updated after each invocation, since we would otherwise get the same value each time we called nextInt.

Basically, if you think about the implementation, it holds an internal STATE using which it generates a NEW RANDOM VALUE when you call the function. To make the implementation pure, accept the STATE as a function parameter asking to be passed by the caller every time when they need a value.

Random Number without Side effect:

Screen Shot 2018-04-27 at 11.27.49 AM

The common abstraction for making stateful APIs pure is the essence of State Monad. The essence of the signature:

Screen Shot 2018-04-27 at 11.28.33 AM

Basically, it encapsulates a run function which takes a STATE argument and return a TUPLE capturing the (VALUE, NEXT STATE). The problem has been inverted in a way where the client needs to pass the “NEXT STATE” to generate the next (VALUE,  STATE).

SIMPLE USE CASE

Assume that there is a CRUD application to create, update, find, delete employee which is using Mysql database for persistence. If you open a SINGLE database terminal and issue CRUD operations against a database what is essentially happening is a STATE TRANSITION. Say there is an “EMPLOYEE” table with zero records which can be thought as the initial state of the database D. Now if you issue a INSERT INTO EMPLOYEE VALUES(‘VMKR’) a new record gets inserted which can be thought as a new state D’ of the database and value produced being the employee record. So it is a database transition from D => (VALUE, D’).

Now assume that you wanted to write unit test case to test this CRUD API. Obviously you would not want to hit the database and would ideally mock it. A simple way to mock a database is to use an in-memory map.

Screen Shot 2018-04-27 at 11.29.22 AM

BINGO! We can use the “State Monad” abstraction to solve this problem. I have listed the source code below: (showing as 2 different images since the size is larger to be captured in one image, but to execute the code, we need to copy code from both the images)

Screen Shot 2018-04-27 at 11.30.39 AMScreen Shot 2018-04-27 at 11.31.30 AMThe code does the following:

  • case class StateMonad[S, A](run: (S => (A, S))) is the crux of making state transitions pure.
  • It has map and flatMap making it a “FUNCTOR” and “MONAD”. To understand more about “FUNCTOR” and “MONAD” read here: FUNCTOR_AND_MONAD
  • case class Employee(id: Int, name: String) is the Employee data model with an id and a name.
  • trait MEmployee[M[_]]  defines the CRUD api’s. Think it as “interfaces” in Java parlance.
  • object MEmployee is the companion object. Its purpose is to make the usage of trait MEmployee easier for the client. The clients can simply call MEmployee.createEmployee. It will work as long as there is an implementation implicitly available as defined by the api: (implicit M: MEmployee[M]).
  • The test implementation of using the State Monad with in-memory Map is provided by MEmployeeInstances.
  • Cryptic syntax: ({ type λ[α] = StateMonad[Map[Int, Employee], α] })#λ is called TYPE_LAMBDAS
  • The absolute magic about the State Monad in the above example is the code execution actually happens when we run the State Monad which happens here :

    println(state.run(Map()))

  • One other important point is: flatMap implicitly passes the state(in this eg: Map) to each of the subsequent functions after the first createEmployee since the for-comprehension on a Monad is a syntactic sugar of using flatMap function all the way finally yielding a value using the map function.

Screen Shot 2018-04-27 at 11.32.53 AM.png