Leaving the trenches of the Option<T> type

Please note currently Skila has only reference types (not that it is well thought over decision, I simply don’t have enough time to deal with value types).

The problem how to return data from the function efficiently while fitting in special “no result” value, haunts me for some time. I am aware of several approaches:

1. magic values, like -1 for indices (it is still used, see Go),
2. thin Nullable<T> type to mark there is no result (you can see this in Kotlin),
3. rich Option<T> type for wrapping the actual value (Swift, Scala approach),
4. Try-Parse pattern (for sure it is used in C# libraries).

The first approach is dead simple and fast, yet it is disaster when it comes to serious programming — each time you have to check what magic value you can get. The second approach is much better but it does not scale very well — you can use it for a substring lookup, but it fails with dictionary getter or such functions as first on collection. Yet, the performance is on par with magic values.

For me the only realistic answers are the last two — with Option<T> type you can work with any function, you just add an extra layer of Option<T> to the working type. The performance suffers but you always have fast counterpart functions tryDoSomething. Of course some poor soul has to write all those pairs of functions now — because of that I was seriously considering supporting two types at the same time, lightweight Nullable<T> and rich Option<T>.

Oh yes, there is another approach:

5. communicate failure (like in Icon),

I have no idea what the performance is, but the Icon code is simply beautiful. It was about time to read a book about it — I barely even opened The Implementation of the Icon Programming Language by Ralph E. Griswold and Madge T. Griswold when I found this inspiring passage:

(…) the design of programming languages should not be overly inhibited by perceived implementation problems, since new implementation techniques often can be devised to solve such problems effectively and efficiently.

I am sold — I want beauty, and I want performance! Nothing less. I want stackable (nested) Option<T> type, easy to use with speed of raw null values. Until now I was focusing on optimizing nested Option<T> type, but maybe I could somehow add a stack to null… wait a second.

Let’s consider what happens on the first nesting level (think of Option<T>) — we have either the actual value or a null. On the second level (Option<Option<T>>) — the actual value or a null again. At both levels when we have the actual value we can recognize that we didn’t end up with no result because our reference is not equal to null. It is the null which has to be wrapped (because null from the first level of nesting plays a role of true data on the second level), the real, actual value does not need any wrapping. It is some progress but we still have to do a little wrapping, right? No, we don’t — just turn the microscope on and take a look. In the first case the failure is indicated by null¹, in the second case by another, different null — null².

Click, click, click — do you hear this sound?

Option<T> type. Who said it is a regular type in the first place? It does not have to be — our Option<Option<T>> is a disjoint union of types. It is Null² type, or Null¹ type, or T type — Null²|Null¹|T.

Because we have to tell compiler what type we would like to get, it knows at what level it operates — i.e. how many layers it should pretend unwrapping to get the value. If it is any of the null value cases, it will also know how long it should pretend it has real data — the show with single null keyword is just for the user. Say the pointer is set to null¹ and our current type is Option<Option<String>> — do we have real value? Sure thing, it is not null² and that’s all we have to care about.

Thanks to all those lies there is no wrapping values in the runtime, the speed is the same as working with plain old null values. The only difference comparing to rich Option<T> school is with down casting — we will be able to tell what type we hold in hand (String for example), but we will not be able to deduce what union of types it comes from (Null¹|String or maybe Null²|Null¹|String).

Could it be this cookie is absolutely for free? Unfortunately — no. Union types does not work well with generic types (at least if you want to keep static control over types), but since we have here very specific case of union we can enrich type info with option counter. Whenever there is Option<T> type used we have to take option counter from type T and increment it.

This leaves me a syntax to think about and supporting three valued logic to consider — this could add an interesting twist to the language.

Advertisement

Teaching the interfaces new tricks

Probably I am the worst person when it comes to shipping the product — once I’ve got a clever idea, I simply cannot wait to implement it. Around 2 weeks ago I found out how object initialization should be done in Skila, and from that moment new ideas couldn’t stop flowing into my mind. Reading books and blogs only worsens the situation.

Skila can already have an internal field for a property:

def myProperty Int
  var field Int; // visible only inside the property
  get return field;
  set field = value;
end

because the lack of such feature was bugging me for a long time in C#. But why stop here when you can bring even more control — defects allowed by imprecise access modifiers.

You can implement interface methods as in Java 8, but after browsing “The D Programming Language” I found out extreme version of Non-Virtual Interface pattern. Private, overridable, yet not accessible to outer world methods of the interface (example is taken from the book and translated to Skila):

interface Transmogrifier
  private def transmogrify();
  private def untransmogrify();

  final def thereAndBack()
    transmogrify();
    untransmogrify();
  end
end

You have to implement the two first methods when deriving this interface, however you even cannot call your own implementation. I hope you feel how it all clicks together — I don’t have the entire picture of the solution yet, but no worries, I am a patient man.

“CLR via C#” brought its own ideas — I used mainly suggestions related to inheritance, classes are final in Skila by default, even if you unseal the class, its methods are still final by default. You really have to make some effort and bring a bigger hammer to turn on virtual gear. I even found a good name to denote unsealing a class (around one week of munching on just a single term — I know, I know) — it’s… “base class”! As you can see no keyword was harmed.

All that work was great opportunity to make some polishing on my own — for example instead of forcing constructor to call only some previous one (as in Scala) I detect recursive loops. Another safety belt — either you call the base method or you state breaking the chain of the override calls:

class SomeInheritance : BaseType
  override def breakChains()
    super break;
  end
  override def callBase()
    super();
  end
end

There are more such minor improvements, but those are nothing compared to the object initialization I devised — I will describe it next time, I have to fine tune some details. I will leave you today with nicely refreshing thought from “Framework Design Guidelines” (yes, I am reading non-stop):

I’ve never been a big fan of choosing performance over ease of use (performance gets better over time; ease of use doesn’t).

— Brian Pepin