DEV Community: Namc

Building resilient services

Namc — Wed, 17 Apr 2019 06:32:57 +0000

Original article published at : namc.in - Retries, Timeouts and Backoff

Distributed systems are hard. While we learn a lot about making highly available systems, we often overlook resiliency in system design.

Sure we have heard about fault-tolerant, but what is "resilience" now? Personally, I like to define it a system's ability to handle and eventually recover from unexpected conditions. There are several ways to go about making your systems resilient to failure, but in this post, we will focus on following

Timeouts
Retries
Backoff
Idempotency in distributed system

Timeouts

Timeout, simply put, is a maximum period of inactivity between two consecutive data packets.

I suppose we have worked with database drivers and http-clients at some point of time. All clients/drivers that help connect your service to an external server has a Timeout parameter, which often defaults to zero, or -1. This means that the timeout is undefined, or infinite.

eg - See the connectTimeout and socketTimeout definition Mysql Connector Configuration

Most requests to external servers should have a timeout attached. This is essential when the server is not responding in a timely manner. If this value is not set, and defaults to 0/-1 , your code may hang for minutes or even more. This happens because when you do not receive a response from application server and since your timeout is indefinite, or infintely large, the connection pool remains open. As more requests come in, more connections open up which consequently never close, thereby causing your connection pool to run out. This causes a cascading failure in your application.

So whenever you are configuring your application to use such connectors, please set an explicit timeout value in their configurations.

One must also implement timeouts on both, frontend and backend. That is, if a read/write operation is stuck on a rest api or socket for too long, an exception should be raised and connection should be broken. This should signal the backend to cancel the operation and close the connection, thereby preventing indefinitely open connections.

Retries

We might need to understand a little about transient failures as we would be using that term frequently.
Simply put, transient failures in your service are temporary glitches, e.g. a network congestion, database overload. Something which is perhaps correct itself given enough cool-off period.

How to determine if a failure is transient?

The answer lies in implementation detail of your API/Server responses. If you have a rest API, return a 503 Service Unavailable instead of other 5xx/4xx error messages. This will let the client know that the timeout is being caused by "a temporary overload" - not because of a code-level error.

Retries, although helpful, are a bit notorious if not configured properly. Here's how you can figure out the correct way to use retries.

Retry

If the error received from the server is transient, e.g. a network packet got currupted while being transmitted, the application could retry the request immediately because the failure is unlike to happen again.

This is however very agressive, and could prove to be detrimental to your service, which might already be running at capacity, or unavailable completely. It also degrades the application response time as your service would be trying to perform a failing operation continuously.

If your business logic requires this retry policy, it is best to limit the number of retries to prevent further requests going to the same source.

Retry after delay

If the fault is caused due to connectivity failures or due to excess traffic on the network, the application should add a delay period as per business logic before retrying the requests.

for(int attempts = 0; attempts < 5; attempts++)
{
    try
    {
        DoWork();
        break;
    }
    catch { }
    Thread.Sleep(50); // Delay
}

When using a library that connects to external services, please check if it implements retry policies, allowing you to configure maximum number of retries, delay between retries etc.

You can also implement retry policy on server-side, by setting a Retry-After in response header.

It is also important to log why the operation might be failing. Some times it is due to lack of resources which can handled by adding more instances of that service. Other times it could be due to a memory leak, or a null-pointer exceptions. Hence, it is imperative to add logs and track the performance of your application.

Backoffs

As we saw above, we can add delay to the retry policy. This delay is often referred to as linear backoff. This approach may not be the best way to implement a retry policy.

Consider the case where the fault in your service could be happening because the database is overloaded. It is quite possible that after some retries our request might succeed. It is also possible that consequent requests might be adding to the overload of your database server.Thus, the service would be in overloaded state far longer and will take more time to recover from this state.

There are several strategies that can be used to solve this problem.

1. Exponential Backoff

As the name suggests. instead of period delay of, say 5 seconds, between retries, increase the delay between requests exponentially. We do this till we reach the maximum retry limit. If the request continues to fail, let the client know that the request has failed.

You must also set a limit on how large the delay can be. Exponential backoff might result in setting a delay which is very large, thereby keeping the request socket open indefinitely, and making the thread sleep for "eternity". This will drain the system resources, thereby causing more problems with connection pools.

int delay = 50
for(int attempts = 0; attempts < 5; attempts++)
{
    try
    {
        DoWork();
        break;
    }
    catch { }

    Thread.sleep(delay);
    if (delay < MAX_DELAY)      // MAX_DELAY could depend upon application and business logic 
    {
        delay *= 2;
    }
}

One major drawback of exponential backoff is seen in distributed systems, where requests that backoff at the same time, also retry at the same time. This causes clusters of calls. Therefore, instead of reducing number of clients competing in every round, we have now introduced periods when no client is competing. A fixed progression exponential backoff does not reduce the contention much, and generates peaks of loads.

2. Backoff with jitter

In order to deal with load of spikes as mentioned in exponential backoff, we add jitter to our backoff strategy. Jitter is a decorrelation strategy, it adds randomness to retry intervals and spreads out the load. This avoids cluster of network calls.

Jitter is usually not part of any configuration property and needs to implemented by the client. All it only requires is a function which can add randomness, and dynamically calculate the duration to wait before retrying.

By introducing jitter, the initial group of failing requests may be clustered in a very small window, say 100ms, but with each retry cycle, the cluster of requests spreads into a larger and larger time window, thereby reducing the size of the spike at a given time. The service is likely to be able to handle the requests when spread over a sufficiently large window.

int delay = 50
for(int attempts = 0; attempts < 5; attempts++)
{
    try
    {
        DoWork();
        break;
    }
    catch { }

    Thread.sleep(delay);
    delay *= random.randrange(0, min(MAX_DELAY, delay * 2 ** i)) // just a simple random number generation
}

In case of long-lasting transient failures, retries of any kind might not be the best approach. This could be due to a connectivity failure, power outtage (yes, they are very real) etc. The client would end up retrying several times, wasting system resources, further leading to cascading failures across multiple systems.

So we need a mechanism to determine if the failure is long-lasting, and implement a solution to handle it.

3. Circuit Breakers

Circuit Breaker pattern is useful for handling long-lasting transient failures of a service by determining its availability, preventing the client from retrying requests that are bound to fail.

Circuit breaker design pattern requires that the state of the connection be retained over a series of requests. Lets look at this Circuit breaker implementation by failsafe

CircuitBreaker breaker = new CircuitBreaker()
  .withFailureThreshold(5)
  .withSuccessThreshold(3)
  .withDelay(1, TimeUnit.MINUTES);

Failsafe.with(breaker).run(() -> connect());

When everything runs as expected, there are no outtages, the circuit breaker remains in a closed state.

When a threshold of executation failures occur, the circuit breaker trips and goes into open state, which means, all consequent requests will continue to fail without going through retry logic.

After a delay (1 minute as mentioned above), the circuit will go into half-open state, just to test if the problem with network call still exists, thereby deciding if the circuit should be closed or opened. If it succeeds, the circuit resets to closed state, else it is set as open again.

This helps in avoiding cluster of retry executions during long lasting faults, saving system resources.

While this can be maintained locally in a state variable, you might need an external storage layer if you have a distributed system. In a multi-node setup, the state of application server will need to shared across all instances. In such a scenario, you can use Redis, memcached to keep a record of the availability of external services. Before making any requests to external service, the state of service is queried from the persistent storage.

Idempotency in distributed systems

A service is idempotent when clients can make same requests repeatedly while producing same end-result. While the operation would produce same result on the server, it might not give the same response to client.

In case of REST APIs, you need to remember -

POST is NOT idempotent - POST causes new resources to be created on server. "n" POST requests result in creating "n" new resources on the server.
GET, HEAD, OPTIONS and TRACE methods NEVER change the resource state on server. Hence, they are always idempotent.
PUT requests are idempotent. "n" put requests will overwrite the same resource "n-1" times.
DELETE is idempotent because it would return 200 (OK) initially, and 204 (No Content) or 404 (Not Found) on subsequent calls.

Why care about idempotent operations?

In a distributed system, there are several server and client nodes. If you make a request from Client to Server A which fail, or times out, then you would like to able to simply make that request again, without worrying if the previous request had any side-effects.

This is extremely essential in micro-services where a lot of components operate independently.

Some key benefits of idempotency are -

Minimal complexity - No need to worry about side effects, any request can be simply retried, and same end-result is achieved.
Easier to implement - You would not need to add logic to handle previous failed requests in your retry mechanism.
Easier to test - Each action result in same result, no surprises.

Final notes

We went through a bunch of ways you can build a more fault-tolerant system. However, that is not all. In closing, I would like to add a few pointers you can look into, which might help make your systems more available and tolerant to failures.

In a multi-node setup, if a client is retrying several times, the requests are likely to hit the same server. When this happens, it is best to give a failure response and making the client try again from scratch.
Profile your systems, keep them prepared for the worst. You might want to check out Chaos Monkey by Netlifx - its a resiliency tool which triggers random failures in your system. This keeps you prepared for faults that might occur, helping you build a resilient system.
If your systems are under excessive loads for some reason, you can try distributing it by load shedding. Google did a brilliant case study which can serve as a good starting point.

Resources -

Thank you! ❤

SSH Tunneling - Local, Remote & Dynamic

Namc — Wed, 27 Jun 2018 00:09:30 +0000

Original article published at : namc.in - SSH Tunneling

Most of us are familiar with SSH (Secure Shell) - a protocol which allows us to securely log onto remote systems. SSH Tunneling (also known as SSH Port Forwarding) is a feature of SSH which forwards encrypted connections between a local and remote system. SSH tunneling works by using the already established SSH connection for sending additional network traffic.

We're going to look at the three types of port forwarding - local, remote & dynamic.

Local port forwarding

Let's see what the man page for SSH tells us about local

local: -L 
Specifies that the given port on the local (client) host is to be forwarded to the given host and port on the remote side.

So generically, the command would look something like

$ ssh -L sourcePort:forwardToHost:destPort connectToHost

This translates to - connect with ssh to connectToHost, and forward all connection attempts to the local sourcePort to port destPort on the machine called forwardToHost, which can be reached from the connectToHost machine. Forwarding can also be done using Unix sockets.

Say YouTube is blocked on your office network, and you reaaaalllyy wanna watch some kitty videos. So, you can get around it by creating a tunnel through a server which isn't on your network and access YouTube. The above command can be translated to :

$ ssh -L 9000:youtube.com:80 user@example.com

The -L flag here signfies that we're doing local port forwarding. We connect with the user@example.com machine. We then forward any connection to port 9000 on the local machine to port 80 (which is the default port for HTTP) on youtube.com. Now, if you open your browser and go to http://localhost:9000 , a request is made to HTTP server listening on youtube.com. However, you, on your local machine, have no webserver running.

You still won't be able to the see homepage - so don't worry about that.

The requests in the browser for localhost:9000 are built with a Host Destination header of localhost value. This request reaches youtube.com machine. But this request is ignored with an error message - Invalid virtual host .. because localhost cannot be a domain name on the server which is running youtube.

To fix this, we change the Host HTTP header enabling remote web server to identify the corresponding destination.

$ curl -H "Host: youtube.com" -L localhost:9000

-L parameter in curl is for following redirects. You should now be able to see the contents of homepage from youtube.com on localhost:9000 as long as you are connected to user@example.com machine.

Also! The good things about SSH tunnels is that they are encrypted, so nobody can see what sites you are visiting - only an SSH connection to your server. (Take that, Office admins!! 😎)

By default, anyone (even on different machines) can connect to the specified port on the local machine. This can be restricted to programs on the same host by supplying a bind address:

$ ssh -L 127.0.0.1:9000:youtube.com:80 user@example.com

SSH binds to port 9000 on the local machine. Any traffic that comes to this port is sent to the SSH server that listens on user@example.com - the remote machine. Once received by remote-machine, the traffic is then sent to port 80 of 127.0.0.1, which is user@example.com itself.

Connecting to a database behind a firewall

forwardToHost host may also refer to the remote machine through which the ssh connection is made (i.e. connectToHost) - in which case, the value for forwardToHost becomes 127.0.0.1 or localhost, as its local in the context of already established connection with connectToHost.

$ ssh -L 9000:127.0.0.1:80 user@example.com

An example for this is when you need to connect to a database console, which only allows local connection for security reasons, running PostgreSQL on your server, which by default listens on the port 5432.

$ ssh -L 9000:localhost:5432 user@example.com

This command forwards the local port 9000 to the port 5432 on the remote machine. You can connect to that remote PostgreSQL server through the local machine using psql on localhost:9000, simply like :

$ psql -h localhost -p 9000

Let's take a moment here and understand what is actually going on.

In the YouTube example, 9000:youtube.com:80 says - forward my local port 9000 to youtube.com at port 80. So SSH on your server actually makes a tunnel (connection) between those two ports - one of which lies on your local machine, and another on target machine.

In the example of database connection, 9000:localhost:5432 means localhost from server's perspective, not localhost on your machine. In other words - forward my local port 9000 to port 5432 on the server - because when you're on the server, localhost means server itself.

Port numbers less than 1024 or greater than 49151 are reserved for the system, and can only be forwarded by root. If you're using port forwarding of any kind, you need to specifiy the destination server, i.e. connectToHost.

Port forwarding is enabled by default. If not, check AllowTcpForwarding in /etc/ssh/sshd_config.

Remote port forwarding

Going back to the man-page again to see the definition of remote

remote: -R 
Specifies that the given port on the remote (server) host is to be forwarded to the given host and port on the local side.

The command would look much like local tunneling's but with an -R flag.

$ ssh -R sourcePort:forwardToHost:destPort connectToHost

This translates to - connect with ssh to connectToHost, and forward all connection attempts to the remote sourcePort to port destPort on the machine called forwardToHost, which can be reached from the connectToHost machine. Forwarding can also be done using Unix sockets.

Okay! Let's see an example.

Say you're developing an application on your local machine and you'd like to show the prototype to your boss.

In most cases, the ISP doesn't provide you with a public IP address, so you cannot connect your machine directly via the internet. While this problem can be solved by configuring NAT (Network Address Translation) on your router - this might not always work, there's a technical overhead of changing the configuration of your router, and you would need the admin access on your network.

In such a scenario, you can setup a server on internet which is publicly accessible and has SSH access. Then we tell SSH to make a tunnel that opens up a new port on server, and you connect to it via local port on your machine.

$ ssh -R 9000:localhost:3000 user@example.com

The syntax here is very similar to local port forwarding, with a single change of -L for -R.

SSH will connect to the remote machine - in this case user@example.com. The flag -R makes ssh listen on the port 9000 of that machine. Once there's a process on the machine connecting to 9000, the ssh server listening on the same machine will transfer that connection to local machine - the machine that initiated the ssh communication - and forward it to localhost on the port 3000.

Remote port forwarding allows to map a port of the local machine onto the remote server via SSH.

Another thing which you need to do is to set GatewayPorts. In your /etc/ssh/sshd_config , set

GatewayPorts yes

And restart SSH

$ sudo service ssh restart

This allows the SSH server to bind port 3000 to the wildcard address - such that the port becomes available to the public address of the connectToHost remote machine.

You can also set GatewayPorts to clientspecified - in which case, the remote port will not bind on the wildcard address. You might need to explicitly specify an empty bind address for binding the wildcard address - which can be done by prefixing remote port with : sign.

$ ssh -R :9000:localhost:3000 user@example.com

You can also specify an IP address from which connections to the port are allowed, such that only connections from the given IP address to the given port are allowed.

$ ssh -R 1.2.3.4:9000:localhost:3000 user@example.com

Now your boss will be able to access your application on port 3000 by pointing their browser to connectToHost IP address on the port 9000.

Double forwarding

If the remote server has GatewayPorts set to no, with no possibility of changing it - you can execute the remote forwarding above followed by a local forwarding using -g option, but from the remote server.

$ ssh -g -L 9000:localhost:3000 user@example.com

-g allows remote hosts to connect to local forwarded ports and this will make loopback port 3000 on the server accessible on all interfaces on port 9000.

Dynamic port forwarding - SOCKS

Dynamic port forwarding allows communication across a range of ports. This port forwarding is created using a -D parameter. This makes SSH acts as a SOCKS proxy server.

There's two kinds of SOCKS protocols - SOCKS4 and SOCKS5. These are basically internet protocols which route packets between a server and a client using proxy server. SOCKS5 uses both TCP and UDP, whereas SOCKS4 uses only TCP.

A SOCKS proxy is a simple SSH tunnel in which specific applications forward their traffic through the tunnel to the remote server, then the proxy forwards the traffic out to the general internet. Unlike a VPN, SOCKS proxy has to be configured for each application separately on the client machine.

Dynamic port forwarding can handle connections from multiple ports. It analyses the traffic to determine the destination for given connection. However, you might need to configure programs to use a SOCKS proxy server.

This can be done by :

$ ssh -D 9000 -f -C -q -N connectToHost

-D tells SSH to create a SOCKS tunnel on the the port 9000.
-f forks the process to the background.
-C compresses the data before sending it.
-q enables quiet mode.
-N tells SSH that no command will be sent once the tunnel is up.

A downside to using proxies is decreased performance and mislabelled errors as they rewrite data packet headers. With SOCKS5 proxy, the server does not rewrite data packet headers - hence being more performant and less prone to data routing errors. Because SOCK5 proxies they are low-level, they can work with any kind of data traffic - program, protocol etc.

Closing Tip!

The -nNT flags will cause SSH to not allocate a tty and only do the port forwarding. This will prevent the creation of shell everytime you create a tunnel.

$ ssh -nNT -L 9000:youtube.com:80 user@example.com

What is Currying?

Namc — Sun, 25 Feb 2018 06:37:10 +0000

Original article published at : https://namc.in/2018-02-22-currying

Inspiration

This post is written after I saw a tweet which read

Every functional programming tutorial:

OK, we're going to talk about currying. Currying is when you break down a function tha-
scrolls down
const Y = f => (g => g(g))(g => f(x => g(g)(x)))

And realized that we need a simpler tutorial to understand currying, the logic behind it, the nuances and the usage.

We will be using Haskell for this tutorial, but this can be extended to any functional programming language.

Higher-order functions!

In mathematics, higher-order functions (HOFs) are called functionals. But to simplify it for general software engineers, HOF is simply a functions that

either takes a function as an argument
or returns a function as a result

A well-known higher order function is map, which performs an action on each element in a collection, e.g.:

-- Haskell
map (\x -> 2 * x) [1, 2, 3, 4, 5] -- => [2, 4, 6, 8, 10]

In usual imperative programming, functions can accept values, like integers and strings (first order functions) and return a value of some other type.

Consider a function, f such that -

f a b c = a + b - c

What if we wanted to generalize the operators in above function? That would make our operators a variable too. Right? Let's see a way to define a more generalized version of f, where g and h represent the operator-functions.

let f g h a b c = a `g` b `h` c

> f (+) (-) 2 3 4 -- returns 1
> f (*) (/) 2 3 4 -- returns 1.5

That was simple! But, we mentioned that HOFs can return a function too. Yes, we can create a function that accepts a function and an argument and returns another function, which accepts an argument and returns a result. For example :

let g f n = (\m -> m `f` n) 

> f = g (+) 2  
> f 10 -- returns 12

> f = g (*) 2
> f 10 -- returns 20

In the above example, (\m -> mfn) construct is an anonymous function of 1 argument m which applies f to m and n. And using this anonymous functions, we can define g h 2 which is a function that accepts one argument g and operates h to it.

Trivia : Scheme, according to Wikipedia, was the first language to introduce proper higher-order functions as first-class citizens, however the first mention dates back to Frege in "Funktion und Begriff" (1891).

Currying

Currying is a technique that transforms a function of several arguments to a function of a single argument, which returns a function of 1 argument, which returns a functions of 1 argument ... till it returns a value.

A curried function is one that returns a function as its result. A fully curried function is a one-argument function that either returns an ordinary result or returns a fully curried function.

Note that a curried function is necessarily a higher-order function, since it returns a function as its result.

Let's take an example, where we have a function of two args, like (+). But what if you could define the same function, by giving only one argument to it, thereby returning a function, which you could use later to add thid 1st argument, now encased in this new function, to something else.

f n = (\m -> n + m)

> g = f 10
> g 8 -- would return 18
> g 4 -- would return 14

Same can be written in javascript like :

function add (a) {
  return function (b) {
    return a + b;
  }
}

add(3)(4)

How could be make it more abstract? Lets define curry , which takes a function and an argument, such that

curry f n = \m -> f n m

g = curry (+) 5
> g 10 -- returns 15

h = curry (*) 5
> g 10 -- returns 50

If we check the type :t of curry function defined above, we find,

curry :: (a -> b -> c) -> a -> (b -> c)

Haskell functions

Haskell curries all functions by default. There are no functions of multiple arguments in Haskell. What you have are only functions of one argument, some of which may return new functions of one arguments. So you can define a multi-argument function as you would in any other language and you automatically get a curried version of it, without having to write lamdas yourself.

For example, take the function (++) which concatenates two strings together.

:t (++)
(++) :: [a] -> [a] -> [a]

The type definition can be understood as, (++) accepts one list, and returns a function of type [a] -> [a]. The resultant function can accept yet another list, and we get a new list of type [a].

If you are familiar with other languages, you can correlate f a b c as Lisp's (((f a) b) c) or Java's f(a, b, c) . This makes sense as , in Haskell, the function f is curried by default.

However, when you're analyzing types, the association is from right to left, so [a] -> [a] -> [a] is equivalent to [a] -> ([a] -> [a]), which means that when you apply an argument to the function, you get back a function of type [a] -> [a].

Similiary, you can analyze map, which accepts a function (a -> b) and a list [a] , and returns a transformed list [b], such that function is mapped over all elements of [a].

:t map
map :: (a -> b) -> [a] -> [b]

Try the following snippet out in ghci

(*)
(*) 5
(*) 5 10
map
map (\x -> head x)
map (\x -> head x) ["hello", "haskell", "kitty"]
map head
map head ["hello", "haskell", "kitty"]

Partial application

Partial application is when you call a function with 1 or multiple arguments to get back a function that still accepts arguments. This allows us to write shorter and concise code.

Partial application can be used as a substitute for anonymous functions. Let's look at some examples.

(\x -> take 2 x)

-- can be written as
(take 2)

What if you want to use an operator, say (+) instead of take? For infix functions, you can partially apply it using sections.

(\x -> 2 + x)
-- can be written as 
(2+)

-- and 
(\x -> x + 2)
-- can be written as
(+2)

In place of (+) , you can use any binary function to define sections.

(\xs -> 2 elem' xs)

-- can be written as
(2elem')

The point to note here is , since every function is curried by default, and accepts one argument only, so sections can be used with any function. For example ,

let f a b c d = a + b + c

-- such that f is (+)

> (2f) 3 4 5 -- returns 14

Currying and Pattern Matching

We take for granted that we can have nested patterns and patterns over more than one term, when in reality for the purposes of a compiler the only thing you can do is branch on the top-level constructor of a single value. So the first stage of the compiler is to turn nested patterns (and patterns over more than one value) into simpler patterns.

Let's take an example, a naive algorithm might transform your function into something like this:

myFunc = \x y -> case x of
    0 -> case y of
        0 -> 0
        _ -> x `some_operation` y
    1 -> case y of
        1 -> 1
        _ -> x `some_operation` y
    _ -> x `some_operation` y

As we can see, there are a lot of caveats in the above implementation.

the some_operation term is repeated a lot
the function expects both arguments before it will even start to do a case at all

Refer to A Term Pattern-Match Compiler Inspired by Finite Automata Theory for further discussions on how we can improve it.

Anyway, in the form below, it should actually be a bit more clear how the currying step happens. We can directly substitute for x in this expression to look at what myFunc 0 does:

myFunc 0 = \y -> case 0 of
    0 -> case y of
        0 -> 0
        _ -> 0 `some_operation` y
    1 -> case y of
        1 -> 1
        _ -> 0 `some_operation` y
    _ -> 0 `some_operation` y

Now this is still a lambda, so no further reduction is done.

We will need to change the definition of our function if we want GHC to do more computation after supplying only one argument. There's a time/space tradeoff here. So GHC leaves it in the programmer's hands to make this choice. For example, you could explicitly write

myFunc 0 = \y -> case y of
    0 -> 0
    _ -> 0 `some_operation` y

myFunc 1 = \y -> case y of
    1 -> 1
    _ -> 1 `some_operation` y

myFunc x = \y -> x `some_operation` y

and then myFunc 0 would reduce to a much smaller expression.

Compositions

Compositions and Application operator are very handy for writing concise and flexible code.

Composition operator (.) chains functions together.
Application operator ($) applies function on the left side to the argument on the right side

f $ x is equivalent to f x. However ($) has the lowest precedence of all operators, so we can use it to get rid of parentheses: f (g x y) is equivalent to f $ g x y.

It is also helpful when we need to apply multiple functions to the same argument:

map ($2) [(2+), (10-), (20/)] 

-- would yield 
[4,8,10]

The following expressions are all equivalent

f (g (h (x + y + z)))   -- 1

(f . g . h) (x + y + z) -- 2

f $ g $ h $ x + y + z   -- 3

f . g . h $ x + y + z   -- 4

(.) and ($) are different things. More can be read about that here - Learn you a haskell ($)

ELI5 - "Map-filter-reduce"

Namc — Mon, 04 Dec 2017 10:12:14 +0000

Many developers that I have lately interacted with associate map-reduce-filter with functional programming, and they are actually dreaded by the combination. It’s one of the reasons they avoid using functional languages, because god forbid they would have to learn how to use map, reduce and filter — 3 functions present in Ruby, Python, Javascript, PHP, Erlang, Scala and many others languages.

So what’s the big deal with map-reduce-filter anyway?

They are just higher-order functions used in functional programming. And they work on anything that is iterable (list, tuple, sets, dicts, and even strings).

Let’s consider a problem statement to be able to follow more clearly. (We’re using Python for the ease of purpose, but I’ll add a gist of how the same thing can be done in various other languages)

Problem statement :
We need the sum of all even squares of integers in the range [0, 9]

Map (Transform)

This function takes a unary function and a list. Unary function is a function that takes one variable. The resultant for map function is a same-sized list of transformed values. The transformation of value is subject to the definition of unary function with the parameter.

Use when : You want to transform all elements in a set to another set of values.

Parameters : unary transformation function & array to be transformed

In order to solve the problem statement, let’s say, our first step is to map the function of calculating squares over the range of numbers [0, 9]

>>> nums = map(lambda x : x*x, [i for i in range(10)])
>>> nums
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

Lambdas are often to define map functions. You can use regular functions as well.

Filter

This function takes a predicate, (a unary function which returns a bool) and the set of values; and gives a resultant set with only those set of values for which the predicate returns true. The resultant set may or may not be of the same length.

Use when : You want to remove elements from a set based on a condition.

Parameters : unary predicate (should only return a bool) & array to be filtered.

In context to our problem above, let’s try to remove all the odd squares from the list. For that, let our predicate return true if the element is even.

>>> def is_even(x):
        return x % 2 == 0
>>> evens = filter(is_even, nums)
>>> evens
[0, 4, 16, 36, 64]

Comprehensions often make it easier to write filters. Those can be used in place of functions as well.

Reduce (Accumulate)

This function takes a binary function and a set of values, and it produces a single value. It does so by running the binary function over the set of values, and accumulating them into a single value.

Use when : You want an accumulated or concatenated value using given set of values.

Parameters : binary function and set of values.

In context to our problem above, we shall add up all the even-valued squares.

>>> reduce(lambda x,y : x+y, evens)
120

If we look at the defintion of reduce in functools module,

def reduce(f,alist)
    if alist == []:
        return None

    answer = alist[0]
    for v in alist[1::
        answer = f(answer,v)
    return v

we see that reduce function starts by setting answer as the first element of array. Then it traverses the array from left to right, invoking a callback function on each element. The cumulative value is passed from callback to callback. After all elements are traversed, cumulative value is returned.

Combining map-filter-reduce

We saw a lot of small functions being written above, that was just for understanding. The true power of higher-order-functions lie in combination. So our problem statement can be solved in one line of code 😅

>>> reduce(lambda a, b: a + b, map(lambda x: x * x, filter(lambda y: not y % 2, range(10))))
120

Don’t Panic! ! We can break it down for simplicity.

f_add = lambda a, b: a + b
f_square = lambda x: x * x
f_is_even = lambda y: not y % 2

Now the complex expression can be rewritten as

>>> reduce(f_add , map(f_square , filter(f_is_even, range[0, 10]))

As a sidenote, there is no restriction on using map , filter & reduce together. You can make your own combinations, and order your functions as per the need.

Other languages

Keeping the problem statement same as above, check out how map-reduce-filter can be used in other programming languages, and is not a rocket science at all 🚀

Ruby

def main()

    nums = [*0..9]

    ans = nums.map{|x| x * x}              # map operation (x*x) over nums
              .select{|x| x % 2 == 0}      # select event elements
              .reduce{|a, x| a + x}        # reduce the list by `+` operation

    p nums                                 
    p ans                                  

end
main()

Clojure

(reduce (fn [a b] (+ a b)) 
        (map (fn [x] (* x x)) 
             (filter even? (range 10))))

Javascript

(I’m really bad at this 😕)

let numbers = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

ans = numbers 
    .filter(function(num) {
        return (num%2 === 0);
    })
    .map(function(num) { 
        return num*num;
    })
    .reduce(function(total, num){
        return total += num;
    });

Try it out in other languages as well!

Applicative functors in Haskell

Namc — Sat, 02 Dec 2017 11:39:36 +0000

Functor

According to Haskell, a functor is simply something that can be mapped over. In other words, it is an abstraction for a context with the ability to apply a function to all the things inside the context.
The context can be defined as container, computation etc.
E.g.; a list or sequence is a container of homogenous elements. You can apply a function to each of the elements, which produces a new sequence of elements transformed by the function.

Let’s create a new functor, implementing myfmap such that Data.Map is an instance of the new functor typeclass. myfmap applies a function f to the value(s) inside functor’s context while preserving the context.

import Data.Map as DataMap
import Data.List as DataList

class MyFunctor f where
  myfmap :: (a -> b) -> f a -> f b

instance (Ord k) => MyFunctor (DataMap.Map k) where
  myfmap f x = DataMap.fromList $ 
                     DataList.map (\(p,q) ->(p,f q)) $ 
                     DataMap.toList x

Applicative Functor

In computer science, applicative is an abstraction for a context, and it has the ability to apply functions in the same type of context to all elements in the context. For example, a sequence A which has homogenous elements, and sequence B which consists of functions that can be applied to sequence A , which produce a new sequence of elements transformed by all the functions. (Super confusing? Sorry 😕)

The Applicative typeclass in Haskell is located in Control.Applicative module and defines pure and (<*>) .

class (Functor f) => Applicative f where
    pure :: a -> f a
    (<*>) :: f (a -> b) -> f a -> f b

An Applicative has to be Functor. This is a class constraint.
pure takes any context and returns an Applicative the value of context inside it.
(<*>) is a representation of fmap , where <*> takes a functor that has a function in it and another functor and run the function from first functor and maps it over the second functor. Whereas fmap which takes a function and functor and applies the function inside the functor.

—

List an an Applicative!

List also instantiates an applicative typeclass, with implementation as :

instance Applicative [] where
    pure x = [x]
    fs <*> xs = [f x | f <- fs, x <- xs]

Here, the implementation of (<*>) is basically a list comprehension, where every function is applied to every value. For example :

ghci> (*) <$> [2, 3] <*> [4, 5]
[8, 10, 12, 15]

If you want to apply each function in first list to the respective value in second list, the ZipList typeclass is very handy.

—

Curious case of `Either`

The base Monad instance for Either is defined as follows.

instance Monad (Either e) where
  return = Right
  Left e  >>= _ = Left e
  Right a >>= f = f a

This instance has inherent short-circuiting, where we go from left to right and once a single computation fails into the Left , then all do as well. But in case you would like to collect error messages which occur anywhere in the above computation, it goes against (>>=) and lazy-evaluation/short-circuiting .

Lazy evaluation is when we proceed from left to right, when a single computation “fails” into the Left then all the rest do as well.

(>>=) takes a function, maps it over an instance of a monad and then flattens the result.
(>>=) :: m a -> (a -> m b) -> m b

(>>=) produces m b from m a so long as it can run (a -> m b) . This demands that the value of a should ideally exists during the time of computation, and this is impossible for Either .

—

So let’s try to solve the above problem by defining a Functor instance of Either .

instance Functor (Either a) where
    fmap f (Left x) = Left x
    fmap f (Right y) = Right (f y)

Things we can understand from the above definition :

We know the definition of fmap :: (c -> d) -> f c -> f d .
If we replace f with Either a , we get
fmap :: (c -> d) -> Either a c -> Either a d

The problem with this implementation of Either is that we cannot map over Left .
(😱Why?) To understand that, let Either a b computation, which may succeed and return b or fail with error a , similar to monad instance. So the functor instance does not map over Left values since you would want to map over the computation, if it fails, there is nothing to manipulate.

—
Let’s see if we can implement an Applicative instance instead, which cannot have a corresponding Monad , to solve the problem.

As we saw the definition of Applicative, we will define pure and (<*>) .

Defining pure is rather simple, as we want it return the Right element. Implementation of (<*>) is rather tricky . The following cases need to be considered for defining (<*>)

instance Applicative (Either e) where
    pure                 =  Right
    Right f  <*> Right a  = Right (f a)    
    Left  e  <*> Right _ = Left e          
    Right _  <*> Left  e = Left e          
    Left e1  <*> Left e2 = Left (e1 <> e2)

The first statement is the pure statement.
(<*>) allows evaluation in parallel instead of necessarily needing results from previous computation to compute present values.
Thus, we can use our purely Applicative Either to collect errors, ignoring Right if any Left exist in the sequence.
As soon as it hits a Left, it aborts and returns that Left.


ghci> (++) <$> Left "Hello" <*> undefined 
Left "Hello"                              -- not undefined

ghci> (++) <$> Right "Hello" <*> undefined 
*** Exception: Prelude.undefined          -- undefined

ghci> (++)  <$> Right "Hello" <*> Left " World"
Left " World"

ghci> (++)  <$> Right "Hello" <*> Right " World"
Right "Hello World"

—

Limitations

There’s some limitations to using purely applicative functor. As we saw in the definition of (>>=) :: m a -> (a -> m b) -> m b ; which means that without (>>=) you can’t pick “what to do next based on what came before”.
Also, if you take a generally pure function and feed the applicative arguments to it, like

> f :: a -> b -> c 
> f <$> getLine <*> getProcessID "chrome" <*> getFreeMemory

All the arguments will get evaluated, no matter what. That is, you cannot express — “if the second argument exits, abort the rest of the computation”. Due to this, anything recursive, as well as most interactive programs do not use Applicatives. Monads, on the other hand are a good choice in that case.

Original Article - Applicative functors in Haskell

—
More Resources :

http://learnyouahaskell.com/functors-applicative-functors-and-monoids
http://adit.io/posts/2013-04-17-functors,_applicatives,_and_monads_in_pictures.html
https://hackage.haskell.org/package/base-4.8.1.0/docs/Control-Applicative.html
https://stackoverflow.com/questions/17409260/what-advantage-does-monad-give-us-over-an-applicative

lazy-seq in Clojure

Namc — Tue, 28 Nov 2017 04:20:02 +0000

Basic idea :
Evaluation of an expression is delayed until the value is needed.

There are two ways to achieve the above :

use lambda functions at runtime
use macros/special forms at compile time

With lazy eval techniques, it is possible to construct infinite data structures that are evaluated as consumed, using lambdas, closures and recursion. In clojure, they are generated using lazy-seq and cons forms.

Let’s take an example from the Clojure docs for lazy-seq

user> (def fib-seq
 (lazy-cat [0 1] (map + (rest fib-seq) fib-seq)))
;; => #'user/fib-seq

lazy-cat is another macro to concatenate lazy sequences. We shall write the above expression to an alternate translation which uses lazy-seq

user> (def fib-seq (concat (lazy-seq [0 1]) (lazy-seq (map + (rest fib-seq) fib-seq))))
;; => #'user/fib-seq

user> (doall (take 2000 fib-seq))

This lazy-seq evaluates for very large indexes without giving an OutOfMemoryException/StackOverFlowError. (Might throw ArithmeticException for extremely large integer, though)

How this works internally :

lazy-seq executes the body once the first time it is accessed.
the result is cached and used whenever the function is called in future.

Going back to the example;

[0 1] is the base case for the problem. In Fibonacci’s sequence, the first two values are 0 and 1. The consecutive computation of each value requires summation of previous value and the value before that one. Hence, we need at least two values to start the process.

(map + (rest fib-seq) fib-seq)
Here, rest will return the part of fib-seq without it’s head. map will combine two sequences using + and produce a next sequence. Let’s take the fibonacci sequence fib-seq-temp

user> (def fib-seq-temp [0 1 1 2 3])
user> (map + (rest fib-seq-temp) fib-seq-temp)
;; => (1 2 3 5)

The sequences fed to map are part of same basic sequence . The first sequence (rest [seq]) is the base seq without the head. The second sequence is the base seq, including the first value.

What is the base sequence here?

According to fibonacci number’s definition, A(n) = A(n-1) + A(n-2) . We need to be able to access previously computed values in order to extend the sequence. So, we use the recursive reference to fib-seq to access our previous results. The base seq is typically [0 1] here to begin with.

Let’s follow the steps mentioned above and run through the process :

Take the first element of fib-seq (base case [0 1] ) — 0
Take the second element of fib-seq — 1
Take the third element of fib-seq — Stuck, aren’t we?

Here, we use map to generate a sequence which is used as remaining values.
The sum of rest [0 1] which is 1, and first item of [0 1] , which is zero is 1 ; which is our result below.

user> (map + (rest [0 1]) [0])
;; => (1)

Similarly, let’s repeat the process for generating fourth element.
We use map again for generating base seq.
Compute the sum of second item of rest [0 1], whose value is (1) as computed above; and second item of [0 1]

user> (map + (rest [0 1]) [1])
;; => (2)

Easy so far?

Now generate the fourth element.
Sum the third element of rest [0 1] (which we computed as 1) and fourth item generated from [0 1] (which was 2 ). And we get 3 .

This will keep building up to match the desired definition for series. To understand this better, let’s add a print statement to our original definition.

user> (def fib-seq
  (lazy-cat [0 1] 
            (map 
              (fn [a b]
                (println (format "%d + %d" a b)
                (+ a b))
            (rest fib-seq) fib-seq)))
;; => #'user/fib-seq
user> (doall (take 10 fib-seq))
1 + 0
1 + 1
2 + 1
3 + 2
5 + 3
8 + 5
13 + 8
21 + 13
;; => (0 1 1 2 3 5 8 13 21 34)

—-

Working with different data-types

map , reduce , take etc work in terms of first , rest and more .
first (as well as others) ensure if the collection implements ISeq .
If yes, then these functions are implemented directly. Else, a seq view of the collection is created to implement first / more / rest .

lazy-seq macro

The macro uses thunk to store the sequence-generating calculations.
When an element/chunk of sequence is requested, next thunk is called to retrieve the values.
The thunk creates next subroutine to represent the tail of the sequence (lose your head).
These thunks implement sequence interface, each thunk is called just once, and then cached. So the realized portion is just a sequence of values.

Holding onto the head

Take these two methods to generate infinite lazy seqs of randoms.

user> (defn infinite[] (lazy-seq (cons (rand) (infinite))))
;; => #'user/infinite
--
user> (defn infinite-1[] (lazy-seq (cons (rand) (infinite-1))))
;; => #'user/infinite-1
user> (def zyx (infinite-1))

If you try to run (last (infinite)) ; it won’t crash, but will neither terminate. However, (last zyx) will crash quickly with an OutOfMemoryError .

This is because of “holding onto the head”.

In (last (infinite)) , Clojure disposes the earlier members of sequence because it is able to determine that they are not of any use. Hence, memory is not lost. Whereas, in (last zyx) , the program is holding on to the definition , and hence, it is not able to clear the memory. This causes it to throw OutOfMemoryError .

So what’s the point of lazy-seq ?

lazy-seq is just one of many possible ways to create lazy sequences. And there are several other ways to do it in clojure.

If a sequence is not lazy, it often holds onto it’s head, which consumes a lot of heap space. If it is lazy, it is computed, then discarded as it is not used for further computations. This is particularly useful when you are dealing with huge sequences, and only using a small part of them for sequential computation.

Original Article on Medium