Wednesday, April 07, 2010

Thinking about continuations

Following up on my previous posts about continuations and Harmony, I want to show how I use the modeling tools of evaluation contexts and operational semantics to sketch out informal designs. I'll use a plausible syntax for a new Harmony operator (based on Neil Mix's NarrativeJS) and start with a reasonably simple semantics based on the well-known shift/reset operators, and sort of work out from there.

I'll keep this as light and informal as possible. To stay on point, I'll ignore most of the ES features-- no mutation (so we don't have to model the heap / object graph), and not even scope chains. For a faithful and precise model, we'd need all of these things. But for design sketches, I can afford to be sloppier.

Stacks and activations

I'll model the stack as a non-empty sequence of function activations:
S ::= A | S(A)
An activation is a function body, but we want to highlight the current statement being executed or expression being evaluated (aka the code pointer). So I'll model the activation as two things: the next bit of code to execute (a statement or expression), and the function body without that bit of code. If the code pointer is at an expression, the activation is a function body with a placeholder that I'll spell () (an "expression hole"); if it's a statement, the activation is a function body with {()} (a "statement hole") in place of the current statement.

For the curious, what I just did was -- informally -- define evaluation contexts for ES.

If that was a little too opaque, here's an example. Let's say we have a function
function foo(x) { f(x); g(x, 2 * x, null); return x + 4; }
If we call foo(42), then at first, our current code is f(42); and our activation is
{ {()} g(42, 2 * 42, null); return 42 + 4; }
When we're about to evaluate the second argument to g, then the current code is 2 * 42 and the current activation is
{ g(42, (), null); return 42 + 4; }
When we get to the return statement, current code is return 42 + 4; and the current activation is
{ {()} }
Notice how after we execute some code, it's gone from the activation; the activation just needs to keep track of the code we have left to run.

For talking about the activation and the current code together, I'll write A(expr) or A{stmt}. This is what people call "plugging" code into the hole of a context. Essentially, it's just a modeling trick that makes it convenient to call out where the current code pointer is, but it also turns out to be really natural for talking about first-class control operators-- because it explicitly models the very things we want to manipulate.

Operational semantics

The above is more or less enough to start writing simple transition rules that describe how programs run, e.g.:
S(A{return val;}) → S(val)
In English, this rule says: "in a stack starting with S and with activation A on top, when the next code to execute is the statement return val; (for some value val), then remove the current activation and place val in the expression hole of the stack."

One thing to make clear: this transition arrow describes a runtime state transition of the program, not a compile-time transformation.

Starting with shift and reset

Here's how a design based on shift and reset might work, specified in one line:
S(A(val->(val1, ..., valn))) → S(val(val1, ..., valn, function(x) A(x)))
The special syntax of a capturing function call comes is from NarrativeJS. The transition rule describes several things:
  1. After evaluating the callee and its arguments, the operator immediately aborts the current activation and saves it in a function.
  2. Next, it calls the callee with its arguments along with the captured continuation value as an additional argument.
  3. If the captured continuation is called, it executes the captured function activation, with its new argument plugged into the hole of that activation.
There's a serious problem with this semantics for ECMAScript: exception handlers. Aborting A will discard any try or finally blocks in A before we call the function. So you'd get surprising behavior like:
function mightFail(k) {
// ...
throw "boo!";
function main() {
try {
catch (x) {
return 42
main() // uncaught exception: "boo!"
A pretty clear violation of principle of least astonishment.

When to abort

Having the semantics in such a concise format makes it easy to tweak and experiment with. Let me modify the above semantics in the following way: instead of aborting before we call the callee, let's abort the activation after we return from the call. That way, if it throws exceptions, they'll be caught by any handlers in A.

We'll have to invent an expression form that aborts the current function activation after evaluating an expression. This is pretty much just like return, exception it's an expression form.
S(A(val->(val1, ..., valn)))
→ S(A(RETURN val(val1, ..., valn, function(x) A(x))))
Actually, we could do this without positing a magic RETURN operator if we have something like the newly-proposed let expressions, which allow you to execute statements inside an expression. Then we'd have:
S(A(val->(val1, ..., valn)))
→ S(A(let (x = val(val1,..., valn, function(x) A(x))) {return x;}))
So that's a brief demo of using evaluation contexts and operational transition rules to sketch the semantics of continuation operators.

Edit: I forgot to mention, it's easy enough to specify the behavior of RETURN:
S(A(RETURN val)) → S(val)
As I say, just like return statements, but as an expression form. To be clear, this is just a specification mechanism, not something I'd suggest as a language feature.


jto said...

S(A(RETURN val)) → S(val)

It seems like that would skip finally blocks.

I found this post pretty hard to follow, but I think I got through it all...

Dave Herman said...

It seems like that would skip finally blocks.

In my efforts to keep things simple, I left try, catch, and finally out of the model. Which probably wasn't the best move, since I was also talking about exception handling. Sorry 'bout that.

I found this post pretty hard to follow, but I think I got through it all...

Yeah, I debated for a while, and decided to go ahead and write it, but it's pretty hard to get the basics of evaluation contexts and operational semantics into a blog post or two. At the same time, I've found these techniques so useful for my own thinking, I wanted to try and convey them. Sounds like I wasn't too successful, though.

Rithi Rawat said...

Outstanding blog thanks for sharing such wonderful blog with us ,after long time came across such knowlegeble blog. keep sharing such informative blog with us.

machine learning training in chennai
best training institute for machine learning
machine learning tution in chennai
artificial intelligence and machine learning course in chennai

IT Tutorials said...

Get the most advanced UiPath Course by Professional expert. Just attend a FREE Demo session.
call us @ 9884412301 | 9600112302
RPA training in chennai | UiPath training in velachery

Unknown said...

If you're looking to burn fat then you absolutely have to jump on this brand new custom keto plan.

To create this service, licensed nutritionists, fitness couches, and top chefs united to develop keto meal plans that are efficient, decent, money-efficient, and delicious.

Since their first launch in 2019, thousands of people have already transformed their figure and well-being with the benefits a good keto plan can give.

Speaking of benefits; clicking this link, you'll discover eight scientifically-certified ones offered by the keto plan.

Ishu Sathya said...

Read your blog, Excellent content written on "Thinking about continuations"

If you are looking for RPA related job with unexpected Pay, then visit below link

RPA Training in Chennai
RPA course in Chennai
RPA course
RPA Training in Velachery
RPA Training
Robotic Process Automation Training
Robotic Process Automation Training in Chennai
Robotic Process Automation Courses
RPA Classes in Chennai
Robotic Process Automation Certification

Ritu Sharma said...

Thanks for the informative post. Gathered lots of information here and do share more.
AngularJS Training in Chennai
AngularJS Online course
AngularJS Online Training
AngularJS course in Chennai
Best Hacking Books
Ethical Hacking Books
Ethical Hacking course in Chennai
Salesforce Training in Chennai
RPA Training in Chennai


An instruction manual for Printer 123 hp printer setup, driver download, software install, wireless setup, USB connection, and troubleshooting issues.

ji jhon 88 said...

CRM Software solutions are an integral part of the sales, marketing and customer service of most organisations lightning interview questions and answers activate said...

you very well explained the topic For providing the important and Knowledgeable

Olivia Foster said...

Thanks for the helpful tips in the post My name is Olivia Foster and I'm studying to be a graphic designer. On Wednesday I went to a graphic design program seminar in San Antonio, I really enjoyed it there, although at first I thought everything would go wrong because the flight was late, but I managed to quickly rent a car and get to the seminar.

Chaitanya said...

Looking forward to reading more. Great blog article. Great.
Azure Solution Architect Online Training
SAP GTS Online Training
SAP BASIS Online Training

스포츠 토토사이트 said...

Thank you for every other great article. said...

I’d like to thank you for the efforts you have put in penning this website. said...

I m very pleased to read this article. said...

Your blog is really nice and sound really good said...

Thank for you shared again. said...

I hope there's an audience next time. thank you