dtrees

dtrees

Clasp has two implementations of discriminating functions. The first generates Lisp code that can be compiled to produce a regular Lisp function to use as the discriminator. This is presently disabled due to metacircularity difficulties, and even aside from that, is slow enough that it's only useful for very frequently called functions. The other is the "dtree interpreter", described here. Most of the dtree code lives in src/lisp/clos/dtree.lisp; the actual VM is defined in src/core/funcallableInstance.cc.

Basic trees

A dtree (discrimination tree) is a simple tree structure representing the different combinations of arguments encountered by a generic function. For example, say we have a function

(defmethod foo ((a z) (b z)) ...)
(defmethod foo ((a z) (b y)) ...)
(defmethod foo ((a y) (b z)) ...)
(defmethod foo ((a y) (b y)) ...)

Then after all combinations of arguments have appeared, the dtree would basically look like this:

root - Z - Z - method 1
         - Y - method 2
     - Y - Z - method 3
         - Y - method 4

At each level of the tree, we can see what possibilities there are for the corresponding argument. At the first level we see that the argument can be a Z or a Y, and the same for the second level in both branches. If we hadn't seen a call with Y Y before, the dtree under Y would only have a node for Z.

There is an additional wrinkle. If a parameter is not specialized by the generic function, the dtree will generate a special "skip" node corresponding to that parameter. E.g. given

(defmethod bar (a (b z)) ...)
(defmethod bar (a (b y)) ...)

the dtree might look like

root - skip - z - method 1
            - y - method 2

The clos::basic-tree function produces a dtree from a call history and specializer profile.

Outcomes

Each leaf of the tree is an "outcome". Outcomes are representations of the effective method to execute. Usually this is just an effective method function, but for standard reader or writer methods it will be a specialized structure, because standard reads and writes are done without using function calls (e.g. in the dtree VM described below).

Outcomes are used outside of the dtree mechanism as well.

Compiled trees

The above sorts of dtrees are called "basic trees" internally, and they are very easily produced from call histories. When producing a discriminator, the basic tree will be "compiled". The result is another tree (or more generally, DAG) of nodes, but each node represents a much more concrete test. It is at this point that Clasp decides whether testing an object is of a class involves testing tags, testing stamps, or etc. In general it will produce a binary search tree using stamp values.

dtree compilation is performed by the clos::compile-tree-top function.

Bytecode

The compiled tree is then further compiled into actual bytecode. This bytecode runs on a different virtual machine from the Common Lisp VM, because it is very specialized - it needs to perform direct type tests, and it does not need sophisticated control structures (e.g. there are no loops).

The VM is defined in src/lisp/kernel/cmp/bytecode-machines.lisp and implemented in src/core/dtree-interpreter.cc. Briefly, a bytecoded discriminating function consists of a vector of bytes (the code) and a vector of objects (used by the code, containing e.g. effective method functions). There are two registers, ARG and STAMP. Each instruction has zero or more operands, which are the successive bytes in the bytecode. If an instruction is preceded by the long modifier (another byte), each operand is instead two bytes, interpreted as a big-endian integer.

In the below, a dispatch miss means that a novel combination of arguments has been used. This takes us to the slow path, where we add a new entry to the call history, recompute the discriminating function, and call the new function. A higher level description of how our CLOS works is available in src/lisp/kernel/clos/README.

The instructions are as follows:

• farg0 through farg4 retrieve the 1st-5th argument and store it in the ARG register.
• argn n retrieves the nth argument and stores it in the ARG register.
• tag-test fixnum cons single char general dispatches to one of five branches based on the tag of ARG. The tested tags are for fixnums, conses, single floats, characters, and general objects. This is closely tied to the details of Clasp's object representation.
• stamp-read sets the STAMP register to the value of ARG's stamp.
• lt-branch pivoti left branches to left if STAMP is less than the pivot, which is the integer stored in the literal table at index pivoti.
• eq-check pivoti checks if STAMP equals the integer in the literal table at pivoti; if it doesn't, dispatch miss.
• range-check low high checks if STAMP is between (inclusive) the low and high values in the literal table; if it's not, dispatch miss.
• eql obji falseb checks if ARG is eql to the object in the literal table, and if it is, branches to falseb.
• slot-read index slot-name reads the index-th slot of the first parameter to the generic function. If the slot is unbound, slot-unbound is called using the slot-name argument. This is an outcome, i.e. interpretation stops after this.
• slot-write index writes the first parameter into the indexth slot of the second parameter. Also an outcome.
• car cons slot-name reads the value from cons, a literal cons. If it's unbound, slot-unbound is called with the slot-name. This is used to implement slots with :class allocation. Outcome.
• rplaca cons writes the first argument into the car of cons. Also used for class slots. Outcome.
• effective-method-outcome emf calls the effective method function with the arguments passed to the generic function. Outcome.