Jasmine-style BDD tests in Scala

I write a lot of JavaScript these days and got quite accustomed to Jasmine-style unit tests with their expressiveness and flexibility. I also code a fair amount of Scala and one thing I miss every time I switch is a good support for BDD. I use ScalaTest and it is a powerful framework but one thing it is missing for years is the support for hierarchical specs. Namely, the analog of Jasmine’s “beforeEach” and “afterEach” in nested “describe”s. So recently, after struggling once again to express a test concisely, I felt that enough was enough. Here is a FunSpec extension trait I came up with:

	package com.prystupa
	import org.scalatest.{Tag, FunSpec}
	import scala.collection.mutable
	trait JasmineSpec extends FunSpec {
	private val itWord = new ItWord
	private val setup: mutable.Stack[List[() => Unit]] = mutable.Stack()
	private val tearDown: mutable.Stack[List[() => Unit]] = mutable.Stack()
	protected def beforeEach(code: => Unit) {
	val list = (() => code) :: setup.pop()
	setup.push(list)
	}
	protected def afterEach(code: => Unit) {
	val list = (() => code) :: tearDown.pop()
	tearDown.push(list)
	}
	protected override def describe(description: String)(fun: => Unit) {
	setup.push(List())
	tearDown.push(List())
	super.describe(description)(fun)
	tearDown.pop()
	setup.pop()
	}
	protected override val it = observe
	private lazy val observe: ItWord = new ItWord {
	override def apply(specText: String, testTags: Tag*)(testFun: => Unit) {
	val before = setup.reverse.flatMap(_.reverse)
	val after = tearDown.flatMap(_.reverse)
	itWord(specText, testTags: _*) {
	before.foreach(_())
	testFun
	after.foreach(_())
	}
	}
	}
	}

view raw

JasmineSpec.scala

hosted with ❤ by GitHub

When mixed in, the trait intercepts FunSpec’s “describe”s to keep track of all the “beforeEach” and “afterEach” on every nesting level. It also overrides FunSpec’s “it” to execute appropriate setup and tear-down code for that “it” before running the test. And here is a contrived example of using it in Scala:

	package com.prystupa
	import org.scalatest.matchers.ShouldMatchers
	import org.junit.runner.RunWith
	import org.scalatest.junit.JUnitRunner
	/**
	* Created with IntelliJ IDEA.
	* User: eprystupa
	* Date: 8/24/13
	* Time: 11:37 PM
	*/
	@RunWith(classOf[JUnitRunner])
	class MathSuite extends JasmineSpec with ShouldMatchers {
	var x: Int = _
	var result: Int = _
	describe("A simple calculator") {
	describe("when turned on") {
	it("displays 0") {
	result should equal(0)
	}
	describe("when I input 5") {
	beforeEach {
	x = 5
	}
	describe("and multiple by 3") {
	beforeEach {
	result = x * 3
	}
	it("shows 15") {
	result should equal(15)
	}
	}
	describe("and add by 3") {
	beforeEach {
	result = x + 3
	}
	it("shows 8") {
	result should equal(8)
	}
	}
	}
	}
	}
	}

view raw

MathSuite.scala

hosted with ❤ by GitHub

For a complete project that you can explore or execute with maven look here: https://github.com/prystupa/jasmine-spec-scala

Matching Engine – Pegged Orders in the Limit Book

In the previous post I finished support for the two fundamental order types: market and limit. In this post I am going to add support for a bit more exotic one – pegged order. Supporting pegged order type is a bit more involved compared to order types we handled before. Therefore I’m going to tackle them in two posts. In this post I’m going to handle pegged order position in the order book. And in the following post I’m going to cross them with other orders. The complete source code for this and other posts in the series is available from my GitHub repo: https://github.com/prystupa/scala-cucumber-matching-engine.

Maintaining pegged orders in the order book

A pegged order is a limit order to buy or sell a stated amount of a security at a displayed price set to track the current bid or ask of the central order book. The description of pegged order by Euronext is given next, and I am going to use it as acceptance criteria to test-drive the implementation: “Peg orders are accepted in continuous trading phase if there is in the order book a best bid or offer on its side. This means that in case of empty order book the peg order is automatically rejected. On a non empty book, the peg order is displayed at the best limit price in the market sheet. In case of an executable incoming order, the Peg order can be updated only if the new best limit is displayed in the order book (after the transaction). In case of a priced Peg order (set with a limit price), the order continues pegging until the display price meets the limit price specified. If the best limit of the order book disappears (following a cancellation or an execution), and the order book is suddenly empty, peg orders are automatically eliminated.”

Lets add a model to represent this new order type – for now, we will consider a simple Peg order that is not priced :

	trait Order {
	val broker: String
	val qty: Double
	val side: Side
	}
	case class LimitOrder(broker: String, side: Side, qty: Double, limit: Double) extends Order
	case class MarketOrder(broker: String, side: Side, qty: Double) extends Order
	case class PegOrder(broker: String, side: Side, qty: Double) extends Order

view raw

Order.scala

hosted with ❤ by GitHub

Matching Engine – Market Orders (Reference Price Rule)

In the previous post I implemented the “best limit” crossing rule, matching incoming limit orders against outstanding market orders. In this post I am going to complete the logic related to market orders matching by implementing the last use case – matching market orders to opposite side market orders. To do this we will introduce and explain a notion of reference price. The complete source code for this and other posts in the series is available from my GitHub repo: https://github.com/prystupa/scala-cucumber-matching-engine

Crossing Market Order with Opposite Side Outstanding Market Orders

Consider when a market order matches with another market order in the opposite order book. At what price should the resulting trade occur? There are two possibilites here:

• the opposite order book with the resting market order also contains one or more outstanding limit orders – in this case the opposite book has a “best limit” price we discussed in the previous post and this price becomes the price for the trade
• the opposte order book does not have outstanding limit orders, so the “best limit” price is not defined. In this case the trade occurs at the “reference price”. Most often reference price is the last traded price for a security. An exchange sets the reference price at the opening, perphaps to the closing price from the last session, or the result of the opening auction session.

Lets capture the first rule (best limit price is available) using Cucumber:

	Scenario: Matching incoming Buy market order against Sell market order when another – limit – Sell order present
	Given the following orders are submitted in this order:
	| Broker | Side | Qty | Price |
	| A | Sell | 100 | MO |
	| B | Sell | 100 | 10.5 |
	Then market order book looks like:
	| Broker | Qty | Price | Price | Qty | Broker |
	| | | | MO | 100 | A |
	| | | | 10.5 | 100 | B |
	When the following orders are submitted in this order:
	| Broker | Side | Qty | Price |
	| C | Buy | 100 | MO |
	Then the following trades are generated:
	| Buying broker | Selling broker | Qty | Price |
	| C | A | 100 | 10.5 |
	And market order book looks like:
	| Broker | Qty | Price | Price | Qty | Broker |
	| | | | 10.5 | 100 | B |
	Scenario: Matching incoming Sell market order against Buy market order when another – limit – Buy order present
	Given the following orders are submitted in this order:
	| Broker | Side | Qty | Price |
	| A | Buy | 100 | MO |
	| B | Buy | 100 | 10.5 |
	Then market order book looks like:
	| Broker | Qty | Price | Price | Qty | Broker |
	| A | 100 | MO | | | |
	| B | 100 | 10.5 | | | |
	When the following orders are submitted in this order:
	| Broker | Side | Qty | Price |
	| C | Sell | 100 | MO |
	Then the following trades are generated:
	| Buying broker | Selling broker | Qty | Price |
	| A | C | 100 | 10.5 |
	And market order book looks like:
	| Broker | Qty | Price | Price | Qty | Broker |
	| B | 100 | 10.5 | | | |

view raw

MatchingEngine.MarketOrders.feature

hosted with ❤ by GitHub

Tarjan’s strongly connected components algorithm in Scala

Recently I have been researching a matching algorithm for a certain sector of a swap market. This turned into a graph problem requiring finding strongly connected components of the graph (and then cycles) to generate possible multi-broker trades. I turned to Wikipedia for help and found this nice Tarjan’s algorithm:

	algorithm tarjan is
	input: graph G = (V, E)
	output: set of strongly connected components (sets of vertices)
	index := 0
	S := empty
	for each v in V do
	if (v.index is undefined) then
	strongconnect(v)
	end if
	repeat
	function strongconnect(v)
	// Set the depth index for v to the smallest unused index
	v.index := index
	v.lowlink := index
	index := index + 1
	S.push(v)
	// Consider successors of v
	for each (v, w) in E do
	if (w.index is undefined) then
	// Successor w has not yet been visited; recurse on it
	strongconnect(w)
	v.lowlink := min(v.lowlink, w.lowlink)
	else if (w is in S) then
	// Successor w is in stack S and hence in the current SCC
	v.lowlink := min(v.lowlink, w.index)
	end if
	repeat
	// If v is a root node, pop the stack and generate an SCC
	if (v.lowlink = v.index) then
	start a new strongly connected component
	repeat
	w := S.pop()
	add w to current strongly connected component
	until (w = v)
	output the current strongly connected component
	end if
	end function

view raw

TarjanCssAlgoPseudocode.txt

hosted with ❤ by GitHub

I quickly coded it up as-is in Scala, my language of choice currently. All worked fine, but it did not feel right in Scala, relying so heavily on mutable state. It took me a bit but I managed to rework the algorithm into a purely functional style. Here is the code:

Matching Engine – Market Orders (Best Limit Rule)

In the previous post I integrated a new order type – market – into the order book, implemented price and time priority rules for market orders, and started matching them. I tested and implemented the simplest case – matching incoming market order against outstanding limit order. In this post I am going to continue using Cucumber to test-drive the implementation of another use case: matching incoming limit order to outstanding market one.  The complete source code for this and other posts in the series is available from my GitHub repo: https://github.com/prystupa/scala-cucumber-matching-engine

Crossing Limit Order with Outstanding Market Orders

What happens when an incoming limit order crosses with a market order in the opposite book? At what price should they cross? The actual rule is a bit involved:

• If the opposite book does not have outstanding limit orders, then the trade settles at the incoming order’s limit price
• “Best limit” price improvement rule: if the opposite book does have limit orders, the trade settles at the better of two prices – the incoming order’s limit or the best limit from the opposite book – the term “better of two prices” is from the point of view of the incoming limit order. In other words, if incoming limit order would have crossed with outstanding opposite “best limit” order in the absence of market order, then trade at that, potentially improved, “best limit” price.

To implement this logic it is useful to have OrderBook class maintain the notion of “best limit” price at any time. Lets capture the different possible scenarios in a Cucumber script:

Matching Engine – Market Orders (Core)

In the first two posts in this series, Prototyping a Matching Engine with Scala and Cucumber and Matching Engine – Crossing Limit Orders, we built a simple limit order book and a matching algorithm that crosses limit orders of opposite sides. In this post I am going to continue using Cucumber to test-drive the implementation of order book and matching engine – this time we are going to add support for another fundamental order type – market order.  The complete source code for this and other posts in the series is available from my GitHub repo: https://github.com/prystupa/scala-cucumber-matching-engine

Maintaining Market Orders in the Order Book

First of all lets model market order as a case class:

case class MarketOrder(broker: String, side: Side, qty: Double) extends Order

view raw

Order.scala

hosted with ❤ by GitHub

	sealed trait PriceLevel
	case class LimitPrice(limit: Double) extends PriceLevel
	case object MarketPrice extends PriceLevel

view raw

PriceLevel.scala

hosted with ❤ by GitHub

	object OrderType {
	def all(): PartialFunction[Order, OrderType] = {
	// Unmodified code omitted
	// …
	case self@MarketOrder(_, _, _) => new OrderType {
	def bookDisplay: String = "MO"
	def price: PriceLevel = MarketPrice
	def crossesAt(price: Double): Boolean = true
	def decreasedBy(qty: Double): MarketOrder = self.copy(qty = self.qty – qty)
	}
	}
	}

view raw

OrderType.scala

hosted with ❤ by GitHub

By definition market orders cross at any price level (line 13). “MO” (line 9) is the code we use to display outstanding market orders in the book.

Since market orders are ready to cross at any price level they sort higher than any limit orders in the order book (they have a higher price priority). Among different market orders time priority is maintained – the orders that enter the order book earlier are closer to the top. Let capture these rules in a form of Cucumber scenarios (Buy and Sell tests are very similar, so I’m using an outline for brevity):

Matching Engine – Crossing Limit Orders

In the first post in this series, Prototyping a Matching Engine with Scala and Cucumber, we built a simple limit order book that properly maintains price and time priority for incoming Buy or Sell orders. In this post I am going to continue using Cucumber to test-drive the implementation of an algorithm that matches incoming limit orders against the opposite side order book.  The complete source code for this and other posts in the series is available from my GitHub repo: https://github.com/prystupa/scala-cucumber-matching-engine

Introducing Matching Engine

So far we have dealt with two independent order books, one for Buy orders and one for Sell orders. Now when we are going to match opposite side orders, it is useful to introduce a concept of matching engine – an algorithm that operates on both order books and matches and determines the prices at which orders are matched:

	sealed trait OrderBookEvent
	case class Trade(buyingBroker: String, sellingBroker: String,
	price: Double, qty: Double) extends OrderBookEvent

view raw

OrderBookEvent.scala

hosted with ❤ by GitHub

	class MatchingEngine(buy: OrderBook, sell: OrderBook, orderTypes: (Order => OrderType))
	extends mutable.Publisher[OrderBookEvent] {
	def acceptOrder(order: Order) = throw new NotImplementedError()
	}

view raw

MatchingEngine.scala

hosted with ❤ by GitHub

Prototyping a Matching Engine with Scala and Cucumber

Implementing matching engine correctly can be tricky when you consider variety of order types offered by real exchanges. In addition to core limit and market orders exchanges offer additional execution strategies: market-to-limit, various types of pegged orders, stop orders, and others. Matching different order types is non-trivial, and there are many edge cases. In addition there are different rules for matching orders when session opens (i.e. auction mode) vs. continuous trading.

The resulting complexity strongly suggests a test driven approach for developing correctly working engine. In the following series of posts I’m going to gradually build a prototype of a functionally rich equity matching engine. To make things interesting I’m going to model the functionality based on a real, publicly available specs from Euronext: https://europeanequities.nyx.com/trading/order-types

The complete source code for every posts in the series is available in my GitHub repo: https://github.com/prystupa/scala-cucumber-matching-engine

The foundation – limit order book

Implementing a matching engine inevitably requires maintaining buy and sell order books. In this first post I am going to test drive the implementation of a simple limit order book using Scala and Cucumber.

First lets start defining the domain model. All orders are created by brokers, are either to sell or to buy a given instrument, and have a known size and quantity. Limit orders, in addition, define a limit price, and will not execute if market conditions are inferior to the limit price:

	trait Side
	case object Buy extends Side
	case object Sell extends Side

view raw

Side.scala

hosted with ❤ by GitHub

	trait Order {
	val broker: String
	val qty: Double
	val side: Side
	}
	case class LimitOrder(broker: String, side: Side, qty: Double, limit: Double) extends Order

view raw

Order.scala

hosted with ❤ by GitHub

	sealed trait PriceLevel
	case class LimitPrice(limit: Double) extends PriceLevel

view raw

PriceLevel.scala

hosted with ❤ by GitHub

	trait OrderType {
	def bookDisplay: String
	def price: PriceLevel
	}
	object OrderType {
	def all(): PartialFunction[Order, OrderType] = {
	case LimitOrder(_, _, _, limit) => new OrderType {
	def bookDisplay: String = limit.toString
	def price: PriceLevel = LimitPrice(limit)
	}
	}
	}

view raw

OrderType.scala

hosted with ❤ by GitHub

Generating Market Data Snapshot from a Tick Stream using Rx

One of my colleges (http://weblogs.asp.net/sweinstein/) brought up an interesting problem: there is a common theme in finance applications to subscribe to a market data source to receive real time updates on the instruments that this source covers. A late subscriber (the one that has not been subscribed since the start of the trading day, for example) usually expects to receive a snapshot per instrument before real time updates. So what is the best way to support snapshot guarantee, per instrument, from a “hot” underlying source using Rx? There are multiple ways to do it, of course, and here is my version of it:

public static IObservable<T> WithCachedSnapshot<T, TKey>(
    this IObservable<T> source,
    Func<T, TKey> keySelector)
{
    var cache = new Dictionary<TKey, T>();
    return Observable.Defer(() => {
            lock (cache)
                return cache.Values.ToList().ToObservable();
        })
        .Concat(source.Do(s => {
            lock (cache) cache[keySelector(s)] = s;
        }));
}

If you can’t take my word for it, here is the proof that it works:

[TestMethod()]
public void CacheByKeyTestHelper()
{
    // Arrange
    TestScheduler scheduler = new TestScheduler();
    var source = scheduler.CreateHotObservable(
        OnNext(100, new { Ticker = "MSFT", Price = 30.5 }),
        OnNext(101, new { Ticker = "IBM", Price = 130.2 }),
        OnNext(102, new { Ticker = "MSFT", Price = 31.5 }),
        OnNext(103, new { Ticker = "IBM", Price = 130.1 }),
        OnNext(104, new { Ticker = "AAPL", Price = 150.5 }));

    // Act
    var target = RxExtensions.WithCachedSnapshot(
        source,
        quote => quote.Ticker);
    var results = scheduler.Run(() => target, 0, 0, 105);
    var cachedResults = scheduler.Run(() => target, 0, 0, 200);

    // Assert
    results.AssertEqual(
        OnNext(100, new { Ticker = "MSFT", Price = 30.5 }),
        OnNext(101, new { Ticker = "IBM", Price = 130.2 }),
        OnNext(102, new { Ticker = "MSFT", Price = 31.5 }),
        OnNext(103, new { Ticker = "IBM", Price = 130.1 }),
        OnNext(104, new { Ticker = "AAPL", Price = 150.5 }));

    cachedResults.AssertEqual(
        OnNext(105, new { Ticker = "MSFT", Price = 31.5 }),
        OnNext(105, new { Ticker = "IBM", Price = 130.1 }),
        OnNext(105, new { Ticker = "AAPL", Price = 150.5 }));
}

private Recorded<Notification<T>> OnNext<T>(
    long ticks, T value)
{
    return new Recorded<Notification<T>>(
        ticks,
        new Notification<T>.OnNext(value));
}

Detecting Running High/Low Prices Using Reactive Framework – Follow-up

This article shows some improvements to the original code presented in my previous post. Improvements are based on the feedback I received from Erik Meijer and his team and mainly focus on some built-in opportunities in Rx framework that I missed. Here is an extract from the original implementation of the running low feed:

// Daily low price feed
double min = double.MaxValue;
var feedLo = feed
    .Where(p => p < min)
    .Do(p => min = Math.Min(min, p))
    .Select(p => "New LO: " + p);

This implementation depends on the external (to the framework) state (current low value stored in “min” local variable), “Do” combinator to continuously update this state with every price tick, and a “Where” combinator to suppress the ticks that do not represent running low value. Turns out, there is a better, more elegant and framework friendly way to implement this. It relies on the built-in “Scan” and “HoldUntilChanged” combinators:

// Daily low price feed
var feedLo = feed
    .Scan(Math.Min)
    .HoldUntilChanged()
    .Select(p => "New LO: " + p);

The code above is functionally equivalent to the original one but is cleaner, more compact, and easier to read. This is how it works:

• “Scan” operator is used to accumulate the running min value. “Scan” is similar to “Aggregate” in the LINQ-to-Objects world but, instead of collapsing the sequence to a single accumulated value, it keeps outputting the current accumulated value with every tick. As a result “Math.Min” function is continuously applied with every new tick with accumulated min value and new price as arguments and its result is “ticked out”. This produces a stream where every successive number is either less than or equal to the previous one. Close to what we need except we want to suppress duplicates.
• “HoldUntilChanged” is another built-in combinator that wraps an underlying stream and only repeats a value from it if this value differs from the previous one. Perfect for removing successive duplicates (please, note, it will NOT remove ALL the duplicates, only successive ones, so it is not a proper substitute to Distinct, when such a combinator exists) . We use “HoldUntilChanged” instead of original “Where” clause.