Strangely Consistent

Theory, practice, and languages, braided together

Continuations FAQ (epoq diary 013)

Tell me about continuations. Explain what they are.

Aww, that warms the cockles of what passes for my heart. Only a fictional reader substitute could guess I was in the mood to explain continuations today.

You're welcome, dear author insert. So, how about it?

Sure thing.

Unfortunately, no-one can be told what continuations are.

I see... a decades-old pop culture reference. Disappointing. By the way, Morpheus could have just said "The Matrix is a machine-made virtual world that your real body, currenly residing in a vat full of snot, has been plugged into and receiving stimuli from all your life."

Right. There's no need to get overly mystical, when good explanations are all that more satisfactory.

Ok, so I challenge you — nay, I curse you — to be similarly down-to-earth and non-mystical with your explanation of continuations.

All right. The continuation represents a running program at some point during its run.

That's it? That sounds almost too easy.

There are some details involved, like how the stack is usually considered to be part of the continuation and the heap isn't, but... yeah, that's it.

I thought continuations were these magical fairy-like beings, whose contours one could only make out near pools of water in dark forests, and in FP languages.

They sure get hyped up a lot. Maybe it's the name, or possibly some kind of guilt by association.

Do you think they have the wrong name, somehow? Kind of like with monads, with that really technical name (Leibniz, seriously?) — maybe if they did name them "warm fuzzy things", they'd have been easier to understand?

Somehow I doubt monads are hard to grok mostly due to an unfortunate name. Not saying monads couldn't have been named better, mind you.

Continuations, on the other hand, might have the perfect name. They are named exactly after the thing they represent: what to continue with.

...Oh no!

What?

I think I forgot what they were. I think I just stopped understanding continuations again.

Ok, don't worry. Take it easy. This happens the first few times.

Let me tell you about the Alma implementation.

Will that help?

I believe it might.

Alma is implemented in the Raku language. It's a simple interpreter, not a compiler. There's a lot of ways you can arrange for the interpreter to work, but one of the questions you need to face is: how do you represent the Alma stack? The call stack, the thing that grows when you call functions, and shrinks when you return from them.

The Alma interpreter does the simplest thing imaginable: it ties Alma's stack to Raku's — the implementation language.

Ok, so you implement a stack using... a stack? Sounds both meta and kind of appropriate.

It sounds appropriate, but it's actually kind of limiting. Bit of a straitjacket.

I mean, it gets you fairly far, but for any advanced, "fun" control flow, you have very limited options.

In Alma, it felt like a relevation when I realized that return and exceptions could be implemented within the stack model, by throwing exceptions up Raku's stack, and catching them higher up.

But that's about as far as you get with that model. You can't use a similar trick to throw yourself down the Raku stack.

I sense you're building up to some kind of punchline here, possibly one involving continuations.

Yes.

Imagine a better way, where instead of tying yourself to the call stack of the implementation language, you let each primitive operation in the implemented language "decide what to do next". Usually, under normal circumstances, what to do next is just "grab the sequentially next statement and execute it".

But sometimes it isn't. What to do next in an if statement — after evaluating the condition — depends on whether the condition was truthy or not. What to do next after the body of a loop might involve going back to the top of the loop and running it another iteration.

What to do next after a function returns is the thing to do next after the function call in the caller.

These "what to do next" pointers, they are the continuations. Making your interpreter use them internally leaves you with a lot of flexibility, and doesn't tie you down to the implementation language's call stack.

Neat! So why didn't you change Alma to work that way?

I started out making a big refactor once, but I didn't make it all the way. I seem to recall I just ran out of tuits. It was definitely possible to do.

Anyway, the Bel interpreter works much more along this idea of continuations. Which is why it was trivial easy not a massive amount of work to expose continuations as first-class values in the language.

Ok, so continuations allow you to do... weird things with control flow? Is that it?

Yes!

Well, no.

Well, yes.

Do you have an example of a weird thing with control flow? Just so we're on the same page here.

I guess exceptions are the classic example.

Here, let me Bel it for you.

(def foo ()
  (prn "Called foo")
  (bar))

(def bar ()
  (prn "Called bar")
  (throw 'some-error)
  (prn "This line never reached"))

(catch
  (foo))

;; "Called foo"
;; "Called bar"
;; some-error

Let me guess... catch and throw uses a continuation somehow?

Yep. catch captures its current continuation (the one that expects a return value from the catch combination), and throw invokes it.

I was going to show how catch is implemented, but that might actually be more harmful than helpful than the above high-level explanation.

Any other examples?

Hm, coroutines. You know, things with yield and stuff. Or gather and take if you prefer.

Something like await of async/await fame.

I guess the common demoninator here is "things that break out of the regular stack-based paradigm". Continuations are good at that.

Who came up with this continuations concept?

Lots of people, independently. It's a fairly natural concept, almost a necessary one.

Let's just say for the sake of it — while I still remember what continuations are and before I forget it again — that I think all this playing around with continuations seems a little pointless, and that call stacks are all you need. What would you say to convince me?

Well, I'm not going to try to wean you off stacks, but...

...it's almost like they form two self-reinforcing and internally consistent universes, each with its own strengths and interesting points. I mean stacks (on the one side), and continuations (on the other).

If you think in terms of composability: stacks are really good at dealing with regular functions, no funny business, no resumable exceptions or coroutines or anything like that. When function calls nest perfectly within each other, stacks work really well.

Continuations get into their groove exactly where stacks fall short: when the control flow gets a bit "weird and interesting" (in the above-mentioned ways).

I think what's important to realize there is that continuations compose really well too; they just happen to have a different shape than function calls do.

Shape?

At the front, a continuation expects zero or more values (kind of like a parameter list), and then it runs some code (kind of like a function body).

Instead of returning "up the stack" to some caller at the end, the continuation just hands over to some other continuation.

You know, when you present it in that way, it sounds really close to what I think of as a function or a closure.

I know. It is.

The one crucial difference is that "up the stack" thing, which functions/closures have, but continuations don't.

In the stack world, there's always an "up" direction (back to the caller) and a "down" direction (further into callees). In the continuation world, it's better to think of it as being "weightless", and each new invoked continuation just leads onwards.

Ten years ago, this was mind-blowing to me. Now, I've passed through the event horizon, and it seems almost natural. Almost.

Can you convert code between "stack style" and "continuation style"?

Well, yes, but...

...before we do, you have to understand that this is usually a property of the language (whether it uses a stack or continuations).

Having said that, we can almost always emulate these mechanisms "one level up", so to speak, using data structures and control structures manually in the language.

When we do it with continuations, we call that "Continuation-Passing Style".

I did the transformation to CPS with one of Knuth's tree-traveral algorithms, and I'm quite proud of how it all came together, and helped explain (to me, at least) why the algorithm in the book could look so unlike a plain recursive function, and yet be related to it.

In order to manually convert some code to CPS, you introduce a state variable, like in the example, and a switch statement in a loop. And then you arrange to "jump around" between your continuations by changing the value of state.

Cool!

Yes, I happen to think so.

Note that this approach is limited to one function only. It won't work if the function calls other functions, because then we conceptually leave the switch statement and the CPS-transformed code.

In the example, there were recursive calls, and those are quite straightforward to handle (with some extra thought to storing stack values on a dedicated value stack).

Ok, so, let me get this. Calling other functions from a CPS-transformed function is a bad idea?

I would put it like this: continuations do not mix well with normal stack-based function calls.

It might be more subtle than that, but this is my experience: they do not mix.

I would say "I believe you" immediately, but I sense that if I did, you wouldn't tell me any war stories about the things that can go horribly wrong...

Fine. Since you insist.

A couple months ago, I was quite happy to land continuations in Bel. As usual, that unlocked some new scripts that had been waiting in the sidelines, and so I could finally try out the Bel script that moves a robot around on a board that I had been writing months earlier. It used catch and throw (demonstrated above), and so it had been waiting on continuations to be finished.

I ran it, and... the script didn't work.

Not because I had coded the script wrong. It didn't work because of a bad interaction between continuations and stacks.

The whole Bel interpreter works using a mechanism that resembles continuations very much. So catch and throw were no problem to implement; they worked with regular Bel code, and all their test passed. Well, their one test passed.

But then there were the "fastfuncs". These are hand-written Perl versions of many of the Bel built-ins (such as map), which currently help run Bel code a bit faster. These functions are stack-based, though.

The robot code had a throw try to jump straight through a map to its catch. Hilarity ensued.

How did you solve it?

Short-term, I had to remove all the fastfuncs that call another function. Those were the one causing the problem.

Longer-term, I'm hoping to be able to CPS-transform those fastfuncs, and re-add them! ☺ I just need to trick my brain into not looking while I accidentally get that to work in Bel. But the principle of it is simple: make fastfuncs work with the Bel continuation-based thinking, instead of against it.

Did Bel get slower when you removed those fastfuncs?

Yes, and it was already quite slow. I needed the extra slowdown like I needed a hole in the head.

Ok, I'll try to take this lesson to heart and never mix wine and beer stacks and continuations in my language implementation.

That's good to hear.

This whole episode reminded me of the phrase "inferior runloop" that I heard long ago in the Parrot community.

In fact, if you Google for that phrase, you still get a lot of Parrot documentation and tickets, and not much else.

The inferior runloop, it turns out, was exactly that problem: a mixing of stacks and continuations, causing a lot of hard-to-debug problems. My takeaway from all that was that the mixing itself just doesn't work. Stacks compose well, continuations compose well, but a mix of them composes really rather unwell.

Look, it's been great catching up! I'm glad you're back to blogging after what I'm sure was a much-needed Winter Solstice sabattical. I'm going to return...

*ahem*.

...I'm going to continue on with whatever it was I was doing before I was summarily recruited to be a reader substitute.

You may pass.

Scatterbrained (epoq diary 012)

Here, have a picture of space.

This picture, along with the rest of this post, gets to represent a few things I haven't done yet. The whole "epoq diary" series is all about doing small things, but doing them regularly, iteratively, and they end up being a big thing. This picture is one of those small things, a return to simplicity. I don't care if you don't like the colors; they make me happy.

How did I create it? There's some code which culminates in these lines:

for (let i = 0; i < 100; i++) {
    setPixel(Math.random() * 320, Math.random() * 200, white);
}

drawCircle(260, 199, 120, { fill: magenta, stroke: magenta });
drawCircle(50, 50, 40, { fill: cyan, stroke: magenta });

(Not the actual code. The code has been changed to look slightly more competent than my current API.)

The coolest thing about it (at least I think so) is that the picture has been generated directly as a PNG image by some JavaScript code. After my umpteenth frustration with the Canvas API and trying to render things without antialiasing, I found this guy's PNG JavaScript library, and it's exactly what I always wanted. Now I can write some JavaScript code, and render a PNG image!

But that's not even what I want to blog about! I wanted to stage a blog post where I ended up with a cute little API for drawing things onto this CGA canvas, but then realized that my API was all wrong because it was like jQuery, when it should really be like React. (That would still be a pretty neat post.)

Or a whole blog post where I extol the virtues of CGA, this hopeless format with no redeeming qualities whatsoever, and yet it makes me warm and happy to look at and to draw with. I have this weird vision of a speculative-fiction alternate timeline where screens never evolved beyond those 320x200 pixels, and that ill-chosen palette of four colors.

In fact, much of the drawing API reminds me of old Turbo Basic, a dialect of basic where LINE and CIRCLE weren't just API calls, but dedicated statement forms. Just the thought of that feels wasteful today, decadent.

And would you believe it, yesterday I wrote almost a whole meta-object protocol in Bel? That would make a pretty darn nice blog post as well. It was effortless to write, and kinda slow to run — which sums up the current Bel experience, I think.

I also had this idea about deriving a good n-queens solver from first principles, starting with just a loose description of the problem and then refining down to a fast algorithm.

And easily a few dozen other ideas right now. The above are just the ones from the past week or so.

But the ethos of these eopq diaries is that ideas on paper aren't enough. Theory and practice need to meet. Sparks need to fly. And it should be possible to get somewhere in 30-minute increments, during those precious evening and weekend moments when inspiration visits.

Hence the picture of space today.

Error messages (epoq diary 011)

I've been thinking about error messages lately.

Error messages from programming language implementations need to be good. Informative. There are a couple of big no-nos that you simply never do, but also a number of "moments of charm" that are easy to overlook.

Here is the prototypical bad error:

Error: invalid input

The trifecta is complete in this one:

One of the things I've been proud of with Raku's error messages is that they almost never do this. (For years, the required minimum in Raku error message quality has been "awesome", and if an error message is less than that, it's a bug.)

Just to be clear, here's the Raku ideal for errors:

Now that's service!

Instead of digging up an example of an excellent Raku error — some other time — let me just say this: Raku doesn't have a monopoly on good error messages, nor is it even the undisputed Chosen One in that regard.

That title, I believe, goes to Elm.

-- TYPE MISMATCH ---------------------------- Main.elm

The 1st argument to `drop` is not what I expect:

8|   List.drop (String.toInt userInput) [1,2,3,4,5,6]
                ^^^^^^^^^^^^^^^^^^^^^^
This `toInt` call produces:

    Maybe Int

But `drop` needs the 1st argument to be:

    Int

Hint: Use Maybe.withDefault to handle possible errors.

(Not included in my blog, but quite evident on Elm's web site: syntax highlighting.)

I love the hint at the end! That one is really hard to pull off, but when you do, that's delightful to a user in need. This is along the lines of "don't just show the error, show possible next steps". Don't just say "no", or even just "sorry", but say what might come next.

Phew!

I have an issue open for my Bel implementation, #18. No need to go look at it, because I'm going to reproduce most of it here.

Currently, I type in some command with a deliberate mistake in it, and here's what I get:

> (srrecip '(+ nil (t t)))
'mistype

Sad.

I mean, on the bright side, it doesn't spend much time blaming the user. But that's mainly because it doesn't utter much at all. Silence might be golden in some cases, but not in this one.

Skipping right to the error message I would like to get (with an example that tries to use the built-in function srrecip to unlawfully create a rational number with a zero as the denominator):

> (srrecip '(+ nil (t t)))
'mistype

In the following function call, the `n` parameter did not satisfy its type
predicate:

                   '+   nil          '(t t)
                   |    |            |
                   v    v            v
    (def srrecip ((s (t n [~= _ i0]) d))
      (list s d n))

The type predicate is: [~= _ i0]    (`i0` has the value `nil`)
The type checker reduced the predicate to: "any value except `nil`"

But the value passed in to `n` was: nil
In order to make the call work, `n` needs to bind to a value which is not `nil`.

The value `nil` was passed to `srrecip` from the REPL:

                   here
                   |
                   v
    > (srrecip '(+ nil (t t)))

I dunno, maybe this is a bit too good. Certainly details would differ when this became a real error message, generated by a machine instead of me dreaming.

I may or may not add a splash of color (as long as it still works fine on non-ANSI terminals).

I also added in the OP of that issue what I value in an error message:

(Emphasis mine. Uh, I mean, mine today.)

Let's go through these. I'd like to get a good feeling for what this would take.

Oh! First off, I just noticed that the error starts off by focusing on the callee first. That both does and doesn't make sense.

From one perspective, once this error happens, you're already calling the function, and so you're already "in" the function in some sense, even though you haven't started executing the body.

On the other hand, the "blame" quite clearly rests with the caller, that is, the code sending in the argument that doesn't type-match against the parameter. If anything, it's probably better to front-load that information.

(Really, I could argue both ways about that one. Python shows its stack traces innermost-last, on the theory that people will be looking at the bottom part first for clues about what went wrong.)

The biggie on the list is "the source code that went wrong". Stating the obvious, source code is one thing, while whatever internal representation that's running once your interpreter/VM is running, is quite another.

In the case of my simplistic Bel interpreter as of today, we're in luck, because the internal list structures really aren't that far from the source code itself. (In the future, that might change.)

So all that needs to happen is Bel needs to mark up the cons pairs in the source code with file-line-column information. It should of course work both for REPL code, for code in files, and for all the built-in code (like the srrecip call above).

(Here's where we once again use the "pocket universe" style of programming in the interpreter. It's quite doable to make those cons pairs representing the code look completely normal, while also carrying hidden information that only the interpreter has access to.)

I consider that part to be a matter of tedious but straightforward programming. What comes next will be quite the opposite — uh, immediate but gnarly?

The mistype error is thrown from the depths of the Bel interpreter, in a utility function called (predictably) typecheck. It's from this function we need to build/emit the excellent error message.

Looking at what information we have at that point: nothing. Only the fact that the typecheck failed.

We need:

Ok, so not quite nothing. Two out of four.

We might even be able to reconstruct the surrounding function from the location information in the predicate, but... I'm not sure how robust that is.

And either way, there's no way we can get at the information about the caller without doing something at this point.

Eyeing the interpreter, I'd say the point to register who the caller is would be evcall. Of course, who "the caller" is needs to be juggled in a delicate way, because making function calls as part of evaluating arguments is definitely a thing.

Anyway, ok. This seems possible. Even seems possible to evolve incrementally in some way.

One thing that sort of shows up here is the separation between "compile time" (when we have full access to the source program) and "run time" (when we are more interested in interpreting whatever format the target program is in).

Error messages squish together these two worlds; while the runtime error definitely happens in the target program, what's user-friendly is showing it happening in the source program.

The reason for that is simple: while it's definitely convenient for the computer to pretend that the target program is the only thing that exists, for the human user it's the opposite — the source program is the only thing they expect to deal with.

It's for the same reason "source mapping" is a thing in the compile-to-JavaScript world — when things to go south, the causes of the problem will be found in the source, not in any code generated from that.

It's a bit of an illusion, but a very helpful one.