http://www.dmst.aueb.gr/dds/pubs/jrnl/2008-JFP-ExoticTrades/html/FSNB08.html
This is an HTML rendering of a working paper draft that led to a publication. The publication should always be cited in preference to this draft using the following reference:

This document is also available in PDF format.

The document's metadata is available in BibTeX format.

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

Diomidis Spinellis Publications

© Copyright 2008 Cambridge University Press.
Link to the online edition of the Journal of Functional Programming at Cambridge Journals Online.

Commercial Uses: Going functional on exotic trades

SIMON FRANKAU
Barclays Capital, 5 The North Colonnade, London E14 4BB, UK

DIOMIDIS SPINELLIS
Athens University of Economics and Business, Patision 76, GR 104 34, Athens, Greece

NICK NASSUPHIS, CHRISTOPH BURGARD
Barclays Capital

Abstract

The Functional Payout Framework, FPF, is a Haskell application that uses an embedded domain specific functional language to represent and process exotic financial derivatives. Whereas scripting languages for pricing exotic derivatives are common in banking, FPF uses multiple interpretations to not only price such trades, but also to analyse the scripts to provide lifecycle support and more. This paper discusses FPF in relation to the wider trading workflow, and our experiences in using a functional language in such a system as both an implementation language and a domain-specific language.

1  Introduction

This application paper is an experience report describing the use of functional programming technologies in the field of exotic equity trading. Our aim is to present the challenges, design decisions, and benefits of applying functional programming in a demanding real-world application domain. The main contributions of this paper are a) the demonstration of the benefits of functional programming in the field of financial derivatives trading, and b) the lessons learned in using functional constructs as a domain-specific language in a production environment. The paper is not intended to cover in depth the internal implementation details of our system. Most of the techniques used have already been described in detail in the existing literature, far better than we could.
In this paper, we present FPF, our Functional Payout Framework through which we manage various lifecycle elements of exotic equity trades. After explaining what an exotic equity derivative actually is and reviewing the pre-existing workflow we describe through examples our language's goals and design (Section 2). We then outline FPF's implementation (Section 3), how our domain-specific language is used in practice (Section 4), and the lessons we learned while working on this project (Section 5). The paper finishes with a discussion of related work (Section 6) and our concluding remarks.

1.1  What is an exotic option anyway?

Options are financial instruments like stocks and bonds. However, in contrast to, say, stocks, which represent ownership interest in a corporation, options are more abstract. An option is a contract whose value is a function of the value of other instruments. As the prices are derived from those of other instruments, options are also termed derivatives.
The purpose of options are to hedge (reduce risk) or speculate (take risk in search of profit). Some options are repackaged for the retail market-to be sold to individuals as a way of getting a return linked to the performance of the stock markets without risking the money investors originally put in. Other forms let speculators express a view by choosing a function that pays out most in scenarios they believe likely, and least in those they believe unlikely.
We will start with the definition of a plain or "vanilla" option. When you buy a vanilla option (by paying an initial premium) you get the right, but not the obligation, to buy (or sell) a fixed amount of an asset at a fixed price. You could buy an option at time t0 that allows you to buy n dollars-worth of asset A at time tT, but at the t0 price. If the price goes up, you earn the diference between the current price and the price at time tT. If the asset's price goes down, you get nothing. Mathematically, if SA(t) is the price of asset A at time t, the amount you receive will be
n max
(SA(tT)/SA(t0) − 1, 0)
Once we move to mathematical notation, we can make the option definition into a more-or-less arbitrary formula. The value n is called the notional of the trade, and the right-hand side can be viewed as an expression specifying the fraction of notional to be paid out. If the payment expression becomes sufficiently complex, the trade is known as an exotic option. Here are some examples of exotic equity options: By the standards of today's trading desks, the examples we described are simple exotic options. Realistic trades may have several "legs" of the above style, plus extra features. It is important to bear in mind that there's no real "standard" exotic trade-there is a wide variety, and clients want variations on existing structures as economic conditions and investor sentiment change. Flexibility is a key requirement for product innovation in exotic options trading.
Exotic equity options (that is, exotic options on stocks) are traded in the over the counter ( OTC) market. This means they are custom-built to a client's request, rather than made into a standard form and traded through an exchange. To give an idea of the amount of money involved, as of June 2006, the outstanding notional in the OTC equity-linked options market was 5.4 trillion dollars. [The Bank for International Settlements, 2007] This figure compares with 6.6 trillion dollars outstanding on exchange-traded (vanilla) equity index options. The notional of a typical exotic option is generally on the order of ten million dollars. While there are larger asset classes, the equity derivatives market is certainly not small.

1.2  Workflow: the lifecycle of exotic trades

The lifecycle of exotic trades involves many different people in different rôles, including structurers, salespeople, quantitative analysts ("quants"), risk management teams and traders. Structurers create new ideas for trades and variations on existing ones. Their aim is to find novel and effective ways to meet the client's requirements. The structurers then develop and test a prototype implementation. Salespeople support interaction with the customer, and write a term sheet that describes the option using a combination of prose and mathematical notation. The quants provide mathematical modelling expertise.
The structurers or the quants write the payout function, which defines how much money the bank will pay out under given market conditions. They will carefully inspect the implementation to ensure it matches the term sheet. A risk management team then independently checks the implementation of the payout function against the term sheet.
A completely new type of trade triggers a much more rigorous sign-off process than for a carbon copy of an existing structure. As such, the ability to innovate is held back by the pressure to standardise.
After the risk management team signs off on an exotic trade, a trader will then receive the coded payout function and create a final price at which the product is sold. After the sale, the traders will manage the financial risk for the lifetime of the trade by pricing the portfolio under various market conditions and hedging with vanilla instruments to minimise the money made or lost as the markets move. In addition to these calculations, the traders will perform other analyses on the structure of the trade itself, to identify, for example, forthcoming events which must be carefully managed.
Other teams handle the actual payments. Some trades pay money to the client at the end, while others pay throughout the lifetime of the trade. In either case, the system must identify when a cash flow occurs, and the correct amount to be paid.

1.3  Downstream operations

A formally described trade can be used in various ways. Each trade defines its input parameters, so it should be possible to automatically derive an interactive input form for them. To manage the trade, one would want to analyze how the trade is likely to perform in the future. For this analysis the trade can be compiled into an efficient representation, suitable for plugging into a Monte Carlo simulation engine. Alternatively, extracting from the trade the conditions expressed in it (for instance, the $/ rate climbing above 1.5) allows the centralized monitoring of the corresponding market conditions. Finally, for those aspects of a trade that require human analysis, it should be possible to represent the trade in a concise mathematical form that analysts can study and discuss.

1.4  An existing implementation

The generality of exotic trade payouts and the corresponding downstream operations lends them to be expressed and manipulated through a domain specific language ( DSL) [Mernik et al. , 2005]. In the past this DSL has often been some form of imperative scripting language, although there has been a noticeable move towards using functional languages in a number of banks, which is not surprising given that the domain is readily specified by functions. Our pre- FPF pricing engine took in a directed acyclic graph equivalent to the syntax tree of an expression representing the payout function, with sharing (a "payout DAG"). This legacy representation had no higher-order functions, so all parts of the trade were fully expanded.
Individual one-off trades were created by hand-writing these payout DAGs. If a trade had several legs, these legs were implemented by cutting and pasting the nodes. As such, rapidly varying the parameters of the trade was difficult. While hand-crafting the payouts is very flexible, it is manually intensive and error-prone. To avoid the overheads of manual labour, once a common pattern of trades was identified, it was converted into a "template". A template provides a standardised input form that covers the majority of the variations people will want on that style of trade. Special cases can still be encoded in a one-off fashion.
The problem with the templates is the effort required to create them. Quants define a standardised pattern to represent a trade type, and write a validation library that ensures a payout DAG matches this pattern. Risk managers sign-off the library, and then the it department develops a front-end to generate these DAGs. The Excel-based front-end will have plenty of trade-type specific code to deal with the particular trade's input fields, and will have a case-specific graph-generator to emit the payout DAG, written in Excel's scripting language, Visual Basic for Applications ( VBA). Each trade is saved in an ad hoc serialisation format. While it can take just hours to generate pricing instructions for an individual trade, the corresponding template may take months to release. Since new templates are so expensive there can be a tendency to cram a new trade type into an existing structure through creative misuse of existing features, increasing the risk of mistakes. At the end of 2006 Barclays managed more than 35 templates, representing a total population of several thousand trades.
A released template in the trade entry system is not the end of the story. The various downstream systems need to be able to process the new trade type. Each system has a central "case" statement to control processing on a per-trade basis, which must be modified with the release of a new template. Hand-crafted trades that are not yet templated must be manually managed.
Given the pace of the business, systems must adapt quickly to cope with new products. The pressure to add new features, rather than maintain existing code (or step back and look for a different, better approach) can lead to increasingly unreadable and unmaintainable code, causing growing operational risk.
The problems we outlined in the preceding paragraphs were the core motivation behind FPF. By spending effort on creating generic analyses that can be applied to all trade types, FPF aims to consistently minimise the cost of production-quality infrastructure, independent of whether we are constructing single one-off trades or wide-ranging templates.

2   FPF overview

We created FPF through an experimental iterative process rather than a formal design based on concrete absolute goals. Nevertheless FPF is best described by looking at its design goals, its structure, and some representative examples.

2.1  Design goals

The core requirement for FPF was to be able to drive multiple back-ends from a single trade description. These back-ends provide different interpretations or analyses of the scripts and trades. The artifacts generated can range from a concrete price through to a user interface schema or barrier risk report.
We designed the payment description DSL with the following goals in mind.
Declarative, compositional construction of payouts
This goal is the driving force behind using a functional approach. A declarative language simplifies the creation of multiple interpretations and static analyses. Compositional construction is a natural mapping of the problem domain, and encourages code reuse by composing new trades from existing trade components.
Minimal coupling
Downstream systems should not be allowed to pollute the language with incidental details. While extensions to the scope of the project may require extensions to the language, our yardstick was that one should not be able to look at a language feature and identify it with a concrete, implementation-specific detail of other systems.
Extensible support for the payout DAGs
If we could not support the pre-existing payout back-end, the project would be dead before its first release. If the language lacked extensibility we could end up in the worse situation where it failed after we had gained everyone's support.
Painless embedding in Haskell
Once we decided to use Haskell (as described in Section 3), embedding the language within Haskell using the language specialization DSL design pattern [Spinellis, 2001] allowed us to reuse much infrastructure (e.g. parsing and typing) and provided us a flexibility which would not otherwise have been available.
Small set of core primitives
By minimising the number of core primitives, multiple back-ends can be produced with minimal effort. Given a set of primitive functions, user-friendly helper functions can be wrapped around them. We considered providing a wider set of primitives with default implementations (in the style of Haskell type classes), but we took the simpler approach to avoid unnecessary complexity.
Attachment of metadata
One of the important goals of FPF is to provide an end-to-end solution, including input forms and documentation. One approach would be to use an external tool, similar to Javadoc [Kramer, 1999] or Haddock [Marlow, 2002]. FPF uses this approach to annotate the trade type, but we can also annotate individual sub-expressions using the "name" primitive and then extract the metadata by static analysis.

2.2  Language overview

As Haskell embeds FPF, FPF's syntax is simply a restricted subset of Haskell's. FPF is thus defined by the primitive functions made available. Figure 1 shows the core FPF primitives and their types.
The types Double and Bool are not those provided by the Haskell prelude, but are types which play the equivalent roles in FPF. List is similarly the FPF representation of a list. We use our own types since our "Double" may represent, under different interpretations, everything from an actual floating point number through to a syntax tree or set of annotations. The exact definitions of the types vary with the embedding used.
All type variables must be instances of FPFVal, the type class representing all values that can exist in FPF. All the types above and tuples of those values are instances of FPFVal. This class allows us to distinguish the values in FPF from those that are not, preventing us applying FPF primitives to non- FPF values. The class also allows us to uniformly traverse FPF programs, and is needed to make tuples (and to a lesser degree, functions) part of the embedded language.

+, −, *, /
::
Double →Double →Double
Arithmetic operators
min, max, pow
::
Double →Double →Double
Arithmetic operators
abs, log, exp
::
Double →Double
Arithmetic operators
observe
::
Asset →Date →Double
Asset price observation
cond
::
Bool →a →a →a
Conditional
map
::
(a →b) →List a →List b
Map
zipWith
::
(a →b →c) →List a →List b →List c
Zip
foldl
::
(a →b →a) →a →List b →a
Left fold
foldl1
::
(a →a →a) →List a →a
Left fold variant
foldr
::
(a →b →b) →b →List a →b
Right fold
mapAccumL
::
(a →b →(a,c)) →a →List b →(a,List c)
Combined map/fold
name
::
String →a →a
Annotation
#1 The core FPF primitives
In FPF let bindings cannot be recursive-the language does not support general recursion. Instead we provide higher-order functions such as map and fold to process lists of data. The restriction on the use of recursion both simplifies the analysis of scripts from within Haskell, and encourages programmers with little functional programming experience to adopt common functional patterns. In other words, we have created something akin to a combinator library (keeping the constraints, but without the points-free approach-see Section 5.2 for details). The fact that the language is not Turing-complete is not an impediment in practice, and in many cases simplifies analysis.
We slowly changed the primitives available, adding new primitives as they were requested. Occasionally the new features subsumed old features, at which point the old primitive could be removed, and a helper function added that implemented the old primitive's behaviour in terms of the new. Through such evolutionary changes we were able to modify the language effectively without requiring huge script rewrites.

2.3  Examples

perf :: Date -> Date -> Asset -> Double
perf t1 t2 asset = observe asset t2 / observe asset t1 - 1
bestOf :: (List Asset, Date, Date) -> Double
bestOf (assets', startDate', endDate') = foldl1 max perfs where
   assets    = name "Assets"        assets'
   startDate = name "Starting date" startDate'
   endDate   = name "End date"      endDate'
   perfs     = map (perf startDate endDate) assets
cliquet :: (Asset, Double, Double, Date, List Date) -> Double
cliquet (asset', gf', gc', initDate', dates') = max gf $ min gc val where
   asset    = name "Asset"        asset'
   gc       = name "Global cap"   gc'
   gf       = name "Global floor" gf'
   initDate = name "Initial date" initDate'
   dates    = name "Observations" dates'
   cliquetPerf (prevDate, prevSum) (currDate', lc', lf') = 
      (currDate, prevSum + currPerf) where
         currDate = name "Observation date" currDate'
         lc       = name "Local cap"        lc'
         lf       = name "Local floor"      lf'
         currPerf  = max lf $ min lc $ perf prevDate currDate asset
   (_, val) = foldl cliquetPerf (initDate, 0) dates
napoleon :: (Asset, Double, Date, List Date) -> Double
napoleon (asset', coupon', initDate', dates') = max 0 $ worst + coupon where
   asset    = name "Asset"        asset'
   coupon   = name "Fixed coupon" coupon'
   initDate = name "Initial date" initDate'
   dates    = name "Observations" dates'
   napCliquet prevDate currDate = (currDate, perf prevDate currDate asset)
   (_, perfs) = mapAccumL napCliquet initDate dates
   worst = foldl1 min perfs
Figure 1: Example trades
For examples, we shall use those three payouts described in Section 1.1. The code is shown in Figure 2. As most of the functions are modelled on standard Haskell functions of the same name, we shall only discuss the FPF-specific functions. The name primitive attaches an annotation to a value which can be extracted and displayed on input forms, for example, but has no numeric effect.
The primitive observe is used to get the value of a particular asset on a particular date. To get the value, it must pull the actual asset prices out of some hidden environment. As the observe function is deterministic in any particular market state, this apparently impure behaviour is of no concern to the script writer, and is purely an implementation detail.
In contrast with earlier work [Peyton Jones et al. , 2000], we only support observing asset values at discrete times. This was a conscious decision to simplify the language, based on known usage patterns. In practice, it has not been a problem; where necessary, a sequence of discrete observations makes a good approximation to continuous observation.
Our examples are for some of the simplest trades we do. However, the compositional nature of the problem domain and language means that the script size and complexity scale up linearly with the complexity of the term sheet.

3  Implementation

Using Haskell to implement the FPF was a non-trivial decision in an environment so strongly weighted towards C++ and VBA. The decision can be split into two parts: choosing a functional language, and choosing Haskell.
Choosing to use a functional language to implement a functional payout language has had a number of benefits. As functional programming researchers have a tendency to write their languages using existing functional languages, these languages generally provide very good support for language engineering in general and domain specific language implementation in particular. Pattern matching, for example, vastly simplifies the writing of a peephole optimiser. Previous experience using functional languages meant the developers were confident that the desired result could be achieved more quickly with a functional language, and with a gentle learning curve. As we performed the work outside of a traditional IT team, management was willing to take a risk on something that promised a good fit and rapid development process.
We tossed away an initial prototype in Prolog after we realized that the code did not use any of the language's logic programming features. Subsequent prototyping continued with functional languages. At that point it had become clear that our main requirements were for strong typing and a large user population. Our previous experience showed that strong typing reduced the effort required to develop and maintain high quality software, by both identifying many "typo"-style bugs, and forcing the developer to plan their algorithms more carefully, reducing the maintenance load later. A large user population generally implies better developed, more stable tools, and a bigger pool from which to hire developers, both now and in the future.
This paper's second author chose Haskell during the prototype stage due to past familiarity [Spinellis, 1993] and the existence of a mature open-source implementation- GHC [Hudak et al. , 2007]. Technically, CAML seemed an equal fit. Erlang was somewhat alien to us, F# seemed too unproven and we did not see any other appropriate candidates. Once we wrote the first prototype in Haskell the path was set. A rewrite in another language would have been far from difficult, but there was no strong case for it.
While the advantages of using Haskell were fairly obvious, the possible pitfalls had to be taken into account. These included:
Integration issues   The FPF has to work as part of a large, complicated, distributed and heterogeneous system. In its way, using Haskell here was an advantage, as it made it easier to argue for a command-line API and text-file I/O. In a wider system suffering from tight coupling, having solid control over our API allowed for a clean design.
Maintenance and support   Maintainability is required on a number of levels. Haskell's high level of abstraction made the addition of new features a lot simpler than it would have been in C++. In the longer term, maintaining the source base requires a supply of Haskell programmers, but if rumours of other Haskell-based banking projects are to be believed, the supply of this skill set is likely to increase with demand. Finally, the Haskell libraries are comprehensive and actively developed, as are the compilers.
Performance   This was the real unknown. Performance on the prototype looked good, but we did not know how it would scale. Other systems implemented in Haskell, like Darcs [Roundy, 2005], have shown that performance can be an issue in real-world workloads. In addition to the runtime performance, we also needed to take into account compilation speed and executable size. We found that compilation speed, while not stellar, was perfectly acceptable. Excellent runtime performance was not vital, since the FPF is not used in any computationally-expensive inner loops. Its performance has certainly been adequate, and our experiences are discussed in more depth in Section 5.5. A surprising weakness was executable size, with our executables coming in at 5 megabytes each. With several executables per release, and several prototype releases running simultaneously, FPF turned out to be unexpectedly disk hungry. Disk space consumption is something of a weakness when one takes into account the need for worldwide replication of the files, but has not been a major problem.


A combination of make [Feldman, 1979] and Perl [Wall & Schwartz, 1990] scripts complete the build system infrastructure, including a program-level regression test suite. Relatively mainstream tools were selected here to simplify maintenance.
We have not used any tools like QuickCheck [Claessen & Hughes, 2000], but this is purely a matter of priorities. A requirement was to be able to check that modifications to the FPF do not result in unexpected price changes to trades booked on FPF, so we have test coverage at that level. Unit tests would be a useful extension, but we have continually been working on other features with higher priority. We hope to make increasing use of Haskell Program Coverage [Gill & Runciman, 2007] to check that our existing tests are providing adequate coverage.
The system has gradually evolved behind the scenes. Over FPF's lifetime, back-ends have been implemented as both shallow embeddings, where the primitive operators actually perform the operations they represent, and a deep embedding, where the primitives simply generate their own abstract syntax tree ( AST), which can then be interpreted. These approaches match "Language embedding" and "Embedding a compiler" in [Elliott et al. , 2003], a paper which explores many of the issues we also faced.
We started off with a single back-end, a shallow embedding which generated payout DAGs. We added further back-ends, also implemented as shallow embeddings. Each back-end was a separate code base which the scripts needed to be run against. While this approach was simple, it required us to manually keep the types consistent, and required a great deal of recompilation when we created a new script.
To relieve these problems, we migrated to a deep embedding. We used a single set of primitives to convert the scripts to ASTs, which could then be processed by a variety of interpreters and static analyses. We now have a two-step process:
  1. The script function is run by the Haskell compiler under the deep embedding, producing an AST which is then serialised. Haskell's type system guarantees the AST is correctly typed.
  2. The AST can be read in and processed by any of the back-ends, without recompilation. Code from multiple back-ends can live in the same executable without type clashes.
The refactoring we described quickly paid for itself in time savings and maintainability improvements.
Our approach still requires us to compile our scripts as Haskell code. An alternative we have considered, but not yet tried is based on GHC's "Language" library. This library allows one to directly parse Haskell source to ASTs. The downside is that we would have to provide Haskell's semantics and typing ourselves. Currently, using the library seems a complex approach with few benefits, but it does provide us with an "escape hatch" should the requirements of the project change.

4  Usage at Barclays

The FPF (excluding trade scripts) is 2-3 effort-years of work, with one full-time and one part-time developer. It consists of 20,000 lines of Haskell. The trade scripts contribute a further 30,000 lines, distributed over more than 400 trade types (including variants), and were written by half a dozen individuals. There are around twenty direct users (traders and structurers), with further users hidden behind the scenes outside of the front-office area.
Currently we use each FPF script in a number of downstream operations.
Generation of pricing instructions   Our original target was the generation of instructions in the legacy "Payout DAG" format. Since then we have started to extend the range of target languages. Currently, we can write out instructions in another proprietary functional format, and in C, which we plan to compile and link into our Monte Carlo engine on the fly. FPF can also emit parameters for PDE-solving.
Generating recursive equations in TEX   An alternative FPF target was to create human-readable instructions. Most people involved in finance, while not used to functional programming, are conversant with common mathematical notation. As such, we can present the scripts by transforming them into sets of recursive equations. This transformation is useful as it allows us to extend our target audience of people who can read an FPF script without providing any further training. The transformation can be applied to both the abstract trade script without input data, in order to generate a general description of the trade type, and to a script specialised with concrete assets and dates to produce a term sheet for a particular trade.
The TEX back-end is perhaps best explained with demonstration output. The term sheet equations generated for the "Napoleon" trade described in Section 2.3 are shown in Figure 3.
One could argue that generating a set of human-readable equations is simply another form of pricing instruction generation, albeit one with a very different optimisation target: of readability rather than efficiency (and where executability is a distinctly secondary target). In FPF this multitude of back-ends is actually the case, since the very last step of generating LATEX can be replaced with emitting Mathematica [Wolfram, 2003] instructions, which can be both visually compared to the LATEX output, and executed in a Monte Carlo engine, with the price checked against our other Monte Carlo systems as part of our validation process.
Input form generation   The parameters to the scripts must be somehow specified by the user. We have created GUI tools to allow us to enter parameter values which match a given type. To generate an input form for a particular trade script, we just need to extract the type of the function's parameters, and any associated annotations, which are used to create labels on the input form.
Other analyses   We are working on tools that allow us to perform generic analyses across the FPF trades in order to simplify trade management. For example, it is simple to pull out the set of dates upon which observations and payments take place, with some context information, or to generate a list of payments that should have taken place.
We are extending these analyses with tools to help monitor "barriers", or discontinuities in the payouts, giving us, for example, the expected size of the discontinuity, and when and under which market conditions the barrier levels are breached.

max
( 0, len(tO )
min
i=1 
( STOP (tO i)

STOP (ai−1)
− 1) + FC)
where

a0
=
tID
ai
=
tO i
The parameters to the preceding trade type are as follows:
Variable Description Type
TOP Top-level input Tuple of (STOP , FC, tID , tO )
   STOP Asset Asset
   FC Fixed coupon Double
   tID Initial date Date
   tO Observations List of Date
Figure 3. Recursive equations automatically generated from the "Napoleon" trade.

5  Lessons learned

From the FPF project we learned a lot regarding the application of functional languages to concrete, production systems with all the deadlines and hard requirements that this entails. As always, a number of the lessons came from failed approaches. An interesting lesson we learned from these failures is that the expressiveness of Haskell allowed us to rapidly and efficiently make these mistakes, leaving us plenty of time to develop a useful system.
In the following sections we endeavour to highlight some of the most notable issues.

5.1  Efficient processing of embedded languages

We were initially unaware of the efficiency issues which could occur when we evaluated complex payouts. Consider the following script:
f x = let x2 = x  + x
          x3 = x2 + x2
          x4 = x3 + x3
          ...
      in x20
A straightforward numerical evaluation would calculate the result in 20 steps. An alternative interpretation generating an AST would also take 20 steps, and internally it would create a DAG with much sharing. The problem comes when one wants to evaluate it. Naïve evaluation processes the tree fully, in exponential time. One can try to improve the result with caching, so that if a sub-expression has already been evaluated we can use the pre-existing result. Unfortunately, the built-in comparison operators are purely structural. In other words, in order to avoid fully traversing a data structure, we must perform a full traversal to compare it to cached items!
We eventually discovered this optimization is a well-known problem. Using CSE, as suggested in [Elliott et al. , 2003] would not work us, as we would have to fully traverse the tree, taking exponential time. Solutions based around memoization with stable names [Peyton Jones et al. , 1999] and observable sharing [Claessen & Sands, 1999] are discussed in the literature, but not knowing what to look for, we reinvented the wheel with our own form of "hash consing". After the fact we refactored the code to be closer to the academic ideal.

5.2  Combinators versus functions

Many domain-specific embedded functional languages seem to get implemented as combinator libraries [Cardelli & Davies, 1997]. The points-free approach, while elegant, can make code unreadable, especially if it is written by quantitative analysts moonlighting as functional programmers. Therefore, while we could have defined a polymorphic higher-order combinator library, in FPF we encourage the user to write in a more basic functional style. Examples of this style are shown in Figure 2, and seem far clearer to us than the same code written in a points-free style.

5.3  Scrap-Your-Boilerplate and caching

Scrap-Your-Boilerplate ( SYB) [Lämmel & Peyton Jones, 2003] has provided a very convenient mechanism to accelerate the writing of transformations. Using it has encouraged us to embrace the common functional pattern of splitting out the recursive traversal and per-node operations. Sadly, the support for monadic generic transformations is not as strong as for non-monadic transformations (lacking, for example, generic monadic queries), leading to some fairly ugly code as we fake up the query with a WriterT monad transformer [Grabmüller, 2006].
We mostly use SYB in combination with caches held inside a StateT monad transformer. As with the original SYB implementation, we split our code into the function that recurses over the tree (with caching and short-circuiting), and the function that transforms individual nodes.

5.4  Scope creep and incremental change

Haskell is a remarkably refactorable language. For the current application intermediate ASTs provide a perfect interface between subsystems, so that processing stages are minimally coupled. Where modifications to data types are necessary, type inference minimises the textual changes and the tools ensure no cases are missed. The pure functional nature of the language means incremental changes tend to have localised effect. Incremental changes, in tandem with a home-grown regression test system, reduce the risk of behaviour changing unexpectedly while modifying the code base. In this way major changes (almost complete rewrites) have been achieved without major problems.
On the other hand, our system's flexibility can lead to unnecessary playing. Perfectionists can have a field day quietly rearranging the internals when they should be adding new features. Not that rearranging Haskell code is painless; for example, converting code to a monadic form in order to add caching to our transformations was a mind-numbing operation.
One of our initial unconscious decisions was to blur the lines between the embedding and embedded language. In the prototype, the embedded language was a mechanism for generating a payout DAG using whatever Haskell functions seemed useful. In later versions, while the embedded language became better defined, we found the ability to break out into the embedding language in an emergency useful for prototyping and even limited production use. We used calls into non- FPF Haskell as our training wheels for developing the embedded language; we finally removed these calls with the switch to a deep embedding.
As experienced practitioners would expect, FPF has been subject to distinct scope creep.1 The original plan was to handle all trades that were either generated with existing templates, or by hand. These trade types tended to have their complexity limited by what was maintainable. As FPF has allowed scripts to be written with no regard to how complex the underlying payout DAGs got, the complexity of trades attempted has grown markedly.
As an example, we previously had problems maintaining hand-structured trades with a few hundred nodes in the payout DAG. FPF makes it much easier to handle such trades. However, FPF also makes it just as easy to construct trades with 30,000 node payout DAGs (to the extent that the output of FPF is now stressing downstream systems!). Some such trades are simply scaled up versions of existing trades, but for the most part these represent trades we had no way of expressing before. Early FPF scripts were generally around 30 lines in length, while our larger scripts now have about 200 lines.
The original architecture was not designed with this level of scalability in mind, and it is to the system's credit that changes to cope with this level of scaling can be incorporated without major risk.

5.5  Complexity and performance issues

Moving to Haskell allowed complex algorithms to be written in a fraction of the time required for implementation in an equivalent first-order imperative production language. However, the ease with which complex algorithms can be written can lead to severe performance problems; an algorithm that would otherwise take days to write can be implemented with little thought, including perhaps little thought for the algorithm's complexity. We found GHC's profiler [Sansom & Peyton Jones, 1995] a real boon to fixing such problems.
While the exponential blow-up described in Section 5.1 was the worst example seen by our rather naïve functional programmers, even the polynomial time optimisation steps start to become very expensive on graphs containing tens of thousands of nodes after CSE.
The most complex performance problems came from the TEX-generation subsystem, which relied heavily on substitution. Straightforward substitution into sub-expressions led to an exponential blow-up as the amount of sharing was reduced. The solution was to not perform the substitution itself, but instead insert a node representing the substitution, and track that information during later passes.
Haskell is perhaps infamous for its space leaks. However the only time we have seen space leaks is when they have accompanied algorithms with poor complexity characteristics. Perhaps this is the result of always compiling with optimisations (including strictness analysis) and using machines with plenty of memory. While we have seen very few pure space leaks, our use of caching and hash-consing means that our programs are quite allocator-heavy, and started to spend most of their time in garbage collection. Simply increasing the default heap size in the runtime system was a quick way of remedying the corresponding overhead.
The lesson here, perhaps, is that there is no silver bullet. While a functional approach greatly simplified our task, commonplace issues such as algorithmic complexity cannot be set aside. Furthermore, these issues may crop up in forms one does not recognise, so that the developer must relearn previous experiences.

5.6  Haskell for non-developers

While the programmers who worked on the core of the FPF framework had previous exposure to functional languages, those implementing the trade scripts generally did not. The scripters are mostly mathematicians with expertise in continuous maths (specifically stochastic calculus). They have been trained in C++, although by no means are they all expert developers. Their previous experience of writing trade scripts was hand-generating the payout DAGs in Excel.
An initial worry was that they would at best write imperative code in a functional language, and at worst flounder completely. The first few scripts were distinctly imperative, but with a bit of practice the payouts were being written in a clean functional style. This transformation is perhaps not surprising to those who teach functional programming, but it was a pleasant surprise to see people quickly picking up the ideas in a production environment.

5.7  Re-inventing the wheel

While the developers were experienced with functional languages, this was the first time they had used such a wide set of Haskell libraries in a commercial setting under commercial pressures. When we needed a complex feature, it was generally a case of reinventing the wheel, badly, followed by a refactoring process where we replaced the implementation by a call to a more-general library function (once we identified the appropriate papers). As simple concrete examples, early on we reinvented some state monad machinery, and we are currently looking at moving to a more structured memoisation framework based on earlier work [Peyton Jones et al. , 1999,Claessen & Sands, 1999].
The development pattern we described is difficult to fix, since although the papers are there, it is somewhat difficult to identify a priori what is relevant, especially under time constraints, and the low-risk approach of rolling-your-own (hacky and restricted) code takes over. The preferred solution would be developers more experienced in Haskell, but the combined Haskell and financial knowledge is rather rare, and it seems that even a relatively inexperienced Haskell programmer can be more productive than an experienced C++ programmer in domains such as ours.
However, reimplementing the wheel is an excellent way of understanding the tricks involved, and a well-designed framework should not make it difficult to replace the offending code with a well-constructed library, so the overall cost is not great.

5.8  Interfacing with other systems

One of the worries typically raised about adopting a new technology in a large and complex system concerns the interfacing of its components. As we described in Section 3, the adoption of Haskell has allowed us to refrain from tight coupling with existing systems. We also found the same approach effective for encapsulating our serialised data structures. Using a Haskell-like text data structure rather than, say, XML we were able to control the representation fully, considerably reducing the risk that third parties will attempt to process these structures themselves. Instead, we provide the translation tools to present the data in the format they need, and we can continue to write fully generic tools.
The command-line interface we adopted made testing and fault identification into a far more productive process. Should in-process operation be required in the future, a COM interface can be integrated [Finne et al. , 1999].
Of course, there are issues remaining to do with versioning and configuration management within a production system. While these issues can be tackled using the standard software engineering approaches, we have yet to consider whether Haskell will provide us with any good tricks to ease these problems.

6  Related work

The interested reader may consult Hull [2005] for a general background on derivatives. Vanilla and exchange-traded derivatives are standardised, and describing the trades becomes an exercise in naming conventions. For exotic trades, however, trade representation is a real issue. Little published work addresses the problem, perhaps because the solutions involved are either kludges the authors do not wish to show off, or thought to be proprietary, cutting-edge software best kept secret. The published approaches in the field of trade representation include the use of frameworks [Eggenschwiler & Gamma, 1992] and the adoption of domain specific languages [Deursen, 1997].
In the past decade considerable work has been published on the use and implementation of domain-specific languages [Spinellis, 2001,Mernik et al. , 2005], and in particular the use of Haskell as a vehicle for creating embedded DSLs [Hudak, 1996,Anand et al. , 2001]. An early attack on our specific problem involved the development of the domain-specific language RISLA, whose code was subsequently compiled into COBOL [Arnold et al. , 1995,van Deursen & Klint, 1998]. Later work [Peyton Jones et al. , 2000,Peyton Jones & Eber, 2003] used Haskell to allow payouts to be defined in an abstract functional language and to provide multiple interpretations of the products. This work was apparently commercially adopted and marketed [MLFi, 2004,LexiFi, n.d.]. We considered that product as a COTS alternative to FPF, but in the end the risks in integrating the product and loss of control in development meant that we instead opted for an in-house product designed from the start to integrate with existing systems.
Various methods for addressing the trade representation problem have spread through word-of-mouth. Given the lack of formal literature, it seems preferable to report what we have heard of than to say nothing. As such, the rest of this section is necessarily light on references. It seems that each bank has at least one (often more!) proprietary payout language. These languages are commonly custom imperative scripting languages. In such a language, the price-calculation stages can be tied to the underlying time-steps of the trade. This evaluation approach allows the past (with its fixed values) to be calculated once, the state to be cached, and then the future dates to be calculated repeatedly under different scenarios, saving much execution time. However, this approach ties the language tightly to the evaluation mechanism, and is not convenient for all trade structures. The alternative of binding trade descriptions to an existing general-purpose language (such as VBA or Python [van Rossum & Drake, 2006]) for the payout evaluation allows incredible flexibility in the pricing strategy, but makes it very difficult to perform any interpretation beyond a simple pricing.
Expressing the payout in a domain-specific language (often a subset of an existing language) allows various analyses to be performed, and lets the end-users work with tools they feel comfortable with. However, this approach involves a delicate trade-off between expressivity and the complexity of the translation to specify the subset that is deemed convertible. A common line of attack here involves writing simple payouts as a set of Excel formulae, checking that they work inside the spreadsheet, and then "shredding" the cells into a document suitable for external evaluation.
Other institutions also use a functional payout language, but the DSL itself is typically implemented in C++ or Java, rather than in a functional language. Even then, they generally perform only a single interpretation; that used for pricing. There may also be other systems in use with particularly novel and interesting approaches but, alas, they apparently have not been published in the open literature.

7  Conclusion

FPF is now integral to our equity exotics business, both tactically and strategically. Not having a system like FPF would give us unacceptable operational risk in a few years time, but in the shorter term it is already making a big impact. We now write all new trades using FPF. In addition, we have migrated all our one-off trades to FPF, freeing up reserve cash devoted to operational risk. Currently we are also starting to migrate templated trades to FPF.
The project is almost a victim of its own success. While we reduced the development cycle, the opportunities this shortened cycle presents mean that we still have a backlog of new ideas to implement that is far greater than our available developer bandwidth!
It will be interesting to see what the future holds for payout description technology. Generating a trade's contract and having each party in the transaction reconcile it with their internal descriptions is currently a manual and error-prone business. Once financial institutions have automated all processing associated with their internal representation of a trade, it makes sense to standardise on external trade descriptions, to eliminate the risk of ambiguous term sheets or human error during translation. What should such a representation look like? Would the constraints of standardisation stifle novelty, or would it reduce risks and provide the framework for increased innovation?

References

[Anand et al. 2001]
Anand, Saswat, Chin, Wei-Ngan, & Khoo, Siau-Cheng. (2001). Charting patterns on price history. Pages 134-145 of: ICFP '01: Proceedings of the sixth ACM SIGPLAN international conference on functional programming. New York, NY, USA: ACM Press.
[Arnold et al. 1995]
Arnold, B. R. T., Deursen, A. van, & Res, M. (1995). An algebraic specification of a language for describing financial products. Pages 6-13 of: Wirsing, M. (ed), ICSE-17 workshop on formal methods application in software engineering. IEEE.
[Cardelli & Davies 1997]
Cardelli, Luca, & Davies, Rowan. 1997 (Oct.). Service combinators for web computing. Pages 1-9 of: USENIX conference on domain-specific languages. USENIX Association, Berkeley, CA.
[Claessen & Hughes 2000]
Claessen, Koen, & Hughes, John. (2000). QuickCheck: a lightweight tool for random testing of Haskell programs. Acm sigplan notices, 35(9), 268-279.
[Claessen & Sands 1999]
Claessen, Koen, & Sands, David. (1999). Observable sharing for functional circuit description. Proc. of Asian computer science conference. Lecture Notes in Computer Science. Springer Verlag.
[Deursen 1997]
Deursen, A. van. (1997). Domain-specific languages versus object-oriented frameworks: A financial engineering case study. Pages 35-39 of: STJA'97: Smalltalk and Java in industry and academia. Ilmenau Technical University.
[Eggenschwiler & Gamma 1992]
Eggenschwiler, Thomas, & Gamma, Erich. (1992). ET++SwapsManager: Using object technology in the financial engineering domain. Pages 166-177 of: OOPSLA '92: Conference proceedings on object-oriented programming systems, languages, and applications. ACM Press.
[Elliott et al. 2003]
Elliott, Conal, Finne, Sigbjørn, & de Moor, Oege. (2003). Compiling embedded languages. Journal of functional programming, 13(2). Updated version of paper by the same name that appeared in SAIG '00 proceedings.
[Feldman 1979]
Feldman, Stuart I. (1979). Make-a program for maintaining computer programs. Software: Practice and experience, 9(4), 255-265.
[Finne et al. 1999]
Finne, Sigbjorn, Leijen, Daan, Meijer, Erik, & Peyton Jones, Simon L. (1999). Calling Hell from Heaven and Heaven from Hell. Pages 114-125 of: ICFP '99: Proceedings of the fourth ACM SIGPLAN international conference on functional programming.
[Gill & Runciman 2007]
Gill, Andy, & Runciman, Colin. (2007). Haskell program coverage. Pages 1-12 of: Haskell '07: Proceedings of the ACM SIGPLAN workshop on Haskell workshop. New York, NY, USA: ACM.
[Grabmüller 2006]
Grabmüller, Martin. 2006 (October). Monad transformers step by step. Available online http://uebb.cs.tu-berlin.de/~magr/pub/Transformers.pdf. Draft paper.
[Hudak 1996]
Hudak, Paul. (1996). Building domain-specific embedded languages. ACM comput. surv., 28(4es), 196.
[Hudak et al. 2007]
Hudak, Paul, Hughes, John, Peyton Jones, Simon, & Wadler, Philip. (2007). A history of Haskell: being lazy with class. Pages 12-1-12-55 of: HOPL III: Proceedings of the third ACM SIGPLAN conference on history of programming languages. ACM Press.
[Hull 2005]
Hull, John C. (2005). Options, futures and other derivatives. Sixth edn. Upper Saddle River, NJ: Prentice Hall.
[Kramer 1999]
Kramer, Douglas. (1999). API documentation from source code comments: A case study of Javadoc. Pages 147-153 of: SIGDOC '99: Proceedings of the 17th annual international conference on computer documentation. New York, NY, USA: ACM Press.
[Lämmel & Peyton Jones 2003]
Lämmel, Ralf, & Peyton Jones, Simon. 2003 (Jan.). Scrap your boilerplate: a practical approach to generic programming. TLDI 2003: Proceedings of the ACM SIGPLAN workshop on types in language design and implementation.
[LexiFi n.d.]
LexiFi. LexiFi Platform. http://www.lexifi.com/. Current September 2007.
[Marlow 2002]
Marlow, Simon. 2002 (Oct.). Haddock, a Haskell documentation tool. Proceedings of the ACM SIGPLAN workshop on Haskell.
[Mernik et al. 2005]
Mernik, Marjan, Heering, Jan, & Sloane, Anthony M. (2005). When and how to develop domain-specific languages. ACM comput. surv., 37(4), 316-344.
[MLFi 2004]
MLFi. 2004 (Apr.). Structuring, pricing, and processing complex financial products with MLFi. Available online http://industries.bnet.com/whitepaper.aspx?&tags=window&docid=103795. Current January 2007.
[Peyton Jones & Eber 2003]
Peyton Jones, Simon, & Eber, Jean-Marc. (2003). How to write a financial contract. Gibbons, Jeremy, & de Moor, Oege (eds), The fun of programming. Palgrave Macmillan.
[Peyton Jones et al. 2000]
Peyton Jones, Simon, Eber, Jean-Marc, & Seward, Julian. (2000). Composing contracts: an adventure in financial engineering (functional pearl). Pages 280-292 of: ICFP '00: Proceedings of the fifth ACM SIGPLAN international conference on functional programming. New York, NY, USA: ACM Press.
[Peyton Jones et al. 1999]
Peyton Jones, Simon L., Marlow, Simon, & Elliott, Conal. (1999). Stretching the storage manager: Weak pointers and stable names in Haskell. Pages 37-58 of: Implementation of functional languages.
[Roundy 2005]
Roundy, David. (2005). Darcs: distributed version management in Haskell. Pages 1-4 of: Haskell '05: Proceedings of the 2005 ACM SIGPLAN workshop on Haskell. ACM Press.
[Sansom & Peyton Jones 1995]
Sansom, Patrick M., & Peyton Jones, Simon L. (1995). Time and space profiling for non-strict, higher-order functional languages. Pages 355-366 of: POPL '95: Proceedings of the 22nd ACM SIGPLAN-sigact symposium on principles of programming languages. New York, NY, USA: ACM Press.
[Spinellis 1993]
Spinellis, Diomidis. (1993). Implementing Haskell: Language implementation as a tool building exercise. Structured programming (software concepts and tools), 14, 37-48.
[Spinellis 2001]
Spinellis, Diomidis. (2001). Notable design patterns for domain specific languages. Journal of systems and software, 56(1), 91-99.
[The Bank for International Settlements 2007]
The Bank for International Settlements. 2007 (Mar.). BIS quarterly review. Available online http://www.bis.org/publ/qtrpdf/r_qa0703.pdf. Current September 2007.
[van Deursen & Klint 1998]
van Deursen, Arie, & Klint, Paul. (1998). Little languages: Little maintenance. Journal of software maintenance, 10(2), 75-92.
[van Rossum & Drake 2006]
van Rossum, Guido, & Drake, Jr., Fred L. (eds). (2006). An introduction to Python. Network Theory Ltd.
[Wall & Schwartz 1990]
Wall, Larry, & Schwartz, Randal L. (1990). Programming Perl. Sebastopol, CA: O'Reilly and Associates.
[Wolfram 2003]
Wolfram, Stephen. (2003). The Mathematica book. Fifth edn. Wolfram Media.


Id: fpf.tex,v 1.31 2008/12/11 06:56:29 dds Exp

Footnotes:

1In fact, FPF was always expected to have some scope creep beyond its initial requirements-indeed, the need for flexibility was one of the main reasons for choosing Haskell. What was surprising, however, was how much scope creep we have seen (and have been able to accommodate) in practice.