In the previous post we saw how JIT inlining works. We also saw how the JVM performs OSR to replace the interpreted version of the method to the compiled version on the fly. In this post we’ll dig even deeper and see the assembly code that is generated when the method gets compiled.

Prerequisites

The flag which enables us to see assembly code is -XX:+PrintAssembly. However, viewing assembly code does not work out of the box. You’ll need to have the disassembler on your path. You’ll need to get hsdis (HotSpot Disassembler) and build it for your system. There’s a prebuilt version available for Mac and that’s the one I am going to use.

1

git clone https://github.com/liuzhengyang/hsdis.git

Once we have that, we’ll add it to LD_LIBRARY_PATH.

1

export LD_LIBRARY_PATH=./hsdis/build/macosx-amd64

Now we’re all set to see how JVM generates assembly code.

Printing assembly code

We’ll reuse the same inlining code from last time:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

public class Inline {
    public static void main(String[] args) {
        long upto = Long.parseLong(args[0]);

        for(int i = 0; i < upto; i++) {
            int x = inline1();
        }
    }

    public static int inline1() {
        return inline2();
    }

    public static int inline2() {
        return inline3();
    }

    public static int inline3() {
        return 4;
    }
}

-XX:+PrintAssembly is a diagnostic flag so we’ll need to unlock JVM’s disgnostic options first. Here’s how:

1

java -XX:+UnlockDiagnosticVMOptions -XX:+PrintAssembly Inline 100000

This will generate a lot of assembly code. We will, however, look at the assembly code generated for inline1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

Decoding compiled method 0x000000010d6095d0:
Code:
[Disassembling for mach='i386:x86-64']
[Entry Point]
[Verified Entry Point]
[Constants]
  # {method} 'inline1' '()I' in 'Inline'
  #           [sp+0x20]  (sp of caller)
  0x000000010d609700: sub    $0x18,%rsp
  0x000000010d609707: mov    %rbp,0x10(%rsp)    ;*synchronization entry
                                                ; - Inline::inline1@-1 (line 11)
  0x000000010d60970c: mov    $0x4,%eax
  0x000000010d609711: add    $0x10,%rsp
  0x000000010d609715: pop    %rbp
  0x000000010d609716: test   %eax,-0x496b71c(%rip)        # 0x0000000108c9e000
                                                ;   {poll_return}
  0x000000010d60971c: retq
  0x000000010d60971d: hlt
  0x000000010d60971e: hlt
  0x000000010d60971f: hlt
[Exception Handler]
[Stub Code]
  0x000000010d609720: jmpq   0x000000010d6050a0  ;   {no_reloc}
[Deopt Handler Code]
  0x000000010d609725: callq  0x000000010d60972a
  0x000000010d60972a: subq   $0x5,(%rsp)
  0x000000010d60972f: jmpq   0x000000010d5deb00  ;   {runtime_call}
  0x000000010d609734: hlt
  0x000000010d609735: hlt
  0x000000010d609736: hlt
  0x000000010d609737: hlt    Decoding compiled method 0x000000010d6064d0:

So this is the assembly code that we get when we run the program. It’s a lot to grok in one go so let’s break it down.

Line #7 and #8 are self explanatory; they show which method we’re looking at. Line #9 and #10 (and #13 to #17) are for thread synchronization. The JVM can get rid of thread synchronization if it sees that there is no need for it (lock eliding) but since we are using static methods here, it needs to add code for synchronization. It doesn’t know that we only have only one thread running.

Our actual program is on line #11 where we are moving the value 4 to %eax register. This is the register which holds, by convention, the return value for our methods. This shows that the JVM has optimized our code. Our call chain was inline1 ⟶ inline2 ⟶ inline3 and it was inline3 which returned 4. However, JVM is smart enough to see that these method calls are superfluous and decided to get rid of them. Very nifty!

Line #21 to #23 has code to handle exceptions. We know there won’t be any exceptions but the JVM doesn’t so it has to be prepared to deal with that.

And finally, there’s code to deoptimize. In addition to static optimizations, there are some optimizations that the JVM makes which are speculative. This means that the JVM generates assembly code expecting things to go a certain way after it has profiled the interpreted code. However, if the speculation is wrong, the JVM can go back to running the interpreted version.

Which flags control compilation?

-XX:CompileThreshold is the flag which controls the number of call / branch invocations after which the JVM compiles bytecodes to assembly. You can use -XX:+PrintFlagsFinal to see the value. By default it is 10000.

Compiling a method to assembly depends on two factors: the number of times that method has been invoked (method entry counter) and the number of times a loop has been executed (back-edge counter). Once the sum of the two counters is above CompileThreshold, the method will be compiled to assembly.

Maintaining the two counters separately is very useful. If the back-edge counter alone exceeds the threshold, the JVM can compile just the loop (and not the entire method) to assembly. It will perform an OSR and start using the compiled version of the loop while the loop is executing instead of waiting for the next method invocation. When the method is invoked the next time around, it’ll use the compiled version of the code.

So since compiled code is better than interpreted code, and CompileThreshold controls when a method will be compiled to assembly, reducing the CompileThreshold would mean we have a lot more assembly code.

There is one advantage to reducing the CompileThreshold - it will reduce the time taken for the branches / methods to be deemed hot i.e. reduce the JVM warmup time.

In older JDKs, there was another reason to reduce CompileThreshold. The method entry and back-edge counters would decay at every safepoint. This would mean that some methods would not compile to assembly since the counters kept decaying. These are the “lukewarm” methods that never became hot. With JDK 8+, the counters no longer decay at safepoints so there won’t be any lukewarm methods.

In addition, JDK 8+ come with tiered compilation enabled and the CompileThreshold is ignored. The idea of there being a “compile threshold”, though, does not change. I’m defering the topic of tiered compilation for the sake of simplicity.

Where is the compiled code stored?

The compiled code is stored in JVM’s code cache. As more methods become hot, the cache starts to get filled. Once the cache is filled, the JVM can no longer compile anything to assembly and will resort to purely interpreteting the bytecodes.

The size of code cache is platform dependent.

Also, JVM ensures that the access to cache is optimized. The hlt instructions in the assembly code exist for aligning the addresses. It is much more efficient for the CPU to read from even addresses than it is to read from odd addresses in memory. The hlt instructions ensure that the code is at an even address in memory.

Which flags control code cache size?

There are two flags which are important in setting the code cache size - InitialCodeCacheSize and ReservedCodeCacheSize. The first flag indicates the code cache size the JVM will start with and the latter indicates the size to which the code cache can grow. With JDK 8+, ReservedCodeCacheSize is large enough so you don’t need to set it explicitly. On my machine it is 240 MB (5x what it is for Java 7, 48 MB).

Conclusion

The JVM compiles hot code to assembly and stores it at even addresses in it’s code cache for faster access. Executing assembly code is much more efficient than interpreting the bytecodes. You don’t really need to look at the assembly code generated everyday but knowing what is generated as your code executes gives you an insight into what the JVM does to make your code run faster.

In the previous post we looked at how interpreted and compiled languages work. To recap, an interpreter works by generating assembly code for every bytecode it encounters. This is a very simple way to execute a program and also a very slow one. It ends up redoing a lot of translation from bytecode to assembly. Also, this simplistic approach means that the interpreter cannot do optimizations as it executes the bytecodes. Then there are compilers which produce assembly ahead-of-time. This overcomes having to generate assembly again and again but once the assembly is generated it cannot be changed on the fly.

JVM comes with both an interpreter and a compiler. When the execution of the code begins, the bytecodes are interpreted. For the sake of this series, I’ll be looking at Oracle HotSpot JVM which looks for “hot spots” in the code as the bytecodes get interpreted. These are the parts of the code which are most frequently executed and the performance of the application depends on these. Once the code is identified as “hot”, JVM can go from interpreting the code to compiling it to assembly i.e. the code is compiled “just-in-time”. In addition, since the code is being profiled as it is run, the compiled code is optimized.

In this post we’ll look at one such optimization: inlining.

Inlining

Inlining is an optimization where the call to a method is replaced by the body of the called method i.e. at the call site, the caller and the callee are melded together. When a method is called, the JVM has to push a stack frame so that it can resume from where it left off after the called method has finished executing. Inlining improves performance since JVM will not have to push a stack frame.

I’ll start with a simple example to demonstrate how inlining works.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

public class Inline {
    public static void main(String[] args) {
        long upto = Long.parseLong(args[0]);

        for(int i = 0; i < upto; i++) {
            int x = inline1();
        }
    }

    public static int inline1() {
        return inline2();
    }

    public static int inline2() {
        return inline3();
    }

    public static int inline3() {
        return 4;
    }
}

Next, let’s compile and run the code.

1

java -XX:+PrintCompilation -XX:+UnlockDiagnosticVMOptions -XX:+PrintInlining Inline 100000

Output:

1
2
3
4
5
6
7
8
9
10
11

63    1             Inline::inline1 (4 bytes)
63    2             Inline::inline2 (4 bytes)
                       @ 0   Inline::inline3 (2 bytes)   inline (hot)
                       @ 0   Inline::inline2 (4 bytes)   inline (hot)
                         @ 0   Inline::inline3 (2 bytes)   inline (hot)
66    3             Inline::inline3 (2 bytes)
66    4 %           Inline::main @ 9 (28 bytes)
                       @ 16   Inline::inline1 (4 bytes)   inline (hot)
                         @ 0   Inline::inline2 (4 bytes)   inline (hot)
                           @ 0   Inline::inline3 (2 bytes)   inline (hot)
66    4 %           Inline::main @ -2 (28 bytes)   made not entrant

Line #1 shows that inline1 was compiled to assembly. Line #2 and Line #6 show that inline2 and inline3 were also compiled to assembly. Line #3 to line #5 show inlining. We can see that inline3 was merged into inline2. Similarly, line #8 and #9 show that inline2 was merged into inline1. So basically, all the methods were inlined into inline1. This means that once a certain threshold is crossed, we’ll no longer be making methods calls at all. This gives a significant performance boost.

Which flags control inlining?

When you run a Java program, you can view the flags with which it ran using -XX:+PrintFlagsFinal. Let’s do that and look at a few flags of interest.

1

java -XX:+PrintFlagsFinal Inline 10000

You’ll see a bunch of flags and their default values. The ones we are interested in are CompileThreshold, MaxInlineLevel, MaxInlineSize, and FreqInlineSize.

CompileThreshold is the number of invocations before compiling a method to native.
MaxInlineLevel is a limit on how deep you’d go before you stop inlining. The default value is 9. This means if we had method calls like inline1 ⟶ inline2 … ⟶ inline20, we’d only inline upto inline10. There after, we’d invoke inline11.
MaxInlineSize decides the maximum size of a method, in bytecodes, to be inlined. The default value is 35. This means that if the method to be inlined has mre than 35 bytecodes, it will not be inlined.
FreqInlineSize, in contrast, decides the maximum size of a hot method, in bytecodes, to be inlined. This is a platform-dependent value and on my machine it is 325.

You can tweak these flags to change how inlining behaves for your program.

What is On Stack Replacement (OSR)?

When we make a method call, JVM pushes a stack frame. When a method is deemed hot, the JVM replaces the intrepreted version with the compiled version by replacing the old stack frame with a new one. This is done while the method is running. We saw OSR being indicated in our example. The % indicates that an OSR was made.

1

66    4 %           Inline::main @ -2 (28 bytes)   made not entrant

Let’s write some code to see OSR in action once again.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

import java.lang.ref.WeakReference;

public class OSR {
    public static void main(String[] args) {
        Object unused = new Object();
        WeakReference<Object> ref = new WeakReference<>(unused);

        int x = 0;

        while( ref.get() != null ) {
            x += 1;
            System.out.println(x);
        }

        System.out.println("Finished!");
    }
}

So this is a loop that will never terminate, right? Let’s run the program and see.

1
2
3
4

...
434062
  16828   59 %           OSR::main @ -2 (48 bytes)   made not entrant
Finished!

What just happened? When the JVM decided to perform an OSR, it saw that there was no use for the unused object and decided to set it to null, causing the WeakReference to return null and thus breaking the loop. When an OSR is performed, the method that is invoked doesn’t restart execution from the start. Rather, It continues from the “back-edge”. In our case, it would be the loop. Since the JVM saw that there was no use for the unused object after this back-edge, it was removed and the loop could terminate.

Being able to resume execution from the back-edge is very efficient. This means that once a method has been compiled to native code it can be used rightaway rather than at the next invocation of the method.

Conclusion

To recap, we saw how JVM inlines code. Fusing the caller and the callee provides for improved performance since the overhead of method dispatch is avoided. We saw the flags which control inlining and we saw how JVM performs OSR.

Inlining is a very useful optimization because it forms the basis for other optimizations like escape analysis and dead code elimination.

Motivation

My day job requires me to write code in Clojure. This means the code is eventually compiled to bytecode and run on the JVM. Intrigued by how the JVM does what it does, I decided to dig a little deeper and look at how it optimizes the code on the fly. In this series of posts I will be looking at JVM JIT (Just-In-Time) compiler.

Myriad ways to run a program

Before I go into how JVM JIT works, I want to take a quick look at how interpreted and compiled languages work. For this post, I’ll take a look at the working of Python (an interpreted language) and C (a compiled language).

Python

Python, by default, ships with CPython - the original Python interpreter that runs C code for every bytecode. There’s other implementations like IronPython or PyPy. IronPython turns Python into a fully compiled language running on top of Microsoft’s .NET Common Language Runtime (CLR) whereas PyPy turns Python into a JIT compiled language. For the sake of this post, however, I will look at CPython and how it works.

I’ll start with some code which will print the bytecodes for another Python file that is passed to it.

1
2
3
4
5
6
7
8
9
10
11

from sys import argv
from dis import dis

script, path = argv
source_file = open(path)
source_code = source_file.read()
compiled = compile(source_code, "<string>", "exec")
bytecodes = dis(compiled)

print(bytecodes)
source_file.close()

Next, here’s some code that’ll print numbers.

1
2

for n in [101, 102, 103]:
    print(n)

Now, let’s run the code and see the bytecodes we get.

1

python3 bytecode.py print_numbers.py

Output:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

  1           0 SETUP_LOOP              20 (to 22)
              2 LOAD_CONST               4 ((101, 102, 103))
              4 GET_ITER
        >>    6 FOR_ITER                12 (to 20)
              8 STORE_NAME               0 (n)

  2          10 LOAD_NAME                1 (print)
             12 LOAD_NAME                0 (n)
             14 CALL_FUNCTION            1
             16 POP_TOP
             18 JUMP_ABSOLUTE            6
        >>   20 POP_BLOCK
        >>   22 LOAD_CONST               3 (None)
             24 RETURN_VALUE
None

The loop starts on line #4. For every element in the list, we’re pushing print and n onto the stack, calling the function, popping the stack, and repeating the loop. For each of the bytecodes, there’s associated C code i.e. FOR_ITER, STORE_NAME, etc. have associated C code.

This is a very simple way to run a program and also a very inefficient one. We’re repeating the stack operations and jumps over and over again. There’s no scope for optimizations like loop unrolling.

C

In contrast to Python is C. All the C code is compiled to assembly ahead-of-time. Here’s a simple C program which will print “EVEN” if a number is even.

1
2
3
4
5
6
7
8
9
10
11
12

#include<stdio.h>

int main() {
  for(int i = 1; i < 10000; i += 2) {
    if( i % 2 == 0 ) {
      printf("EVEN!");
    } else {
      printf("");
    }
  }
  return 0;
}

Next, let’s compile this code.

1

gcc -S numbers.c

This will generate numbers.s. The assembly is fairly long so I’ll just cover the relevant parts.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

LBB0_1:
        cmpl    $10000, -8(%rbp) 
        jge     LBB0_7
        ...
        idivl   %ecx
        cmpl    $0, %edx
        jne     LBB0_4
        leaq    L_.str(%rip), %rdi
        ...
        callq   _printf
        movl    %eax, -16(%rbp)
        jmp     LBB0_5
LBB0_4:
        leaq    L_.str.1(%rip), %rdi
        movb    $0, %al
        callq   _printf
        ...
LBB0_5:
        jmp     LBB0_6
LBB0_6:
        ...
        addl    $2, %eax
        ...
        jmp     LBB0_1
        ...
LBB0_7:
        ...
        retq
        ...
L_.str:
        .asciz  "EVEN!"
L_.str.1:
        .space  1

Lines #2 - #3 show that if we’ve reached the limit of 10k, we’ll jump to LBB0_7 and the program ends.
If not, on line #5 we perform a signed division (idivl) and check if it is not zero. If it is not zero, we jump to LBB0_4 and print L_.str.1 which is just a whitespace.

We will always end up making this jump because we’ll never reach the condition where we have an even number. This is the problem with ahead-of-time compilation where you cannot speculate what the data is going to be and therefore you have to be ready to handle all the possibilities.

JVM JIT

JVM JIT combines the best of both the worlds. When you execute your program the first time, the bytecodes are interpreted. As the code continues to execute, JVM collects statistics about it and the more frequently used code (“hot” code) is compiled to assembly. In addition, there are optimizations like loop unrolling. Loop unrolling looks like this:

1
2
3
4
5
6
7
8
9

// Plain ol' loop
for(i = 0; i < 3; i++) {
    System.out.println(arr[i]);
}

// Unrolled
System.out.println(arr[0]);
System.out.println(arr[1]);
System.out.println(arr[2]);

Unrolling a loop helps avoid jumps and thus makes execution faster.

Also, since JVM collects statistics about code, it can make optimizations on the fly. For example, in the case where an even number is never reached, JVM can generate assembly code that’ll only have the else part of the branch.

Conclusion

JVM does some fairly intersting optimizations under the hood. The aim of this series of posts is to cover as much of this as possible. We’ll start simple and build upon this as we go.

One of the nice things that you’ll come across in Clojure is transducer. In this post I’ll go over what transducers are, how you can use them, how you can make one, and what transducible contexts are.

What are transducers?

In simple terms, transducers are composable transformation pipelines. A transducer does not care about where the input comes from or where the output will go; it simply cares about the transformation of the data that that flows through the pipeline. Let’s look at an example:

1
2
3
4

(let [xf (comp 
           (map inc)
           (filter even?))]
  (sequence xf (range 10)))

Here xf (external function) is our transducer which will increment every number and then will keep only the even numbers. Calling sequence functions like map, filter, etc. with single arity returns a transducer which you can then compose. The transducer doesn’t know where it will be used - will it be used with a collection or with a channel? So, a transducer captures the essence of your transformation. sequence is responsible for providing the input to the transducer. This is the context in which the transducer will run.

Here’s how the same thing can be done using threading macro:

1
2
3

(->> (range 10)
     (map inc)
     (filter even?))

The difference here is that the 2-arity version of map and filter will create intermediate collections while the 1-artity versions won’t. Transducers are much more efficient than threading together sequence functions.

Source for images

Inside a transducer

Let’s look at the 1-arity version of map and see what makes a transducer.

1
2
3
4
5
6
7
8
9
10
11

(defn map
  ([f]
    (fn [rf]
      (fn
        ([] (rf))
        ([result] (rf result))
        ([result input]
           (rf result (f input)))
        ([result input & inputs]
           (rf result (apply f input inputs))))))
   ...)

When you call 1-arity version of map you get back a transducer which, as shown above, is a function. Functions like map, filter, etc. take a collection and return a collection. Transducers, on the otherhand, take one reducing function and return another. The function returned is expected to have three arities:

So, the general form of a transducer is this:

1
2
3
4
5

(fn [rf]
  (fn 
    ([] (rf))
    ([result] (rf result))
    ([result input] ... )))

Using transducers

You can use a transducer in a context. There’s four contexts which come out of the box — into, transduce, sequence, and educe.

into

The simplest way to use a transducer is to pass it to into. This will add your transformed elements to an already-existing collection after applying the transducer. In this example, we’re simply adding a range into a vector.

1
2
3

(let [xf (comp (map inc)
               (map dec))]
  (into [] xf (range 10)))

Internally, into calls transduce.

transduce

transduce is similar to the standard reduce function but it also takes an additional xform as an argument.

1
2
3

(let [xf (comp (map inc)
               (map dec))]
  (transduce xf + (range 10)))

sequence

sequence lets you create a lazy sequence after applying a transducer. In contrast, into and transduce are eager.

1
2
3

(let [xf (comp (map inc)
               (map dec))]
  (sequence xf (range 10)))

eduction

eduction lets you capture applying a transducer to a collection. The value returned is an iterable application of the transducer on the collection items which can then be passed to, say, reduce.

1
2
3
4

(let [xf (comp (map inc)
               (map dec))
      coll (eduction xf (range 10))]
  (reduce + 0 coll))

Inside a transducible context

As mentioned before, transducers run in transducible contexts. The ones that come as a part of clojure.core would suffice most real-world needs and you’ll rarely see yourself writing new ones. Let’s look at transduce.

1
2
3
4
5
6
7
8

(defn transduce
  ([xform f coll] (transduce xform f (f) coll))
  ([xform f init coll]
     (let [f (xform f)
           ret (if (instance? clojure.lang.IReduceInit coll)
                 (.reduce ^clojure.lang.IReduceInit coll f init)
                 (clojure.core.protocols/coll-reduce coll f init))]
       (f ret))))

transduce is just like reduce. The 3-arity version expects an initial value to be supplied by calling the 0-arity version of the supplied function. The 4-arity version is slightly more involved. IReduceInit is an interface implemented by collections to let them provide an initial value. It lets a collection reduce itself. If not, the call goes to coll-reduce which is a faster way to reduce a collection than using first/next recursion.

Stateful transducers

It’s possible for transducers to maintain reduction state.

1
2
3
4
5
6
7
8
9
10

(defn multiply-xf
  []
  (fn [rf]
    (let [product (volatile! 1)]
      (fn
        ([] (rf))
        ([result] (rf result))
        ([result input]
         (let [new-product (vswap! product * input)]
           (rf result new-product)))))))

Here’s a transducer which will multiply all the incoming numbers. We maintain state by using a Volatile. Whenever we get a new input we multiply it with the product and update the state of Volatile using vswap!. Let’s see this in action:

1
2

(into [] (multiply-xf) [1 2 3])
=> [1 2 6]

Early Termination

The way the above transducer is written, it’ll process all the inputs even if one of the inputs is zero. We know that once we encounter a zero, we can safely end the reduction process and return a zero. reduced lets you return a reduced value and end the reduction. Let’s make a minor change to the above transducer and add in early termination.

1
2
3
4
5
6
7
8
9
10
11
12

(defn multiply-xf
  []
  (fn [rf]
    (let [product (volatile! 1)]
      (fn
        ([] (rf))
        ([result] (rf result))
        ([result input]
         (let [new-product (vswap! product * input)]
           (if (zero? new-product)
             (reduced result)
             (rf result new-product))))))))

In the 2-arity function, we check if the new-product is zero. If it is, we know we have a reduced value. We end the reduction by returning the result we have so far. Let’s see this in action:

1
2
3
4

(into [] (multiply-xf) [1 2 3])
=> [1 2 6]
(into [] (multiply-xf) [1 2 0 3])
=> [1 2]

Conclusion

Transducers can be a very useful tool in your Clojure toolkit that let you process large collections, channels, etc. effectively by letting you make composable transformation pipelines that process one element at a time. They require a little getting used-to but once you’re past the learning curve, performance galore!

December 2017 marks my completing one year as a software engineer. This post is a restrospective where I list down the lessons I’ve learned, in no specific order of priority.

Personal Life

Learn to invest

We’re having too good a time today. We ain’t thinking about tomorrow.
— John Dillinger, Public Enemy

It’s easy to get carried away because of the fat pay cheque your fancy developer job brings you at the end of the month. Think of all the bling you can buy. This hedonistic attitude, however, does not help you hedge against the volatility of the job market. In his book Out of our Minds: Learning to be Creative, Ken Robinson states that secure life-long employment in a single job is a thing of the past. This applies even more if you work in a startup environment where things change in the blink of an eye.

Making proper investments and establishing a second flow of cash can help you get a grip on the situation when it gets rough. The simplest way to invest is to put your money in the stock market and let the dividends add to your monthly flow of cash. You do not have to be an active day trader managing your positions. You can very easily invest in mutual funds, index funds, etc. and they are not that difficult to begin with.

One of the best books I’ve been recommended by a friend of mine is Trading and Exchanges: Market Microstructure for Practitioners by Larry Harris. This will give you a very good overview of the market and all that you need to become a confident investor.

Be ready to interview

Love your job but don’t love your company, because you may not know when your company stops loving you.
— A. P. J. Abdul Kalam, 11^th President of India

The key takeaway of working in a startup environment is this: things change very rapidly and when the push comes to shove, you will be thrown overboard. Having seen this happen to people close to me, I’ve learned that you need to be ready to interview with other startups and/or companies as soon as you are fired or have resigned. This includes staying in touch with the fundamentals you’ve learned in your CS class like data structures and algorithms, and also knowing the technologies you’ve used in reasonable depth. Also, having a good network of developers goes a long way in easing your search for a new job. And don’t forget to sharpen the saw — do things that are not programming that make you a better programmer.

Learn to negotiate

Dude, it’s five minutes. Let’s un-suck your negotiation.
— Patrick McKenzie

Learning how to negotiate is one of the most important skills that is often overlooked. It is overlooked because it is perceived to be cheap to negotiate for salary, or just plain avoiding difficult conversation. Whatever the case, get over it and learn the skill. As Patrick McKenzie mentions in his brilliant blog post Salary Negotiation: Make More Money, Be More Valued, all it takes is five minutes to finalize your salary. These five minutes have a lasting impact for alteast an year to come.

Read a lot

Read, read, read.
— William Faulkner

I’ll admit that it is hard to take time out to read daily but keeping a dedicated slot of 30 minutes just for reading goes a long way. I make sure it’s a distraction-free slot with no dinging notifications and I try not to multitask. Another exercise that I do in conjunction with reading is trying to improve my retention of the material I’ve read by improving my recall memory. The best way to do this is to use Feynman technique where you eludicate what you’ve learned and pretend to teach it to a student.

I prefer keeping one programming and one non-programming book as a part of my daily reading. In addition, there’s a list of blogs, and papers that I read from time to time. I’ll probably post a list as a separate post.

Engineering

Understand Peter principle

The key to management is to get rid of the managers.
— Ricardo Semler

Laurence Peter came up with the concept that a person in a role keeps getting promoted based on their performance in their current role and not on the abilities that the role demands. It is quite possible to have a manager who doesn’t know how to do his job well i.e. he’s risen to his level of incompetence. This principle is important to understand as an engineer and is something that should make one reflect on one’s current skillset - do you possess the abilities to be in the role you are currently in or do you need to skill up? Again, this goes back to my point on sharpening the saw and doing non-programming things that make you a better developer.

Tech debt is evil

Simplicity is hard work. But, there’s a huge payoff. The person who has a genuinely simpler system - a system made out of genuinely simple parts, is going to be able to affect the greatest change with the least work. He’s going to kick your ass. He’s gonna spend more time simplifying things up front and in the long haul he’s gonna wipe the plate with you because he’ll have that ability to change things when you’re struggling to push elephants around.
— Rich Hickey

When Ward Cunningham came up with the tech debt metaphor, he was referring to writing code despite having a poor understanding of the requirements. As time passes, whatever little understanding there was of the requirement fades away and the code is taken for granted. The definition of tech debt has since then come to represent poorly written code that later nobody understands and it’s taken for granted - something Ward Cunningham disagrees with.

The lethal combination is poorly written code for badly understood requirement(s) and you’ll come across this very often in startup environments. This comes with some pretty nasty ramifications like team in-fighting, and politics. In worst cases, it can bring the development of new features to a grinding halt.

Avoiding tech debt has to be a top priority for any startup that wants to grow. A lot of it revolves around establishing some processes to convey requirements among teams and ensuring that the resulting system design is simple. Like the quote by Rich Hickey shows, it is hard work but it will pay off in the longer run.

Centralize your Logs

However, logging doesn’t seem to receive the same level of attention; consequently, developers find it hard to know the ‘what, when, and how’ of logging.
— Colin Eberhardt

Please stop asking developers to SSH into machines to read the logs. Centralize your logs by using ELK or if you want to avoid the hassle of setting up ELK, use a third party service like Fluentd or similar. A good centralized logging strategy will not only save you the pain of SSH-ing into multiple servers and grep-ing, it will also let you search through them easily. In addition, aggregating logs from various servers helps you identify patterns that may emerge by checking what’s happening on multiple servers in a specific time range.

clojure.spec is a standard, expressive, powerful, and integrated system for specification and testing. It lets you define the shape of your data, and place contraints on it. Once the shape, and constraints are defined, clojure.spec can then generate sample data which you can use to test your functions. In this post I’ll walk you through how you can use clojure.spec in conjunction with other libraries to write unit tests.

Motivation

As developers, we are accustomed to writing example-based tests - we provide a known input, look at the resulting output, and assert that it matches our expectations. Although there is nothing wrong with this approach, there are a few drawbacks:

1. It is expensive as it takes longer to complete.
2. It is easier to miss out on the corner cases.
3. It is more prone to pesticide paradox.^[1]

In contrast, clojure.spec allows you to do generative, property-based testing. Generative testing allows you to specify what kind of data you are looking for. This is done by using generators. A generator is a declarative description of possible inputs to a function.^[2] Property-based testing allows you to specify how your program is supposed to behave, given an input. A property is a high-level specification of behavior that should hold for a range of inputs.^[3]

Setup

Creating an App

We’ll begin by creating an app using lein and defining the dependencies. So go ahead and execute the following to create your project:

1

lein new app clj-spec

Adding Dependencies

Next we’ll add a few dependencies. cd into clj-spec and open project.clj. Add the following to your :dependencies

1
2
3
4
5

[org.clojure/clojure "1.8.0"]
[clojure-future-spec "1.9.0-beta4"]  
[org.clojure/test.check "0.9.0"]  
[circleci/bond "0.3.0"] 
[cloverage "1.0.9"]

clojure.spec comes as a part of Clojure 1.9 which, as of writing, isn’t out yet. If you’re on Clojure 1.8, as I am, you can use clojure-future-spec which will give you the same APIs. circleci/bond is a stubbing library which we’ll use to stub IO, network calls, database calls, etc. cloverage is the tool we’ll use to see the coverage of our tests.

Using clojure.spec

Simple Specs

Fire up a REPL by executing lein repl and require the required namespaces ;)

1
2
3
4
5
6

clj-spec.core=> (require '[clojure.spec.alpha :as s])
nil
clj-spec.core=> (require '[clojure.spec.gen.alpha :as gen])
nil
clj-spec.core=> (require '[clojure.future :refer :all])
nil

spec will let us define the shape of our data, and constraints on it. gen will let us generate the sample data.

Let’s write a simple spec which we can use to generate integers.

1
2

clj-spec.core=> (s/def ::n int?)
:clj-spec.core/n

We’ve defined a spec ::n which will constrain the sample data to only be integers. Notice the use of double colons to create a namespace-qualified symbol; this is a requirement of the spec library. Now let’s generate some sample data.

1
2

clj-spec.core=> (gen/generate (s/gen ::n))
-29454

s/gen takes a spec as an input and returns a generator which will produce conforming data. gen/generate exercises this generator to return a single sample value. You can produce multiple values by using gen/sample:

1
2

clj-spec.core=> (gen/sample (s/gen ::n) 5)
(0 0 1 -1 0)

We could have done the same thing more succinctly by using the in-built functions as follows:

1
2

clj-spec.core=> (gen/generate (gen/vector (gen/int) 5))
[25 -29 -13 26 -8]

Spec-ing Maps

Let’s say we have a map which represents a person and looks like this:

1
2

{:name "John Doe"
 :age 32}

Let’s spec this.

1
2
3

(s/def ::name string?)
(s/def ::age int?)
(s/def ::person (s/keys :req-un [::name ::age]))

We’ve defined ::name to be a string, and ::age to be an integer (positive or negative). You can make your specs as strict or as lenient as you choose. Finally, we define ::person to be a map which requires the keys ::name and ::age, albiet without namespace-qualification. Let’s see this in action:

1
2

clj-spec.core=> (gen/generate (s/gen ::person))
{:name "KXYXcbk", :age 107706}

By now you must have a fair idea of how you can spec your data and have sample values generated that match those specs. Next we’ll look at how we can do property-based testing with specs.

Using test.check

test.check allows us to do property-based testing. Property-based tests make statements about the output of your code based on the input, and these statements are verified for many different possible inputs.^[4]

A Simple Function

1
2
3
4
5

(defn even-or-odd
  [coll]
  (map #(cond
          (even? %) :even
          :else :odd) coll))

We’ll begin by testing the simple function even-or-odd. We know that for all even numbers we should get :even and for all odd numbers we should get :odd. Let’s express this as a property of the function. Begin by require-ing a couple more namespaces.

1
2
3
4

clj-spec.core=> (require '[clojure.test.check :as tc])
nil
clj-spec.core=> (require '[clojure.test.check.properties :as prop])
nil

Now for the actual property.

1
2
3
4
5
6
7
8
9
10
11

(def property
  (prop/for-all [v (gen/vector (gen/choose 0 1))]
    (let [result (even-or-odd v)
          zeroes-and-ones (group-by zero? v)
          zeroes (get zeroes-and-ones true)
          ones (get zeroes-and-ones false)
          evens-and-odds (group-by #(= :even %) result)
          evens (get zeroes-and-ones true)
          odds (get zeroes-and-ones false)]
      (and (= (count zeroes) (count evens))
           (= (count ones) (count odds))))))

We have a generator which will create a vector of 0s and 1s only. We pass that vector as an input to our function. Additionally, we know that the number of 0s should equal the number of :evens returned and that the number of 1s should equal the number of :odds returned.

Next, let’s test this property.

1
2

clj-spec.core=> (tc/quick-check 100 property)
{:result true, :num-tests 100, :seed 1510754879429}

Awesome! We ran the test a 100 times and passed. The added benefit is that the input generated will be different every time you run the test.

Using bond

bond is a library which will let you stub side-effecting functions like database calls. We’ll require the namespce and modify our code to save even numbers to database.

First, the namespace.

1
2

clj-spec.core=> (require '[bond.james :as bond])
nil

Next, the code.

1
2
3
4
5
6
7
8
9
10
11
12

(defn save
  [n]
  ;; let's assume there's a database call here
  nil)

(defn even-or-odd
  [coll]
  (map #(cond
          (even? %) (do
                      (save %) ;; save to database
                      :even)
          :else :odd) coll))

Now let’s update the property and stub save.

1
2
3
4
5
6
7
8
9
10
11
12
13

(def property
  (prop/for-all [v (gen/vector (gen/choose 0 1))]
    (bond/with-stub [save]
      (let [result (even-or-odd v)
            zeroes-and-ones (group-by zero? v)
            zeroes (get zeroes-and-ones true)
            ones (get zeroes-and-ones false)
            evens-and-odds (group-by #(= :even %) result)
            evens (get zeroes-and-ones true)
            odds (get zeroes-and-ones false)]
        (and (= (count zeroes) (count evens))
             (= (count ones) (count odds))
             (= (count zeroes) (-> save bond/calls count)))))))

Notice how we’re using bond/with-stub and telling it to stub save function which calls the database. Later, we assert that the number of times that the databse was called is equal to the number of evens in the vector. Let’s verify the property.

1
2

clj-spec.core=> (tc/quick-check 10000 property)
{:result true, :num-tests 10000, :seed 1510834022725}

Voilà! It works!

The last part of this post is about finding out test coverage using cloverage. For that, we’ll be moving our code to core.clj and writing test under the test directory.

Using cloverage

To see cloverage in action, we’ll need to add our functions to core.clj. Here’s what it’ll look like:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

(ns clj-spec.core
  (:gen-class))

(defn save
  [n]
  ;; let's assume there's a database call here
  nil)

(defn even-or-odd
  [coll]
  (map #(cond
          (even? %) (do
                      (save %) ;; save to database
                      :even)
          :else :odd) coll))

(defn -main
  "I don't do a whole lot ... yet."
  [& args]
  (println "Hello, World!"))

Update your clj-spec.core-test to the following:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

(ns clj-spec.core-test
  (:require [bond.james :as bond]
            [clojure.test.check.properties :as prop]
            [clojure.spec.gen.alpha :as gen]
            [clojure.test.check.clojure-test :refer :all]
            [clj-spec.core :refer :all]))

(defspec even-odd-test
 100
 (prop/for-all [v (gen/vector (gen/choose 0 1))]
   (bond/with-stub [save]
     (let [result (even-or-odd v)
           zeroes-and-ones (group-by zero? v)
           zeroes (get zeroes-and-ones true)
           ones (get zeroes-and-ones false)
           evens-and-odds (group-by #(= :even %) result)
           evens (get zeroes-and-ones true)
           odds (get zeroes-and-ones false)]
       (and (= (count zeroes) (count evens))
            (= (count ones) (count odds))
            (= (count zeroes) (-> save bond/calls count)))))))

Here we are using the defspec macro to run the same property-based test a 100 times only this time we’ll run the test via command-line using lein. Execute the following command to run the test and see the coverage.

1

lein run -m cloverage.coverage -t 'clj-spec.core-test' -n 'clj-spec.core'

This will make use of cloverage to run the tests. -t denotes our test namespace and -n denotes the namespace for whom the tests are written. You’ll get an output like this:

1
2
3
4
5
6
7
8
9
10
11

...
Produced output in /Users/fasih/Personal/clj-spec/target/coverage .
HTML: file:///Users/fasih/Personal/clj-spec/target/coverage/index.html

|---------------+---------+---------|
|     Namespace | % Forms | % Lines |
|---------------+---------+---------|
| clj-spec.core |   82.61 |   88.89 |
|---------------+---------+---------|
|     ALL FILES |   82.61 |   88.89 |
|---------------+---------+---------|

Perfect!! Now we know how much coverage we have. The HTML file has a nice graphical representation of which lines we’ve covered with our tests.

Conclusion

This brings us to the end of the post on using clojure.spec to write generative, property-based tests in both the REPL and source files. Generative testing automates the task of having to come up with examples for your tests. Where to go from here? Each of these libraries is pretty powerful in itself and will provide you with the necessary tools to write powerful, robust, and expressive tests that require minimal effort. So, head over to the offical docs to learn more.

So far we’ve looked at monoids and functors. The next algebraic data structure we’ll cover is a monad. If you’ve wondered what a monad is but never really understood it, this is the post for you. I am sure that you’ve used it without realizing it. So let’s get to it.

Definition

A monad has more structure than a functor. This means that you can call map on it and that it obeys all the functor laws. In addition, a monad has a flatMap function which you can use to chain monads together. In essence, monads represent units of computation that you can chain together and the result of this chaining is also a monad.

Let’s look at a few examples.

Example

1
2
3
4
5
6
7
8

val first = List(1, 2)
val next = List(8, 9)

for {
  i <- first
  j <- next
}
yield(i * j)

The above code^[1] uses a for comprehension to muliply elements of the list together. Under the hood, this gets translated to:

1
2
3
4
5

first flatMap {
  f => next map {
    n => f * n
  }
}

The compiler is making use of the List monad to chain operations together. Let’s break this down.

1
2
3

next map {
  n => f * n
}

This part of the code will return a List since that is what calling map on a List does. Since we have two elements in first list, the result of mapping will generate two lists of two elements each. This isn’t what we want. We want a single list that combines the results together.

1
2
3

first flatMap {
  ...
}

The flattening of results is what flatMap does - it takes the two lists and squishes them into one.

Monad Laws

For something to be a monad, it has to obey the monadic laws. There’s three monad laws:

1. Left identity
2. Right identity
3. Associativity

Left Identity

This law means that if we take a value, put it into a monad, and then flatMap it with a function f, that’s the same as simply applying the function f to the original value. Let’s see this in code:

1
2
3
4
5
6

scala> def f(x: Int): List[Int] = { List(x * 2) }
f: (x: Int)List[Int]

// left identity
List(2).flatMap(f) == f(2)
res5: Boolean = true

Right Identity

This law means that if we take a monad, flatMap it, and within that flatMap we try to create a monad out of it, then that’s the same as original monad. Let’s see this in code:

1
2
3

// right identity
scala> List(1, 2, 3).flatMap({ x => List(x) }) == List(1, 2, 3)
res6: Boolean = true

Let’s walkthrough this. The function to flatMap gets the elements of the original list, List(1, 2, 3), one-by-one. The result is List(List(1), List(2), List(3)). This is then flattened to create List(1, 2, 3), which is the original list.

Associativity

This law states that if we apply a chain of functions to our monad, that’s the same as the composition of all the functions. Let’s see this in code:

1
2
3
4
5
6
7
8

scala> def f(x: Int): List[Int] = { List(x + 1) }
f: (x: Int)List[Int]

scala> def g(x: Int): List[Int] = { List(x + 1) }
g: (x: Int)List[Int]

scala> List(1, 2, 3).flatMap(f).flatMap(g) == List(1, 2, 3).flatMap(x => f(x).flatMap(g))
res8: Boolean = true

Conclusion

This brings us to the end of the post on monads and their laws. List isn’t the only monad in your arsenal. Options and Futures are monads, too. I suggest going ahead and constructing examples for monadic laws for them.

The next algebraic structure we’ll look at is a functor. In the introduction, we saw that a category consists of objects and arrows. As an example, we morphed a set of strings to another set which contained the reverse of those strings. In other words, we morphed an object to another object. What if we could morph an entire category to another category while preserving the structure? Well, that’s what a functor does.

Formal Definition

Let and be categories. A functor is a map taking each -object to a -object and each -arrow to a arrow , such that all -objects and composable -arrows and

Example

Say we have a set . From this set we create another set which contains finite lists of elements drawn from . The functor we want maps from set to set. Since we know that a category contains objects and arrows, becomes the object part. The arrow part takes a function to a function that given a list maps over elements of

How does this translate to code? This actually translates fairly easily to code. Containers like lists, trees, etc. that you can call map on are functors.

Let’s write some code. We’ll begin by creating a set .

1
2

@ val S = Set(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
S: Set[Int] = Set(0, 5, 1, 6, 9, 2, 7, 3, 8, 4)

Next, we’ll create .

1
2

@ def f(x: Int) = { x * 2 }
defined function f

Next, let’s create .

1
2

@ val L = List(1, 2, 3)
L: List[Int] = List(1, 2, 3)

Next, we’ll create the function maplist.

1
2

@ def maplist(f: Int => Int)(L: List[Int]) = L map f
defined function maplist

Finally, let’s see this in action:

1
2

@ maplist(f)(L)
res4: List[Int] = List(2, 4, 6)

As we can see, maplist applied the function f on all elements of L. We did this by using the map method of a List instance.

Functor Laws

All functors are expected to obey the two laws that we saw in the formal definition. Let’s see how they translate to code.

First Law

The first law states that if we map the identity function over a functor, we’ll get back a functor which is the same as the original functor.

1
2

@ List(1, 2, 3) map identity
res5: List[Int] = List(1, 2, 3)

As we can see, applying identity to the list gives back the same list.

Second Law

The second law states that if we map a functor using a composition of two functions, , it’s the same as first mapping the functor using the first function and then mapping the resulting functor using the second function, .

We’ll begin by creating two functions f and g.

1
2
3
4

@ def f(x: Int): Int = x + 1
defined function f
@ def g(x: Int): Int = x + 1
defined function g

Now let’s put the theory into practice.

1
2
3
4
5
6
7

// composition of two functions
@ List(1, 2, 3) map { x => g(f(x)) }
res8: List[Int] = List(3, 4, 5)

// applying map twice
@ List(1, 2, 3) map f map g
res9: List[Int] = List(3, 4, 5)

As we see, the two lists are the same.

More Functor Examples

Example 1

Let’s consider a category where objects are integers. Arrows between objects indicates a “divided by” relationship. For example,

This indicates that 10 can be divided by 5. To reiterate, objects are numbers and arrows represent a “divided by” relationship.

Now let’s create a functor from the category to itself. This functor will multiply each object by 13. So, . Is this a valid functor? We have but is it true that ?

The answer is yes. Our category has arrows that indicate a “divided by” relationship. So, will be an integer. Similarly, will also be an integer and maintain a “divided by” relationship. This shows that arrows do not always have to be functions. They can also indicate a relationship between their domain and codomain.

Conclusion

In this post we saw functors which map objects from one category to another. Containers like trees, lists, etc. are functors. All functors are required to obey the two functor laws.

The first algebraic structure we’ll look at is a monoid. We’ve covered monoid previously in Scalaz Under the Hoods. In this post we’ll look at it again from a more abstract standpoint.

Formal Definition

A monoid is an underlying equipped with

1. a binary operation from pairs of elements of into such that for all
2. an element such that

We’ve already translated this definition to code. Just to recap, here’s what we wrote previously:

1
2
3
4

trait Monoid[A] {
  def mempty: A
  def mappend(a: A, b: A): A
}

mappend is the binary operation , and mempty is the element .

More concretely, we wrote this:

1
2
3
4

object IntMonoid extends Monoid[Int] {
  def mempty: Int = 0
  def mappend(a: Int, b: Int) = a + b
}

So, translates to the addition operation , and translates to . That way, where is any integer. That was fairly easy to understand.

Monoid Homomorphism

A monoid homomorphism from to is a function such that

1. and
2. .

The composition of two monoid homomorphisms is the same as their composition as functions on sets.

I know this is abstract so let’s have a look at a concrete example. Let’s write some code. We’ll be reusing the monoids that we previously wrote.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

@ trait Monoid[A] {
    def mempty: A
    def mappend(a: A, b: A): A
  }
defined trait Monoid

@ object Monoid {
    implicit object StringMonoid extends Monoid[String] {
        def mempty: String = ""
        def mappend(a: String, b: String): String = a + b
    }
    implicit object IntMonoid extends Monoid[Int] {
        def mempty: Int = 0
        def mappend(a: Int, b: Int) = a + b
    }
  }
defined object Monoid

Next, we’ll write a homomorphism

1
2

@ def f(s: String): Int = s length
defined function f

Let’s see this in action. We’ll begin by testing the first rule.

1
2
3
4
5
6
7

// bring the monoids into scope
@ import Monoid._
import Monoid._

// rule 1
@ f(StringMonoid.mempty) == IntMonoid.mempty
res6: Boolean = true

So we see that the first rule is satisfied. Applying on the zero element of StringMonoid gives us the zero element of IntMonoid. Onto the second rule.

1
2
3
4
5
6
7
8

@ val x = "apple"
x: String = "apple"
@ val y = "banana"
y: String = "banana"

// rule 2
@ f( StringMonoid.mappend(x, y) ) == IntMonoid.mappend( f(x), f(y) )
res9: Boolean = true

And we see that the second rule is also satisfied. Therefore, is a homomorphism such that . To recap, a monoid homomorphism is a map between monoids that preserves the monoid operation and maps the identity element of the first monoid to that of the second monoid^[1]. The monoid operation is still and the empty string is mapped to , which is the zero/identity element of IntMonoid.

Category with One Object

Suppose there’s a category with just one object in it. The identity arrow would point to itself. And the composition of this arrow with itself is , which satisfies the associativity law. A monoid may be represented as a category with a single object. The elements of M are represented as arrows from this object to itself, the identity element is represented as the identity arrow, and the operation is represented as composition of arrows.

Any category with a single object is a monoid.

We’ve covered a lot of topics in Scalaz but before moving forward, I’d like to cover functors, monoids, monads, etc. These form the basis of functional programming and are predicated in category theory. This post is intended to be an introduction to category theory.

What is Category Theory?

Category theory is a mathematical theory involving the study of categories. A category consists of a group of objects and transformations between them. Think of a category as a simple collection.^[1]

Formally, a category consists of the following:

1. a collection of objects
2. a collection of arrows (called morphisms)
3. operations assigning each arrow an object , its domain, and an object , its codomain. We write this as
4. a composition operator assigning each pair of arrows and , with a composite arrow , satisfying the associative law:
   for any arrows , , and (with , , , and not necessarily distinct),
   
5. for each object , an identity arrow satisfying the identity law:
   for any arrow ,
   and

The formal definition above is taken verbatim from Basic Category Theory for Computer Scientists.

Let’s relate the diagram above^[2] to the formal definition that we have. This simple category has three objects , , and . There’s three identity arrows , , and . These identity arrows satisfy the identity law. For example, . Intuitively, if you were “standing” on and you first “walked along” the arrow and then “walked along” the arrow to reach , it’s as good as just “walking along” .

A More Concrete Example

Let’s consider a category whose objects are sets. We’ll translate this into code and hold it to the laws stated above.

1. is a collection of sets i.e. each object is a set.
2. an arrow is a morphism from set to set
3. for each function , we have , and
4. the composition of a function with is a function from to mapping each element to
5. for each set , the identity function is a function with domain and codomain as .

Code

Let’s begin by creating our first object of category - a set .

1
2

@ val A = Set("apples", "oranges")
A: Set[String] = Set("apples", "oranges")

Next, let’s define a function which morphs to .

1
2

@ def f(a: Set[String]): Set[String] = a map { _.reverse }
defined function f

Next, let’s morph to by applying the function

1
2

@ val B = f(A)
B: Set[String] = Set("selppa", "segnaro")

The domain of is the set where as codomain is the set of reversed strings, .

Next, let’s define a function

1
2

@ def g(b: Set[String]): Set[Int] = b map { _.length }
defined function g

Now let’s compose and

1
2

@ val C = g(f(A))
C: Set[Int] = Set(6, 7)

And finally, let’s create an identity function

1
2

@ def idA(a: Set[String]): Set[String] = a map identity
defined function idA

Let’s see this in action

1
2

@ idA(A)
res7: Set[String] = Set("apples", "oranges")

This is how we translate a category to code. In the coming posts we’ll cover more category theory.

In this post we’ll look at Memo which is a Scalaz goodie to add memoization to your program. We’ll recap what memoization is, write a recursive function to calculate Fibonacci numbers, and then add memoization to it using Memo.

What is Memoization?

In computing, memoization or memoisation is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.^[1]

Fibonacci (without Memo)

1
2
3
4
5
6
7

@ def fibo(n: Int): Int = {
    n match {
      case 0 | 1 => n
      case _: Int => fibo(n - 1) + fibo(n - 2)
    }
  }
defined function fibo

So here’s the non-memoized recursive fibo which calculates the n^th Fibonacci number. The issue here is that it’ll recalculate the Fibonacci numbers a lot of times and therefore cannot be used for large values of n.

Fibonacci (with Memo)

1
2
3
4
5
6
7
8
9
10

@ import scalaz._
import scalaz._
@ import Scalaz._
import Scalaz._
@ val fibo: Int => Int = Memo.immutableHashMapMemo {
    case 0 => 0
    case 1 => 1
    case n: Int => fibo(n - 1) + fibo(n - 2)
  }
fibo: Int => Int = scalaz.Memo$$$Lambda$2233/1055106802@48649202

Here’s the memoized version using Scalaz Memo. We are using an immutable, hash map-backed memo. The immutableHashMapMemo method takes a partial function defining how we construct the memo. In our case, if the value of n is not 0 or 1, we try looking up the value in the memo again. We recurse until we reach 0 or 1. Once that happens and our recursion returns, the resultant value is cached in an immutable.HashMap.

Conclusion

Memoization is a great way to optimize your programs. In this post we used an immutable hash map memo. There are other types of memos applying different strategies to cache their results. The Memo companion object is the place to look for an appropriate memo that suits your needs.

In this post we’ll look at Lens which is a pure functional way of getting and setting data. Before we get into lenses, we’ll look at why we need lenses by looking at a simple example.

Motivating Example

1
2
3
4

@ case class Address(city: String, zip: Int)
defined class Address
@ case class Person(name: String, address: Address)
defined class Person

Say we have a class Person which has the name of the person and their address where the address is represented by Address. What we’d like to do is to change the address of the person. Let’s go ahead and create a Person.

1
2

@ val p1 = Person("John Doe", Address("Doe Ville", 7))
p1: Person = Person("John Doe", Address("Doe Ville", 7))

Changing the Address while maintaining immutability is fairly easy.

1
2
3
4
5

@ val p2 = p1.copy(
    p1.name,
    Address("Foo City", 9)
  )
p2: Person = Person("John Doe", Address("Foo City", 9))

The problem arises when things begin to nest. Let’s create an Order class representing an order placed by a Person.

1
2
3
4

@ case class Order(person: Person, items: List[String])
defined class Order
@ val o1 = Order(p1, List("shoes", "socks", "toothpaste"))
o1: Order = Order(Person("John Doe", Address("Doe Ville", 7)), List("shoes", "socks", "toothpaste"))

Now, the person would like to change the address to which the items are delivered.

1
2
3
4
5
6
7
8

@ val o2 = o1.copy(
    o1.person.copy(
      o1.person.name,
      Address("Foo City", 9)
    ),
    o1.items
  )
o2: Order = Order(Person("John Doe", Address("Foo City", 9)), List("shoes", "socks", "toothpaste"))

So, the deeper we nest, the uglier it gets. Lenses provide a succinct, functional way to do this.

Lens

Lenses are a way of focusing on a specific part of a deep data structure. Think of them as fancy getters and setters for deep data structures. I’ll begin by demonstrating how we can create and use a lens and then explain the lens laws.

Creating a Lens

1
2
3
4
5
6
7
8
9
10
11

@ import scalaz._
import scalaz._
@ import Scalaz._
import Scalaz._

// creating a lens
@ val addressInPerson = Lens.lensu[Person, Address] (
    (p, address) => p.copy(address = address),
    _.address
  )
addressInPerson: Lens[Person, Address] = scalaz.LensFunctions$$anon$5@4e32e2a2

What we’ve done is create a lens that accepts a Person object and focuses on its Address field. lensu expects two functions - a setter and a getter. In the first function, the setter, we’re making a copy of the Person object passed to the lens and updating its address field with the new one. In the second function, the getter, we’re simply returning the address field. Lets see this in action by getting and setting values.

Getting a Field

1
2

@ addressInPerson.get(p1)
res12: Address = Address("Doe Ville", 7)

Once you create a lens, you get a get method which returns the address field in the Person object.

Setting a Field

1
2

@ val p3 = addressInPerson.set(p1, Address("Bar Town", 10))
p3: Person = Person("John Doe", Address("Bar Town", 10))

Similarly, there’s a set method which lets you set fields to specific values.

Modifying a Field

1
2

@ val p4 = addressInPerson.mod({ a => a.copy(city = s"${a.city}, NY") }, p1)
p4: Person = Person("John Doe", Address("Doe Ville, NY", 7))

mod lets you modify the field. It expects a function that maps Address to Address. In the example here, we’re appending “NY” to the name of the city.

Lenses are Composable

The true power of lenses is in composing them. You can compose two lenses together to look deeper into a data structure. For example, we’ll create a lens which lets us access the address field of the person in an Order. We’ll do this by composing two lenses.

1
2
3
4
5
6
7
8
9
10

// creating the lens
@ val personInOrder = Lens.lensu[cmd5.Order, Person] (
    (o, person) => o.copy(person = person),
    _.person
  )
personInOrder: Lens[cmd5.Order, Person] = scalaz.LensFunctions$$anon$5@33d58abf

// testing the lens
@ personInOrder.get(o1)
res16: Person = Person("John Doe", Address("Doe Ville", 7))

Ignore the cmd. prefix to Order. That is just an Ammonite REPL quirk to avoid confusing with the Order trait from Scalaz. Next, we’ll combine the two lenses we have.

1
2

@ val addressInOrder = personInOrder >=> addressInPerson
addressInOrder: LensFamily[cmd5.Order, cmd5.Order, Address, Address] = scalaz.LensFamilyFunctions$$anon$4@73679b13

>=> is the symbolic alias for andThen. The way you read what we’ve done is: get the person from the order AND THEN get the address from that person.

This allows you to truly keep your code DRY. Now no matter within which data structure Person and Address are, you can reuse that lens to get and set those fields. It’s just a matter of creating another lens or few lenses to access the Person from a deep data structure.

Similarly there’s also compose which has a symbolic alias <=< and works in the other direction. I personally find it easier to use andThen / >=>.

Lens Laws

Get-Put: If you get a value from a data structure and put it back in, the data structure stays unchanged.
Put-Get: If you put a value into a data structure and get it back out, you get the most updated value back.
Put-Put: If you put a value into a data structure and then you put another value in the data structure, it’s as if you only put the second value in.

Lenses that obey all the three laws are called “very well-behaved lenses”. You should always ensure that your lenses obey these rules.

Here’s how Scalaz represents these lens laws:

1
2
3
4
5
6
7
8
9
10
11
12

trait LensLaw {
  def identity[A >: A2 <: A1, B >: B1 <: B2](a: A)(implicit A: Equal[A]): Boolean = {
    val c = run(a)
    A.equal(c.put(c.pos: B), a)
  }
  def retention[A >: A2 <: A1, B >: B1 <: B2](a: A, b: B)(implicit B: Equal[B]): Boolean =
    B.equal(run(run(a).put(b): A).pos, b)
  def doubleSet[A >: A2 <: A1, B >: B1 <: B2](a: A, b1: B, b2: B)(implicit A: Equal[A]): Boolean = {
    val r = run(a)
    A.equal(run(r.put(b1): A) put b2, r put b2)
  }
}

identity is get-put law, retention is put-get law, and doubleSet is put-put law.

Lenses and State Monads

Formally, a state monad looks like the following:

1

S => (S, A)

Given a state S, it computes the resulting state S by making mutations to the existing state S and produces a resulting A. This is a bit abstract so let’s look at a scenario. Say we have a list of people whose addresses we’d like to update to Fancytown with zip code 3. Let’s do that using lenses.

Creating a State

1
2
3
4

@ val state = for {
    p <- addressInPerson %= { add => Address("Fancytown", 3) }
  } yield p
state: IndexedStateT[Id, Person, Person, Address] = scalaz.IndexedStateT$$anon$11@25b51460

Here we are creating a state using a for comprehension. The %= operator accepts a function which maps an Address to an Address. What we get back is a state monad. Now that we have a state monad, let’s use it to update the address.

Updating the State

Next, let’s make person p1 move to Fancytown.

1
2

@ state(p1)
res33: (Person, Address) = (Person("John Doe", Address("Fancytown", 3)), Address("Fancytown", 3))

Here we are updating person p1‘s address. What we get back is a new state S, p1 but with Fancytown address, and the result A, the new Address. state(p1) is the same as state.apply(p1). In short, we’re applying that state to a Person object.

Conclusion

This brings us to the end the post on lenses. Lenses are a powerful way to get, set, and modify fields in your data structures. The best part about them is that they are reusable and can be composed to form lenses that focus deeper into the data structure.