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.

I'm leaving on a jet plane...

Szerintem mindenki, aki olvassa a blogomnak a magyar nyelvű-személyes részét, már nagyjából tudja, miről akarok most itt írni, de azért az egyszerűség kedvéért összefoglalnám az előző részek tartalmát:

Szóval a lényeg, hogy csütörtökön Szingapúrba költözöm, hogy aztán hétfőtől a Standard Chartered Bank-nél dolgozzam, mint funkcionális programozó. Ez úgy jött, hogy most már kb. két éve foglalkozom intenzíven funkcionális programozással (és konkrétan Haskellel), és amikor közeledett, hogy végre lediplomázom az ELTE-n, akkor elkezdtem körülnézni, hogy keressek egy olyan munkahelyet, ami egyrészt izgalmasabb, mint az ISC, ahol már kb. egy éve szinte csak akkor csináltunk valami érdekeset, ha magunknak kitaláltunk valamilyen feladatot, másrészt amiben van perspektíva, hogy elkezdjek karriert építeni a funkcionális programozásból. Szerencsés véletlen, hogy közben az ISC budapesti irodáját elkezdte leépíteni Eric, az új CEO (ha minden igaz, akkor most utólag már ő is rájött, hogy ez egy nagyon rossz döntés volt), így aztán végkielégítéssel távozhattam.

Az SCB egy CUFP-s álláshirdetés kapcsán merült fel, bár akkor még nem volt világos, hogy nem itt Londonban lesz a munka, hanem (legalábbis az elején, kilenc hónapig mindenképpen) Szingapúrban. Az persze nem az a hazaugrom kéthetente szituáció, de hát mikor ugorjak bele egy ilyen kalandba, ha nem most, fiatalon!

Szóval a terv az, hogy egy tízfős csapat áll össze Szingapúrban, és egyfajta gyorsreagálású deszantosokként segítjük a tradereket meg elemzőket, aztán ha felépítettük az alapokat, akkor szétszóródunk a világba, és jó kiscserkészekként ott segítünk, ahol kell. Ha minden igaz, akkor úgy fél év múlva fogják elkezdeni megkérdezni, hogy ki merre menne. Ha nem jön be Szingapúr, akkor végülis ezen a ponton hazamenekülhetünk Európába (konkrétan Londonba).

A körülményekről pár szót: egy hónapig biztosítanak szállást, úgyhogy ezalatt az idő alatt kell megoldanom a lakásbérletet. Ma voltak itt a költöztetők, akik akár a kocsit kivéve az összes ingóságomat szívesen eljuttatták volna leendő új lakásomba, ugyanis egy akkora konténer volt a limit, mint kb. a hálószobánk. Ezzel a lehetőséggel nem igazán éltünk, mert elhatároztuk, hogy könnyen, kevés holmival utazunk — úgyis bútorozott lakást fogunk bérelni. Így aztán kb. két köbméter lett a csomag, még úgy is, hogy végül magunkkal visszük a TV-t.

Apropó kocsi: szállítás nem játszik, mert baromi drága lenne, de nem csak a szállítás, hanem az üzembeállítása is, bérelni drága, venni drága, Szingapúr igazából nem akarja, hogy autókat tartalmazzon. Úgyhogy az MX-5-öst most leteszem; el akartam adni, de apám kitalálta, hogy neki az kell, úgyhogy most nyári játékautóként fog, gondolom én, sokat pihenni.

Remélem minden lényegeset és publikusat összefoglaltam. Mivel a kommunikáció Veletek most jó időre elektronikus formára korlátozódik, igyekszem a blogot felpörgetni. Kommenteljetek és írjatok sokat, hogy lássam, van értelme :)