Strangely Consistent

Theory, practice, and languages, braided together

Continuations (epoq diary 010)

Debugging is weird.

It's a fundamentally contradictory activity. I mean... you, the developer (by which I clearly mean "I, the developer", but let's commiserate together) obviously didn't make a mistake when coding up the thing.

Why would you make mistakes? That makes no sense. You coded the thing the way you did, because that's what you meant, and so, ipso facto, it's correct. And now you're looking for the mistake in it, going over the code again, even though clearly it's correct and the universe just doesn't realize it.

Maybe it's the compiler. Maybe some hardware error? Could be the laws of physics are broken.

And so, in a magnaminous show of good will, you're going over the code a third time, just to check all your assumptions. You look at a line of code, confirming that...


Ok, there's the mistake.

You discretely discard your draft email to the compiler vendor.

Ok, so it was human error this time! PEBKAC. One of those rare occasions. Programming is easy!

(Fair warning: this post is more of an expressionist painting than a full tutorial. It's best thought of as a retroactively recreated core dump of my thoughts as I found a bug.)

In my increasingly exciting race to the finish line, I'm implementing continuations in Bel. Well, I was, already back in June, but reality's stubborn refusal to run my code correctly prevented me from making any progress. The code, needless to say, looked fine. (Duh.)

Some other time, I'll have a go explaining what continuations are, philosophically. It does not matter for this post. I'll give a short list of what they enable in the language, though:

(In summary, continuations mess with your control flow.)

If we ignore the metaphysics and just look at what it takes to implement a continuation, it needs to be an object that captures a moment in execution. It needs to preserve the execution state at that moment. The execution state, for our purposes, consists of two things: what we've yet to compute (s), and what we've already computed (r). s as in (expression) "stack", and r as in "result" (values). Easy! We save those in a Bel-native object, and later when we restore it... doesn't work‽

As a side quest, I realized this is the point where I really shouldn't leak any internal implementation details out of the Bel interpreter (written in Perl).

Back in June, I wrote:

Interesting unexpected consequence of this work: because the value stack now gets "exposed" by being stored in a continuation, a number of non-Bel values would need to be changed into pure Bel values. This includes our three types of smark so far: fut, loc and bind. That is probably a good change to make anyway.

I realize I have some explaining to do, with those special terms. It'll all make sense, I promise.

Anyway, to make a long story short before the guided tour through the Bel interpreter: I fixed the above internals wardrobe malfunction, rebased my branch with the continuation work, and voilà: it still didn't work!

Imagine you're the person in the Searle's Chinese Room. (That one's been on my mind lately; can't imagine why.) All day you get passed notes with symbols on them, which you look up according to rules to take the appropriate actions and produce new notes with symbols on them.

But there's one additional complication: you seem to have task-induced amnesia, and can't seem to trust yourself with remembering the steps of multi-step procedures. Carrying out a task confined to a single note is not a problem at all, but... any note that requires handling additional subtasks, and then saying "right; where were we?" completely stumps your abilities as a filing clerk. Let's say the in-world explanation for this is that your workspace gets messy, you lose track of your original note, and it's too long ago since you read it.

Eventually, you come up with a brilliant solution to this: you start to leave notes to yourself in your inbox. The notes explain exactly where you were in your previously put-on-hold task, allowing you to smoothly recover your context. (To be honest, this sounds like a trick out of the "inbox zero" crowd's playbook.)

This type of self-note is what the Bel interpreter calls a fut. It's a mechanism for keeping long-term memory and context around while still separating the work of interpretation into small, granular, non-nested subtasks. In the original Bel code, futs are thin wrappers for Bel closures. In my Perl port, I sensibly made them thin wrappers for Perl closures — which worked fine until this new continuation functionality snitched on me and exposed them, since the expression stack s is now visible in userspace.

So, I had to fix that, naturally. The futs are now pure Bel objects, with no visible event horizon into Perl-land. (Hidden away in folds in undetectable space, there's still a Perl closure. I'll need that for as long as my interpreter is actually in Perl. But now you can't see it anymore from userspace. Lies, damn lies, and implementation.)

For completeness, here are all the smark types of the special values that end up on the value stack:

In retrospect, it's not so weird that making these smarks native didn't affect the correctness of the continuations one way or another. Sure, the continuation object contained Perl values that had leaked out into Bel space, but... as long as you didn't look at them, that wasn't really an issue. And the were to all appearances correctly put back into the interpreter later.

So the mystery remained. I glared at the obviously correct code.

One place where we have to use several futs is when interpreting the call to a function. This is a multi-step process:

I looked at this code, although it had really worked fine for months at this point. It's some of the first code I wrote, since function calls are so fundamental. It's maybe the most involved part of the interpreter, as it needs no less than two futs to do its job. It also needs two iterator-like variables, which I use to step through the arguments. For reasons that make sense in context, these are called $es1 and $es2. The code that initializes them looks like this:

my $es1 = pair_cdr($e);

$e being the whole expression; the arguments are in the tail, so the pair_cdr makes sense.

And then, a bit further down:

my $es2 = $es1;

Taking a pre-emptive backup of $es1 before we consume it. See, these variables really are like iterators, because we end up running them down the cons lists. Singly linked lists, so you can't run back up again. Not that you'd want to.

Then we use $es1 to spool the argument expressions onto the expression stack, we evaluate them, and... waking up from the next fut, we use $es2 to spool the computed argument values into $args.

It all works out nicely, because we always use $es1 first, and then we only ever use $es2 once...



Ok, there's the mistake.

The second fut, the one that took the evaluated arguments and bundled them up for applyf, used to only ever run once. I mean, because of course it did. No-one's ever heard of a function call that evaluates its arguments once, and then invokes the function several times.

As bad luck would have it though, that's the exact moment the continuation gets taken, just before the second fut. (Not 100% sure why, but why is not as important as the fact that it does.) And so that once-safe assumption gets broken. And so $es2 would now be all used up, and so continuations wouldn't work.

Looking at the code again, though, I found it strange that my second line of code broke a dearly-held principle of mine:

my $es2 = $es1;

Namely, that variables should have the smallest possible scope.

In the case of $es2, it had a scope that was wider than the second fut, even though it was only used inside of it.

Simply moving it inside the second fut wouldn't work, though: by the time the second fut runs, $es1 is already consumed. But that's easily solvable by also rewriting the line like this:

my $es2 = pair_cdr($e);

Boom! Now continuations worked!

All this to say, debugging is weird.

You get to ride a roller-coaster from understanding nothing one moment, to Boris "I am invincible" Grishenko the next. If you're lucky, you get to remember that not that long ago, you were the person who made the mistake you now so clearly understand and would never make again.

And, the gods willing, the next time you're ready to entomb the same mistake in a piece of code, you'll look up, remember the long debugging session, and steer carefully around that mistake...

...towards new, more interesting ones.