Milestone 1 revisited

So it turns out that I am an idiot. Well, I was being an idiot. Now perhaps not so much. I talked in the Milestone 1 post  about how looping eventually will overflow because of how it's implemented. In short, that I can't use tail call optimization because the compiler can't tell if the recursive call is in tail position, since conditionals are implemented in-language.

That was entirely true. But what I failed to realize (until last night, idly thinking on the edge of sleep) is that it doesn't matter if the recursive call is in tail position. Let's look again at our while code:

while (condition: ~>bool) (body: ~>void) => void {
    if condition { 
        body; 
        while condition body; 
    };
}

and think about how this gets compiled into CIL:

temp1 = condition
temp2 = new Closure({ body; while condition body; });
call if(temp1,temp2)

So while the recursive call is in tail position for the closure, the real eureka moment was realizing that the conditional was the thing that mattered conceptually. It was the function call in tail position for the loop. All of the internet articles reiterate how conditionals are special for determining tail call usage, and because I was so focused on the recursive aspect I did not stop to consider how doing things differently invalidated conventional wisdom.

Anyways, loops now work as expected without stack overflow and without needing to build them into the language. The code is in github marked as Milestone 2.

Changes to return and added debugging support

Two updates to talk about today.

The first is a change to how return works in the language. It now does not work. This is a side effect of making blocks into implicit closures. By doing that, it lets you pass them around (cool), but it makes it really awkward to return from them. I had intended to have return simply set a return value and exit, allowing the calling function to use the return value if it was expecting one. But even there, it becomes confusing if the return value is for the function or for the closure. In the end, I decided it wasn't really worth the confusion (for now).

So instead, Tangent will now do a little type inference with blocks (and functions). Similar to CIL, the return value for a function (or block/closure) will be the last statement in the function. So it works something like this:

f(x: ~> int) => void { }
g => string { 
    must-return-void;
    must-return-void;
    f {
       must-return-void;
       // ...
       must-return-int;
    };
    must-return-void;
    must-return-string;
}

So the normal Tangent order of operation inference works, but the target of the algorithm differs. For normal blocks, the last statement will need to return void, just like any other statement (or any other block). Otherwise, it provides a mechanism for basic anonymous functions.

The second change was the addition of debugging info to the compiler. If you start debugging versus the exe the compiler generates, you'll now be able to step through code, set breakpoints, inspect variables, etc. While it was a lot of work to wire the line/column info from source to compiler, there's not much to actually making the debugging work. One extra ILGenerator call to mark the reductions with their location in code. Visual Studio does the rest. I had done this with earlier revisions of the language, but it is a nice reminder of how powerful well made software can be.