Odin Intro (2 / 3) - Polymorphism

So what is polymorphism exactly? Well, according to Wikipedia, polymorphism allows a value type to assume different types. In practice, this means polymorphism allows the thing to potentially vary in type and behave in different ways. Where otherwise a single thing in code could only be one concrete type or have one behavior, polymorphism allows it to have multiple types or multiple behaviors. Another way to think of it, polymorphism allows us to express that a piece of code or data has variations that are similar but also somehow different. In this sense, polymorphism is a kind of abstraction building beyond what just plain functions and plain data types allow. It's something that gives us additional ways to generalize. Now, how much one should attempt to abstract is a very debatable question, but polymorphism is a useful thing to have in your tool set. In particular, we very commonly need the ability to store heterogeneous data in a collection. And then we also need the ability to operate upon the heterogeneous elements when iterating such collections. In C, for example, we can create an array of pets that may store any kind of pet, whether say a cat or dog. And then when we iterate through the collection, we can perform a common operation on every pet regardless of its concrete type. This is enabled in C either by virtue of cat and dog inheriting from a class pet or by cat and dog implementing an interface pet. Odin, however, lacks inheritance, interfaces, and other common polymorphism related language features. So, we're going to look at how problems like this can be solved in Odin by other means. To start, it's helpful to distinguish between compile time polymorphism and runtime polymorphism. Not only do the implementations differ, they serve quite different purposes. Compile time polymorphism serves two main purposes. Dduplicating code and overloading names. There are five features in Odin that effectively enable compile time polymorphism, procedure groups, parametric polymorphic procedures, parametric polymorphic strcts, parametric polymorphic unions, and the using modifier when applied to strruct fields. The first of these features, procedure groups, very simply are procedures defined not as bodies of code, but rather as lists of other procedures. At compile time, a call to a procedure group dispatches to the procedure in its list, which has the matching call signature. Here, for example, we have a proc group named sleep, which is defined to have two member procedures, sleep cat and sleep dog. When sleep is called with a single cat argument, the call resolves at compile time to sleep cat. when sleep is called with a single dog argument to call resolves at compile time to sleep dog. So procedure groups simply give us the stylistic and organizational convenience of overloading a procedure name allowing us to use one single name at the call sites unlike overloading in other languages. However, we still have to give the individual overloads their own names when we define the overloads. Parametric polymorphic procedures are Odin's semi-equivalent of what other languages call generic functions. An Odin procedure is parametric polymorphic aka parapoly if it has any parameter names or types with dollar sign prefixes. A dollar sign prefix on a parameter name means that the parameter requires a compile time expression passed as argument. In this simple example, we have a proc fu with an int parameter named dollar sign x. When fu is called with an integer literal, that's valid because a literal is a compile time expression. If though we try to call fu with an integer variable, we get a compilation error because a variable is not a compile time expression. Because these compile time arguments are guaranteed fixed at compile time. One thing we can do is use a compile time integer to specify array sizes in the procedure including in the return type. This procedure make array takes a compile time u int which it uses to specify the array size of a local variable r and also the array size of the return type. When we call make array with a value three, it returns an array of size three. But when we call it with a value seven, it returns an array of size seven. Another potential advantage of a compile time parameter value is that the compiler can be smart about evaluating some expressions at compile time. Here the multiplication operation in this procedure can be evaluated at compile time because val is guaranteed fixed at compile time. Note that the compiler may need to generate separate code paths or even wholly separate copies of the procedure for different calls with different compile time arguments. So keep in mind that parapoly procedures can end up increasing the footprint of the generated code. Usually this is not a major concern but it is a trade-off. Anyway, one more use of compile time arguments is probably the most common, but to explain it, we first must introduce a data type that Odin calls type ID. In a compiled Odin program, each unique type is given a unique integer ID called a type ID. We can get the type ID of any type by calling the built-in procedure type ID of. Here we declare a variable T of type type ID and then we assign it the type ID of a bool pointer. Type ids have a number of uses, but probably the most common is as the type of a compile time argument. Here, for instance, this procedure my new takes a compile time type ID expression for its parameter T. Because a compile time type ID expression can be used as a type specification. T can be used where we specify the return type. Plus, we can pass T to these two library procedures, new aligned and align of, which both require compile time type ID arguments. A type specification counts as a valid compile time type ID. So this call here passes the type ID of int and the call then returns an int pointer. In another call to the procedure, we pass the type ID of bool. So the call instead returns a bool pointer. Again, understand that the compiler must generate wholly separate procedure code for these two calls because they operate on wholly different types. When a parameter's type is prefixed with a dollar sign, that indicates that the parameter's type is determined at compile time by the type of the argument at each call site. Here, the procedure repeat 5 takes a single argument with a dollar sign parameter type T, which is used in the body and in the return type. So when we call repeat 5 with boolean argument true, the call returns an array of five booleans in which each element of the array has the value true. If we call repeat five with a string high, then it returns an array of five strings in which each element of the array has the value high. For another example, this procedure clamp has three parameters, all of type dollar sign t. Note, however, that the dollar sign must only be written on the first parameter of type t. Putting dollar signs on the other t parameters would trigger a compilation error. Anyway, if we then call this clamp procedure with three I64 values, it returns the value five as an I64. If instead we call clamp with three F-32 values, it returns the value 5 as an F32. And note that in both cases, we only need to cast the first literal because the compiler can infer from context that the other two literal arguments should match the type of the first. Now be clear that for a parapoly procedure not all input types are necessarily valid. In this case the type t is being used with the less than and greater than operators. So this t must be a type for which these operations are valid. So say calling clamp with boolean arguments triggers a compilation error because a boolean is not a valid operand of less than or greater than. Conversely, calling clamp with string arguments won't cause a compilation error because strings actually are valid operands of the less than and greater than operators, even though the end result isn't really meaningful in this particular procedure. An individual parameter can in fact both require a compile time argument and have a caller determined type. Here's a very artificial example. This procedure array n takes a single parameter having the name dollar sign n and the type dollar sign t. Because the procedure uses n to specify array sizes, any argument for n must be an integer. When we call the procedure with int value 3, it returns a pointer to an array of three ins. When we call the procedure with u8 value 5, it returns a pointer to an array of five u8s. Again, this example is not actually useful, but it does illustrate that an individual parameter can require a compile time argument while also having a caller determined type. In some cases, we may wish to restrict which compile time argument values and which callerdet determined types should be allowed for certain parameters. This is something we can do by adding a wear clause to a procedure. The wear clause takes a compile time boolean expression which is evaluated at compile time for each call of the procedure. And if the expression evaluates false, the call triggers a compilation error. Here, for example, we've added a wear clause to the clamp procedure. The wear is boolean expression uses a procedure from the base library to test if type is numeric. And so now any call to clamp with non-numeric arguments such as strings will trigger a compilation error. Without the wear clause, the compiler would accept strings as valid input for the clamp procedure. But with this wear clause, a call with string arguments triggers a compilation error. Additionally, a parapoly procedure can use syntax called specialization. For the most part, specialization is just shorthand syntax for what you can otherwise express in a wear clause. But unlike a wear clause, specialization can introduce new type parameters. Here the parameter nums has type dollar sign t and the slash after t specifies that t must be a slice type of dollar sign e, which itself is required by the wear clause to be a numeric type. When we call sum, then we're allowed to pass a slice of ins, but passing a slice of booleans or a non-slice type will trigger a compilation error. By the way, E is the conventional name chosen in this situation because it's short for element as in element of the slice. Now, in this case, we actually can express the same thing more directly without specialization. We simply prefix dollar sign T with square brackets instead of using the SL syntax and introducing another type parameter. However, other cases do exist where the specialization syntax is necessary or just clearer to read. What Odin calls a parametric polymorphic strct is a near equivalent of what other languages would call a generic strct or a templated strct in C++. The type parameters are expressed as type ID params with dollar sign prefix names. Just like in a procedure, this indicates the parameters require compile time argument type ids. Here the cat type takes two type parameters T and U where T is used as the type of field A and U is used as the array type of field C. Having declared cat as a parapolstruct, we cannot use plain cat itself as a type. Instead, we must always specify concrete types for T and U. So here first we declare a variable C which has type cat where T is F32 and U is string. And then the second variable declared here C2 has type cat where T is int and U is string. If we attempt to assign one of these variables to the other, we trigger a compilation error because different concretizations of a pair polystruct are different types. This makes sense if you consider that two different concretizations may have completely different types of fields and also then may have completely different sizes. We also get a compilation error if we attempt to use plain cat for a variable type because again plain cat itself is not actually a concrete type. Aside from compile time type ID params, a strruct can also have compile time integer params which can be used to specify sizes of arrays in the strruct. So here now cat has a dollar sign n parameter which specifies the field c array size. Like with the type ids, concretizations with different integer values are considered separate distinct types. So here we still cannot assign variable C2 to C or vice versa. Despite both having the same types for T and U, they have different values for N and thus are not the same type. Like a parapoly procedure, a parapolystruct can also optionally have a wear clause whose boolean expression is evaluated for each concretization at compile time. Here the type cat with integer value six for n is valid because 6 is less than 10. But type cat with integer value 11 for n is invalid because 11 is not less than 10. So what are these parolyrs good for? Well the most obvious use case is for collections. For example, a stack could be defined like so. This parapolstruct stack takes a type ID t so that we can write just one definition for a stack of any kind of element. We then can also define parapoly procedures for the stack operations. When we call this make stack with type int, it returns a stack of ins to which we can push int values with push stack and from which we can remove int values with pop stack. Like strrus unions can also be parametric polymorphic with compile time type ID and integer parameters. Here this union type pet requires type parameters t and u plus an integer parameter n. If we then create a variable p of type pet where t is f32, u is string and n is 4, then the member variants of this concretization are f32 int and arrays of four strings. Thus we can assign say an array of four strings to p. If though we create a second variable P2 of type pet where T is F32, U is string and N is six, then we cannot assign P to P2 or vice versa because they are simply different concrete types. A strruct field which itself is of a strct type can be marked with the reserved word using. This modifier doesn't change the structure of the data at all, but it makes the members of the nested strct directly accessible as if they were fields of the containing strruct itself. Here the catstruct contains a field pet of the petstruct type and this pet field is marked with a using modifier. Consequently, we can access the fields of the pet inside a cat as if they directly belong to the cat as a syntactical shorthand. So the second assignment here is actually just shorthand for the assignment of the prior line. We can also now use a cat value in places where the compiler otherwise expects a pet and the compiler will assume this is shorthand for the pet field. So here the second assignment looks like it's assigning the cat value to the pet variable but actually it is just shorthand for assigning the pet field of the cat to the pet variable with the same effect as the prior line. Similarly, assuming here that procedure feed pet expects a pet argument, we can pass a cat value. But again, this is just shorthand for actually passing the pet field of the cat. So the second call here is really the same as the first. So that covers the features of compile time polymorphism in Odin. You might be unclear though about when you should use these features. So here are some guidelines. Parapoly procedures are useful when you otherwise would have to write multiple versions of the same procedure with all the same code or virtually the same code for different parameter types. In contrast, procedure groups are useful when you have a logically grouped set of operations for different types, but they require significantly different implementations. So whereas parapoly procedures can dduplicate code and effectively spare you work, procedure groups are really just a stylistic organizational affordance for when it makes sense to give a group of procedures a shared name. Another difference to keep in mind is that procedure groups can only be modified by editing the definition. So they cannot be extended by downstream code. In contrast, if we import a parapoly procedure, we can often use that procedure with types that we've defined in our own downstream code. As for parapoly strrus, again the most obvious use cases are collection types. Now you might also be tempted to use parapoly strrus to approximate type inheritance, but this is a bad idea. Instead, the better approach in Odin is to define parent and child types as regular strrus where a child contains its immediate parent. For example, a childstruct cat would have a field to store an instance of its parent struck pet. For parapoly unions, one use case is for maybe result or option types. In fact, Odin's based library actually includes a parapoly union maybe type which effectively represents either a t value or nil. Parap polyuns can also occasionally be useful when a union type needs to include a member variant which is itself a parap polystructure union because then if the member variant requires type parameters, the containing union itself must have type parameters as well. Aside from these cases though, you generally won't see parapoly unions very often. Lastly, the using modifier is really just a small stylistic convenience. If say a catstruct contains a petstruct, it can make sense for the pet field to be marked with using because then a cat can be used where a pet is expected. A cat after all is a kind of pet. Just keep in mind that this is purely a compile time shortorthhand for the pet field itself. Whereas compile time polymorphism enables dduplication of code and overloading of names, runtime polymorphism enables us to have dynamically typed data, including heterogeneous collections, and enables us to operate upon this dynamically typed data. Runtime polymorphism can be achieved in Odin with a few features, unions, untyped pointers, and procedure references, which we'll introduce in a minute. First though, consider the problem of heterogeneous collections, meaning collections that may contain a mix of different types. The preferred way to represent a mixed type collection in Odin is by simply using a union. Here, for example, we have a pet union with two member variants, cat and dog. If we have an array of pets, we can process each element of the array in a loop by using a type switch. If a union's member variant types are large in size and this concerns us, we can store them as pointers in the union instead of storing them directly. Keep in mind though that this added indirection has its own performance cost. And now we must also worry about the lifetimes of the values. Either way, notice that using a union always necessitates type assertions or type switches to use the actual underlying values. Effectively then the set of types in the mixed collection is always fixed when we define the union to allow for truly open mixed collections and more generally to allow for data that is truly dynamically typed. What we need is a way to express extensible interfaces. By interface here we mean a defined set of operations shared by a set of data types. And by extensible we mean that additional data types that implement the interface can be added by downstream code. It's tempting to think that unions can help us implement extensible interfaces, but this simply doesn't work out for reasons I'll demonstrate step by step. First, consider this pattern, which is neither a proper interface nor extensible. Again, we have a union pet with member variants cat and dog, and we've defined respective sleep procedures for both variants plus a sleep procedure group that includes them both. If we then have a pet value and wish to invoke the appropriate sleep procedure for the underlying cat or dog held by that pet, our only choice is to use type assertions or type switch. Consequently, the operation that is common to both cats and dogs, sleep, is not invoked dynamically at all. Yes, we can invoke the procedure group with either a cat or dog argument, but in each case, the compiler resolves which actual procedure to invoke at compile time. In the cat case, P is known to be a cat value. And in the dog case, P is known to be a dog value. To make the invocation actually dynamic, we need procedure references, which are simply what other languages would call function pointers. Here we have a procedure add, which takes two ins and returns an int. We then create a variable f, which is a reference for a procedure taking two ins and returning an int. And because the add procedure has the same signature, it can be assigned by reference to this variable. At runtime, invocation of the procedure reference variable will invoke the procedure that it currently references. So this call here will invoke the ad procedure. So to use procedure references to create an interface, we've now given the cat and dog strrus procedure reference members such that each cat and dog can store a sleep operation. You might expect the cat sleep procedure reference to take a cat argument and the dog sleep procedure reference to take a dog argument. But we need both procedure references to have the same signature. So they both instead take a pet argument. Anyway, we then define procedures to assign to these references. One for cat and one for dog. The sleep cat procedure expects the pet union value to hold a cat, so it does a type assertion for cat. And the sleep dog procedure expects the pet union value to hold a dog, so it does a type assertion for dog. If we then create a dog instance, we make sure to set its sleep field to sleep dog. Unfortunately, this still doesn't really let us make a dynamic invocation because if we store a dog or cat in a pet union, Odin will not let us access the sleep field directly from the union. We still must once again unpack the union value and handle each variant in a separate case. You might think that Odin should automatically recognize that all variants of pet have the same sleep field and then let us access it directly from the union. But that wouldn't work. First, a pet union value may be nil, in which case it has no fields. And second, even if two strrus share a field of the same name and type, there's no guarantee that the fields reside at the same offset within the strruct. So the general rule is that we can never do anything useful with a union value directly. we must always first unpack it with a type assertion or type switch to get the underlying value. This explains one reason unions are unsuitable for extensible interfaces. The other reason is that unions, as we explained before, are not extensible. We simply cannot add additional member variants to a union without editing the definition. And so a union can never be extensible by downstream code. So first, we'll no longer represent our pet interface as a union. Instead, we'll just make it a strct. And we'll also move the sleep fields from cat and dog into pet and give pet one additional field, a raw pointer. This raw pointer is where we'll store a reference to a cat or dog or any other type that implements the pet interface. In the sleepc cat procedure, now we no longer do a type assertion. Instead, we cast the raw pointer into a cat pointer. And in sleep dog, we cast the raw pointer into a dog pointer. Then when we create a pet instance to store a dog, we assign a dog pointer to the data field and we assign the sleep dog procedure to the sleep procedure reference. Finally, now we can invoke the sleep operation of a pet fully dynamically. No type switch required.