Generic static fields — see you next year

I wanted to make a mental note at the end of 2015 — “feature freeze”. It won’t happen, I cannot make my mind what is the right choice.

The natural decision would be to copycat C# — each constructed type has its own copy of static fields which allows to use generic static fields. Resharper wiki warns about this approach — “in the vast majority of cases, having a static field in a generic type is a sign of an error” ¹. We can find simpler one in Java (more for historical reasons than technical, but still) — it does not support generic static fields and it shares static fields among all constructed types. Scala takes another angle for the same model — since static data can live only in companion objects and they cannot have type parameters the issue is solved by design. As for Swift it is an open question because as the error message says static fields are “not yet supported in generic types”.

C# has some peculiarities — till now I didn’t figure out why C# makes instances of static constructor (see Accelerated C# 2010 by Trey Nash, p.263). Skila would have to add its own because of static variables in generic methods. I feel really insecure here so I wonder whether C# model is worth the effort?

A memento from C++ world:

The original intention of C++ template support envisioned a use-directed automatic instantiation mechanism that required neither user intervention nor multiple instantiations of the same file. This has proved considerably more difficult to achieve than anyone at the time imagined (see [STROUP94]).

— Stanley B.Lippman, Inside the C++ Object Model

Sure, it is not the same issue, over 22 years passed, nevertheless I still have the chills. Until I have firm knowledge or burning desire for this feature I’d better follow Swift footsteps — not supported. Yet.

---

¹ I was curious what “vast majority” means so I contacted the author of that entry, Dmitri Nesteruk. As it turned out it doesn’t translate to any numbers, it was just a generalization based on the nature of C# model.

Advertisement

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.

Two sides of variadic parameters

Until now variadic parameters seemed obvious for me. But consider such code:

stdOut.writeLine("hello","world");
list.append('a','b','c');
let arr = Array<Int>(data:1,2,3);

Looks fine (Skila has also shorter syntax for arrays, similar to Swift). But since all three methods are defined with variadic parameter let’s remove arguments:

stdOut.writeLine();
list.append();
let arr = Array<Int>();

Still technically valid, yet there is something off with the second call — what is the point of appending nothing to the list? I noticed it, however it looked like a corner case at the time, something not perfect but not worth worrying about so I moved on.

But recently I had trouble with overriding methods (Skila does not have explicit overriding, yet). For example with existing constructor for `Array`:

def init(data: T ...)
  // body of the method
end

it is impossible to define default parameterless constructor. The straw was broken — I had to find out the nature of the problem. As it appeared, it is the dual perspective of variadic parameter. One side is what we pass, and the second side is what we get. If we got no data at all from parameter, does it mean user passed empty “bag” of data, or no data at all?

Obviously there are two notions and both need to be reflected in semantics of the language because both are useful — Skila currently supports such definitions as:

// can be called with no arguments
def writeLine<T>(s T ?...) // code goes on
// has to be called with at least one argument
def append(elem T ...) // code goes on

Please notice you can still call `append` with argument having no data in it, but there has to be something between parentheses of the call.

And as a reminder — this feature is not a replacement of variadic limits. For example with only limits, you cannot express `append` as above. Compare:

def append(elem T 1...) 

Such code works the same for explicit arguments, but not for splatted (unpacked) collections:

let a = 5;
let xx = Array<Int>(data:1,2,3);
let yy = Array<Int>();
list.append(a);
list.append(xx/...); // splat operator
list.append(yy/...);

On the last call you will get exception (in run time), because `append` with limits requires on the callee side at least one element of data. Such definition of `append` is not robust for real use.

What is easy — generics with nullable types not for sure

For a week I have been removing features from Skila (so far just two) and postponing some nice things for later implementation — I still want Skila to look at least nicely. Ironically that easy subset is not that easy to grasp, currently I hit hard on nullable types. So far I could see three camps:

• C# — implicit null-check with null values (there are no referential non-nullable types though),
• Kotlin camp — explicit null-check with null values,
• Swift camp — as Kotlin but with wrapper class “Option” instead of null.

Take my words with grain of salt because I don’t know Kotlin or Swift.

Using “null” is not the same as having “Option”, the second can be wrapped as many times as you like when in case of the former you cannot wrap “null” into “null” — it is a value, not a wrapper.

On the other hand all checks designed for nullable type can be applied to non-nullable type, this is not true with optional types. For example one can blindly execute “x != null” check in Kotlin, while the analogous code in Swift requires “x” to be really an “Option”.

Worse, both Kotlin and Swift approaches bring problems to Skila, for example — how do you initialize objects of generic type? If I choose Kotlin solution how does inheritance tree look like for nullable types? And even if I choose Kotlin approach indeed I know that “Option” type will have to be added as well, so maybe add it right from the beginning… and so on and on.

Just to increase my confusion I found out some inconsistency in Kotlin:

open class Foo {
  fun foo() : Int {
    return 0;
  }
}

fun test<T : Foo?>(x : T) : Int {
  return x.foo() // (*)
}

fun main(args : Array<String>) {
  println(test<Foo?>(null))
} 

Compiler should demand “x!!.foo()” in line marked with “(*)”, but the code above compiles without any errors. And it worries me for Skila — those two ideas (generics with nullable/optional types) are not easy and it is hard to foresee (at least for me) all the problems with writing generic classes in practice.

If you are curious you can play online with both languages — playground for Swift and for Kotlin.

Swift — all good names were already taken…

…so we stole this one.

When Google introduced theirs “Go” some (including me) were concerned about similarity with already existing language “Go!”. But try to sue Google over one character. Who can stop rich, right?

Same story with Apple now — they just introduced new programming language called “Swift”. The name, you have to admit, has the striking resemblance with already existing programming language called “Swift”. Hmm, maybe the typeface is changed at least.

So far I just peeked at the basic syntax, and it looks interesting. As always, there is a question if it is good enough to stop developing my own language…