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 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

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 α → μ α