Avail - Rich's Blog

Method Overloading and Method Overriding

If you haven't yet had an introduction to methods, I highly recommend reading my previous blog post for a basic introduction before proceeding.

A good way to describe Avail is that it is an operation-oriented language (operations take precedence in Avail). Avail supports objects, however, unlike in object oriented-programming, method definitions are independent of any object. Methods can take objects as input, but they are not subordinate to any object in their definition. This is important as it allows for much greater flexibility when using methods. Two key method features supported by Avail are method overloading as well as method overriding.

At compile time, The parameters' types of any given method defines the behavior dispatched at runtime for any method call (Avail supports multiple dispatch). Though Avail has objects, With respect to methods, objects are treated like any other parameter (like whole number or 5's type). So overloading methods in Avail is simply taking a method and defining different functions based upon the provided parameters' types.

For example, take the method "_fires the_" in the two following calls: Grandma fires the plumber and The submarine fires the torpedoes. The meaning of the word fires implied in a statement is usually based upon the context within which it is used. Grandma is not picking up the plumber and using him as a projectile weapon, nor is the submarine sending the torpedoes to the unemployment line. Though the functionality of "_fires the_" implied for each call here is very different, the implementations of these methods can exist side by side in Avail without ambiguity because of the context in which they are used. That context in the case of Avail are the types of the method's input parameters. In the two examples of our method, "_fires the_", we have the input types [employer, employee] for grandma and the plumber and [weaponized vehicle,projectile] for the submarine and the torpedoes(these different parameter types of the inputs determines the implementation of the method used at runtime).

Overrriding in Avail is defining how a method reaches the desired result based upon the parameter inputs. For example, some sorting algorithms are more efficient at sorting smaller tuples and less efficient at sorting larger tuples. A sorting method can have different implementations for different ranges of tuple sizes using the most efficient sorting algorithms for the given range (you can read more about Avail's tuple types here). I have done this with my implementation of the merge sort algorithm in the Avail library.

At much smaller tuple sizes, it is more efficient to use insertion sort than merge sort due to the overhead of merge sort (here is a nice video on insertion sort put together by the Khan Academy). Because of this, I have created multiple implementations of merge sort as a public method in the Tuples module of the library (a public method is exported for use outside the module). In the implementation of merge sort for tuples with 2 to 10 elements, I have made a call to the private implementation of insertion sort to do the sorting (a private method is not exported and can only be used inside the module it is defined in). My implementation of insertion sort only operates on tuples ranging in size from 2 to 10 elements (the merge sort algorithm is implemented for merge sort calls on tuples of 11 elements or more).

The following is the method definition of insertion sort. As it is only used in cases of tuples of 2 to 10 elements when calls are made to the library's merge sort or quicksort methods, I've only defined it for use of the tuple type of the size range [2..10]. The implementation is fairly simple, so I'll let the inline comments provide the necessary explanations.

For maximal utility of the definition of insertion sort as well as for merge sort, I employed the strategy pattern in order to permit the user of the method call to define the criteria of the sorting order. For example, if I wanted to sort the tuple, <8,7,4,6,3,5,1,2> so that the tuple is sorted first in ascending odd numbers followed by descending even numbers, <1, 3, 5, 7, 8, 6, 4, 2>, then print it to screen, I would use the following call to insertion sort:

/* the tuple to sort */
aTuple : <natural number…|1..8> := <8,7,4,6,3,5,1,2>;

/* a function that accepts as its inputs two natural numbers *
 * and determines the order they come in                     */
comparator :  [natural number, natural number]→boolean :=
[
   n : natural number, m : natural number
 |
   /* n comes before m if n is odd and m is even */
   n is odd ∧ [m is even] ∨
	  /* n comes before m if n and m are odd and n ≤ m */
      [n is odd ∧ [m is odd ∧ [n ≤ m]]] ∨
      /* n comes before m if n and m are even and n ≥ m */
      [n is even ∧ [m is even ∧ [n ≥ m]]]
];

/* insertion sort takes the tuple as the first input and the *
 * comparison function as the second input and returns the   *
 * sorted tuple.  In this case, the size of the tuple is     *
 * exactly 8 elements.                                       */
sorted : <[1..8]…|8> := insertion sort aTuple with comparator;

/* The result is the printing of the tuple result,    *
 * <1, 3, 5, 7, 8, 6, 4, 2>.  The smart quotes are    *
 * used in conjunction with the print statement when  *
 * the input type is not a subtype of the type string */
Print: “sorted”; 

I think that is enough ground covered for method overloading in one blog. When I initially set out, I was also going to discuss merge sort in this post. Part way through writing this post, I decided that merge sort would make a great tutorial. So keep watch for my tutorial on merge sort.

‹ Previous

Return to Rich's Blog