Static analysis with Applicatives (1 December 2012)

Static analysis with Applicatives

1 December 2012 (programming haskell language SCB) (12 comments)

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.

« A Brainfuck CPU in FPGA

All entries

Basics for a modular arithmetic type in Agda »

pandawill 2013-04-23 04:56:31

z The Pandawill an online store, operates various brands,a variety of a variety of large-screen smart phones and tablet PCs,and the necessities of life.Crystal 2

the best china wholesale 2013-04-23 05:25:24

Y Tablets, smart phones, online sales, the cheapest electronic wholesale market, China - pandawill.comLenovo A520

Tucson personal trainer (http://www.ptitucson.com) 2013-04-24 06:27:03

I have never used this website before so I wasn't really sure what this was going to do. So this is just a test post. I really like this forum, it has some excellent discussions that take place.

ルイ・ヴィトン (http://www.louisvuitonshopjp.com) 2013-04-28 11:03:12

dafadga 2013-04-29 07:17:08

K The gradual improvement of living standards, demand for mobile phones is not limited to communications, is the pursuit of the appearance of the phone and entertainment properties, then in the end what kind of phone is able to meet all these requirements? Pandawill special launch lifestylish digital shopping guide series, holding a purse you accurate shot, to buy their favorite products. cheap tablets

Tintenpatronen Epson Stylus Sx200 (http://www.tinteablager.de/s/drucker/d-sx200.html) 2013-05-02 10:32:48

Thanks for posting such a great blog, I seriously liked it. The video is plus point of your blog.

Adidas Jeremy Scott 2013-05-13 10:19:53

Prefabricated storage products consist of a variety of colorations, sizes in addition to prices. It is possible to obtain simple twelve month period back button 30 back button 7 system with regard to less than 5K, as well as the bigger 40' buildings may be around something like 20 -- 50K+. In comparison with classic engineering, they are extremely less expensive selections. A variety of prefabricated storage products usually do not include the storage panels, walk-through doors, masonry anchors, in addition to home windows, yet Cycling Sets can be bought intended for obtain on your own. Frequently, its most effective whenever you can set up the system for a concrete piece. That permits the most secure base, yet seriously isn't the simply method. You might construct over diet property as well as stones. The concrete base possesses clear rewards which is strongly suggested. When you have the inspiration all set it is possible to commence system along with assembly. Because generally, just be sure to measure nearby making constraints to assure many will be nicely before beginning. Even though these types of jerseys are generally originally created for bike riders, various physical activities buffs are applying these types of jerseys because good. Also, these types of jerseys are generally perhaps utilised not alone for virtually every distinct athletics occasions, yet inside virtually any out-of-doors action also. Riding a bike jerseys are additionally labelled as mountain bike jerseys. They are specifically designed for individuals who perform a good number of pedaling. The truth is, riding a bike jerseys usually are not such as just simply virtually any regular jerseys, considering that these types of jerseys are generally created specifically prolonged from the backside. That Maillot Cyclisme Pas Cher will be really extremely simple intended for bike riders because long-back style connected with riding a bike jerseys is made for the cyclist's decrease to continue being taken care of because they bends in the tackle icon connected with that mountain bike. In addition, specifically developed jerseys will often have hard drive budgets positioned in the again. Budgets intended for riding a bike jerseys are generally rationally positioned in the again since that retains things through spilling, because what is normally to be able to occur if budgets come in entrance.

http://bibi6612.008.burogu.jp/000202715.html?ext=1 http://bibi6612.008.burogu.jp/000202716.html

louis vuitton (http://www.louisvuitonshopjp.com) 2013-05-14 11:54:03

x888b 2.7-inch 2013-05-16 03:32:32

H I just wanted to comment on your blog and say I really enjoyed reading your blog here. It was very informative and I also digg the way you write! Keep it up and I'll be back soon to find out more mate.x888b 2.7-inch

Huntsville SEO (http://trafficfromus.com) 2013-05-16 04:36:01

I really appreciate your professional approach. I would like to thank you for the efforts you made in writing this post. I am hoping the same best work from you in the future as well. Huntsville SEO

advice for new parents (http://www.parentmania.com) 2013-05-16 11:51:03

Your concepts were simple to understand that I wondered why I in no way looked at it prior to. Glad to know that there’s a blogger out there that certainly understands what he’s discussing. Great job.

boutique louis vuitton 2013-05-20 03:51:21

Outre les vêtements,boutique louis vuitton sont certainement parmi les accessoires les plus importants dans la garde-robe de la femme. au cours des douze derniers mois, plus la réclamation hommes de Louis Vuitton sac troubles normale sur la planète, l'ingestion visible est de retour.louis vuitton sac dispose de deux sangles qui sillonnent le long avec l'étiquette LV. Je vais avec la version Damier. Eh bien actuellement, vous n'avez pas le choix, mettez vos écouteurs filaires sur et vous positionner à proximité de l'amplificateur d'entre eux pendant de longues périodes de temps où vous n'aurez pas accès à des installations de recharge des batteries. Ici le populaire <strong>boutique louis vuitton</strong> est décorée avec intime broderie lurex qui utilise dentelle réelle. Deux raisons, il ya, d'une part ajouté, produits de moulage de renommée, d'une part ajouté, il aswell est capable de adeptness le cachet de leur qualité supérieure. Et ces magasins en ligne propose également un don gratuit pour certain montant d'achat qui ressemble double avantage pour les acheteurs.<strong>http://www.boutiquelouisvuittonsac.org/</strong>

Contents

Blog tags