Tuesday, March 4, 2014

Curried and Partial Functions in Scala

Target audience: Intermediate
Estimated reading time: 5'



Table of contents
Follow me on LinkedIn

Introduction

Although most of Scala developers have some level of knowledge of curried and partial functions, they struggle to grasp the different use case either of those functional programming techniques are applied and their relative benefits. For those interested in more detailed explanation of currying existing functions, I would recommend the excellent post of Daniel Westheide.

Note: For the sake of readability of the implementation of algorithms, all non-essential code such as error checking, comments, exception, validation of class and method arguments, scoping qualifiers or import is omitted

Partial functions

Partially defined functions are commonly used to restrict the domain of applicability of function arguments. The restriction can apply to either the type of the argument or its values. Let's consider the computation of square root of a floating point value dsqrt. The value of the argument has to be positive. A simple implementation relies on the Option monad.

def dsqrt(x: Double): Option[Double] = 
    if(x<0.0) None else Some(Math.sqrt(x))

The same method can be implemented using a partial function by applying the matching pattern to the argument as follows.

val zero = 0.0

def dsqrt: PartialFunction[Double, Double]= { 
    case x: Double if(x >=zero) => Math.sqrt(x) 
}

The method dsqrt return an object of type PartialFunction with an input argument of type Double and an output of type Double. The method can handle only input value x >= 0.0. Any other input value generates a MatchErr exception.

Let's evaluate the partial function with different argument types and values. The partial function accepts input with type for which an implicit conversion has been already defined. The first invocation of dsqrt (line 2) returns a valid Partial Function. The second invocation (line 8) triggers an implicit conversion from Long to Double, before returning the partial function. The third call to dsqrt will returns a MatchErr (line 12)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
  // Succeeds
Try (dsqrt(3.6)) match { 
  case Success(res) => {} 
  case Failure(e) => Console.println(e.toString)
 }

  // Succeed because the implicit conversion Long to Double
Try (_sqrt(4L)) match { }

  // Fails with the following message
  // "throws scala.MatchError: -3.6 (of class java.lang.Double)"
Try (_sqrt(-3.6)) match { }

A similar restriction can be applied to the type of argument. Let's consider the incremental methods add1 (line 3) and add2 (line 15) of class Value. These two methods process values of type AnyValue. It requires that the type of argument to be checked. add and add2 described two alternative and crude type safe checking approaches.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Value(x: Int) {

  def add1(anyVal: AnyVal): AnyVal = {
    if(anyVal.isInstanceOf[Int]) {
      val value = anyVal.asInstanceOf[Int]
     (x + value).asInstanceOf[AnyVal]
    }
    else if (anyVal.isInstanceOf[Double]) {
      val value = anyVal.asInstanceOf[Double].floor.toInt
     (x + value).asInstanceOf[AnyVal]
    }
    else { }
  }
   
  def add2(anyVal: AnyVal): AnyVal = anyVal.getClass.getName match {
    case "Int" => {
      val value = anyVal.asInstanceOf[Int]
     (x + value).asInstanceOf[AnyVal]
    }
    case "Double" => {
      val value = anyVal.asInstanceOf[Double].floor.toInt
     (x + value).asInstanceOf[AnyVal]
    }
    case _ => {}
  }
} 

The two implementation add1 and add2 are cumbersome to say the least. An alternative implementation using a pattern matching on the type an returning a partial function is far more elegant.

1
2
3
4
5
6
7
8
9
class Value(x: Int) {
  def add: PartialFunction[Any, Any] = {
    case n: Int => x + n
    case y: Double => x + y.floor.toInt
  }
}

val value = new Value(4)
Console.println(value.add(4.5))

In the example above, we do not have to handle the case for each the argument has an improper type. The partial function will simply discards it.

Note: The method Actor.receive that define a message loop in an actor, consuming messages from the mail box are indeed partial functions.

Currying

Currying is the transformation of function with multiple arguments into a chain of function taking a single argument. if f: x-> f(x,y) then curry(f): x -> (y->f(x,y))
Let's take a simple example of a sum of two floating point values. The original 2 arguments functions (1) can be converted into a single argument function returning a anonymous function taking the second argument as parameter (2). Scala provides developers with a simple syntax sugar to define the cascade of functions calls (3)

def sum(x: Double, y: Double): Double = x+y
def sum(x: Double): Double = (y: Double) => x+y
def sum(x: Double)(y: Double): Double = x+y
 

Most of high order methods on collections are curried. The following example illustrate the commonly used foldLeft.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Collection[T](private val values: Array[T]) {

  def foldLeft[U](u:U, op:(U,T)=>U):U = 
    values.foldLeft[U](u)((u,t)=> op(u,t))
  def foldLeft[U](u:U)(op:(U,T)=>U):U = 
    this.foldLeft(u, op)    
}
 
val myCollection = new Collection[Int](Array[Int](3, 5, 8))
val product = myCollection.foldLeft[Int](0)((prod, x) => prod*x)


Is there any benefits of using curried function instead of functions or methods with multiple arguments? Yes, in the case the type inferencer has more information that the second argument can use. Let's consider the foldLeft method above:
    def foldLeft[U](u: U)(op:(U, T)=>U):U = this.foldLeft(u, op)

The type inferencer determine the type U of the first argument and used it subsequently in the binary operator parameters
op:(U, T) => U

References

Monday, February 17, 2014

Efficient Trading Option Pricing in Scala

Target audience: Intermediate
Estimated reading time: 5'

Ever pondered how the pricing of an option on a future or index works? Curious about the underlying formula?
This article offers a succinct summary of the Black-Scholes formula and discusses how it's implemented in Scala, utilizing memoization to enhance execution speed.


Table of contents
      Formulation
      Memoization
Follow me on LinkedIn

What you will learn: A fast, memoized implementation of option pricing equation of Black-Scholes.

Notes
  • For the sake of readability of the implementation of algorithms, all non-essential code such as error checking, comments, exception, validation of class and method arguments, scoping qualifiers or import is omitted.
  • Familiarity with option trading [ref 1] is not required to understand the topic
  • Environments: Scala 2.12.10, JDK 11

Overview

You don't need to be a seasoned professional in option trading or asset valuation to grasp the essence of Black-Scholes. 

The Black-Scholes model is a method employed to calculate the fair or theoretical value of a call or put option. This calculation is based on six key factors: the volatility, the type of option, the price of the underlying stock, the duration until expiration, the strike price, and the risk-free interest rate.

The Black-Scholes-Merton equations, a notable set of stochastic partial differential formulas, are renowned for pricing options based on underlying security's price, volatility, and expiration time [ref 2]. Functional languages like Scala give developers the flexibility to experiment with and test various volatility and time decay models [ref 3].

Theory

Black-Scholes approach assumes that the price of the underlying security follows a geometric Brownian distribution known as the Wiener process. If we note S(t) the price of security (stock, bond, future), V(t) the price of the option over time, r the annualized compound risk-free interest rate or rate of return, and sigma the volatility of the price of the underlying security S then the Black-Scholes equation can be described as \[\frac{\partial V}{\partial t} + \frac{\sigma ^{2}S^{2}}{2}\frac{\partial^2 V}{\partial S^2} + r (S\frac{\partial V}{\partial S}- V) = 0\] The resolution of the partial differential equations produces the following solution for a call option: \[(1)\ \ C(t) = N(d)S - N(d')Ke^{-r(T-t)}\,\,with\\N(x)=\frac{1}{\sqrt{2 \pi }}\int_{-\infty }^{x}e^{-\frac{t^{2}}{2}}dt\\(2)\ \ d = \frac{1}{\sigma \sqrt{T-t}}[log(\frac{S}{K}) + (r+\frac{\sigma ^{2}}{2})(T-t)]\\(3)\ \ d^{'}=d-\sigma \sqrt{T-t}\] K is the strike price for the underlying security. The price of a put option is computed as \[P(t)=N(-d + \sigma \sqrt{T-t})Ke^{-r(T-t))} - N(-d)S\] As a reminder, a financial call option gives a buyer the right for a premium fee but not the obligation to acquire an agreed amount of assets S (securities, bonds, commodity) from a seller at a future date T for a certain predefined price (strike price: K). The seller is obligated to sell the commodity should the buyer so decide. A put option gives the buyer the right but not the obligation to sell an asset by a future data at a predefined (Strike) price.

Implementation

Calculating the price of an option requires extensive CPU usage. The approach includes several steps:
  1. Establish and encapsulate the parameters used in the Black-Scholes formula.
  2. Carry out the process to calculate the price of a call option.
  3. Identify the various computational elements involved in the Black-Scholes formula.
  4. Create a system for storing temporary results.
  5. Combine these interim outcomes to finalize the call price.
  6. Use Monte Carlo Simulation for determining the security's price.

Formulation

First let's define a data class, BSParams to encapsulate the parameters of the Black-Scholes formula:
  • S Current price of the underlying security
  • K Strike price
  • r Annual compound risk-free interest rate
  • sigma Volatility of the price of the underlying
  • T Expiration date for the option
case class BSParams(
   S: Double, 
   K: Double, 
   r: Double, 
   sigma: Double, 
   T: Double)


The Scala code snippet below implements the pricing of a call option for a security S and reflect the mathematical equations defined in the previous paragraph.

def callPrice(p: BSParams, t: Double): Double = {
    import Math._

   // Implement the Black-Scholes stochastic equation,
   val sigmaT = p.sigma * sqrt(p.T - t)

   // Formula (2)
   val d = (log(p.S/p.K)+ (p.r + 0.5*sigma*sigma)*(p.T-t)) /sigmaT 

   // Formula (3)
val d' = d1 - sigmaT
   
val gauss = new Gaussian
   // Computation of the call C(t) as per formula. (1)
   p.S*gauss.value(d) - p.K*exp(-p.r*p.T)*gauss.value(d')
}

However, professional traders in commodities and futures for instance are more interested simulating the impact of volatility, sigma, time decay t -T or price of the commodity on the price of the option using Monte Carlo simulation. In this use case, the computation of the entire Black-Scholes formula is not necessary. 

Memoization

Memoization, in the realm of computing, is a strategy for optimizing program performance. It involves caching the outcomes of costly function calls to pure functions. This way, when inputs are repeated, the program can quickly retrieve the stored result instead of recalculating it.

The aim is to reduce computational expenses by incorporating the algorithm into a workflow. In this approach, steps within the workflow that remain unchanged by the alteration of a single variable's value are not executed. For example, a change in the underlying security's price, denoted as S, necessitates recalculating only a specific part of the workflow, namely \[S=> log(S/X)\] The Black-Scholes algorithm is divided into five distinct internal computational stages:

object BSParams{
   val fLog = (p: BSParams) => Math.log(p.r / p.T)
   val fMul = (p: BSParams) => p.r * p.T
   val fPoly = (p: BSParams) => 0.5 * p.sigma * p.sigma * p.T
   val fExp = (p: BSParams) => -p.K * Math.exp(-p.r * p.T)
}

The 4 computational steps are used to maintain intermediate results so the entire Black-Scholes formula does not have to be computed from scratch each time one of the parameters S, K, r, sigma or T is changed.
The computational state is completely described by
  • Parameters of Black-Scholes equations S, K, r, sigma, T
  • Partial or intermediate results {bs1 to bs5}
Next, we need to wrap the computation and update of intermediate results of the Black-Scholes formula.

case class PartialResult(bs1: Double, bs2: Double, bs3: Double, bs4: Double, bs5: Double){
    import BSParams._

    lazy val d1: Double = (bs1 + bs2 + bs3) / bs4

    def f1(p: BSParams): PartialResult = this.copy(bs2 = fLog(p))

    def f2(p: BSParams): PartialResult = this.copy(bs2 = fMul(p), bs5 = fExp(p))

    def f3(p: BSParams): PartialResult = this.copy(bs3 = fPoly(p), bs5 = fExp(p))
 }

As mentioned earlier, the computation state is defined by the Black-Scholes parameters p and intermediate results values, pr.

class State(p: BSParams, pr: PartialResult){

    def setS(newS: Double): State = new State(p.copy(S = newS), pr)

    def setR(newR: Double): State = new State(p.copy(r = newR), pr)

    def setSigma(newSigma: Double): State = 
                  new State(p.copy(sigma = newSigma), pr)

    lazy val call: Double = {
       import org.apache.commons.math3.analysis.function.Gaussian

       val gauss = new Gaussian
       p.S * gauss.value(pr.d1) -pr.bs5 * gauss.value(pr.d1 - pr.bs4)
    }
}

Each of the methods setS, setR, setSigma updates one of the Black-Scholes equation parameters that automatically triggers a selective re-computation of some of the intermediate results.
The price of the call is a lazy value computed only once (immutable state).  The update of the state of the Black-Scholes computation is rather straight forward.
The following code snippet illustrates the immutable update of sigma in the price of a call 

// Initial computation/state of Black-Scholes  
val state0 = new State(0.4, 0.6, 0.1, 2.0, 1.4)

  // Compute the price of a call
val callValue = state0.call
log.info(callValue)
// Update the value of sigma val state1 = state0.setSigma(0.14) val newCallValue = state1.call
log.info(newCallValue)

Monte-Carlo Simulation

A Monte Carlo simulation is a method employed to estimate the various possible outcomes of a process that is challenging to predict owing to the presence of random elements. This technique is instrumental in assessing the effects of risk and uncertainty.
The Monte Carlo simulation finds application in an array of disciplines, such as finance, business, physics, and engineering, among others. It's often used to solve a variety of problems and is sometimes known as a multiple probability simulation.

The Black-Scholes formula can be validated through a Monte-Carlo simulation, using a Gaussian distribution to represent the stochastic component of the formula.
The price of security S(t) at time t is defined as \[(4)\ \ S_{t}=S_{0}+e^{(r - \frac{\sigma^{2}}{2})t+\mathbb{N}(0,1)\sigma\sqrt{t}}\]
The solution S(t) can be approximated using an iterative or recursive process. \[(5)\ \ S_{t}=S_{t-1} + e^{(r - \frac{\sigma^{2}}{2}).dt+\mathbb{N}(0, 1)\sigma\sqrt{dt}}\] 
This particular implementation uses a fast tail recursion to simulate the computation of the underlying security at any given time t. The sampling times are normalized as integers with dt =1 for a faster simulation.

 import Random._

def monteCarlo(p: BSParams, s0: Double): List[Double] = {
     // Implementation of equation (4)
   val initialValue = s0*exp((p.r-0.5*p.sigma*p.sigma)+p.sigma*nextGaussian)
   monteCarlo(p, 0, List[Double](initialValue))
}

  
@tailrec
private def monteCarlo(p: BSParams, t: Int, values: List[Double]): List[Double] = {
   import Math._
    
   if(t >= p.T)
     values.reverse
   else {
        // Implementation of equation (5)
val st = values.last * exp((p.r-0.5*p.sigma*p.sigma)+p.sigma*nextGaussian) monteCarlo(p, t+1, st :: values) } }

The implementation of the Monte Carlo simulation relies on the fast Scala tail recursion [ref 4].

Evaluation

Let's predict the price of security using the Monte Carlo method for 100 units of time.

val S0 = 80.0
val r = 0.06
val sigma = 0.2
val K = 0.9
val bsParams = BSParams(S0,  r, K, sigma, 100)
val pricePrediction = monteCarlo(bsParams, S0)

The plot below illustrates the impact of the risk free of interest rate, r (6% and 1%) on the simulated price, pricePrediction  of the underlying security.


References

[2] Black-Scholes Model: What It Is, How It Works
[3] Scala for the Impatient - C. Horstman - Addison-Wesley 2012  

Friday, January 31, 2014

Performance Evaluation of Scala Maps

Target audience: Beginner

Overview

The Scala programming language API provides developers with a set of short immutable maps of predefined length, Map1, .. Map4,  Set. I thought it would be worthwhile to evaluate the performance of those short,  dedicated collections compare to their generic counterpart.
A second test consists of comparing HashMap with TreeMap for sorting a hash table by key.

Note: For the sake of readability of the implementation of algorithms, all non-essential code such as error checking, comments, exception, validation of class and method arguments, scoping qualifiers or import is omitted


Benchmark short maps

The benchmark consists of a very simple methods calls on immutable Map and Map4 instances as well as a mutable HashMap as defined in the code snippet below.

val map4 = new Map4("0"-> 0, "1" ->1, "2 ->,2, "3"-> 3)

val map0 = Map[String, Int]("0" -> 0, "1" -> 1, "2" -> 2, "3"-> 3)

val hMap = HashMap[String, Int]("0" -> 0, "1" -> 1, "2" -> 2, "3" -> 3)


We evaluate the time needed to execute 10 million iterations of a map, get and sum methods as follows:

aMap map { kv => kv._2 + 2 }
aMap get("2")
aMap values sum

The results of the performance test is shown in the table below. As expected the "short" collection is faster that the immutable Map and the mutable HashMap. However the performance improvement is not very significant.

Methods immutable.Map.Map4 immutable.Map mutable.HashMap
get 0.835 s 0.879 s 1.091 s
map 7.462 s 7.566 s 1.106 s
foldLeft 3.444 s 3.621 s 4.782 s


Sorting tables: TreeMap vs. sortBy

The second test consists of sorting a very large list or array of tuple (String, Float) by using maps. There are few options to sort a table among them:
  • Creating, populating and sorting a scala.collection.mutable.HashMap
  • Creating and populating a scala.collection.immutable.TreeMap
The test is set-up by creating pseudo-random key by concatenating the name of a city with an unique id. The values in the map are completely random.

 // Hashmap to be sorted 
val hMap = Range(0, sz)./:(new mutable.HashMap[String, Float])(
  (h, n) =>
      h += (s"${cities(Random.nextInt(cities.size))}_$n", Random.nextFloat )
)
val sortedByKey = hMap.toSeq.sortBy(_._1)

   // TreeMap
val treeMap = Range(0, sz)./:(new immutable.TreeMap[String, Float])(
    (h, n) => 
       h + ((s"${cities(Random.nextInt(cities.size))}_$n",  Random.nextFloat))
)

val sorted = sortedByKey.toSeq


The test is run with map which size varies between 10,000,00 and 90,000,00 entries


Sorting a tuple (String, Float) using TreeMap is roughly 40% faster than populating a HashMap and sort by key.

References