## Static analysis with Applicatives

1 December 2012 (programming haskell language SCB)### 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 `MarketKey`s 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.