Mythryl generics derive from David MacQueen’s 1990 design for an SML module system. This sparked off a research effort which continues to this day. There is still much that we do not understand about such module systems.
One thing that is reasonably clear is that as a result of this research, we now for the first time have a solid engineering basis for programming in the large. In some ways these module systems are what “object oriented” programming should ideally have been but in practice could not be because we simply did not know enough back in 1967 when OOP originated.
The Mythryl generic package system is best understood as a compile-time language in which the types are APIs, the values are packages, and the functions are generics — entities which take a package as an argument and produce another package as result.
The process of applying a generic package to a package to produce another package is a lot like macro expansion — but well-typed macro expansion with exquisitely carefully worked out semantics. (SML is the only programming language with a fully defined semantics as well as syntax. The benchmark definition is The Definition of Standard ML (Revised) by Milner, Tofte, Harper and MacQueen. Mythryl, which is essentially SML with a Posix face, inherits that semantic clarity and precision.)
Enough verbiage, let’s look at a concrete example. We will define a generic binary tree which can deal with any type of key so long as it is sortable and of course with any type of value.
First we need to define concretely the notion of a sortable key. For our purpose, it consists of some type together with a function which can compare two values of that type and announce whether the first is greater, equal or less than the second.
The Mythryl standard library already defines a type Order which will do nicely. (Re-use is better than re-invention!)
It is defined in src/lib/core/init/order.pkg as:
Order = LESS | EQUAL | GREATER;
With that in hand, we can define the key concept so:
api Key {
Key;
compare: (Key, Key) -> Order;
};
This demands some type Key and a function compare which, given two Keys, returns one of LESS, EQUAL or GREATER. (Actually, I cheated; Key is also part of the Mythryl standard library, as api Key. Never replicate what you can simply steal!)
Now we can define the API for our binary tree implementation:
api Binary_Tree {
exception NOT_FOUND;
package key: Key;
Tree(X); # Tree holding any type of value.
make_tree: Void -> Tree(X);
set_key_value_pair: (Tree(X), key::Key, X) -> Tree(X);
get_key_value: (Tree(X), key::Key) -> X;
};
Here:
To keep things simple, this is very much a toy api definition. (For an industrial-strength example of such an api see the Map api in the Mythryl standard library.)
Now for the fun part. Here is a Mythryl generic package to generate implementations of our Binary_Tree api:
generic package binary_tree_g (k: Key): Binary_Tree where key == k
{
package key = k;
exception NOT_FOUND;
Tree X
= EMPTY
| TREE_NODE { key: key::Key,
value: X,
left_kid: Tree(X),
right_kid: Tree(X)
};
fun make_tree ()
=
EMPTY;
fun set_key_value_pair (EMPTY, key, value)
=>
TREE_NODE { key, value, EMPTY, EMPTY };
set_key_value_pair (TREE_NODE { key=>k, value=>v, left_kid, right_kid }, key, value)
=>
case (key::compare(key, k))
EQUAL => TREE_NODE { key, value, left_kid, right_kid };
LESS => case left_kid
EMPTY => TREE_NODE { key=>k, value=>v, left_kid=> TREE_NODE { key, value, EMPTY, EMPTY }, right_kid };
_ => TREE_NODE { key=>k, value=>v, left_kid=> set_key_value_pair( left_kid, key, value ), right_kid };
esac;
GREATER => case right_kid
EMPTY => TREE_NODE { key=>k, value=>v, left_kid, right_kid=> TREE_NODE { key, value, EMPTY, EMPTY } };
_ => TREE_NODE { key=>k, value=>v, left_kid, right_kid=> set_key_value_pair( right_kid, key, value ) };
esac;
esac;
end;
fun get_key_value (EMPTY, key)
=>
raise exception NOT_FOUND;
get_key_value (TREE_NODE { key=>k, value, left_kid, right_kid }, key)
=>
case (key::compare(key, k))
EQUAL => value;
LESS => get_key_value( left_kid, key );
GREATER => get_key_value( right_kid, key );
esac;
end;
};
Since this tutorial is not about binary trees per se, we will not discuss the binary tree construction and lookup algorithms, which are anyhow very vanilla.
The main thing to note is that the above generic package looks just like a vanilla package declaration except that it takes a k: Key package argument on the first line.
(The alert reader will also have noted the where key == k modifier on the Binary_Tree api reference. This is necessary to specialized the generic package Binary_Tree api definition to the particular key type in use.)
Now we may generate specific binary tree implementations by invoking the generic package with appropriate key package arguments:
package int_key {
Key = int::Int;
compare = int::compare;
};
package binary_tree_with_int_keys
=
binary_tree_g( int_key );
Usually there is no point in actually assigning a name to the argument package, so instead we pass an anonymous package defined on the spot:
package binary_tree_with_int_keys
=
binary_tree_g (
package {
Key = int::Int;
compare = int::compare;
}
);
Put it all together in a test script and it looks like this:
#!/usr/bin/mythryl
api Binary_Tree {
exception NOT_FOUND;
package key: Key;
Tree(X); # Tree holding any type of value.
make_tree: Void -> Tree(X);
set_key_value_pair: (Tree(X), key::Key, X) -> Tree(X);
get_key_value: (Tree(X), key::Key) -> X;
};
generic package binary_tree_g (k: Key): Binary_Tree where key == k
{
package key = k;
exception NOT_FOUND;
Tree X
= EMPTY |
TREE_NODE { key: key::Key,
value: X,
left_kid: Tree(X),
right_kid: Tree(X)
};
fun make_tree () = EMPTY;
fun set_key_value_pair (EMPTY, key, value)
=>
TREE_NODE { key, value, left_kid => EMPTY, right_kid => EMPTY };
set_key_value_pair (TREE_NODE { key=>k, value=>v, left_kid, right_kid }, key, value)
=>
case (key::compare(key, k))
EQUAL => TREE_NODE { key, value, left_kid, right_kid };
LESS => case left_kid
EMPTY => TREE_NODE { key=>k, value=>v, left_kid=> TREE_NODE { key, value, left_kid => EMPTY, right_kid => EMPTY }, right_kid };
_ => TREE_NODE { key=>k, value=>v, left_kid=> set_key_value_pair( left_kid, key, value ), right_kid };
esac;
GREATER => case right_kid
EMPTY => TREE_NODE { key=>k, value=>v, left_kid, right_kid=> TREE_NODE { key, value, left_kid => EMPTY, right_kid => EMPTY } };
_ => TREE_NODE { key=>k, value=>v, left_kid, right_kid=> set_key_value_pair( right_kid, key, value ) };
esac;
esac;
end;
fun get_key_value (EMPTY, key)
=>
raise exception NOT_FOUND;
get_key_value (TREE_NODE { key=>k, value, left_kid, right_kid }, key)
=>
case (key::compare(key, k))
EQUAL => value;
LESS => get_key_value( left_kid, key );
GREATER => get_key_value( right_kid, key );
esac;
end;
};
# Generate a package implementing
# binary trees with Int keys:
#
package binary_tree_with_int_keys
=
binary_tree_g (
package {
Key = int::Int;
compare = int::compare;
}
);
# Define a shorter synonym for the package name:
#
package ti = binary_tree_with_int_keys;
# Create and exercise a binary tree with
# Int keys and String vals:
t = (ti::make_tree ()): ti::Tree(String);
t = ti::set_key_value_pair( t, 1, "one" );
t = ti::set_key_value_pair( t, 2, "two" );
t = ti::set_key_value_pair( t, 3, "three" );
printf "%d -> %s\n" 1 (ti::get_key_value( t, 1 ));
printf "%d -> %s\n" 2 (ti::get_key_value( t, 2 ));
printf "%d -> %s\n" 3 (ti::get_key_value( t, 3 ));
# Create and exercise a binary tree with
# Int keys and Float vals:
t = (ti::make_tree ()): ti::Tree(Float);
t = ti::set_key_value_pair( t, 1, 1.0 );
t = ti::set_key_value_pair( t, 2, 2.0 );
t = ti::set_key_value_pair( t, 3, 3.0 );
printf "%d -> %f\n" 1 (ti::get_key_value( t, 1 ));
printf "%d -> %f\n" 2 (ti::get_key_value( t, 2 ));
printf "%d -> %f\n" 3 (ti::get_key_value( t, 3 ));
# Generate a package implementing
# binary trees with Int keys:
#
package binary_tree_with_string_keys
=
binary_tree_g (
package {
Key = string::String;
compare = string::compare;
}
);
# Define a shorter synonym for the package name:
#
package ts = binary_tree_with_string_keys;
# Create and exercise a binary tree with
# String keys and Int vals:
t = (ts::make_tree ()): ts::Tree(Int);
t = ts::set_key_value_pair( t, "one", 1 );
t = ts::set_key_value_pair( t, "two", 2 );
t = ts::set_key_value_pair( t, "three", 3 );
printf "%s -> %d\n" "one" (ts::get_key_value( t, "one" ));
printf "%s -> %d\n" "two" (ts::get_key_value( t, "two" ));
printf "%s -> %d\n" "three" (ts::get_key_value( t, "three" ));
# Create and exercise a binary tree with
# String keys and Float vals:
t = (ts::make_tree ()): ts::Tree(Float);
t = ts::set_key_value_pair( t, "one", 1.0 );
t = ts::set_key_value_pair( t, "two", 2.0 );
t = ts::set_key_value_pair( t, "three", 3.0 );
printf "%s -> %f\n" "one" (ts::get_key_value( t, "one" ));
printf "%s -> %f\n" "two" (ts::get_key_value( t, "two" ));
printf "%s -> %f\n" "three" (ts::get_key_value( t, "three" ));
Here is a demo run of the script:
linux$ ./my-script
1 -> one
2 -> two
3 -> three
1 -> 1.000000
2 -> 2.000000
3 -> 3.000000
one -> 1
two -> 2
three -> 3
one -> 1.000000
two -> 2.000000
three -> 3.000000
linux$ ./my-script
So there you have it — four different tree varieties from a single code specification. (And, obviously, we could have generated dozens more with negligible additional effort.)
Bottom line: Mythryl generics provide a powerful programming tool for increasing code reusability.
For an industrial-strength version of the above example see src/lib/src/red-black-map-g.pkg.