Adding += and friends to Leaf

Yesterday I finished a rather simple Kata from Codewars: the sum of a sequence of numbers. It was straight forward to implement, but I felt like it was missing something. It looked like this:

defn sequence_sum = (start : integer, end : integer, step : integer ) -> ( total : integer ) {
    for v in std.incl_range( start, end, step ) {
        total = total + v
    }
}

That total = total + v bugged me. I've become used to seeing total += v in other languages. Though it'd only be a simple convenience syntax, it now felt necessary. Time to add it to the compiler.

I also added the incl_range function to clean up the loop. Leaf doesn't have the traditional C-style for-loop, and I'll only add it once I find the use-case that needs it. incl_range is part of the standard library, written in Leaf.

Parser construction

First thing is parsing, as always. I added the operators +=, -=, *=, /=, and ++=. These all have the same precedence as the = assignment operator: grouping together everything on either side first. In simple terms, it has the familiar imperative semantics.

I started adding the support as a built-in function, as part of the typing phase. Something felt a bit off, like it was more complicated than it needed to be. I undid that work then opted to translate the syntax in the parser itself, so:

a += b

becomes:

a = a + b

Then let the typer handle this normally, unaware of the new syntax. It saves a lot of work and avoids any novel typing rules.

The conversion happens as part of tree rewriting. It's not truly that form you see above, but rather the tree form, then flattened trees of that transfromation are [funccall [⁑assign_op_add] [value-list [a] [5]]]] converted to [funccall [⁑assign] [value-list [a] [funccall [add] [value-list [a] [5]]]]].

Share the whole story

That's easy, but rewriting like that is invalid. Was I to copy the expression to both sides of the = bad things could happen. Consider something like this:

pine(a).b += c

What if pine has side-effects? If I expanded the form as before, it would end up evaluating pine(a) twice. That's obviously not desired.

This double evaluation comes up in several contexts. The typer stage already knows how to deal with it. A shared expression can be created that allows an expression to be used twice but only evaluated once. This is different from a variable assignment, which might involve type inference and conversion. The shared expression does no transformation on its own.

This shared expression is nothing more than a no-op transform that reuses the same sub-tree. If you want I could write an article with more information about this part. I warn you it'll be a bit drier material, as many things about compilers tend to be.

It was a nearly trivial change to make this usable from the parser, allowing the parser to transform the expression into this:

shared_expr(pine(a).b) = shared_expr(pine(a).b) + c

Where the two shared_expr components are the same sub-tree, resulting in just one evaluation.

I covered this in the obtuse test-case below. In practice, it comes up a lot more naturally, but requires additional types, functions and classes. This unit test is meant to be minimal.

/* EXPECT(61) */
//ensures the expression is not being reevaluated
var x : [ a : integer, b : integer ] = [ 4, 5 ];

var count = 0
var data : shared [ a : integer ] := [ 5 ]

defn pine = -> {
    count += 1
    return data
}

pine().a += 1
trace(data.a)
trace(count)