Of the statistical significance of “best of X” tournaments

Most games consist of players opposing each other, competing for the win. We play competitive games to prove, by the way of winning, that we are a better player, and therefore smarter, more skilled, etc. But does winning actually prove that we are a better player?

We know intuitively that winning one game might be a fluke, a stroke of luck. So often, we play several games, and the winner of the majority of games is declared the winner of the whole “tournament” (best of 3, best of 5, etc.)

Does that make sense, mathematically? After all, if we suspect that there might be chance involved in the outcome of one game, there should be chance as well in a series of 3, 5, or 7.

In scientific experimentation, we measure the statistical significance of a result by determining how unlikely it is that it was obtained purely by chance, rather than as the consequence of the phenomenon we try to measure and prove. What happens if we apply this method to games and tournaments?

The experiment

Let’s take a symetrical 2 players game that doesn’t allow a draw. The two players will play a total of N games. We will count how many games were won by each player.

The “null hypothesis” H0 is that the players have the same strength. Or equivalently, that game outcomes are random. Since the game is symmetrical, each player has a 1/2 chance of winning each game.

Our “alternative hypothesis” H1 is that player A is stronger than player B, and that the outcome is not random. I give names to my players to have a so called “one-tailed” test: it’s easier to think in terms of “A being stronger than B” rather than “either A or B is stronger than the other”, and in the end it cuts some numbers in half. But it’s a detail really.

What we’ll do now is check how likely was a certain result, assuming the null hypothesis. If it was quite likely, we can give the benefit of the doubt: the tournament wasn’t much different than a bunch of coin tosses. If the result is very unlikely assuming H0, then there is a reason to believe H1, that is, that player A actually plays better than by pure chance.

Let’s call X the random variable denoting the number of games won by player A, if it was pure chance. The probability of player A winning c games is a standard binomial distribution:

P[X = c] = C(N,c) * p^c * (1-p)^(N-c)

C(n,k) is the combination (the number of ways to select k elements among n), and is equal to n!/(k! * (n-k)!). With p = 1/2, this simplifies to:

P[X = c] = 1/2^N * C(N,c)

We are not really interested in the probability of winning an exact number of games, since a player is declared winner when he wins at least a certain number of games (usually half). Let’s compute the probability of player A winning c or more coin tosses:

P[X >= c] = 1/2^N * sum(C(N,k), k: c -> N)

This is simply the sum of the probability to get c wins, c+1 wins, c+2 wins, etc. until N.

The result

So let’s check how “good” is a player who won a best of 3 tournament. N = 3, c = 2. Probability: 50%. Yes. Someone who wins a best of 3 tournament is just as impressive as someone who guesses a coin toss correctly.

Best of 5 (that is, at least 3 wins on 5 games): 50% as well. Best of 9: 50%. Best of 99 games, take a guess… 50%.

If a game is purely random, the probability of winning at least half the time is exactly 50% (for an odd number of games). Therefore, if you see someone win “best of X” tournament, you have no statistical reason to believe that the outcome is anything else than chance. Or at least you can have a serious doubt.

Careful about the semantics though, we are not proving or disproving anything. We are not even measuring the probability of the game to actually be random. We’re only saying “if the game was random, player A winning best of X would have a 50% chance of happening”.

The improvement

So winning at least half the games is not statistically significant. What would be? Two thirds of the games? Three fourths? All the games? Surely if a player wins all the games, they have to be the best player?

Scientists often use 5%, or even 1% as the highest accepted probability of the measured outcome to be consistent with randomness.

We saw that 2 games on 3 was 50% likely. Winning all 3 games on three by chance has 12.5% chance of happening. That’s still much higher than 1% or 5%. This is not statistically significant.

Winning 4 games on 5 by chance is 18.7% probable. 5 on 5: 3.12%. That’s already much better. It’s significant with the 5% limit.

What you can say when player A wins 5 games on 5, is that “if hypothesis H0 was true, this outcome would have been quite unlikely”. In other words, the game is probably not random, and it’s probable that player A is a better player.

Here’s a table of the minimum number of games that one must win for the outcome to be statistically significant (for various values of N and several levels of significance):

N	5%	1%	0.1%
3
5	5
7	7	7
9	8	9
10	9	10	10
20	15	16	18
50	32	34	37
100	59	63	66

Empty cells mean that no amount of winning will be significant for that total number of games.

So next time a player pretends they are better than you at a game, ask them to prove it by winning for instance 10 games on 10, or at least 16 games on 20. Anything less than that should be declared a draw, for lack of statistical significance on the data :)

Unified member access and interfaces

This last article told us that there is now two ways to read a member (or element in an array): through a method that returns the value directly, or through a method that returns an alias to it. As for setting, there is also two ways: an alias, or a setter method.

How does that work with interfaces? They work only with methods, which is fine because member access is (still) always done through methods.

Reading

Now suppose an interface describes objects that have a “color” member, real or fake. If we only need to read it, we can always do:

interface Colored
    Color color()
end

First issue: objects with actual Color member will only have the compiler-provided accessor, which returns an alias to Color. On the other hand, objects that expose a fake color member will probably not have an alias to return, if it is procedurally generated. Also, some object might not want to expose an alias, as it would allow the outside world to modify it.

The most general case must win: in a read-only scenario, the vanilla non-alias method should be all that is needed. But then how can we cast an object with only the alias method to a generic that expect a return value of the actual type?

object Pumpkin
    Color color

    -- automatic:
    method alias Color color()
    end
end

If we just gave a pointer to a Pumpkin as a generic Colored, the color method would return an alias instead of a Color, and the low-level code would fail by not deferencing the alias. Easy solution: a magical hidden read-only method that is used when casting to an interface that needs a non-alias!

-- automatic:
method Color color_hidden()
    return color
end

That’s a bit of inside magic, but it’s still acceptable. To make it less magic, that automatic method could be called get_member (so as to not conflict with the alias accessor called member), and be exposed by the compiler as a perfectly valid method, only it returns a non-alias.

Writing

The same issue exists for writing to members, real or fake. Here too, real members will have only alias methods, while fake members will be setter methods, and an interface that can use both will have to accept the most general one:

interface WritableColor
    set_color(Color)
end

And here too, we can have automatic wrappers made for real members:

-- automatic:
method set_color(Color value)
    color = value
end

For the setter, we don’t even have a name conflict with the alias accessor method (member vs. set_member).

Reading and writing

If the interface describe a member that can be both written and read, we can simply combine both:

interface RWColored
    Color color()
    set_color(Color)
end

and both objects with a real member or a fake one would work.

What if we’d like to force the use of objects with real members, and aliases? After all, even if this is semantically equivalent, using this with a struct Color would mean copying a struct, doing stuff with it (including modifying it) and then copying it back entirely using the setter method. Even with objects, it’s two dynamically dispatched method calls where it could be two direct read/writes from memory.

Additionally, it might get annoying to have to write both getter and setter in an interface, if read-write is a common requirement. The straight-forward (and legal) idea is:

interface RWColored
    alias Color color()
end

But it does seem to go completely against the idea of generics, to restrict cool algorithms to real variables, when the entire paradigm of the language is to encapsulate members deep inside objects and allow procedural members to be used just the same way as real ones.

(Note that “the same way” here means “by writing the same code”, even though at low level it is of course translated to different instructions, which is exactly where generics would fail. The advantages of writing generic methods for aliases only versus set/get methods would come down to the previous discussion of having automatic template-like instanciation of generic code, which is an interesting prospect but largely out of scope for now).

So even though we can’t prevent coders to restrict their interface to alias methods, we can always facilitate the transparent use of real and fake members. For instance with something like:

interface Colored
    Color color     -- OMG, is this a member in an interface? Wuut?
end

This would be stricly equivalent to asking for Color color() and set_color(Color), both of which could be automatically wrapped from the alias accessor of a real member.

Naming convention

Although we insisted from the very beginning that both the member and its getter method should be the same (because of the parentheses-less call), it creates an inelegant asymmetry:

Color color()
set_color(Color)

Wouldn’t it be much nicer to have:

Color get_color()
set_color(Color)

And the alias method, which is really neither a getter nor a setter (these operations are done to the result of this method, the alias itself), could have the naked name?

alias Color color()

In the end, a member would come with three free methods, filled in by the compiler:

object Foo
    Bar bar

    -- automatic:

    alias Bar bar()
    Bar get_bar()
    set_bar(Bar)
end

And therefore every object can be casted out-of-the-box to any generic that requires reading and/or writing of one of its members, whether by alias, or by individual methods. For consistency, any user-made alias accessor method (such as in wrappers) should come with the free setter and getter as well.

object Bar
    method alias Foo some_foo()
        -- ...
    end
end

-- can also:

local f = bar.get_some_foo()
bar.set_some_foo(f)

For consistency, the indexing methods should now be Type get_index(args) and set_index(Type,args), with the alias one being alias Type index(args).

This is beautiful and utterly satisfying. Symmetry, elegance, consistency.

Unified member access

State of sool

An early design decision in sool was that member access ans indexing operations were all method calls behind the scenes. On top of that, method call with no arguments can be written without parentheses, which makes it even look like member access:

foo = meh.bar   -- is really:
foo = meh.bar()

At first we had the concept that member setting was also done through a method:

meh.bar = foo   -- is really:
meh.bar=(foo)

where a method can end in = to signify it’s a setter. Defining a member Bar bar asks the compiler to reserve some room in the memory layout of the object, and expose two accessor methods Bar bar() and bar=(Bar).

Indexing was done exactly in the same way:

foo = meh[4]    -- is really method T [](uint)
meh[5] = foo    -- is really method []=(uint,T)

We realized later that this cause problems when dealing with structs (or “value classes”) because getter methods such as these would return a copy of a member struct, since structs are treated a value types. As such, struct members and elements would be immutable.

To solve this, we introduced the concept of “alias” (or in C++ terms, references). A method could return an alias of a variable, which can be used as left-value to modify the original variable, for instance change its value or call a method on it.

This simplified things, as accessor methods could now be simply returning an alias, used both as right-value (immediately dereferenced) and left-value (as destination address for assignment):

object Foo
    Bar bar

    method alias Bar my_bar()
        return bar
    end
end

This works fine, although it removes the possibility of having special setter methods that processes arguments before setting anything (the old foo=(Foo) kind).

What would the others do?

Many languages have the concept of properties, that is pairs of methods that act as members. They typically have a separate syntax. In C#:

class Foo
{
    private int color;

    public int Color 
    {
        get
        {
            return this.color;
        }
        set
        {
            this.color = value;
        }
    }
}

Ruby has, like sool, pairs of foo and foo= methods. Objective-C 2.0 needs a @property keyword on the member, and then a @synthetize one on the implementation. ActionScript 3 has a get and set keyword to sneak in a function declaration for this purpose.

All of these are explicit. D, this beautiful bastard, does what I had in mind for sool: implicit genius. Any method can be used as property, if the prototype matches.

class Foo
{
    private int m_color;

    public int color()
    {
        return m_color;
    }

    public void color(int value)
    {
        m_color = color;
    }
}

auto foo = new Foo;
foo.color = 5;
auto blah = foo.color;

In D 2.0, though, these methods have to be marked as @property, but sometimes a compiler switch lets you bypass this restriction.

AngelScript has an interesting hybrid system:

class Obj
{
    private int m_foo;
    int foo
    {
        get const
        {
            return m_foo;
        }
        set
        {
            m_foo = value;
        }
    }
}

// so far, nothing new, but it actually generates this:

class Obj
{
    private int m_foo;
    void set_foo(int value)
    {
        m_foo = value;
    }
    int get_foo() const
    {
        return m_foo;
    }
}

Accessing foo is then converted simply to the set_ and get_ methods. Indexing works in a similar way, where calling global blah[i] is translated to get_blah(i) and set_blah(i,value).

I want it all!

If in sool we want all of:

• transparent access of member as methods
• aliases for modifying structs
• setters that actually involve processing

then we’ll need a generic system where right-values can be:

• methods that take void and return something (alias or not)

and left-values can be:

• methods that return an alias
• methods that take a value

So that the call res = foo.bar could be a call to:

Res Foo:bar()
alias Res Foo:bar(), then dereferencing

and foo.bar = val could be a call to:

alias Val Foo:bar(), then assignment
Foo:bar(Val value)

This brings the immediate problem of ambiguity:

object Foo
    method alias Bar bar()
        -- do something
    end

    method bar(Bar value)
    end
end

local foo = Foo
foo.bar = Bar   -- which is it? Does one have priority, or is it wrong to call this?

Ambiguity is not lifted by forcing the setter to have a different name, like bar= or set_bar. We have to decide that, for instance, the alias method has precedence. A careful programer will not, anyway have 36 different accessors for his properties.

Multiple assignments

Let’s also think about the neat feature of having multiple assignments in the same statement.

a,b = c,d

This evaluates c and d, then assigns the results to a and b, whatever these are (variables, aliases, setter methods, etc.) This allows nifty swapping without having to write the temporaries. Also, in a language that allows functions to return multiple values, cool things like:

local a,b,c = foo.bar()

In Lua, if a multiple value is in a list on the right side, it’s truncated to its first result, so:

local a,b,c = foo(),5       -- where foo returns 2 values

actually doesn’t do what you’d expect. In sool, it would, so all the values would appear in the right side, and be assigned one by one on the left side.

About the left side, could expressions be multiple lvalues?

foo.bar = 1,2,3
-- yes, easy:
foo.bar(1,2,3)      

Or using aliases, if a alias int, alias int, alias int bar() method exists. We never thought about it, but why not. I’m thinking in particular about things like:

vec.xy = vec2.yz

Instead of having to create a middle object:

value Vec3
    method Vec2 xy()
        return Vec2(x,y)
    end

    method xy=(Vec2 other)
        x = other.x
        y = other.y
    end

    -- etc
end

you could simply pass values and do direct assignments using aliases:

value Vec3
    method alias num, alias num xy()
        return x,y
    end

    -- etc
end

And of course still create middle objects where needed:

Vec2(vec.xy)    -- calls constructor init(num x, num y)

Wrapping it up

Right-values are never a problem. Expression a.b(c,d,e) is always a direct method call (even when arguments and even parentheses are absent). It can return a value, or an alias, and all is well.

On the left side, we can have, in a generic form:

a.b(c,d,e) = f,g,h

First we evaluate a.b(c,d,e). If it returns aliases, we gently add them to the lvalues of the assignment, and try to assign the rvalues. If it doesn’t, we try a.b(c,d,e,f,g,h). If it exist, we add dummy lvalues to the left expression and go on with our lives.

The question of ambiguities remain. If the setter method has no specific name, it means that a method that takes say 5 values can be used in any of the following ways:

a.b = c,d,e,f,g
a.b() = c,d,e,f,g
a.b(c) = d,e,f,g
a.b(c,d) = e,f,g
a.b(c,d,e) = f,g
a.b(c,d,e,f) = g
a.b(c,d,e,f,g)

Is it a problem? It might. Consider:

a.b(1,2), a2.b(1,2,3) = u,v,w,x,y,z

How many rvalues will the first a.b eat? Does the compiler try to call a.b(1,2), then a.b(1,2,u,v,w,x,y,z) failing both, or does it smartly match the setters to find that only a.b(1,2,u,v,w) exists, leaving the second call to be a2.b(1,2,3,x,y), and one r-value hanging? Not very clear. But then again it would be so nice to have a procedural setter that takes several values:

foo.bounds = 10,20      -- checking that 10 < 20

instead of:
foo.set_bounds(10,20)

That especially helps to swap code but keep the same syntax in calling sites, if later you replace this by an unchecked setting with aliases, or vice-versa.

Even without the left-arguments, and regardless of whether the setter has a specific name, we have ambiguity due to overloading:

object Foo
    int x,y

    method set_values(int x)
        self.x = x
    end

    method set_values(int x, int y)
        self.x = x
        self.y = y
    end
end

-- later

foo1.values, foo2.values = 1,2,3

Is it foo1.set_values(1,2); foo2.set_values(3) or foo1.set_values(1); foo2.set_values(2,3)? The guessing of the correct setter works without ambiguity only if all the rvalues go to the one lvalue. Or will the first lvalue try to eat as many rvalues as possible, as a rule? It’s also the responsability of the coder to not abuse the flexible systems set in place by the language. If need be, you can always add a few temporary locals.

Conclusion

Right-values have never been an issue: methods take arguments or not, and returns aliases or values, which add up as a flat list of rvalues.

An expression a.b(args) (possibly with no args) as left-value is first evaluated as it is, and must return at least one alias. If that doesn’t work, try calling: a.set_b(args,rvalues). If it fails, remove the rvalues from the right until it matches or fails.

As for indexing, an expression a[args] (again possibly with no args) is rewritten a.index(args), and then the same rules apply: as is for rvalues, or as is as lvalue if it returns alias(es), or then rewritten a.set_index(args,rvalues).

The automatic accessor written by the compiler for members is one that takes no argument, and returns an alias.

The great overhaul

Keep it simple, stupid. Let’s see if we can do that: core is simple, add a bit of sugar on top.

Functions

So we have functions. Let’s see how that works.

function Foo,Bar do_it(Meh arg)
end

This makes a function in the module space. To call it:

do_it(arg)
arg.do_it()

You can also put a function inside a class definition, which only adds additional namespacing (must be prefixed with class name from outside the class):

object Foo
    function bar() end

    function baz()
        bar()
    end

    method blah()
        bar()
        baz()
    end
end

-- elsewhere
Foo:bar()
Foo:baz()

Note that inside a method’s body, we have an implicit self so there might be conflicts there:

object Meh
    method foo()
        bar(5)      -- could be functions bar(uint) or bar(Meh,uint)
    end
end

In D, the method of the object shadows the outside function. Makes sense. If you really want the function, you need to use its module’s path.

Methods

Method definitions are a simple syntactic shortcut:

object Foo
    method blah()
    end
end

Is exactly the same as:

object Foo
    function blah(Foo self)     -- for value classes, `self` is passed by ref
    end
end

Meaning that the method has the hidden self, and is defined in the class’s namespace. When using extend, same story.

Note that I mean “exactly the same” in terms of function prototype. In the body of the method, the self keyword can be omitted for methods to self.

Constructors and factories

They are just methods and functions with a special name, init, that is called when you use the class name as a function (sugar!):

object Foo
    function Foo? init(bool isRaining)
        if isRaining then
            return Foo()
        else
            return nil
        end
    end

    method init()
        -- do the thing
    end
end

-- later

local a = Foo(true)     -- is really Foo:init(true)
local b = Foo()         -- is really make a Foo and call method init() on it

Factories and constructors cannot have the same selector, obviously, and a constructor cannot return anything. Also constructors have this special semantic analysis that prevents you from reading from uninitialized members, or pass self as parameter (including sending message to self).

Interfaces

Interfaces cannot use “functions”, only methods, because the point of interfaces is to test compliance of classes to it.

interface UintMaker
    uint make(ArgType arg)
end

If there is a function uint make(Foo,ArgType), whatever way it is defined (in the class, outside the class, in extension), then class Foo complies to interface UintMaker. Period. Nothing changed.

References

Internally, references are a type, and in low level code they are handled differently than the type they refer to (by dereferencing). However, like in C++, references cannot be re-initialized: once set, they are a perfect alias of the original variable and any operation happening to them happens to the original one.

Question is: do we need a full blown reference type, to be used for members and as template arguments, or is the only reasonable use for passing and returning to and from functions?

If it is a full type, then we need to be able to declare it for locals:

function foobar()
    local myRef = ref something.that[might].be["quite"][far]

    myRef.do_this
    myRef.do_that
    myRef.dance_a_little_jig
    myRef = replacement
end

Note that “taking the reference” operation is automatic for the first “assignment” to a thing that is declared as reference:

function fiveIt(ref uint i)
    i = 5
end

-- later

local foo = 10
fiveIt(foo)     -- no need to write fiveIt(ref foo)

Not sure about members though:

object
    ref uint i

    method init(ref uint other)
        i = other       -- this is the first assignment, but how to know?
        i = ref other   -- more straightforward
    end
end

Of course, this ref operator cannot be applied to things that are not in the heap, like locals, because that would allow horrible horrible things like returning a pointer to a local, which scope is limited.

function ref uint blah()
    local i = 5
    local myRef = ref i

    return myRef        -- EEEEEEK!
end

Anyway, a local is a simple name, you never need a shortcut to it from the same function body. I think. Then again, you can definitely pass a local by reference, since it always oulives the inner function. Maybe the forbidden thing is only to return a reference to a local.

Now how about having references as template arguments:

local arr = array|(ref uint)
arr.push(somevar)

arr[1] = otherint       -- are we setting the array cell, or the thing refered by it?
arr[1] = ref otherint   -- is it clearer? or even possible?

Even the protoypes would be weird:

method ref T [](uint)           -- template
method ref ref uint [](uint)    -- applied template to uint

Ooops, can reference types be recursive? How can we possibly use the intermediary steps, since they are always autodereferenced?

This seems like a bad idea. The natural use for references is arguments and return values. Both are locals. We can add explicitely declared locals, why not, for nice shortcuts. But no other variables.

But they do participate to the functions’ prototypes, and therefore, to interface compliance.

interface Blah
    changeAnInt(ref int)
    ref text getSomeVar()
end

Cool stuff could happen for loops and iterators:

for i, ref v in arr do
    v = 5       -- no more of the annoying Lua way of reindexing arr[i]
                -- which also means no boundary check. FAAAST.
end

Final note: the name “reference” is well known, especially from C++. But it is a tad confusing that our object variables are also said to be references.

function(ref MyObject obj)
    -- obj is a reference to a reference to a MyObject
end

Another name could be alias. It abstracts the fact that we’re using pointers, and says “this is now exactly the same as that other variable”. Longer to type though, and “passing/returning an alias” is not exactly as well known as “passing/returning by reference”.

function fiveIt(alias uint i)
    i = 5
end

object Foo
    text blah
    method alias text getText()
        return blah
    end
end

Maybe.

Promoting values to generic

Generics use dynamic dispatch, and I always assumed that, like in C++, you could only apply this to pointers, and therefore, to objects. But references/aliases are in fact pointers to data, and it makes them look like objects. With a pointer to a value, and a bunch of method pointers, you could definitely cast a value to a generic.

The only tiny weeny problem is that the pointer has to be valid (obviously), so it would work only for values that are stored in the heap (array elements and object members). However, we know that there is a way to alias a local, by passing it “by reference”:

function a()
    local i = 50
    b(i)
end

function b(alias uint i)
    local gen = i to MyGeneric
    someobject.save(gen)
end

Oooh, bad. Here, someobject potentially remembers the address of the local i in function a, which is destroyed when a returns. Very bad. Two solutions: no casting values to generics, or somehow refuse to cast one if you don’t know where it comes from. The same way the compiler doesn’t let you return a local as alias, it won’t let you cast a local to a generic, only one that comes from elsewhere, because that’s guarantied to be from the heap.

Anonymous functions

We now have functions. So anonymous ones seem easy. But so far we had used anonymous methods as a shortcut to:

• add a nameless method to a class
• wrap an object of this class in a generic which demands that prototype
• pass/save this generic (object pointer plus function pointer)

With plenty of syntactic shortcuts. That doesn’t work anymore for functions, which do not have an object. Can’t have a generic that acts on nothing.

We would need a new concept: the first level function. Or function pointer. Or “function interfaces”, which are just a way to invent a function pointer type.

The whole anonymous method and callback discussion was pretty clunky already. Maybe this needs a rewrite as well.

Note: anonymous methods could really be anonymous functions that close on self. Instead of having it as a hidden parameter, it could be a hidden upvalue.

In any case, for anything like this to happen in a clean and simple way, we would need function (pointers) as a primitive type. And a recursive one at that.

uint function(Foo,function(Bar))

Here’s a function that returns a uint, takes a Foo and a function that takes Bar. Also, syntax fun:

(array|Foo) function(Bar)
array|(Foo function(Bar))
int function(int) function(bool)    -- woo, a function that returns a function!

Grr. Also, the tiny problem that so far, every thing was an instance of a class, with methods, etc. Even arrays, that have a type parameter, interpreted in low level as templates. But functions would need variadic templates, because of their varying number of parameters.

THE HORROR. Is a function an object? Can I call methods on it? The only thing we really want from a function is to call it. So maybe a function is an object with a single method call and a bunch of arguments.

Then would function call be a shortcut for calling the method call on a function object, which is itself calling a function with the object as hidden self and… AAAAH. Madness.

Let’s wave this away for now. Maybe sool is not ready for this.

Templates

So far, templates applied only to whole classes, therefore affecting the member types, the method protoypes, and the methods’ code. Since now functions are actually quite independant from classes, could they be templates as well?

function foo|(any T) ()

end

With of course an “automatic” template if they are defined in template classes or extensions.

object Foo|(any T)
    method blah()
    end
end

-- is actually

function Foo:blah|(any T) (Foo|T self)
end

The semantic analyzer will have so much fun with these…

local f = Foo|uint
f.blah

Results in:

• look for all functions blah(Foo|uint)
• didn’t find any
• look for templates that might match
• found blah(Foo|T) with T is uint
• is uint compliant with interface any?
• yes
• instantiate function template blah|(any T) (Foo|T self) for uint

Oh lord.

For the fun: can you have templates of templates? I guess so.

object Foo|(any T)
    method blah|(any U) ()
    end
end

-- is actually

function Foo:blah|(any T, any U) (Foo|T self)
end

Oh double lord. On the other hand, separating classes from methods might actually make things easier. When you have a class template, just generate the accessors as templated functions. Then all you have is functions, and the lookup can be the same in every case. Maybe.

In terms of compiler, reading the DMD compiler’s source, I noticed a pretty nice way to deal with templates: template declarations are basically just scope declarations, which bind a symbol to a (unknown yet) type. When analyzing the code within, you do type lookup just like for any other class, except that it resolves, in this scope, to the bound of the template parameter. This works transparently for classes, functions, extensions and whatnot.

In the instanciation part, when you use template parameters, you just make a template instance type, which refers to the original symbol (which in our case is always either a type or a function), and keeps a list of argument types to bind to the unresolved symbols.

It probably sounds easier on paper. But one has to start somewhere.

sool’s identity crisis

Pun intended. Yes, really.

What’s the problem? Not a problem, really, just a time to sit back, and figure out what sool has become, albeit conceptually. It started as “Lua with static typing”. And this lead to a waterfall of consequences that greatly increased complexity.

Static typing leads to named constructs: objects. An object centric design is nice to think of as “every thing is an object, every action is a method call”. Every thing is an object leads to awkward performance for primitive types and “small objects”. We create structs with value semantics. Every action is a method (including member access), combined with structs, leads to the necessity of still being able to manipulate structs by reference. With the compromise between: explicitely, which adds more syntax and features, or implicitely, which add more “behind the scene” stuff.

Also, every action is a method rules out simple functions, makes factory methods special cases of constructors, and external C functions as well.

Plus, on top of that, we want interfaces for elegant generic programing and polymorphism. And templated classes for containers (plus more efficiency on critical algorithms).

Not so simple anymore.

Initial goal

Lua is a beautiful language, in great parts thanks to its simplicity. Of course, being dynamic in nature makes that quite easy: delay every kind of semantic checks to runtime. In fact almost everything is allowed in Lua, thanks to metamethods. Very few operations fail, and they usually come down to trying to call or index nil.

But its simplicity doesn’t mean it’s not a rich language. Thanks to very flexible core elements, and a handful of smart syntactic sugar, Lua looks almost like a fully blown object-oriented language, with functional programming capacities.

The problem – to me at least – is that amount of freedom. When everything is allowed, it’s just too easy to take shortcuts that eventually turn out to be self-foot-shooting. If my brain cannot be rigorous and disciplined enough, then the language must force me. It’s fine for small scripts, but as the codebase grows, the discipline diminishes and spaghetti occurs.

That lead to this new language idea, in which I’d toss the features I want to see in a “stricter Lua that can be compiled to machine code”. Let’s see what went “wrong” on the way.

Object centric language

It’s hard to avoid the concept of “objects”. It doesn’t have to be fully compliant to the principles of object-orientation (I abandoned inheritance already), but basically everything you do (or I do at least) when programming is defining data structures, and actions that can be taken on them.

Hence, objects and methods.

But methods are, fundamentally, just syntactic sugar for functions with a hidden argument. If you write object-centric code in C, you make structs, and functions that take pointers to this struct as a first argument. Why sugar? Because with language supported “methods”, you hide the hidden self argument in function prototype and body, and the method call syntax is more natural. It also makes natural namespacing for methods.

That’s great. But it’s just syntactic sugar. The core is still just structs/objects and functions. Maybe we could go back there.

Values and functions

Suppose we build the language from scratch again. The very basis is primitive types, undivisible. Most of them are value classes, so the next thing we build is composite types, that group other values. That’s C structs.

Then we have functions that take in values, compute stuff, have side effects, and return more values.

But then very fast we realize that copying structs all the time is not very practical, in term of performance and semantics. So we invent the object, which doesn’t live in a variable, but in a magical space that can be accessed from anywhere. No need to copy objects around, only their identity. That’s what pointers and references contain.

The only difference, in C++ terms (which I adopted here), is that pointers need to be dereferenced explicitely, while references are automatically treated “as if” they where the object itself (except for assignment and identity comparison).

In C++, everything is explicit. Classes define values, but you can choose to create them in the heap to make objects, and you manipulate them through differently typed variables (pointers). Every function or method specifies the exact type of its arguments, pointers or plain types. The hidden self argument is always a pointer.

In Rust or Go, same deal, only with a bit of syntactic sugar to automatically dereference pointers or take pointers to values. Methods are also written for specific receivers (plain type or pointer to it).

In D, you decide when writing a class whether it’s going to be only values or only objects, so the syntax for using them is almost identical. But arguments can have a ref keyword to be able to modify the outside variable, practically allowing you to have pointers to structs. The hidden this argument for structs is itself a ref.

And there you have it. The more flexibility you want, the more syntax you need (dragging those pointer types around for instance). It’s also more explicit, you always know what is what (pointer or not). On the other hand, if you want something simpler and less verbose (value/object-ness decided by class writer, manipulation of both with identical syntax), then you have less flexibility and transparency.

Full disclosure is – for sool – too much information. I discussed this before, but I think the D way is the sool way, because it’s simple and in most cases sufficient. And when really necessary, it’s easy to box a value in an object. The only thing you cannot ever do is use an object as a true value. But you can semantically reproduce the behavior by doing copy assignment, content comparison, and even internizing. Close enough.

For the deep struct access and return issue, we only need the ref passing and returning. And all our problems are solved. Yes they are.

Methods

One last thing left. In the grand “every action is a method call” scheme, we force every function to be attached to a class and have a self. This gave us two problems:

• no void or object-less functions possible (but they’re nice for factory methods and static class functions, not to mention anonymous functions, especially callbacks)
• struct methods must be sent to ref self, but object methods don’t need to, so which is it?

Also, in low level, methods are really just functions in class namespaces, with hidden self arguments, and nice call syntax.

Lua only has functions, but syntactic sugar to make them look like methods if you put them in tables.

function Foo:bar() end      -- is really:
function Foo.bar(self) end

obj:bar(arg)                -- is really:
obj.bar(obj,arg)

And D actually lets you call functions like methods, transforming their first argument into a receiver:

void do_the_foo(Foo f, int arg)
{
}

// later:

Foo f;
do_the_foo(f,20);   -- is exactly the same as:
f.do_the_foo(20);

Oh see how beautiful this is! Can we design a system that follows the beautiful Lua tradition of simple core concepts, and syntactic sugar?

Classes

The first and foremost purpose of writing a class in sool is to name a type with a specific data layout (the members). But in the same block, we can also add methods. How about saying that writing methods is really just writing functions with the hidden self argument. Litteraly. Instead of conceptually and in hidden form.

object Foo
    uint i

    method uint add_it(uint meh)
        return i + meh
    end
end

Would be strictly equivalent to:

object Foo
    uint i
end

function uint add_it(Foo self, uint meh)
    return self.i + meh
end

Thanks to the fact that argument types are part of the function’s selector, there is no inter-class collision risk. If the first argument is a Foo, this is conceptually part of the Foo class.

Of course, that requires having functions as a language feature. Say we do. They are local to the current module, so no name collision there either, but they are exported just like classes.

Remember extensions, to add methods to classes? Ha, again, they are just here to help with the syntax:

extend Foo
    method print_your_i()
        print(i)
    end
end

function print_your_i(Foo self)
    self.print(i)
end

Exactly the same! And so transparent! This is what happens at low level. Why hide it? You never have to write functions, if you prefer the “method” syntax. But it’s the same!

Also: choose if your self is ref or not:

function blah(ref Foo self)
    self = Foo()    -- haha, changed self!
end

-- later
local f = Foo()
local f2 = f
f.blah
assert(f is f2)     -- FAIL

It’s transparent and nice.

Let’s move the rest to a new article.

Yet another Ouya review (spoiler: it’s great!)

Finally, I got my Ouya! I backed the project on Kickstarter and received my Ouya with two controllers.

I am not sure exactly what model it is, nor I am actually sure of how many models there actually are (at least pre-release and retail, plus a Kickstarter special edition, but that might be just a different color). Having ordered two controllers, my order got pushed to the end of the queue, and I got it quite late. Hopefully it means that it’s also a most recent build (ie. retail?)

Here’s a few thoughts (some specifically addressing comments read on the web since the first Ouyas were shipped).

Outside look

Pros:

• Elegant, sleek, nice cold metallic feel.
• Box is small and heavy enough, feels solid.
• Overall professional looking.

Neutral:

• Box is so small that it doesn’t hide the two cables that stick out the back. No “console topples over because of cable rigidity” for me though.

Controller

Pros:

• Fits very nicely in (my) hands.
• Also heavy. Nice texture. Doesn’t feel cheap or plasticky.
• Magnetic faceplates are a nice modern touch (no mobile parts that seem like they would break if you forced on them). Then again you need to remove them only to change the batteries, so not that often.

Neutral:

• Touchpad. It works fine (no particular lag), but I just don’t see the point on a console. Menus are much easier to navigate with stick/d-pad and buttons. But it’s there, so it could be fun to see an actual creative in-game use.
• Right-thumb buttons (which spell “OUYA”) have the same colors as the Xbox ones, but different lettering. Y is on top like on Xbox, A is on the right, unlike on Xbox. Just a little gymnastic to get used to.

Cons:

• The triggers are squeaky and don’t feel smooth. You can feel the springs inside. This might be why people have been saying it feels like a toy. They are perfectly functional, though.
• The d-pad is very soft and doesn’t move much. No click feeling when pressing or releasing a direction. But it’s not that much of a problem in menus with visual/audio feedback. Must test more in-game situations.
• The Xbox-like placement of the sticks (but that’s a personal preference).

Myths (?):

• I haven’t experienced any kind of controller lag at all. Note that my TV has a “PC mode” that removes postprocessing to get best response time possible. Without this mode I got – indeed – a noticeable lag, but it is of course not the console’s fault. People have been mentioning lag related to distance with the console. I play 2~3 meters away, and the Ouya is even hidden behind my TV. Some games might also have horrible software handling, but the few “top” games I tried are just fine. Maybe this was fixed since the pre-release versions. Maybe people just have crappy TVs. I simply didn’t have the problem.
• Buttons getting stuck under faceplates. Didn’t happen for me either, but maybe I haven’t played too frantic games yet.

In any case, you can use regular USB gamepads (Xbox, PS3, Wii, random brand) if the game supports it (and most of the big games do). I think that the Ouya gamepad is just fine, even though it could be improved in future versions (triggers). But I also love the idea that you can plug whatever pad you already own, and have immediate couch-gaming parties with 4, 6, or who knows, 10 players without additional cost.

System

Pros:

• Fast boot.
• Quite original deep red color theme.

Neutral:

• Entering wifi password and account information using gamepad operated keyboard is tedious, but I suppose it’s the same on any console. Also, you do it only once.

Cons:

• System update at first boot can be longish, especially via wifi.
• Must enter credit card information at first setup, even if you don’t buy anything. You can probably put a bogus number, but I haven’t tried. Also, there is a parental control option you can setup to prevent buying without a password.
• Wifi connection is easily lost (is this a remnant of mobile power saving?) but most of the time you just need to redo what you just did and it works right away. I’m considering pluging an Ethernet cable.
• The occasional Android-looking dialog box breaks the visual look and feel a little bit. Not dramatic.
• Turning it off from the menus doesn’t seem to work so well (it turns back on when I change the source on my TV). But you can always just press the button on it.

Game shop interface

Pros:

• Straightforward “Play” menu with your installed games, and “Discover” for the shop.
• Games are automatically sorted (in principle) by popularity.

Cons:

• Thumbnail display is a bit slow on wifi (again, might try a wired connection instead).
• No separate display of the games currently queued for downloading. Difficult to find them again to cancel.
• Categories and “playlists” are a bit messy, but you can always do a text search if you know what you’re looking for.

Ideology

Of course, all of these things are details (except deal breakers like broken controller, if it was the case). On a “big” console, things like clumsy interface or lack of polish are totally forgotten, and people still throw their money at them.

What matters is games. I won’t review games here, but let’s just say that for the moment there is, as expected, 80% of crap, 15% of OK, and maybe 5% of great. Let’s just keep in mind that:

• The platform is open for development. Free dev-kit, no developer subscription, no publishing cost. Any PC/Mac/Linux can develop for Ouya. Compare this to contracts, NDAs, physical devkits to buy/rent, long review processes, etc.
• The Ouya shop is open as well, under very light conditions (not totally broken, no porn, no hate, etc.) Popularity rankings will sort them out.
• Shop policy of “some free to play element” (completely free, demo, time limitation, IAP, whatever).
• Even without the shop, you can sideload any game/app that you found shared on the webs. You own the device and you can do WTF you want with it.

To me, as both a player and a developer, this is what matters. It’s a major break from the classic console format where everything is tightly controlled by the manufacturer. In a way, it is indeed a small “revolution”.

But is it a relevant revolution? Why do we need an open console?

Some buyers (and more concerning, some magazine reviewers) only see the 100$ pricetag and expect a competitor to Xbox and PS and Wii. This is obviously wrong. Of course, the console is far less powerful, and no, Witcher 3 won’t run on it. But let’s be honest, in terms of design, graphics and fun, SNES games are still relevant today. You don’t need billions of polygons and terabytes of textures to make a pretty, clever, fun game. Ouya might be a nice wake up call.

The other very wrong expectation is that Ouya will let you play mobile games on TV. Not only this is simply not true (no Android shop, minimal porting to do), but it’s also wrong. Touch controls and gamepad controls are fundamentally different and shape the games designed around them. Ouya is meant to be an actual console, that enables local and online multiplayer, longer play times, rich “non casual” content and gameplay, full HD screens, etc. It is “just” less powerful than the big guys.

But why a console at all? You can have all of this on your basic PC anyway.

I’ve always been PC gamer and I never really found the appeal in the big consoles. I update my PC hardware once in a while, and I can play all the games I need, be them indie, retro or AAA, with keyboard or gamepad. But I am a gamer, and not everyone is willing to have a destkop PC box under their desk, or spend 150 euros on graphic cards (and yet, I’m not such a big spender). The Ouya has the benefit of the internet enabled console:

• trivial setup
• no worries about specs
• no need to buy additional PC gamepad
• immediate access to games

100$ is the price of two AAA games for PC/big-console. For the price of a new Wii U in my local shop (250€), you get an Ouya and probably more than 30 Ouya games, because they seem to follow roughly the mobile game pricing.

Ouya is of course very indie oriented, but this could be a good thing. Maybe it’s the bridge we need to get indie games to be more recognized in the general public. Buy your kids an Ouya, and they might spend hours and hours trying free games and demos, and then inviting their friends over for “true social” gaming afternoon, instead of mindlessly fragging random people from the internets on Halo 4, or spending monthly subscription fees on MMOs raiding dungeons with strangers.

Don’t get me wrong, I love big productions that knock my socks off with polygon fests, epic cutscenes and symphonic soundtracks. But they have to be good games too, and smaller, pretty, smart games can be just as good in terms of sock knocking (hello, FEZ…)

And who knows, with the openness in mind, it might inspire a new generation of game developers to create more meaningful games, where hardware is only the slave of gameplay, design and art instead of being their master.

Of course, I’m an idealist, and that’s why I backed the project on Kickstarter in the first place. But all biases removed, it’s still a pretty neat little machine that does exactly what it’s meant to do: run games.

All the Ouya needs now is the support of a few famous studios, who with their games ported (or exclusive) to it will generate a snowball effect and bring more and more attention, respect and success to this beautiful idea.

Structs and references (again)

Structs, or value classes, have been a problem since I decided I wanted them. Their only raison d’être has been performance, as functionally they can be entirely replaced by objects. And additionally, the value type semantics is inherent to some of the built-in classes (number, boolean, text, etc.), so it’s a feature that we’ll need at low level no matter what. Might as well make it available to the user.

Reminder: the struct problem

Structs were originally defined semantically as “exactly like objects, but always copied at assignment”. And implementation wise, allocated on the stack (or even registers if the compiler sees it fit).

This comes with two major problems:

1. The self parameter for methods defined on structs would be itself a copy of the original, therefore making every struct immutable.
2. Even assuming the first problem solved, member access is a method call, and therefore in case of struct members, would return copies, making struct members immutable.

After several rounds of self discussion, I had come up with the solution that the self parameter would be actually a reference, and that some methods (in particular member accessors) would also return references, which could be returned immediately as references as well. Every other use would be a copy.

This solution was utterly unsatisfying, because of all the hidden shenanigans used to make “expected behavior” work:

obj.structMember.foo = 5
someStruct.modify()

What would Jesus do?

When in doubt, steal. Both C++ and D have structs and methods on structs. Assembly analysis reveals that they (obviously) pass the this parameter as a pointer, and access it as a pointer (this-> in C++, and this. in D).

However, since both languages also have pointer and reference syntaxes, any other plain struct argument or return value will be copied unless stated otherwise.

Go and Rust, however, have an interesting twist on this: methods are defined not in classes, but for specific receivers. In other words, the self or this parameter is explicit. And it can be of either type: the plain struct, or a pointer to it.

The method syntax there is a very thin wrapper over the low level reality, which is that methods are functions. And if you can decide to pass parameters by copy or reference to a function, why not also the not-so-special self?

If you define a method on a plain struct, then it will be copied, or equivalently, read only. If you define a method on a reference to a struct, then obviously, the struct can be modified in place.

And in a funny manner, it works also for primitive value types. With our extension syntax, we could very well have (assuming passing by reference):

extend num
    method doubleIt()
        self = self * 2
    end
end

-- somewhere
local a = 5.0
a.doubleIt
assert(a == 10.0)

In any case, it seems that self must be passed by reference, always. This was already our earlier conclusion. What about problem 2?

Return by reference

The second problem is linked to the fact that sool has member access done through methods and therefore returning a member (or an array element, too) would return a copy, making it impossible to modify without reassigning a whole new struct.

In C and others, member access through the dot is really, in low level, returning a reference (the address of the field inside the struct), which is then used to read or write info.

What if sool always returned structs by reference?

-- obj.struct is "a reference"

obj.struct.doThing      -- or obj.struct.foo = 1
local copy = obj.struct
return obj.struct

Look at the three things we did there:

1. calling a method on the returned struct
2. assigning the struct to a local (or something else)
3. returning the struct

The first one would, as expected, call the method on the remote struct, by forwarding directly the reference we just received from obj.

The second one would copy the struct, because the reference is not a type (like a pointer), you can’t store it or modify. It’s always automatically dereferenced.

The third one would return the reference directly, as expected for chaining accesses.

So far so good.

What happens with:

method Struct giveStruct()
    local foo = Struct()
    return foo
end

We’re supposed to return foo by reference, but it’s a local, it’s living on the stack, its life ends when the method returns. It’s a classic error in C.

Rust allows it, in the form of the “borrowed pointer” a general purpose pointer that can point at anything of the right type. Even locals from inner functions. How does it work? Simple, the local is boxed into a heap allocated memory chunk, and a reference to that is returned. Of course, garbage collection takes care of the details after use.

Wow, wait, isn’t that horrible performance? Allocating memory for a return value? Well, it can probably be optimized somehow. First if the method is inlined, the whole allocation step can be bypassed. Also, the calling method might reserve some stack space and have the callee fill it with the value. The compiler might be doing that anyway, when returning “normal” structs.

What matters is that the semantics at high level are respected. If you return a local struct, all that can happen to it is calling a method on it, in which case it works, or be copied somewhere else, which works as well.

Are there downsides to always return structs by reference? It can be a tad confusing that value objects are always copied at assignment, except the “special assignment” that is returning a value. Then again:

local foo = obj.member

obj.member is the return value, it’s a hidden temporary local variable. We might argue that it hasn’t been assigned yet. Only the presence of the = sign could be considered as an “assignment” in the rule that struct are copied at assignment. That and when passed as arguments, because they get a new local name in the function.

Again, as long as the semantics are clearly defined, everything is allowed. But it’s still not very satisfying. It feels like an added hack, for something that should be a core feature.

Finding the culprit

The second problem was based on the fact that member access in sool is done through methods.

foo = obj.member    -- is really method: Type member()
obj.member = foo    -- is really method: member=(Type)

This is always fine with objects, because they are stored as references already. The problem arose with structs.

So why did we have this in the first place?

1. So that member access and method call have the same apparent semantics (encapsulation, from the outside it doesn’t matter if it’s an actual member or if you computed the result, or set something elsewhere than in a member)
2. So that member access participates in the class’s interface (for dynamic dispatch)

Earlier, we still had inheritance and the idea was that you could override a member with methods. Now we have interfaces and the idea is that an object with a member Foo foo works just the same as an object with a method Foo foo().

So I decided, members only define the memory layout of the object, but they are accessed with compiler provided methods, the getter and the setter. And you can also define methods that looks like getters and setters, and make the object look like it has another member.

First point: can be waved by just allowing it in the grammar. obj.foo can be either accessing member foo or calling method foo, whichever happens to exist.

Second point: the compiler can provide glue methods, used specifically when casting an object to a generic, to access its members as if they were methods. No fuss required.

And then define “member access” as this magical operation that brings the desired nested variable to first level, to be used as right or left value.

To be fair, documentations don’t always explain what member access is. D just tells you what the syntax for it. Lua has a fuzzy explanation about variables being location where values can be stored. Rust is quite formal though, about lvalues, rvalues, and what they mean in different contexts.

Anyway, the result is that these rules – explicit or not – involve the fact that an expression is used:

1. as a value as rvalue
2. as a location as lvalue

Even the most evident thing, assignment, is actually quite confusing when you think about it.

Even then…

Assume we define member and array access as the magical thing that always works, and is separate from method call. We still want the glue accessors, and the glue indexing so that we can build wrapper objects that look like containers (especially when embedding):

object Foo
    method Elem [](uint index)
        return Elem()   -- dummy
    end

    method []=(uint index, Elem e)
        -- discard
    end

    method Elem fakeMember()
        return Elem()   -- dummy
    end

    method fakeMember=(Elem e)
        -- discard
    end
end

-- later
local foo = Foo
foo[19].modify()
foo[50] = Elem()
foo.fakeMember.modify()
foo.fakeMember = Elem()

Looks cool. Except that for this particular Foo class, the syntaxes for field access and indexing will not be the magically defined low-level ones, but resolve as simple method calls.

In particular, the modify() calls would happen on the variables that were returned. If we don’t have a syntax to return a reference (ie. an address), we can’t extend the “expected behavior” to manually defined accesses and indexings.

Explicit references

So it’s clear, we need references. Maybe not as a full blown recursive type, but at least for the matter at hand: return values.

-- suppose foo is a member or in an array we know of

method ref Elem fake()
    return foo      -- return the address, not the value
end

-- elsewhere

local foo = obj.fake    -- dereference, copy
obj.fake.modify()       -- modify original!
obj.fake = haha         -- yep, we know where it is!

Huh, we don’t even need the setter methods anymore. Any method that returns a single reference can be used as if it was a member. Thus we can even come back to the original concept that member access is method call. A method call that returns a ref, and can be used both as left and right value!

Same goes for indexing. Same goes for anything. Would that be the magical solution? We needed the reference at least at low level anyway for the self param, so why not for return values.

Note that it’s necessary to have them for objects as well, now that the fake= style setters are gone. But when they’ll be used in rvalues, the compiler will happily bypass the whole “return a ref and deref it immediately” part.

We lose the ability to use foo= setters for doing anything else than actually setting a real variable, like doing input validation. Maybe it wasn’t a killer feature anyway.

Conclusion: it’s actually pretty simple

• for value classes methods, the self hidden argument is passed by reference
• any method with a single return value can be declared to return by reference
• a reference (as returned by such method) cannot be stored, it must be either:
  • the recipient of a message
  • assigned to a variable, which copies the original variable
  • returned as a reference
  • used as left value in an assignment
• each member Class name in a class has a compiler provided accessor method ref Class name() that returns a reference to it

And I think that’s it…

Fun stuff

• obj.foo(1,2,3) = 4 is completely valid and simplifies the grammar. Every method call can be a left value, the validity is determined by semantic analysis (is it a reference?)
• built-in read-only variables: make an accessor wrapper. Return normally, it’s a copy, return by reference, the caller can modify it (whether it’s a struct and all its content, or an object reference)
• return by ref or not is now part of the method’s prototype, and participates to interfaces, for binary compatibility between methods in dynamic dispatch. Compiler could automatically wrap by-ref into normal, though.
• the word “reference” is getting a tad confusing, given that it’s the one we use for these object pointers that are automatically dereferenced

A change of words

Since it can be confusing to have “reference” mean two different things (albeit related or even similar), maybe we can slightly hide this concept in a higher-level point of view. But still explicit, because we don’t want to hide things too much.

We now know that this new “return by reference” concept is essentially meant to wrap containers and provide accessors to internal (or in any way remote) variables. And that the most natural accessors are these that the compiler provides for the class members. Why not call this an “accessor method”, and make it even clearer:

object Wrapper
    Struct struct
    #Struct array

    accessor Struct fake()
        return struct
    end

    accessor Struct [](uint index)
        return array[index]
    end
end

They’re still methods, but they return a “magical thing” that makes the expression a left value, and makes you modify the original returned thing, not a copy.

Arrays and slices

Arrays in sool, like in many modern languages, should be a little bit smarter than C arrays. C arrays are just a chunk of contiguous memory, with a pointer to the first element. All the rest is pointer arithmetics. The biggest issue with these is that the length of the array is not known, so you always need to keep it around and make sure your accesses are valid.

sool has to be memory safe, and as much as possible, prevent logical bugs as well. Therefore, sool arrays must know about their length, and accesses rendered safe via compiler enforced rules. On the top of my head, there are two main ways to do so.

Length + data

The first obvious way to have an array know its length, is to stick the length at the beginning of the array, in the chunk of dynamic memory. The runtime can easily check the length before any element access and generate appropriate errors.

That’s a reasonable way to do things. The array is manipulated by reference, just like a regular array. You can have functions to duplicate, resize, insert, etc. Every reference to the array sees the same array.

One particular downside is that you can’t use the same data type to refer to sub-arrays. All the arrays must be “unique” and their reference point at their beginning, where the length can be found.

However, you could share a subarray by giving the reference to the array, and an offset inside of it. It’s a bit convoluted, but would work. And more importantly, it would have to be a different type.

Slices

What if the length information was not included in the array, but in the reference to it? When you allocate the memory, return a pointer to it, and the length, bundled together in a special type called slice.

Now imagine you’d advance the pointer by 10 elements, and reduce the length by 10. Woo, subarray! They point at the same data, and they both have a valid length information. We assume that we are in a garbage collected environment, so as long as any part of the array is accessible, the whole chunk will exist.

Slices are pretty convenient for subarrays, and if they have fancy semantics, they can make some operations very easy. Anything is possible:

s = #uint(100)      -- s is a slice representing an array of 100 uints
sub = s[3,6]        -- sub is a subslice of s
s[1,4] = foo        -- assign foo to elements 1 to 4
s[1,2] = s2[6,7]    -- copy a slice to another
s[] = 0             -- init entire array
lol = s[2,6] + 4    -- apply operation to entire slice

All of this can be figured out when making the library, as long as the base semantics are well defined.

Of course, you have to remember that slices actually share the same data, they are just different views of the same chunk of memory, so modifying through one will have consequences for others. But that’s called aliasing, and it’s nothing new.

And note that we don’t need a separate type for the full array. We just remember that the first slice returned at allocation actually spans the entire array.

Growable arrays

A modern language wouldn’t be called dynamic if its arrays weren’t resizable. You can always fake it by creating a new array with the desired size, copying the elements that fit into it, and delete the old array. But we all know that it leads to terrible performance for even the simplest operations like pushing N elements at the end of the array, the dreaded O(N*N) complexity.

The “proper” approach is to do what C++ does with its std::vectors, that is, always allocate more than the requested size, and pretend that the array is smaller than it actually is. When pushing new elements, you then magically find room right here at the end of the array, and just increase the length field accordingly. When reaching the actual end of the array, actually resize, and add a lot of free space at the end. Rinse and repeat.

Science tells us that the most efficient way to do this is to double the array’s size when reaching full capacity. This leads to the so called “amortized constant” complexity for pushing at the end. That is, pushing N elements at the end of the array will take, on average, N operations. Which is, on average, pretty cool.

One way to do that is on the language side, a wrapper around the basic array, just like std::vector. Add a “capacity” field, which gives you the actual size of the array, and handle the logic of resizing only when your full capacity is reached.

Or you can do it the D way: be a smartass, and always allocate chunks in power-of-2 sizes. That way, if your array is 10 elements long (it’s actually 16), and you push something at the end, the system tries to resize to 11, which is really 16, and no realloc occurs. The length is returned as 11, and you had a constant time insertion. Only when you step over a power of two will an actual realloc occur. Magical built-in amortized constant time appending!

Slices and realloc

That’s all very nice, but what happens with slices? How do these “vector-like” operations work with a slice that refers to only a part of a chunk?

The problem is that we don’t really know when an array will be resized in place, or when it will be copied to a fresh new chunk. Assuming the “power of 2” allocation rule:

a = {1,2,3,4,5,6,7,8}
b = a

a.push(9)   -- this triggers actual realloc

Here, a is given a reference to the new chunk, but b still refers to the old one. They are now separate arrays. If you intended to use b as a shortcut to a in an another part of the program, you will have problems. a might be your list of game objects, and you can’t allow different parts of the program to see unsychronized lists of game objects. Darn.

Of course, you can always box the slice and use this everywhere. Make sure that everyone uses the slice inside the box, instead of their own slice. That’s one more level of indirection, and that is how Lua arrays probably work.

Note that semantically, we could make sure that no function modifies (grows) a slice in place. By forcing you to take a return value, it makes clear that it might be something else than what you passed:

a = a ~ elem    -- and not a.push(elem)

But then we lose the “array as an object” semantics that Lua has, and convenient methods like in-place concatenation, appending, insertion and deletion. These additional methods would have to either return a new slice, or act upon a boxed slice only (an actual object).

Slices and growth

D somehow manages to still have the slice as the main (only!) way to manipulate arrays, and do appending and concatenation directly on the slices. Best of both worlds? We know that for performance reasons, D always tries grow/reallocate in place. But wouldn’t that be a huge mess if many slices referred to different, possibly overlapping parts of arrays?

Yes. However, the D semantics add the condition that “It will always do a copy if […] resizing in place would overwrite valid data in the array”. Valid meaning being part of another slice. Yikes. The D runtime keeps metadata about all slices to check what pieces of array are actually used and which are free to overwrite. That sounds like a lot of overhead.

According to this article, it’s a tad less systematic than that. The only information kept by the runtime about an array is the number of used bytes in it, dividing it into two contiguous parts: the valid data, and the unused data. If a slice ends at the end of the valid data and tries to expand, it will expand into the unused data. Any other growth operation will trigger a reallocation and a copy.

So the D arrays actually have a “used length” field at their beginning, and thanks to the garbage collector, we can always find, from a pointer/slice, the base object to which it points. But this is apparently is fairly costly operation (log(N), according to the same article), so the D runtime caches the last few lookups to speed things up, resulting in a convenient and efficient system.

Final note: all the D library operations for inserting into arrays actually act on slice references, thus allowing to modify them in place, in the likely case that reallocation will be triggered. In sool terms, this would mean writing methods on boxed slices. The alternative is of course having methods that return a new slice.

What to do?

The D slice seems to me like the ideal system. It’s lightweight and efficient. And as long as we have the exact semantics in mind, very clear and simple.

Both Go and Rust have somewhat equivalent systems, except that there, the array itself is a base value type (and can be stored on the stack), and the slice is a reference to a boxed version of it. But quite the same.

The art of closures

In the previous episode we talked about callbacks, and more generally, of method delegates, which we decided would be only casting to interfaces with remapping of the method names. A concept often associated with callbacks is the anonymous function. In Lua or AS3, functions are first-class elements, can be stored, and called later.

local fun = function(i) return i*2 end
print(fun(2))   -- prints 4

This is especially useful for callbacks

lib.registerCB(function() print "done" end)

In our approach in sool, there are no functions, only methods on an object, and methods are always named: “when you’re done, call my method onCallback“:

object Foo
    method initLibrary(Library lib)
        lib.registerCB(!onCallback)
    end

    method onCallback()
        io:print "done"
    end
end

But sometimes it’s quite cumbersome to make a whole new method just for one meager instruction. And you might end up encumbering the method name space (callback1, callback2, etc).

What would be the equivalent of the anonymous function in sool?

Anonymous method

Well, obviously. All objects can do is send messages to each other and run methods. So any piece of code has to be a method on an object. No problem. Let’s make anonymous methods:

lib.registerCB(method() io:print "done" end)

This would create a method on the current class, without a name, and the expression would directly return self casted to the generic class required as a callback.

This also means that this floating method block can only appear where an interface can be inferred, or something is explicitly casted:

local cb = self to Callback with method(uint i) return i*2 end

Hey, it’s not even that bad! Obviously, these are real methods and can use the members and methods of the object they’re added to:

object Foo
    uint i
    method init(Library lib)
        lib.registerCB(method() i = i*2 end)
    end
end

To close or not to close

So far, these anonymous methods are exactly like named methods, except they have no name and are defined in the middle of other methods. But languages often associate the concept of closures with anonymous functions. Simply, it means that anonymous functions can access local variables in the scope in which they are defined. Every time the code is called, the environment is “closed” and a new closure is created: a pointer to the function, and a bit of data representing the environment when it was closed. Example in Lua:

local funcs = {}
for i = 1,10 do
    local tmp = function() io.write(i, ' ') end
    funcs[i] = tmp
end

for i,func in ipairs(funcs) do
    func()
end

-- prints: 1 2 3 4 5 6 7 8 9 10 

And the “upvalues”, the outside locals, are modifiable. Different functions can even share the same closure :

do
    local i

    set = function()
        i = 10
    end

    read = function()
        print(i)
    end
end

print(i)    -- prints nil   
set()
read()  -- prints 10

Outside the do ... end bloc, the variable i does not exist anymore. The functions work on an anonymous hidden object that initially contains a copy of i. But if the original variable is still in scope when calling the functions, it is the one that gets changed:

local i = 1

set = function()
    i = 10
end

read = function()
    print(i)
end

print(i)    -- prints 1
set()
print(i)    -- prints 10
i = 20
read()      -- prints 20

The ability of functions to “close” on their environment is super powerful. A closure is like a function with state. It’s quite equivalent to a functor with members, except it’s all anonymous. We could have things like this:

local arr = {1,2,3,4,5}
local sum = 0
arr.apply(method(uint v) sum = sum + v end)
sum.print   -- prints 15

And things like return types could even be inferred.

In terms of implementation, full closures as described are a little bit complicated, because they force to determine which local variables are going to be upvalues in a closure, and these need to be allocated on the heap, so that the closure can still access them once the original went out of scope. But heh, it’s not that bad. And with our syntax, nothing prevents you to also write anonymous methods on objects other than self:

register(obj with method()
    -- do obj things
end)

I like this. I fear feature creep, but remember the original goal of sool: a language as usable and dynamic as Lua in appearance, with an object system and strong typing. Anonymous functions are a must for dynamic behaviors, and anonymous functions are quite crippled without closures.

The art of callbacks

I’ve been learning quite a lot of Flash recently, and therefore, of ActionScript 3. It’s an interesting language, and I might make a small review of the features I like. Today however, I’ll focus on the library part of Flash, and in particular its event system.

One of the original goal of sool was to make a general purpose language, but that would be particularly fitted to developing games, in particular prototypes or gamejams. Hence the emphasis on easy to use and fast to write. And necessarily, the idea that a game library (not to say “engine”) will probably have to be written partly in sool at some point. And one particular thing in high level game libraries is that they often rely on the availability of callbacks for event systems.

When using a low level multimedia library like SDL, the typical game loop is:

• poll events (raw input such as mouse and keyboard)
• treat events
• update game state
• draw

In higher level libraries such as Flash, it’s more a matter registering event listeners. If an object needs to react to certain events, they need to tell Flash “oh hai, please let me know any time this happens”. For instance, a click, a mouse move, or even every time a frame starts.

addEventListener(Event.ENTER_FRAME, update);
addEventListener(MouseEvent.CLICK, onClick);

And the “let me know” part is done through a callback. Of course, Flash didn’t invent callbacks. The C standard function sort uses a callback for comparing elements in an array. In C, the callback is a function pointer. In higher level languages they might have other names or not be exact equivalents, but they exist often.

What about sool? Firstly, we don’t have functions, only methods, but that’s almost the same. Let’s see first if we can do without.

Don’t call me back!

We could of course rely simply on polymorphism. If we take the example of the hypothetical MouseEvent, the library could define an interface MouseEventListener and force you to comply to it:

interface MouseEventListener
    onMouseEvent(MouseEvent e)
end

-- and you'd use it:

local game = Game
system.registerMouseEventListener(game)

Then every time the low-level system detects a mouse click, it will call generate an event event and call game.onMouseEvent(event).

That certainly works. But it’s quite restrictive. It forces you to use a certain method name (that could collide with your own), and more importantly, it means that a given object can only have one particular method used as callback for this specific back-caller. Since the point of event systems is to be able to swap callbacks at runtime to achieve complex state machines, that’s a bit limited.

Certainly, we can define helper classes that simply wrap the other method:

object Helper
    Game helpee
    method onMouseEvent(MouseEvent e)
        helpee.onOtherMouseEvent(e)
    end
end

But that’s definitely horrible.

Real callbacks

Furthermore, callbacks can be used for a variety of things that may require many callbacks on a single object. With the object and message metaphor, callbacks fit in perfectly: “send me this message when you’re done”. “Call foo on me in five minutes.” “If a keypress comes, tell me to handleKeyPress“, and so forth.

To do that, we need a syntax to give the information of which method to call later on. In C, where parentheses are mandatory for a function call, the function name is itself a pointer to the function. In sool, the naked method name is already a call to the method. We need an additional token to mean “literal method name”. We don’t have many symbols left.

timer.registerCB(@my_method)    -- or &, $, `

And on the caller side

object Timer
    Callback cb     -- problem 1
    method registerCB(Callback cb)
        self.cb = cb
    end

    method update()
        // assume timer timed out
        cb.call()   -- problem 2
    end
end

Whatever the syntax, several questions are raised.

Problem 1. In C, the function pointer is a complex recursive type that embeds the arguments and return types. foo might be a pointer to a function taking an int, a uint and returning a pointer to char. Since sool is fully typed we would need something similar: a type that includes arguments and return type. Suppose something like:

@uint(text,num)     -- a method that takes a text and a num, and returns a uint

This “method type” could be used to declare method arguments and class members. We need to store the callback before we can call it. But everything in sool is an instance of a class. So we would have objects (or values) which contain callbacks and themselves answer to methods, can be assigned, etc. So @text(uint) would be in fact a class, the class of callbacks that take a uint and return a text.

But beware, methods are not functions, they need a receiver. Is it automatically the one who emitted the callback object? Is that information included inside the callback object? Probably.

method text my_method(uint i) end

-- later
local cb = @my_method

would create a callback object of class @text(uint), passing it the information of self and of where to find the actual method.

Wait, that sounds suspiciously close to defining an interface and casting self to the corresponding generic type. Except that interfaces require fixed method names while this allows you to pick any method you like, as long as the types match.

In these examples, using type @Foo(Bar) and letting an object Object write @my_method is somewhat equivalent to defining:

interface Anonymous123
    Foo call(Bar)
end

object Wrapper123
    Object receiver
    method Foo call(Bar b)
        receiver.my_method(b)
    end
end

-- later
local wrap = Wrapper123(myobject)
local cb = wrap to Anonymous123

-- and somewhere else
cb.call(Bar)

Of course it sucks to have to write it, but the mechanism is already in the language. Dynamic dispatch is nothing more than object pointers stuck with method pointers to them. Except that interfaces require not only matching types but also matching names (“can you do uint foo(Bar)“, versus “can do you anything with a Bar that returns an uint?”)

Interfaces with renaming

Inside a generic type, the original name of the method in the non generic type doesn’t matter, it’s just a function pointer. What if the casting syntax could be enriched with a way of selecting the method you want?

interface Callback
    uint call(Foo)
end

object Meh
    method uint my_method(Foo f)
    end
end

-- later
local meh = Meh
local cb = meh to Callback with my_method as call

Lulz. “When casting, map my_method to the one supposed to be call in the interface”. Could even have more than one:

meh to Callback with
    my_method: call,
    another: something_else
end

It seems that it would work, but it’s not very satisfactory either.

What would others do?

The D language has “delegates”, which are pretty much what I’ve been describing: a sort of “method reference”, that contains a receiver and a method to execute.

int delegate(int) dg;   // declare a delegate to a method that takes an int and returns an int
dg = &obj.meth;         // set dg to refer to method meth on object o
dg(5);                  // call obj.meth(5);

And of course you can pass delegates around, store them, call them, etc.

my_lib.registerCB(&this.onClick)

A delegate is really just an object reference and a function pointer. It’s clean and nice, but requires to have a new recursive type. In sool, the only type we have is the class, that can be templated with parameters. Even the array #num is just sool:array|num. We could have some standard sool:delegate, that would be a template as well. Unfortunately our templates have fixed numbers of arguments, so we’d need to have a different class for combination of numbers of arguments and return values:

object delegate2_1|(any ret1, any ret2, any arg1)
    method ret1,ret2 call(arg1 a)
    end
end

Unacceptable, (just like in my discussion of functors we had Predicate, BinaryOperation, etc.) And if we can’t provide these in standard (can’t really write an infinite number of combinations), it means the user would have to write his own delegate class when needed, thus doing a very low-level wrapping job.

Having the delegate as a language feature would imply having variadic templates. Oh lord.

Compromise

Since the low-level mechanism exists already (dynamic dispatch through interfaces), and that is needed to make it work is glue, maybe the compiler can fill in the glue. Syntactic sugar, whatever.

1. When you need to store “method pointers” or “delegates”, write an interface with a single method call and the appropriate types. Or use the few standard ones (interface templates with up to two inputs, two outputs, for instance).
2. Ask the user to provide this delegate as a generic instance of that interface.
3. Have a syntax that lets you select an instance and a method, such as &self.foo or deleg(obj,meth). This has to be stored immediately as a generic instance of a compliant interface.

Semantically, what the compiler does is make a wrapper class that statically wraps the given method in the call method. In reality, it can bypass the actual wrapper class, and simply store the instance reference and the method pointer, exactly as when casting an object to a generic. That way, if your object already has the call method, it’s strictly just a cast (and you can pass self or any other object that complies). Otherwise you do the “cast to interface with remapping”, to select another method than call. Being able to remap several methods would be nice too, if you need multiple callbacks on the same objects (onStart and onFinish, or something). Plus, the general mechanism of being able to comply with interfaces by simply changing your method names is powerful. Interfaces which were sets of prototypes, become sets of arguments types and return types. Even more generic.

The final syntax, I don’t know. It should be an extension of the casting syntax, obviously.

cb = obj to Callback with
    onStart = handleStart,
    onFinish = killPlayer
end

Doesn’t look so bad after all. And it could be shortened. If the expression is assigned immediately to a variable of the generic class (for instance also passed as argument), you don’t need to indicate it, it’s inferred:

lib.registerCB(obj with
    onStart = handleStart,
    onFinish = killPlayer
end)

And if there is no ambiguity (interface inferred, and the interface only has one method with matching types, or one possible mapping of the methods):

obj with handleStuff end
obj with doThis,doThat end

That’s quite short, and that would be the common case, for callbacks. It could be even shorter if self is implied, using one of our free tokens:

cb = !handleStuff   -- is actually "self to SomeCallback with call = handleStuff end". Not bad for sugar :)

Or maybe:

cb = &handleStuff   -- reminiscent of function address, is also D's syntax
cb = `handleStuff   -- huh?
cb = @handleStuff   -- at does mean "it's there". Does it actually make sense?

Could even give a different object than self, for free:

cb = obj!handleStuff

Coolio, finally used my with keyword!