Rohit's Blog

Occasional writing on software engineering.

Composing Contracts, Part 4: Lattices, Laziness, and the Sharing Problem

scaladsl

The last of four, following “Composing Contracts” by Peyton Jones, Eber and Seward (ICFP 2000). Parts 1, 2 and 3 built a contract language and gave it a compositional valuation semantics in terms of abstract value processes.

Now we make a computer compute one. That means picking a financial model, picking a numerical method, and representing a process as a data structure — and it turns out that the last of those is where laziness stops being a stylistic preference and becomes load-bearing.

The paper ends on an unsolved problem. So does this post, though Scala 3 gets closer to a solution than Haskell did, for a reason worth the whole series.

🔗Choosing a model

A value process is a mathematical object. To compute with one you need to represent uncertainty about the future explicitly, and there are three families of numerical method in industrial use: partial differential equations, Monte Carlo, and lattice methods.

The paper picks the Ho–Lee interest rate model with a lattice, for technical simplicity and historical importance — and stresses something worth repeating, because it’s the payoff of the two-layer design from part 3: changing the numerical method would entail bigger changes, but nothing in the language or its semantics would be affected. You can even use different methods for different parts of one contract.

A lattice is a recombining tree. Time runs left to right in discrete steps. Today’s interest rate is known, so the first column has one entry. By the next step the rate has moved up or down, so the second column has two. In the third, up-then-down and down-then-up land on the same node — that’s the recombination — so there are three, not four.

That recombination is the whole trick. The tree grows linearly rather than exponentially, which is what makes the scheme computable at all. Column t has exactly t + 1 nodes.

final case class Lattice(rates: Vector[Vector[Double]], dt: Double):
  def rate(step: Int, node: Int): Double = rates(step)(node)
  def steps: Int = rates.length

Column t is rates(t), with t + 1 entries, indexed from the bottom.

🔗Representing a value process

A value process has the same lattice shape as the rate model, with a value at each node instead of a rate. So:

type RV[A] = Vector[A]        // a random variable: one column
type PR[A] = LazyList[RV[A]]  // a value process: columns, one per time step

Column i has i + 1 entries. A LazyList rather than a List because a process may be defined for all time — and, as we’ll see, because it must not be computed eagerly.

The generic operations from part 3 fall out immediately:

def K[A](x: A): PR[A] =
  LazyList.from(0).map(i => Vector.fill(i + 1)(x))

def lift[A, B](f: A => B, p: PR[A]): PR[B] =
  p.map(_.map(f))

def lift2[A, B, C](f: (A, B) => C, p: PR[A], q: PR[B]): PR[C] =
  p.zip(q).map((sp, sq) => sp.zip(sq).map(f))

K(x) is infinite and costs nothing until observed. And lift2 gets its domain semantics for free: part 3 said the result of lift2 is defined only where both arguments are, and LazyList.zip truncates to the shorter of the two. The type did the bookkeeping.

and needs more care. Its rule (part 3) keeps whichever process survives past the other’s horizon, so plain zip — which takes the intersection — is wrong there. You need a zip-the-longer variant. It’s the one place where the horizon bookkeeping doesn’t fall out of the standard combinators, and it’s worth knowing before you discover it in a test.

🔗Discounting: the one equation that does the work

disc maps a payout at a future date into a process giving its value at earlier dates. On a lattice, that’s a backwards recurrence:

V(t, i) = ( V(t+1, i) + V(t+1, i+1) ) / ( 2 · (1 + R(t, i) · Δt) )

Take the two successor values, average them (each branch is equally likely), then discount that average back one step at the interest rate sitting at this node.

def disc(model: Lattice, horizon: Int, payout: RV[Double]): PR[Double] =
  def back(step: Int, next: RV[Double], acc: List[RV[Double]]): List[RV[Double]] =
    if step < 0 then acc
    else
      val prev = Vector.tabulate(step + 1) { i =>
        (next(i) + next(i + 1)) / (2 * (1 + model.rate(step, i) * model.dt))
      }
      back(step - 1, prev, prev :: acc)
  LazyList.from(back(horizon - 1, payout, List(payout)))

Work an example by hand once and the whole scheme clicks. Take a bond paying £10 at step 3. At step 3 every node is worth exactly 10 — the payout is certain by then, which is axiom disc ᵗₖ(v)(t) = v from part 3 showing up as a base case. Step 2 averages pairs of 10s and discounts, giving something a little under 10 at each node. Repeat back to step 0 and the single value there is what the bond is worth today — call it £8.64 at plausible rates.

snell, for Anytime, is the same shape with one extra step: discount the next column back, then take the pointwise maximum against the original process at this column, then repeat. That max is “exercise now versus hold”, evaluated at every node.

def snell(model: Lattice, horizon: Int, p: PR[Double]): PR[Double] =
  val cols = p.take(horizon + 1).toVector
  def back(step: Int, next: RV[Double], acc: List[RV[Double]]): List[RV[Double]] =
    if step < 0 then acc
    else
      val held = Vector.tabulate(step + 1) { i =>
        (next(i) + next(i + 1)) / (2 * (1 + model.rate(step, i) * model.dt))
      }
      val best = held.zip(cols(step)).map(_ max _)
      back(step - 1, best, best :: acc)
  LazyList.from(back(horizon - 1, cols(horizon), List(cols(horizon))))

🔗Why laziness is not optional

The paper is emphatic that lazy evaluation plays a crucial role, and gives two reasons. Both survive the trip to Scala; one comes with a warning.

Process trees are quadratic. A tree over n time steps has about n²/2 nodes. A complex contract combines many sub-trees, and fully evaluating each before combining them would be — in the paper’s words — Very Bad. Laziness pipelines the computation: only the current column of each tree needs to exist at any moment.

Only part of a tree may be needed. Take the bond from part 1:

Get(scaleK(10, Truncate(t, One(GBP))))

The inner process is defined at every time, with value 10 everywhere, all the way back to step zero. But Get samples it only at its horizon. Computing the earlier columns is pure waste, and with a lazy list you don’t — not because you wrote an optimisation, but because nobody asked.

That second one is the better argument for laziness generally: it isn’t that lazy code is faster, it’s that lazy code doesn’t need you to know in advance which parts will be needed. The get combinator and the process representation were written independently and compose without waste.

LazyList memoises, and that cuts against reason one. Each cell caches its value once forced, so a LazyList you hold a reference to retains every column you’ve walked — turning the pipelining win back into the quadratic memory you were avoiding. The fix is to not hold the head: consume the process in a fold and let the prefix be collected. Haskell has the same hazard, but Scala makes it easier to trip over, because binding a process to a val in an enclosing scope is the natural thing to write and the compiler says nothing. If your valuation engine’s memory grows with the square of the time steps, this is why.

🔗The problem the paper ends on

Recall the American option from part 2:

def american(t1: Date, t2: Date, u: Contract): Contract =
  val opt = Anytime(perhaps(t2, u))
  Get(Truncate(t1, opt)) thereafter opt

opt appears twice. In the source it’s obviously one thing — it’s a val. But by the time eval walks the tree, it sees two branches of a Thereafter and has no way to know they’re the same contract. It values opt twice. Nest a few of these and the duplicated work compounds exponentially.

The paper is candid: this arises in almost every embedded domain-specific language. They cite hitting it in Fran’s reactive animations and in extracting netlists from Hawk circuit descriptions. What makes it especially galling, they say, is that the sharing is absolutely apparent in the source program — and invisible to the interpreter.

The obvious response is to memoise eval. They reject it, and the reasoning is worth absorbing: losing sharing can cost an unbounded amount of duplicated work, so it’s unpleasant to relegate something that important to an operational mechanism that might be defeated by an unevaluated argument or an automatically purged table. They leave it as an open problem, citing Claessen and Sands as the only work addressing it head-on.

🔗Scala 3 can do better here, at a price

This is the one place in the series where the port has a genuine advantage, and it’s instructive because the advantage isn’t a language feature — it’s a consequence of a design choice we’re free to make differently.

A memo table needs to answer “have I seen this contract before?”, which needs structural equality and hashing on Contract. Scala 3 enum cases are case classes, so they get equals and hashCode derived for free. So this should work:

val memo = collection.mutable.HashMap.empty[Contract, PR[Double]]
def eval(c: Contract): PR[Double] = memo.getOrElseUpdate(c, evalImpl(c))

Except it doesn’t, and the reason is Obs. Look back at part 2:

case Lift[A, B](f: A => B, o: Obs[A]) extends Obs[B]

Lift holds a Scala function. Functions have reference equality, not structural. Two observables built the same way are unequal, so any Contract containing a Scale is unhashable in practice. Obs being higher-order poisons structural equality for the entire Contract type.

The fix is to make observables first-order — symbolic operations instead of embedded functions:

enum Obs[A]:
  case Konst(a: A)
  case TimeObs(t: Date)                          extends Obs[Days]
  case Plus(o1: Obs[Double], o2: Obs[Double])    extends Obs[Double]
  case Times(o1: Obs[Double], o2: Obs[Double])   extends Obs[Double]
  case Negate(o: Obs[Double])                    extends Obs[Double]
  case Libor(k: Currency, m1: Days, m2: Days)    extends Obs[Double]

Now Contract is a first-order algebraic data type all the way down. Structural equality works, hashing works, and the memo table is two lines. Better still, you can now inspect observables — simplify them, print them, compile them, serialise a contract to a database and read it back.

The cost is real and worth stating plainly: you can no longer embed arbitrary Scala functions in an observable. lift(sqrt, o) is gone unless Sqrt is a case. That’s the classic deep-versus-shallow embedding trade — a shallow embedding borrows the host language’s functions and is easy to extend but opaque to analysis; a deep embedding is a closed vocabulary you can take apart.

So I don’t think this solves the paper’s problem so much as dissolve it for the first-order fragment. The general problem — observing sharing in a higher-order embedded DSL — is still open, and Scala’s reference equality (eq, or an IdentityHashMap) is available as an impure escape hatch with all the fragility the authors objected to.

What I’d take away: if you want your DSL to be analysable, keep it first-order. The temptation to let users drop in a host-language lambda is enormous and it costs you every whole-program transformation you might later want. That’s a rule I’d apply well outside finance.

🔗Looking back at the series

Some numbers from the paper. Their Haskell implementation was about 900 lines for a working, limited valuation engine with a COM interface into a commercial risk system. Not as fast as the production C++, but not unbearable: roughly 20 seconds for a contract with 15 sub-contracts over 500 time steps, on a desktop of the year 2000.

And the detail I keep coming back to: despite lacking much functionality, the compositional approach meant it could already value contracts — options over options — that the production system could not. Not because C++ can’t express them, but because the production system was programmed case by case, and the complicated cases were daunting.

That’s the argument for the whole approach, in one observation. Ten primitives and a compositional semantics gave a research prototype capabilities that a mature commercial system, built as a catalogue, didn’t have.

Twenty-five years on, LexiFi is still trading on it.

And the through-line from the algebra series holds here too. This paper is algebra-driven design, done in 2000, in the least likely domain imaginable: find the primitives, refuse to make the convenient thing primitive, give a compositional semantics, prove your identities, and only then pick a numerical method. The Scala 3 translation is mostly frictionless — opaque types for Date, an enum for the contract algebra, LazyList for the processes. The two places it isn’t frictionless were both informative: Numeric couldn’t hold an observable, and LazyList’s memoisation is a trap where Haskell’s laziness is merely a hazard.

Neither is a reason to write Haskell. Both are reasons to know exactly which of your Scala habits are choices and which are consequences.

🔗Sources

  • Peyton Jones, Simon, Jean-Marc Eber & Julian Seward. Composing Contracts: An Adventure in Financial Engineering. ICFP 2000. The lattice representation, the discount recurrence, the slice-list representation of a value process, both arguments for why laziness matters, the sketch of snell, the memoisation problem and the reasons for rejecting a memo function, and the implementation statistics are all theirs.
  • Ho, Thomas & Sang-Bin Lee. Term structure movements and pricing interest rate contingent claims. Journal of Finance, 1986 — the interest rate model.
  • Claessen, Koen & David Sands. Observable sharing for functional circuit description. ASIAN 1999 — the work the paper cites as the only one tackling sharing head-on.
  • Elliott, Conal & Paul Hudak. Functional Reactive Animation. ICFP 1997 — Fran, one of the DSLs where the authors report hitting the same sharing problem.

The Scala 3 translation, the LazyList memoisation warning, and the analysis of how making Obs first-order dissolves the sharing problem for a price are mine.