Maynard's Site    

Index Mailing list

Stealing Utensils and Splitting the Callstack

If you asked my university friends to tell you something strange about me, I think a good amount of them would talk about the cafeteria. See, I love our university's cafeteria. Back when the semester was in session, I could spend upwards of four hours a day (or more!) in the cafeteria. Besides the food, it was a place where I could be sure that I'd see all my friends.

Much of this story is fabricated, but this is actually true.

Our cafeteria was pretty simple. You'd check in with your student id, and go grab your food. To get your utensils, you'd just

const utensils = grabUtensils();

and then go ahead and

eatMealWith(utensils).while(talkingToFriends);

and when you were done, you'd just

returnUtensils(utensils);

This was great.

Mostly.

See, there was some trouble. Some people, for some reason, didn't return their utensils when they were done with them. There began to be a shortage of utensils. You could feel it in the air when you walked in, invariably spotting out of the corner of your eye a group of four or five students around the empty fork holders, waiting for a refill.

This is also true, at least for forks. Though I've dramatized it some for this blog post.

Tensions began to rise. Students were annoyed at staff because they wanted forks, and staff were annoyed at students because they were the reason there were no utensils to begin with!

Finally, a change was made.

Students were no longer allowed to simply

grabUtensils: () => Utensils

Instead, they had to

withUtensils: (callback: (utensils: Utensils) => void) => void

For the most part, this was a huge success! Students would now

withUtensils(utensils => {
  eatMealWith(utensils).while(talkingToFriends);
});  // utensils automatically returned

and their utensils would be automatically returned at the end of the inner function! No more tricky theivery.

... assuming the student doesn't throw.

However.

One group of students was absolutely outraged at this change. And, no, it wasn't the group that had been stealing the forks—mostly, those kids were just doing so for shits and giggles. Instead, it was a tight-knit group of deviant thinkers known as the silly forking kids. The thing that bound these kids together is that their utensil habits weren't so simple as grab-use-return. Most silly forkers liked to eat outside of the cafeteria, and would return the forks long after they were done eating. Some would wait until the end of the week and return them in-bulk, and some would return their forks once a day. The most common, however, was to return their forks the next meal. Their dinner routine looked like

goToCafeteria();
const utensils = grabUtensils();
goHome();
eatMealWith(utensils).while(talkingToFriends);
goAboutDay();
sleep();
// breakfast time!
goToCafeteria();
returnUtensils(utensils);
const freshUtensils = grabUtensils();
// ...

But with these new policy changes, they couldn't do this anymore! Instead, they had to

goToCafeteria();
withUtensils(utensils => {
  goHome();
  eatMealWith(utensils).while(talkingToFriends);
  goAboutDay();
  sleep();
  // breakfast time!
  goToCafeteria();
});  // utensils automatically returned

// breakfast
withUtensils(freshUtensils => {
  // ...
});

Certainly their outrage seems justified! Why should anything regarding utensils be in the callstack for sleep()? So of course these silly forkers were angry.

Alas, the campus officials were unwilling to rollback the policy for the sake of such a small portion of students. For a long time, the silly forkers simply had to live with it.

Fast forward a semester.

The campus begins rolling out changes to modernize policies, including such things as increasing the number of in-library cats, replacing Linux with an OS written in JavaScript, and... Promises!

The entire campus API was slowly becoming asynchronous. In regards to the cafeteria, this meant that students would now

withUtensils: (func: (ut: Utensils) => Promise<void>) => Promise<void>

For the most part, this was not an impactful change; the majority of the student population simply had to

await withUtensils(async utensils => {
  await eatMealWith(utensils).while(talkingToFriends);
});

However, for our silly forking friends, this semingly-innocuous change would go down in history.

One day, one silly forker decided to do an experiment. He wanted to see if he could go a week without sleeping in his own dowm room. As a result of this, he found himself one night at the library with a backpack, preparing to try and doze under the 24/7 flourescant lights. As he danced in and out of slumber, his mind wandering to and returning from foreign, mystical places, he was suddenly struck with a realization.

It's me. I did this experiment. Though I'm not a silly forker.

With this new Promise-based policy, the campus had really forked up.

He jumped up with excitement. Ignoring that it was 4:30 in the morning, he went and rounded up his silly forking friends. He sat them down and showed them how they could finally return to their former glory, their days of free forking, unrestrainted by the callstack.

The next morning, all the silly forkers arrived to breakfast before the doors had even opened. They chattered excitedly, somewhat to the annoyance of the tired students around them. When the doors finally opened, they all rushed in before anyone else, and, one after another, they

let doneWithUtensils: () => void;
const utensils = await new Promise(resolveUtensils => {
  withUtensils(utensils => {
    resolveUtensils(utensils);
    return new Promise(resolve => doneWithUtensils = resolve);
  });
});

They filed back out of the cafeteria, smiling at the people around them with a mix of giddiness, pride, and perhaps a bit too much smugness. Each of them went and

await goHome();
await eatMealWith(utensils).while(talkingToFriends);
await goAboutDay();
await sleep();

And enjoyed a delightfully empty callstack, free of any call to withUtensils. And the next morning they simply

await goToCafeteria();
doneWithUtensils();

and repeated the process, just as they had in the years before the original policy change.

And for the rest of their eduation at the university, each silly forker enjoyed the freedom to take their fork where they pleased without being followed by the callstack. They passed this secret trick down to new generations of students, but never to the general student population; they feared that fork theives would return, another policy would come to be, and once again their ability to freely fork would be compromised.

But now, I tell this secret to you.


I call this kind of code splitting the callstack. It regards resource management.

It's not uncommon to have a resource that needs some setup and some teardown around when it's used. For instance, a file needs to be opened before it's used, and closed when it's done being used. Same with a database connection. Or perhaps you want to track resource usage for debugging purposes.

Regardless, you end up with a pair of operations, which I'll call acquire and release. Then, you

const resource = acquire();
doWhateverWith(resource);
release(resource);

The issue with this is that it's easy to forget to release the resource. To mitigate this, you need some way to find out when the code is done with the resource, and then you automatically clean it up. In Python, this is done with context managers. In JavaScript, an idiomatic way to do this is to have a function wrap: (callback: (resource: Resource) => void) => void, which is defined as follows

function wrap(callback) {
  const resource = acquire();
  callback(resource);
  release(resource);
}

and then you use it like

wrap(resource => {
  doWhateverWith(resource);
});  // automatic cleanup

This is mostly pretty awesome. However, it can become a problem because it demands that all usage of the resource be contained in the callback. Sometimes this isn't a problem, but sometimes it is.

A theoretical example of when this can be an issue:

If, for instance, you use the resource in several places of the codebase, then you'll have to raise the call to wrap up higher and higher in your code until all uses are enclosed by the callback, and then pass the acquired resource back down the callstack.

Sometimes this is appropriate, but sometimes it's just ugly and in-the-way.


A real example of when this can be an issue (in fact, the example that lead me to discover splitting the callstack):

I had class which I wanted to make iterable. Instances were to iterate over some resource that was only available through a wrap function.

Of course, there's a conflict there. The iterator must call wrap to get the resource, for starters. But then the iterator must keep the resource open between calls to .next(). However, the resource will close as soon as wrap returns, which will be when the first call to .next() returns.

I'm not sure if it's even possible to write such an iterator. I would have instead had to have the caller invoke wrap and pass in the resource, or something like that. Which can be a somehwat undesirable solution, depending on context.

Luckily for me, I didn't have to do something so horrid. I happened to be in an async context, which, as the rest of the post explores, means I could write an iterator that does this.

Now, I'm not sure if there's a solution for this problem when in a synchronous context. However, interestingly, when you lift the wrap function to be asynchronous, the problem practically solves itself!

With a synchronously handled resource, we could define wrap in terms of acquire and release, but not the other way aroud. But, as it turns out, with an asynchronous wrap, we can do this! Check it out: we start with

wrap: (callback: (resource: Resource) => Promise<void>) => Promise<void>

and now we can define acquire and release!

Note that my implementation isn't perfect. It is, however, pretty good. Two drawbacks: it relies on wrap always returning a new resource, and it leaks memory if release isn't called.

// vvv Some meta-info will need to get from `acquire` to `release`
//    For API convenience, we'll use the following `Map` object
//    to handle this information behind-the-scenes
const doneMap = new Map();

function acquire(): Promise<Resource> {
  // vvv Return the promise that will resolve to our resource
  return new Promise(resolveResult => {
    // vvv Get the resource
    wrap(resource => {
      // vvv We'll resolve this promise to signify that we're done with the
      //     resource and it can be cleaned up
      return new Promise(done => {
        // vvv Put it in the map to pull back out in `release`
        doneMap.set(resource, done);
        // vvv Return the resource
        resolveResult(resource);
      });
    });
  });
}

function release(resource: Resource): void {
  // vvv Mark that we're done with the resource
  const done = doneMap.get(resource);
  done();
  // vvv Delete the no-longer-needed meta info
  doneMap.delete(resource);
}

And now, amazingly, we are able to do the following:

const resource = await acquire();
doWhateverWith(resource);
release(resource);

I call this splitting the callstack because it looks as though we are taking something that had a coherent callstack—wrap calls callback which returns up to wrap—and we are ripping it in half lengthwise at callback, letting the first half run but waiting on the second half of the callstack, saying, hey, wait here, I'll finish this later.

Essentially what's going on is that, since asynchronous code is built on the idea of saying, hey, hold on for a bit, we are able to do so to the callstack when in an asynchronous context. In particular, instead of running the second half of the callback—the cleanup bit—when we return from acquire, we are able to store it in a Promise to be invoked when we desire.

In short: why was the callstack afraid of the Promise? Because promises can rip callstacks in half!

Now go manage some resources!