Type Safe Bit Fields Using Higher-Kinded Polymorphism

August 13, 2010

Refering to securities, such as stocks or bonds, is far from standard. We all know Apple’s ticker AAPL; But what about the Oracle of Omaha’s company Berkshire Hathaway? Google says BRKA, Yahoo! BRK-A, Bloomberg BRK/A and Reuters BRKa.

Due to these oddities, every serious automated trading system like kaChing’s has at its core a powerful cross-referencing system called a security master.

To handle ambiguous tickers which are context sensitive we have resorted to tagging. For instance, BRKA will be tagged with “good for Google” whereas BRK-A will have a “good for Yahoo!” tag. In this article, we will cover tagging data in a type safe way using higher-kinded types in Java.

Since Java’s type system does not offer kinds, we will emulate them using marker types.

interface SecurityTag {
  interface Google extends SecurityTag {}
  interface Yahoo extends SecurityTag {}
  interface Bloomberg extends SecurityTag {}
  interface Reuters extends SecurityTag {}
}

Using our kinds, we can create a kinded tagged ticker wrapper.

class TaggedTicker<T extends SecurityTag> extends AbstractIdentifier<String> { ...

Wrappers like TaggedTicker (see AbstractIdentifier) are immensely useful to let the compiler hand hold you in various contexts. Consider the following API.

double getPriceFromGoogle(TaggedTicker<Google> ticker) { ...

void sendBuyOrderToBbg(TaggedTicker<Bloomberg> ticker, int quantity) { ...

It is simply impossible to trip yourself. The code embodies the intended data flow. Correctness by design as exemplified by these signatures pays such high dividends that it has become second nature in our code base.

Finally, let’s add a method to retrieve a tagged ticker from a security.

interface Security {
  <T extends SecurityTag> TaggedTicker<T> getTaggedTicker(Class<T> kind);
}

Here again, the signature precisely captures our intention.

  1. Kinds, such as T, extend SecurityTag
  2. Given a kind (materialised by values of Class<T>)
  3. Return a ticker tagged by T

Under the hood, we associate with each ticker a bit field where positions encode contexts. The mapping between kinds and bit field position is captured in a map.

private static final Map<Class<? extends SecurityTag>, Long> TAG2MASK
    = ImmutableMap.<Class<? extends SecurityTag>, Long>builder()
    .put(SecurityTag.Google.class,    0x01)
    .put(SecurityTag.Yahoo.class,     0x02)
    .put(SecurityTag.Bloomberg.class, 0x04)
    .put(SecurityTag.Reuters.class,   0x08)
    .build();

It is then straightforward to write the usual set and unset methods.

public <T extends SecurityTag> void set(Class<T> kind) {
  tags = (tags | TAG2MASK.get(kind));
}

public <T extends SecurityTag> void unset(Class<T> kind) {
  tags = (tags & ~TAG2MASK.get(kind));
}

You’ll notice that the non type safe part of the implementation is kept to the strict minimum and easily testable.

From the high-level description provided here, it should be easy to apply this technique to your own problems. By investing a little time upfront, you will be able to better leverage domain experts’ knowledge. Consider a new employee discovering TaggedTicker<Yahoo> in the code; He will either understand why this complexity is required or pause and ask a peer. In most organisations, you would instead have String yahooTicker and a legion of bugs. Test-Drive Safely: Use Types!

PS: If you like such topics, register for the Applying Compiler Techniques to Iterate At Blazing Speed talk at the next Silicon Valley Code Camp.