Lifetime crisis

This is one of such embarrassing moments when I have to admit that because of lack of proper design I fell into trouble. I’ve been recently working on adding lifetime checks to Skila and I found more problems than expected.

let iter = coll.getIterator();

This benign piece killed the idea of not adding any new features — I already have pointers and references, but since collection can be on stack or on heap I would need to add something in between. A pointer with limited lifetime — this way I could tie up coll with iter — if it is regular pointer with global lifetime, go ahead be global. But if not — iterator needs to be local.

Or I could perform boxing on fly… C# has this feature and I hate it — it is difficult to see with naked eye performance offending code.

let elem = coll[index];
coll.clear();

I use references with indexer so this would lead to cherished undefined behavior. The easiest way would be to change semantics and working with values, two other approaches would require reworking entire language — I could go Rust way with ownership or functional way with immutable data (collection could not be altered, thus all references would be guaranteed to be valid).

foreach (let elem in coll)
  coll.clear();

Here Rust simply shines detecting the problem in compile time. This is the least problematic piece though, because one way or another it will always work correctly, maybe only surprisingly.

Honestly those problems undermine entire Skila existence — I wanted to get easy, likeable yet performant language. And I don’t see it on the horizon.

Advertisement

Strings — performance hurts

I barely have time to write what happens with Skila but this one is so off I cannot resist — strings. Wide Unicode or UTF-8? The latter right, because they take less space so they require less fetches from the memory. How do we index them? By character or by byte? The former will not give us constant time thus by byte.

I know there are currently languages going this path — like Rust or Julia — but I don’t feel comfortable with it. For one, there is no abstraction layer here, the implementation details leak right into API. Secondly it forbids having common IString interface with UnicodeString because it would be indexed differently. Oh boy…

This choice even pushed me to a strange at first glance decision for having reverse methods lastIndexOf starting from exclusive index rather than inclusive. Oddly this is somewhat in sync with ranges (inclusive to exclusive).

UTF-8 string, where will you lead me…?

Skila3 — starting again…

Well, the first Skila attempt is dead and maybe luckily so. The compiler was way too slow (it needed for entire testsuite around 40 minutes) and I tried to fix it, then to start from scratch but I stopped the work — the design of the language itself was doomed to fail from the beginning. You simply cannot ignore performance of the language (not compiler) itself — in C# if you rely on exceptions instead of methods TryXXX you can face x220 slowdown. In Python if you use regular arrays you will soon hear “use NumPy instead”, in JS if you need speed you have to shove your code into GPU (“ConvNet.js is great but it is written in JS, so now we have DeepLearn.js…”). It is the same story no matter what the language is.

And so on the 28th of December, 2016 I started Skila3, initially as only a good-bye exercise in type matching. In time the work gained some speed as I added more features.

This time I dropped parser, at this point it is only a distraction. This decision allowed me to gain a new perspective — why not treat semantic analyser and code generator as engine, and parser as exchangeable skin? Something like C# and VB for .Net but on different level.

Anyway, syntax is so ahead of me that I don’t think about it at all. As for the old code, instead of refactoring it I started clean, I don’t even bring it in pieces. Currently I have rough basics — notion of deep immutability, conditionals, loops, generics, concurrency and channels (as in Go). A lot of ideas from initial Skila wait for being brought to this new project.

To speed working on compiler at first I wrote interpreter instead to check whether I can add numbers together, and well — I can.

The code is more straightforward than before — there two passes of computation, evaluation and validation. The former does name binding, computes the types of the expressions and so on, the latter one checks whether the outcomes of the expressions are read or whether the variables are assigned before they are used. I put the code at GitHub, so take a look at spare time.

Starting over with errors

Current state

It didn’t take me long to realize I simply hate working with Option type as a replacement of exceptions — instead of simply writing the code I have to babysit each possible failing function and write conditions for each optional value (I am not the only one in pain). So I read again about Java, C#, Haskell, OCaml and Rust (did you notice Rust team introduced subtle flaw in design — in Haskell and OCaml the correct outcome of the function is the right outcome. In Rust it is on the left, so the right answer is the erroneous answer). I can sum this up as follows:

• C# approach is a dead end because it leads to duplicating functions — dreadful Do and TryDo pattern,
• Java annotated functions with exceptions that can be thrown and passed was a mistake, it only takes few minutes of writing the code to feel tired. And for unchecked exceptions it shares the same problem as C#,
• Haskell looked promising until I saw the real code tackling the errors — so partially I would be in camp I want to escape from already (Skila), and partially in heavy function annotating camp which I dislike since my Java experience. Also I am sceptical how smooth this solution is when it comes to inheritance and when you read “Error handling” chapter (from Real World Haskell by Bryan O’Sullivan, John Goerzen, Don Stewart) you might get the impression that something is fishy, if one feature kills another feature and you need to jump extra hoops to use both.

I have wrong design (more in artistic sense) and three approaches which, well, I don’t like.

I could agree with the sentence “if you don’t have anything right to say, or anything that moves the art forward, then you’d better just be completely silent and neutral, as opposed to trying to lay out a framework” (from interview with Anders Hejlsberg) but not in this case — working on and implementing the language which is broken from start is no fun, and has no value at all. I must make a second, third — fourth if necessary — try to find out the solution. After all it has to be somewhere.

Envisioned design

Skila will have exceptions but they will be thrown usually by code injected by compiler. All errors in computations should be signalled by:

• optional value — if it is likely that user will handle the error. It is counterpart of function that requires its outcome to be read. As an example consider String.indexOf — not finding character in string could lead to an error, but it is rather not an error by itself,
• Error type — here the situation is reversed, it is more likely that the “client” would treat an error like a serious computation failure and pass it for handling to some upper function, it is counterpart of the function that allows its outcome to be ignored. Every unhandled error is automatically converted to exception. Error type will be subtype of any other type, so returning an Error instead of “real” value does not need to (and cannot?) be annotated in function signature. In other words every function can fail.

You can convert optional value to exception (this is already done), you can convert error to exception or to optional value. The beauty I foresee is present in several aspects:

• it is transparent to inheritance,
• it should not clash with any other feature,
• single function will be enough,
• the flow of the errors is layered,
• no extra code necessary — you want to cope with errors, you do it, you don‘t want to — simply behave naturally (as with exceptions).

What is layered flow of errors? By default, the function you talk directly to could give you an error, but all third party functions involved in computation can result in exception (because every unhandled error becomes an exception). You could depict such propagation in default flow:

deep function ⟶ nearby function ⟶ your function
  (error)      |                  |
               |     (error)      |
               |   (exception)    |
               |                  |   (exception)

In the first line you see deep function returns an error. The error is passed to the nearby function (line 2), since it is incoming error and it is unhandled it becomes an exception (line 3), it is then “passed” to your function. In more real life perspective, when you call for example dict[key] (nearby function) for non existing key you will get error and you can handle the error right away. But if the failure is caused because there is a some logging (deep function) involved, and that logging failed, you will get an exception, not an error.

Again, this is the default flow — every function can handle the values it gets and convert them to whatever necessary.

Problems

Entire mechanism is very similar to passing null in C# — in Skila it will be done on purpose, as a bait. But there is difference — in C# you can pass null without triggering exception, in Skila even passing has to be checked. This is for easier finding the source of the error and also to consistently process all the functions including those which work for their side effects (all Void functions are prime examples). So performance can be a victim here.

The handy, the needed, the dangerous

I recently dug up an old topic on Programmers SE — “Why do so many languages restrict string literals to a single source line?” and it provoked me to go through various programming languages. I liked Ceylon approach so much that I immediately implemented it as well. With a little twist — when the opening line is effectively empty it is removed and the base column is set to zero. Such code:

s String = "
            Hello
            World";

is equivalent to:

s String = "            Hello\n            World";

After reading Groovy in Action, 2ed. by Dierk König, Paul King, et al. I appreciated (again) the ability to drop parentheses on function call. Since I just removed / operator for Int I thought it was a great opportunity to implement it, which let mod and div methods to be called as operators:

x = a div b;

Nice, isn’t it? The moment I wrote the first piece of code using new syntax I realized it is a bug mine. Consider such code:

x = a div b + c;
x = a mod b ^ c;

Do you know the precedence by heart? That is why this feature was short-lived. But the next one, also taken from Groovy is a must — power asserts. I planned to implement it a bit later, but since now I am writing bunch of real (i.e. executable) test cases for Skila and for the n-th time I hit old plain assert I decided — enough. I need this tool, and I need it for yesterday. Since I don’t have any keystroke to spare, please excuse me, I am heading back to Skila…

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.

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

Self type and pinned spiral

It is amazing how different ideas can all of the sudden click and create one coherent blueprint for a cool feature. Yes, I know, I should be doing generator — but this is exactly where the problem began.

Here is how it went — I was implementing rich `Iterable` interface and stumbled on `concat` method. On the first glance it is obvious — it takes another `Iterable` and also returns `Iterable`, no problem. But think about using it — when you have some arbitrary `Iterable` it works as expected, but if you have for example `String`… Do you really expect to concatenate two strings and get some `Iterable` in result?

OK, so let’s make a correction ¹ — the outcome should be `Self`. It will work perfectly with `String`, we can also define `prepend` and `append`. But… wait a second, `Set` is `Iterable` as well, right? How can you prepend anything to a set and get a set back? If you don’t see a problem — you can add something to set, but not concatenate sets, or append anything to it, because except for one special case, set is not a sequence (there is no order in a set).

I found a solution, it waits right now for implementation (I needed a break from coding, thus this post) — `Set` is not an `Iterable`, it can be treated as one (thanks to implicit conversion) — subtle difference, but making things consistent. You can call `append` on `String` and get back a `String` and at the same time you can `append` on `Set` and get an `Iterable`, because it will be silently converted to this type on call.

Implicit conversions were easy — they are just a parameterless methods overloaded on result type. In Skila with “have to read the result of the function” feature it simply fitted right in.

One thing was still missing — how can you ensure that regular method returns `Self` type? You can track whether the returned value is really pure `Self`, but sometimes you don’t work with `Self` type in the first place. The only alternative would be relying on the fact that every descendant type will override such method and produce its own type, making effectively given method a factory of `Self`. And this concept was already present in Skila — `pinned` regular methods waited long for such cause, but now it is done. So either you write one general method with `Self` or you will guarantee with `pinned` every type will have its own implementation.

---

¹ If I am not mistaken, Scala solves similar kind of problems with what-can-build-what types. This part seems too convoluted for me so I even didn’t dig deeper.

Hello world! — finally

It sounds funny but for me it is a historic moment — today I compiled Skila program and it was successfully executed. As the title says it is nothing special:

def main()
  let s = "Hello world!";
  System.Terminal.stdOut.writeLine(s);
end

but few classes are already involved. Plenty of hard work ahead of me (starting from implicit outgoing type conversion) — but today I celebrate!

`return` with no `else` — no more papercuts

I understand this or that omission in given language — not enough resources, somebody was not bitten by specific error, but it is strange when you see on multiple occasions a guideline which goes against software safety. Consider such code:

def foo() Int
  if x > y then
    return 17;
  end
  return 44;
end

Such code is legit in every language I know, what’s more it is advised way to write according to Mozilla guidelines and Go as well ¹. I admit it is more pleasing for the eye than version with added explicit `else`, but when it is time to refactor the code it is way too easy to make a stupid mistake like this:

def foo() 
  if x > y then
    my_flag = 17;
  end
  my_flag = 44;
end

I noticed it because I was hit by it — you don‘t have clear mind all the time. And since Skila is designed to prevent exactly this kind of errors (“stupid mistakes”) I am about to add not even an opposite guideline, but simply a check — any flow interruption instruction has to be followed with `else` branch. Safety first.

---

¹ Read more: “No-else-after-return” considered harmful, Effective Go.