15.3.1.3 Sealing rib objects

A non–empty rib can be “sealed” once all bindings are inserted. This happens every time a syntax creates a lexical contour with a number of syntactic bindings that is immediately known; examples are: lambda, let and its variants.

To seal a rib, we convert the lists name*, mark** and label* to vectors and insert a frequency vector in the sealed/freq field.

The frequency vector is a Scheme vector of fixnums: an optimisation that allows the rib to reorganise itself by moving frequently used tuples towards the beginning of the vectors. This is possible because the order in which the tuples appear in a rib does not matter.

Let’s see how it works. An unsealed rib holding two syntactic bindings with source names ‘a’ and ‘b’ and the src mark, looks as follows:

name*       = (b       a)
mark**      = ((src)   (src))
label*      = (lab.b   lab.a)
sealed/freq = #f

and right after sealing it:

name*       = #(b       a)
mark**      = #((src)   (src))
label*      = #(lab.b   lab.a)
sealed/freq = #(0       0)

the access frequencies in the sealed/freq field are initialised to zero; after accessing once the binding of ‘b’ in the sealed rib, its frequency is incremented:

name*       = #(b       a)
mark**      = #((src)   (src))
label*      = #(lab.b   lab.a)
sealed/freq = #(1       0)

and after accessing twice the binding of ‘a’ in the sealed rib, the tuples are swapped:

name*       = #(a       b)
mark**      = #((src)   (src))
label*      = #(lab.a   lab.b)
sealed/freq = #(2       1)

Let’s see what happens when there are multiple syntactic bindings with the same access frequency. If the scenario before the access is:

name*       = #(f e d c b a)
sealed/freq = #(1 1 1 0 0 0)

and we access a: first we want the tuple of a to be moved in the leftmost position in the group of tuples with frequency equal to zero:

name*       = #(f e d a b c)
sealed/freq = #(1 1 1 0 0 0)

we do this by swapping tuples in the vectors, in this case we swap the tuple of a with the tuple of c; then we increment its access frequency, the scenario after the access is:

name*       = #(f e d a b c)
sealed/freq = #(1 1 1 1 0 0)