[ < ] | [ > ] |  | [ << ] | [ Up ] | [ >> ] |  |  |  |  | [Top] | [Contents] | [Index] | [ ? ]

#### 2.7.7.4 Weight

The following virtual code implements a function that returns the weight of its argument in the standard representation for natural numbers.

    weight = ((nil,nil),((nil,nil),(nil,(nil,nil))))

The weight of a tree is zero if the tree is `nil`, and otherwise the sum of the weights of the two subtrees plus one.

An algorithm to compute the weight of a tree would be trivial to implement without being built in to the virtual machine. The built in capability could also be used for purposes unrelated to code maintenance. Nevertheless, it is built in for the following reasons.

- Computing weights happened to be a bottleneck for a particular aspect of code generation that was of interest to the author, namely the compression of generated code.
- A built in implementation in C runs at least an order of magnitude faster than the equivalent implementation in virtual code.
- It runs even faster when repeated on the same data, by retrieving previously calculated weights rather than recalculating them.

The only disadvantage of using this feature instead of implementing a function in virtual code to compute weights is that it relies on native integer arithmetic and could overflow, causing a fatal error. It has never occurred in practice, but is possible due to sharing, whereby the nominal weight of a tree could be exponentially larger than the actual amount of memory occupied by it.

[ < ] | [ > ] |  | [ << ] | [ Up ] | [ >> ] |  |  |  |  | [Top] | [Contents] | [Index] | [ ? ]

This document was generated on November 8, 2012 using texi2html 1.82.