Counting the infinite sequences

Doesn’t it strike you as odd, that you can write such code in C#:

if (sequence.Any()) ...

and it is efficient as it can be, but when you rely on Count method:

if (sequence.Count() > 0) ...

you may fall into a trap of extensive computation despite you just need confirmation whether the sequence is empty or not. Well, this disparity annoyed me for a long time and all I could think of was passing somehow a predicate to Count. It is as fishy as it sounds, and it annoyed me even more.

Until the perspective changed — who said Count should count anything? Why Count should jump right away with exact answer?

Count should be lazy and it should simply return the instance of some numeric like type, say SequenceCount — that type should keep reference to the sequence, have implicit conversion to Int and — what is crucial — it should also overload comparison operators. With all those goodies you could finally write:

// Skila syntax
if (1...).count() > 0 then 
  stdOut.writeLine("not empty");
end

to see a printout after a few CPU cycles.

Now when I solved this issue I can think of general lazy evaluation design for Skila…

Advertisement

Properties — enough with monkey typing

The more I use properties in C# the more annoyed I am with repetitions. Consider such code:

private SomeType field;
public SomeType Field
{
  get { return this.field; }
  set 
  {
     // some logic with previous value
     this.field = value;
     // some logic with new value
  }
}

Triggering events, logging data in a database, you name it — this pattern occurs over and over again. And the best you can come up is writing Wrapper class and using it like here (still C#):

private Wrapper<SomeType> field = new Wrapper<SomeType>();
public SomeType Field
{
  get { return this.field.value; }
  set { this.field.value = value; }
}

Some advise the solution to this is using snippets which is hilarious idea — it is like saying that you can reduce the amount of code by typing faster. Besides I am not a monkey, so I look for the solution elsewhere.

Somewhere along AOP or Scala-like traits — I am thinking of property specialized overlays:

overlay Wrapper // implicit first generic parameter: T
  def set(value T)
    // some logic with previous value
    inner.set(value);
    // some logic with new value
  end
end

Since overlay will be mixed with property we have to connect it somehow to the already existing setter or getter — all we need is inner reference. And the usage could be reduced to this:

def field SomeType with Wrapper; 

The type of the field would be SomeType, keyword with does not change a type, it just indicates what wiring compiler should do behind the scenes.

It is just a vague idea, but it has to be done, yesterday my inner monkey wrote:

private SomeType field;
public SomeType Field
{
  get { return this.field; }
  set 
  {
     // some logic with new value
     this.field = value;
     // some logic with previous value
  }
}

So it is about time to make properties right.

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.

I need Skila even more badly

Boy, I have been busy! Unfortunately nothing related to Skila or NLT. I have “little” project going and I fell into a cycle of adding just the last feature and having five more ideas. Now I am at the point that I have tons of good ideas, the project looks really interesting and useful (educational area — I am not giving the address away yet, because I didn’t figure out the good name for it), I am enjoying it tremendously and I need server side language very badly.

PHP, Python, JS (with Node.JS), C# or maybe C++ — oh man, not those. I’ve been there — this one is not compiled, that one is cryptic, other closed but open-source. No, no, no. I can write programs in those languages for somebody else, but why hurt myself? Apple’s Swift could come to the rescue, but I don’t live in Apple ecosystem. Skila is supposed to be my solution but Skila is not ready.

Seriously, I am desperate. I am bored to death with limitations of nowadays languages, I want to enjoy writing code (after all it will take a lot of time, my leisure time).

And so I am evaluating another possibility — killing Skila! Yes, that’s correct. I am thinking that I made a mistake with the attitude to design — creating perfect language, with perfect features. That is exactly what is stopping me. Perfect is complex, perfect is hard, and I don’t have time for that. I need Skila for yesterday so my other project could grow.

I need imperfect language, simplified so I could cover at least server side of my project, and then client side. This is not awfully far for what I had in mind initially, but I drop performance from my goals. There is also a small advantage for me — I could make a compiler faster, design language faster and learn more from working language while implementing other projects than sitting forever and theoretically decide which feature or syntax is better.

Simplified Skila is the last chance for my own language — either I manage to pull this off and use it, or I won’t have any more time for language development, simply because I have other solid projects waiting for implementation, and however tempting is having nice language, it is not material for startup. All other projects are.

To end this post — some good readings, a blog OnStartups and few years old (I got to know about it a week ago) but still interesting reading about work culture in Netflix.

A reminder from the closed source world

Now and then I get stern reminder to stick with open source when it comes to base system. I have to replicate the system, it refuses to do so, I have to install the updates, it cannot find root partition, and so on. 16 years ago I switched from Microsoft Windows to SUSE Linux and I found it is plagued with bugs as well. The difference is with Linux I can boot the computer from the pendrive, I can run console, I can actually diagnose the problem — same story with programs. And when I need something badly I can modify the source code, compile it and voilà I have my custom tool.

Around week ago I finished GLR parser as part of NLT suite. The only annoyance is it is too slow to publish it, so I need to profile it. And then Visual Studio profiler stopped working, I switched to PerfView and instead usual 3% of broken stacks I got something more like 80%. Just my luck — go figure the bottleneck now.

And still, I am grateful for this refreshing experience, it is good to know what closed source programs stands for — reinstall everything or buy newer versions and pray the problem will go away. Right…

Don’t mix deferred execution with optional outcome

I prefer using yield when returning IEnumerable because code looks really clean — storing the output manually loses this nice look, not mentioning extra wrapper method.

But the look can be misleading when the language design leaves a hole — and I fell into this trap. I used yield in method that returns not some crucial data, but simply a report about what was not computed. You can read it, display it, or ignore it, your call. The problem is yield unlike cached result, uses deferred execution. And deferment is based on usage of… the outcome. So if you ignore it (and C# compiler does not make a peep about it), it will be not executed at all.

The lesson for C# devs is this — if it is OK to ignore the outcome of the method (as in my case, just a summary of computation), do not use yield. Go with storing the output inside the method.

All the things that can bite you…

The summer is rather slow when it comes to development (hopefully we passed 35°C zone) but I am doing good progress with cleaning the code anyway.

One thing that stopped me was C# struct. Most of the time I work with classes and despite I know what the struct is, I simply don’t have vast practice with it, and so I was caught off-guard.

I was implementing Option which should work as Nullable for all types. Since it should express strictly the notion of an option, it has to be a struct (otherwise you would have to deal with missing option, unset option and set option with missing value — tad too much). Implementing it was no brainer, thanks to C# properties next to SetValue I added nice Value setter which changes HasValue as well. Concise, easy to understand and… completely wrong.

I added it to Skila and to my surprise on one end I called SetValue just to observe no value was ever set on the other end. What on the Earth? Well, struct is always passed by value, which means that if Option is returned from property getter or a method, there is a copy returned of real data. I could call SetValue million times and it would not change a thing for stored data (only local, temporary, copy of Option would be changed).

So rule of thumb for C# developer — by default make your structs immutable. For a language/framework designer there is a lesson too — don’t make risky features implicit.

I‘ve recently watched “Essential Truths Everyone Should Know about Performance in a Large Managed Codebase” by Dustin Campbell. It is longer version of an old saying “profiler is your friend” — but what struck me while watching it is that in C# you don’t see bottlenecks. Boxing? Implicit. Unboxing? Implicit. Method wrapping (with boxing)? Implicit.

Add to this a framework which uses object too often, and profiler becomes necessity. And I thought implicit conversion constructors in C++ were bad — boy, you can at least make them explicit by yourself.

Generics — just around the corner

The last few posts were about NLT only but Skila things were move forward as well. I added value and reference types with control of data mutability. So for example:

func getconst() const Foo = new Foo();

func readconst()
do
  var x = getconst();
end

It will work if “Foo” is value type (because all data from the function “getconst” will be copied) but it won’t work if “Foo” is reference type, because in such case only a reference is passed — one could still alter the data obtained from “getconst”.

I am aware that I missed a lot of cases but I will fix the bugs as I will implement next, and probably the last major feature before I make first upload of Skila — generics. I need it to provide arrays, tuples and IEnumerable interface. Those in turn will be required when implementing macro constructors.

My schedule looks like this:

• think over the constructor naming — maybe instead ”func Init” it would be better to have just “constructor”,
• polish “const/var/!” syntax — the mutable methods are denoted by “!” in front of their names, but objects are marked with ”var”,
• add shuffle feature to NLT parser,
• implement true generator for NLT,
• add generics to Skila,
• toss arrays, tuples and IEnumerable,
• finish with macro constructors.

9 days as 2 hours

I am in rather bitter mood because I finally did validation of static features in Skila — however instead of 2 hours as I anticipated it took me 9 days. I wish I could say I fainted in the process, but I didn’t — and I feel bad about this.

But no matter how bad the things are there is always a lesson to learn — this experience supports in a way idea expressed by Peter Seibel in his talk “Practical Common Lisp” that the language defines thought.

Here, I was so used to the framework I already had for name resolution that it was obvious I should add a few patches, fix this and that, and I will get working solution. I was absolutely deluded — the right way to achieve solution was a major rework and coming up with completely new name resolver. If I did it right from the beginning I would spent 2-3 days on it with steady progress and no frustration.

Now I need some time to take care of my regular duties, I should be back in 2 weeks.

All the noise about static

Who would thought that adding “SELF” can cause so much fuss — obviously I needed “static” notion in Skila, which I hadn’t have and when I added it appeared NLT parser is not suitable for new set of parsing rules.

The last problem came as no surprise — so far NLT forking parser executed all user actions, even in multiple branches. This had to lead to problems and hit me this weekend. So instead of doing fancy stuff with pinned constructors, I sat down and changed executing user actions into logging parser actions. On successful parse, all commands are played back and then user actions are executed.

No rocket science, nevertheless I was one day short, and after adding exposing field’s methods feature plus fixing PHP backend a bit I ran out of time. I plan to squeeze error reporting on static misuse into workdays so I will be able to come fresh to implementing pinned constructor and “SELF” next weekend.