10.11.8  Generic Packages

Often a package must make an arbitrary choice among a number of available sumtypes. For example, a binary tree needs to know the type of its keys in order to keep the tree sorted, but the logic of the binary tree does not otherwise depend particularly upon the key type.

In such a case, rather than coding up separate versions of the tree for each key type of interest, it is more efficient to define a single generic package which can then be expanded at compiletime to produce the various specialized tree implementations needed.

A generic package is in essence a typed compiletime code macro which accepts a package as argument and returns a package as result:

    api  Key {

        Key;

        compare:  (Key, Key) -> Order;
    };

    generic package binary_tree (k: Key) {

        Binary_Tree
            = LEAF
            | NODE { key:   Key,

                     left_kid:  Binary_Tree,
                     right_kid: Binary_Tree
                   }
            ;

        fun make_tree () = ... ;
        fun insert_tree  (tree: Binary_Tree, key: Key) = ... ;
        fun contains_key (tree: Binary_Tree, key: Key) = ... ;
    };

    package tree_of_ints    = binary_tree (Key = int::Int;       compare = int::compare;);
    package tree_of_floats  = binary_tree (Key = float::Float;   compare = float::compare;);
    package tree_of_strings = binary_tree (Key = string::String; compare = string::compare;);

Here we have defined a single generic package binary_tree which accepts as argument a package containing Key, the type for the trees keys, and compare, the function which compares two keys to see which is greater (or if they are equal). (For expository brevity, we have omitted the bodies of the package functions.)

We have then generated three concrete specializations of this generic package, one each for trees with Int, Float and String keys.

Here the arguments

    (Key = int::Int;       compare = int::compare;)
    (Key = float::Float;   compare = float::compare;)
    (Key = string::String; compare = string::compare;)

define anonymous packages as arguments for the generic package.

(This is not a general syntax for defining anonymous packages; it works only in this specific syntactic context. A general syntax for anonymous packages is to again change the package name to an underbar: package _ { ... }.)

For an industrial-strength example of generic packages in action, see src/lib/src/red-black-set-g.pkg, src/lib/src/string-set.pkg and src/lib/src/string-key.pkg.