Suppose we want to write a library function which accepts a tuple of two strings and returns a tuple containing those two strings in reverse order:
api Swap_Lib {
swap_strings: (String, String) -> (String, String);
};
package swap_lib: Swap_Lib {
fun swap_strings (a, b) = (b, a);
};
After hours of debugging we get it working, and are so excited by the new horizons thus opened up that we immediately want the same thing for integers:
api Swap_Lib {
swap_strings: (String, String) -> (String, String);
swap_ints: (Int, Int) -> (Int, Int);
};
package swap_lib: Swap_Lib {
fun swap_strings (a, b) = (b, a);
fun swap_ints (a, b) = (b, a);
};
Wow! How about floats?
api Swap_Lib {
swap_strings: (String, String) -> (String, String);
swap_ints: (Int, Int) -> (Int, Int);
swap_floats: (Float, Float) -> (Float, Float);
};
package swap_lib: Swap_Lib {
fun swap_strings (a, b) = (b, a);
fun swap_ints (a, b) = (b, a);
fun swap_floats (a, b) = (b, a);
};
This is so much fun! Let’s do all the types!
Um, wait. There are an infinite number of possible types in Mythryl. We could be at this a really, really long time.
Furthermore, the code generated by the Mythryl compiler for each of our functions is exactly the same; it doesn’t actually depend on the types of the arguments at all.
Why cannot we just write one generic swap function and be done with it?
In a language like C, there is no way to do this. At least, no typesafe way: The C type system is not rich enough to have a representation for the any type here concept. (Although void* works as a weak approximation.)
In practice, C programmers at this point would simply bypass the type system by casting all arguments to void on input and casting them back again on output. In short, by lying to the C compiler because it is just too dumb to do the job otherwise.
The Mythryl type system is considerably more subtle. In Mythryl, we can actually do this right:
api Swap_Lib {
swap: (X, X) -> (X, X);
};
package swap_lib: Swap_Lib {
fun swap (a, b) = (b, a);
};
Here the X identifiers introduce a match-anything type variable.
Type variables do for type declarations what parameter variables do for function declarations: They let us talk concretely about arbitrary members drawn from a large class of possibilities. In a declaration like
fun double x = 2.0 * x;
the x lets us refer to any possible floating number which may become relevant during later processing. In a declaration like
swap: (X, X) -> (X, X);
the X lets us refer to any possible type which may become relevant during later processing.
In Mythryl any identifier consisting of a single uppercase character is a type variable:
A
B
C
...
X
Y
Z
For the (rare) cases where more semantic content is desirable, Mythryl also supports type variable names beginning with such a lone uppercase letter and then followed by an underbar and a lower-case identifier:
A_sorted_type
Z_best_type_available
...
Returning to our swap-library example, here is a wet run:
linux$ my
eval: api Swap_Lib { swap: (X, X) -> (X, X); };
eval: package swap_lib: Swap_Lib { fun swap (a, b) = (b, a); };
eval: swap_lib::swap( 1, 2 );
(2, 1)
eval: swap_lib::swap( "abc", "def" );
("def", "abc")
eval: swap_lib::swap( 1.23, 3.21 );
(3.21, 1.23)
In fact we can do even better and allow swapping not just any two-tuple of two values of the same type, but any two-tuple whatever:
api Swap_Lib {
swap: (X, Y) -> (Y, X);
};
package swap_lib: Swap_Lib {
fun swap (a, b) = (b, a);
};
Here the X and Y type variables can match different types.
Here is the improved version in action:
linux$ my
eval: api Swap_Lib { swap: (X, Y) -> (Y, X); };
eval: package swap_lib: Swap_Lib { fun swap (a, b) = (b, a); };
eval: swap_lib::swap( 1, "one" );
("one", 1)
eval: swap_lib::swap( 2, ("one", { name => "Johnny", age => 21 } ) );
(("one", { age=21, name="Johnny" }), 2)
Type variables open up whole new worlds of expressiveness in programming.
There are many, many datastructures in which the code really does not care what type is in a given slot.
For example, binary trees usually care about the types of node keys, because they have to know how to compare them for order, but they usually do not care at all about the types of node values, because they just store them on request and then produce them upon demand.
In a language like C, binary tree implementations have to specify a type for such node values anyhow, greatly reducing code reusability, but in Mythryl we can — and do — write them in fully general form:
Tree(X) = EMPTY
| NODE { key: Float, value: X, left_kid: Tree, right_kid: Tree };
Here Tree(X) is essentially a compile-time type function which takes a type as argument and returns a new type as its result. These type functions are usually called type constructors, often truncated to typ.
For example, we can now start writing api declarations like
sum_integer_valued_tree: Tree(Int) -> Int;
Here Tree(Int) is a new type defined in terms of existing ones.
Sometimes, of course, we may be able to build new datastructures out of Tree(X) without needing to reduce its generality. For example, maybe we have a type which is allowed to hold any pair of trees so long as they are of the same type:
Tree_Pair(X) = (Tree(X), Tree(X));
The one real lack of generality in the above Tree definition is that its key type is hardwired. If we want a binary tree with integer keys, we need to write another declaration. Ditto if we want a binary tree with string keys.
We cannot abstract away from key type by using a type variable because the binary tree implemention actually does care about key type; it has to know how to compare keys in order to keep the tree sorted.
Thus, in order to write a single generic version of binary tree, we need a bigger bat. That bat is the Mythryl generic package, which is the subject of the next section.