Static analysis with Applicatives

The problem

One class of problems solved by the software stack we have here at SCB is pricing structured financial products. This requires four components: some data structure describing the details of the actual transaction (e.g. the strike and the maturity date of an option), market data (e.g. spot prices), a pricer configuration (e.g. the pricing date and the currency in which the value is requested), and a computation method for the given type of transaction. This latter part is basically a function mapping the trade data, the market data, and a pricer configuration to a value:

-- These types will be used in the running example
data Ccy 
data Date

data Config = Config{baseCcy :: Ccy, pricingDate :: Date}

-- The kinds of market observations we are interested in
data MarketData α where
  FXSpot :: Ccy -> Ccy -> MarketData Double
  IRDiscount :: Ccy -> MarketData Double

-- A market is the collection of market data  
data Market
getMarketData ∷ Market -> MarketData α -> α

-- We will define several versions of this datatype
type Pricer₁ = Market → Config → Double

-- Our running example will be a (discounting) pricer for payments
data Payment = Payment{ccy ∷ Ccy, notional ∷ Double, date ∷ Date}

discount ∷ Floating α ⇒ α → α → α → α
discount τ df x = x * (1 + df) ** (-τ)

pricer₁ ∷ Payment → Pricer₁
pricer₁ Payment{..} market Config{..} = discount (date - pricingDate) df notional′
  where
    notional′ = notional * getMarketData market (FXSpot ccy baseCcy)
    df = getMarketData market (IRDiscount baseCcy)

Fetching market data on demand

Of course, the type of data needed from the market depends on the choice of valuation function, and in practice, it would be a really poor idea to assemble a kind of super-total market that contains everything from the Woolong vs. Latinum FX spot price to volatility of Buttfuckistani dirt just to valuate a payment in USD. One way around it is to have pricing happen in the IO monad, so that valuation functions can load market data (from external sources) as needed:

type Pricer₂ = (∀ α. MarketData a → IO α) → Config → IO Double

Of course, we don't want pricers to do arbitrary IO — for example, for the more complex pricers, we might want to run them on the grid; so let's hide the fact that market data is loaded in IO:

type Pricer₂′ = ∀ μ. Monad μ ⇒ (∀ α. MarketData α → μ α) → Config → μ Double

pricer₂ ∷ Payment → Pricer₂′
pricer₂ Payment{..} loadMarketData Config{..} = do
    spot ← loadMarketData $ FXSpot ccy baseCcy
    let notional′ = notional * spot
    df ← loadMarketData $ IRDiscount baseCcy
    return $ discount (date - pricingDate) df notional′

Bulk fetching

However, this is still not perfect. It is much more efficient to bulk-fetch the market data; furthermore, risk calculations often require repeated pricings with slightly modified markets, where only the numbers change, not what is actually in the market. So you want to be able to assemble a market containing just the right data for a given pricer function for the given trade, and then regard the pricer as a pure function.

Our first idea might be to request market data explicitly, separate from the actual pricing algorithm:

data MarketKey = ∀ α. MarketKey (MarketData α)
type Pricer₃ = Config → ([MarketKey], Market → Double)

pricer₃ ∷ Payment → Pricer₃
pricer₃ Payment{..} Config{..} = (deps, price)
  where
    deps = [MarketKey $ FXSpot ccy ccyBase, MarketKey $ IRDiscount ccyBase]
    price mkt = discount (date - pricingDate) df notional′
      where
        spot = getMarketData mkt $ FXSpot ccy ccyBase
        notional′ = notional * spot
        df = getMarketDate mkt $ IRDiscount ccyBase

But this is both cumbersome to use (you have to explicitly list your dependencies), and also unsafe (what if pricer₃ returned an empty dependency list? It would still be accepted by the type checker...)

Can we do better?

Static analysis with an Applicative interface

The idea is to write pricers using a type exposing only an applicative interface. The implementation of this type will allow us to determine, without doing any actual computation, the list of dependencies.

data P α
instance Applicative P
        
get ∷ MarketData α → P α
runP ∷ ∀ μ. (Monad μ) ⇒ ([MarketKey] → μ Market) → P α → μ α
dependencies ∷ P α → [MarketKey] -- To be used by the implementation of runP

type Pricer₄ = Config → P Double

pricer₄ ∷ Payment → Pricer₄
pricer₄ Payment{..} Config{..} = discount (date - pricingDate) ⟨$⟩ df ⟨*⟩ notional'
  where
    notional' = (notional *) ⟨$⟩ get (FXSpot ccy baseCcy)
    df = get $ IRDiscount baseCcy

Since get has type MarketData α → P α, and no monad interface is exposed for P, it is statically enforced that what keys you get from the market can only depend on the trade details, not on data previously retrieved from the market.

So how do we define P and implement Applicative, get, dependencies and runP?

The key insight is that the Functor and Applicative instances are not really supposed to do anything. So I came up with the concept of free applicative functors, which we can use with a datatype that statically tracks the requested MarketKeys while accumulating the pure post-processing functions. The module Control.Applicative.Free contains functions both for static analysis and evaluation (in some other applicative functor) of computations built using the Applicative interface; here, we use the Identity functor, since both collecting the results and running the pricer (once the market is loaded) are pure operations.

import Control.Applicative
import Control.Applicative.Free
import Control.Monad.Identity

data MarketRequest a = forall b. MarketRequest (MarketData b) (b -> a)

instance Functor MarketRequest where
    fmap f (MarketRequest req cont) = MarketRequest req (f . cont)

type P = Free MarketRequest

get ∷ MarketData α → P α
get key = effect $ MarketRequest key id

dependencies ∷ P α → [MarketKey]
dependencies = runIdentity ∘ analyze (Identity ∘ collect)
  where
    collect :: MarketRequest a -> [MarketKey]
    collect (MarketRequest key _) = [request key]

runP ∷ ∀ μ. (Monad μ) ⇒ ([MarketKey] → μ Market) → P α → μ α
runP loadMarket pricer = do
    let deps = dependencies pricer
    mkt ← loadMarket deps
    return $ runIdentity ∘ eval (Identity ∘ step) $ pricer
  where
    step ∷ MarketRequest a → a
    step (MarketRequest key cont) = cont $ getMarketData mkt key

Conclusion

I think the above approach of using free applicatives can be useful in a lot of similar situations; I've already used it in another project at work beside the pricer API briefly outlined here.

I should also mention that the free arrows stuff came from the same thought process that led me to the solution presented here.