Welcome back.

This week, some content from my book (which, as I announced last week, is now available as an ebook from Leanpub; thanks to all those who bought it so far). This post is the first part of a series that will describe the QuantLib tree framework.

But first, some news: with the help and organization of the good Jacob Bettany from MoneyScience, I’ll hold a new edition of my Introduction to QuantLib Development course. It’s an intensive three-day course in which I explain the architecture of the library and guide attendees through exercises that let them build new financial instruments based on the frameworks I describe. It will be in London from June 29th to July 1st, and you can find more info and a brochure at this link. An early-bird discount is available until April 30th.

Subscribe to my Substack to receive my posts in your inbox, or follow me on Twitter or LinkedIn if you want to be notified of new posts, or subscribe via RSS if you’re the tech type: the buttons for all that are in the footer. Also, I’m available for training, both online and (when possible) on-site: visit my Training page for more information.

The tree framework

Together with Monte Carlo simulations, trees are among the most commonly used tools in quantitative finance. As usual, the dual challenge for a framework is to implement a number of reusable (and possibly composable) pieces and to provide customization hooks for injecting new behavior. The QuantLib tree framework has gone through a few revisions, and the current version is a combination of object-oriented and generic programming that does the job without losing too much performance in the process.

The Lattice and DiscretizedAsset classes

The two main classes of the framework are the Lattice and DiscretizedAsset classes. In our intentions, the Lattice class (shown in the listing below) was to model the generic concept of a discrete lattice, which might have been a tree as well as a finite-difference grid. This never happened; the finite-difference framework went its separate way and is unlikely to come back any time soon. However, the initial design helped keeping the Lattice class clean: to this day, it contains almost no implementation details and is not tied to trees.

    class Lattice {
      public:
        Lattice(const TimeGrid& timeGrid) : t_(timeGrid) {}
        virtual ~Lattice() {}

        const TimeGrid& timeGrid() const { return t_; }

        virtual void initialize(DiscretizedAsset&,
                                Time time) const = 0;
        virtual void rollback(DiscretizedAsset&,
                              Time to) const = 0;
        virtual void partialRollback(DiscretizedAsset&,
                                     Time to) const = 0;
        virtual Real presentValue(DiscretizedAsset&) const = 0;

        virtual Disposable<Array> grid(Time) const = 0;
      protected:
        TimeGrid t_;
    };

Its constructor takes a TimeGrid instance and stores it (its only concession to implementation inheritance, together with an inspector that returns the time grid). All other methods are pure virtual. The initialize method must set up a discretized asset so that it can be put on the lattice at a given time. (I do realize this is mostly hand-waving right now. It will become clear as soon as we get to a concrete lattice.) The rollback and partialRollback methods roll the asset backwards in time on the lattice down to the desired time (with a difference I’ll explain later); and the presentValue method returns what its name says.

Finally, the grid method returns the values of the discretized quantity underlying the lattice. This is a bit of a smell. The information was required in other parts of the library, and we didn’t have any better solution. However, this method has obvious shortcomings. On the one hand, it constrains the return type, which either leaks implementation or forces a type conversion; and on the other hand, it simply makes no sense when the lattice has more than one factor, since the grid should be a matrix or a cube in that case. In fact, two-factor lattices implement it by having it throw an exception. All in all, this method is up for some serious improvement in future versions of the library.

The DiscretizedAsset class is the base class for the other side of the tree framework—the Costello to Lattice’s Abbott, as it were. It models an asset that can be priced on a lattice: it works hand in hand with the Lattice class to provide generic behavior, and has hooks that derived classes can use to add behavior specific to the instrument they implement.

As can be seen from the listing below, it’s not nearly as abstract as the Lattice class. Most of its methods are concrete, with a few virtual ones that use the Template Method pattern to inject behavior.

    class DiscretizedAsset {
      public:
        DiscretizedAsset()
        : latestPreAdjustment_(QL_MAX_REAL),
          latestPostAdjustment_(QL_MAX_REAL) {}
        virtual ~DiscretizedAsset() {}

        Time time() const { return time_; }
        Time& time() { return time_; }
        const Array& values() const { return values_; }
        Array& values() { return values_; }
        const shared_ptr<Lattice>& method() const {
            return method_;
        }

        void initialize(const shared_ptr<Lattice>&,
                        Time t) {
            method_ = method;
            method_->initialize(*this, t);
        }
        void rollback(Time to) {
            method_->rollback(*this, to);
        }
        void partialRollback(Time to)  {
            method_->partialRollback(*this, to);
        }
        Real presentValue() {
            return method_->presentValue(*this);
        }

        virtual void reset(Size size) = 0;
        void preAdjustValues() {
            if (!close_enough(time(),latestPreAdjustment_)) {
                preAdjustValuesImpl();
                latestPreAdjustment_ = time();
            }
        }
        void postAdjustValues() {
            if (!close_enough(time(),latestPostAdjustment_)) {
                postAdjustValuesImpl();
                latestPostAdjustment_ = time();
            }
        }
        void adjustValues() {
            preAdjustValues();
            postAdjustValues();
        }

        virtual std::vector<Time> mandatoryTimes() const = 0;

      protected:
        bool isOnTime(Time t) const {
            const TimeGrid& grid = method()->timeGrid();
            return close_enough(grid[grid.index(t)],time());
        }
        virtual void preAdjustValuesImpl() {}
        virtual void postAdjustValuesImpl() {}

        Time time_;
        Time latestPreAdjustment_, latestPostAdjustment_;
        Array values_;

      private:
        shared_ptr<Lattice> method_;
    };

Its constructor takes no argument, but initializes a couple of internal variables. The main inspectors return the data comprising its state, namely, the time \( t \) of the lattice nodes currently occupied by the asset and its values on the same nodes; both inspectors give both read and write access to the data to allow the lattice implementation to modify them. A read-only inspector returns the lattice on which the asset is being priced.

The next bunch of methods implements the common behavior that is inherited by derived classes and provide the interface to be called by client code. The body of a tree-based engine will usually contain something like the following after instantiating the tree and the discretized asset:

    asset.initialize(lattice, T);
    asset.rollback(t0);
    results_.value = asset.presentValue();

The initialize method stores the lattice that will be used for pricing and sets the initial values of the asset (or rather its final values, since the time T passed at initialization is the maturity time); the rollback method rolls the asset backwards on the lattice until the time t0; and the presentValue method extracts the value of the asset as a single number.

The three method calls above seem simple, but their implementation triggers a good deal of behavior in both the asset and the lattice and involves most of the other methods of DiscretizedAsset as well as those of Lattice. The interplay between the two classes is not nearly as funny as Who’s on First, but it’s almost as complex to follow; thus, you might want to refer to the sequence diagram shown below.

lattice sequence diagram

The initialize method sets the calculation up by placing the asset on the lattice at its maturity time (the asset’s, I mean) and preparing it for rollback. This means that on the one hand, the vector holding the asset values on each lattice node must be dimensioned correctly; and on the other hand, that it must be filled with the correct values. Like most of the DiscretizedAsset methods, initialize does this by delegating part of the actual work to the passed lattice; after storing it in the corresponding data member, it simply calls the lattice’s initialize method passing the maturity time and the asset itself.

Now, the Lattice class doesn’t implement initialize, which is left as purely virtual; but any sensible implementation in derived classes will do the dance shown in the sequence diagram. It might perform some housekeeping step of its own, not shown here; but first, it will determine the size of the lattice at the maturity time (that is, the number of nodes) probably by calling a corresponding method; then, it will store the time into the asset (as you remember, the asset provides read/write access to its state) and pass the size to the asset’s reset method. The latter, implemented in derived classes, will resize the vector of values accordingly and fill it with instrument-specific values (for instance, a bond might store its redemption and the final coupon, if any).

Next is the rollback method. Again, it calls the corresponding method in the Lattice class, which performs the heavy-machinery work of stepping through the tree (or whatever kind of lattice it models). It reads the current time from the asset, so it knows on what nodes it is currently sitting; then, a close interplay begins.

The point is, the lattice can’t simply roll the asset back to the desired time, since there might be all kind of events occurring: coupon payments, exercises, you name it. Therefore, it just rolls it back one short step, modifies the asset values accordingly—which includes both combining nodes and discounting—and then pauses to ask the asset if there’s anything that needs to be done; that is, to call the asset’s adjustValues method.

The adjustment is done in two steps, calling first the preAdjustValues and then the postAdjustValue method. This is done so that other assets have a chance to perform their own adjustment between the two; I’ll show an example of this in a later post. Each of the two methods performs a bit of housekeeping (namely, they store the time of the latest adjustment so that the asset is not adjusted twice at the same time; this might happen when composing assets, and would obviously wreak havoc on the results) and then calls a virtual method (preAdjustValuesImpl or postAdjustValueImpl, respectively) which makes the instrument-specific adjustments.

When this is done, the ball is back in the lattice’s field. The lattice rolls back another short step, and the whole thing repeats again and again until the assets reaches the required time.

Finally, the presentValue method returns, well, the present value of the asset. It is meant to be called by client code after rolling the asset back to the earliest interesting time—that is, to the time for which further rolling back to today’s date only involves discounting and not adjustments of any kind: e.g., it might be the earliest exercise time of an option or the first coupon time of a bond. As usual, the asset delegates the calculation by passing itself to the lattice’s presentValue method; a given lattice implementation might simply roll the asset back to the present time (if it isn’t already there, of course) and read its value from the root node, whereas another lattice might be able to take a shortcut and calculate the present value as a function of the values on the nodes at the current time.

As usual, there’s room for improvement. Some of the steps are left as an implicit requirement; for instance, the fact that the lattice’s initialize method should call the asset’s reset method, or that reset must resize the array stored in the asset (in hindsight, the array should be resized in the lattice’s initialize method before calling reset. This would minimize repetition, since we’ll write many more assets than lattices.) However, this is what we have at this time. In next post, we’ll move on and build some assets.