What Color is Your Function?

I don’t know about you, but nothing gets me going in the morning quite like agood old fashioned programming language rant. It stirs the blood to see someoneskewer one of those“blub” languages the plebians use, muddling throughtheir day with it between furtive visits to StackOverflow.

(Meanwhile, you and I, only use the most enlightened of languages. Chisel-sharptools designed for the manicured hands of expert craftspersons such asourselves.)

Of course, as theauthor of said screed, I run a risk. The language I mockcould be one you like! Without realizing it, I could have let the rabble into myblog, pitchforks and torches at the ready, and my fool-hardy pamphlet could drawtheir ire!

To protect myself from the heat of those flames, and to avoid offending yourpossibly delicate sensibilities, instead, I’ll rant about a language I just madeup. A strawman whose sole purpose is to be set aflame.

I know, this seems pointless right? Trust me, by the end, we’ll see whose face(or faces!) have been painted on his straw noggin.

A new language#a-new-language

Learning an entire new (crappy) language just for a blog post is a tall order,so let’s say it’s mostly similar to one you and I already know. We’ll say it hassyntax sorta like JS. Curly braces and semicolons.if,while, etc. Thelingua franca of the programming grotto.

I’m picking JSnot because that’s what this post is about. It’s just that it’sthe language you, statistical representation of the average reader, are mostlikely to be able grok. Voilà:

functionthisIsAFunction(){return"It's awesome";}

Because our strawman is amodern (shitty) language, we also have first-classfunctions. So you can make something like this:

// Return a list containing all of the elements in collection// that match predicate.functionfilter(collection,predicate){varresult=[];for(vari=0;i<collection.length;i++){if(predicate(collection[i]))result.push(collection[i]);}returnresult;}

This is one of thosehigher-order functions, and, like the name implies, theyare classy as all get out and super useful. You’re probably used to them formucking around with collections, but once you internalize the concept, you startusing them damn near everywhere.

Maybe in your testing framework:

describe("An apple",function(){it("ain't no orange",function(){expect("Apple").not.toBe("Orange");});});

Or when you need to parse some data:

tokens.match(Token.LEFT_BRACKET,function(token){// Parse a list literal...tokens.consume(Token.RIGHT_BRACKET);});

So you go to town and write all sorts of awesome reusable libraries andapplications passing around functions, calling functions, returning functions.Functapalooza.

What color is your function?#what-color-is-your-function

Except wait. Here’s where our language gets screwy. It has this one peculiarfeature:

1. Every function has a color.

Each function—anonymous callback or regular named one—is either red orblue. Instead of a singlefunction keyword, there are two:

blue_functiondoSomethingAzure(){// This is a blue function...}red_functiondoSomethingCarnelian(){// This is a red function...}

There areno colorless functions in the language. Want to make a function?Gotta pick a color. Them’s the rules. And, actually, there are a couple morerules you have to follow too:

2. The way you call a function depends on its color.

Imagine a “blue call” syntax and a “red call” syntax. Something like:

doSomethingAzure()blue;doSomethingCarnelian()red;

When calling a function, you need to use the call that corresponds to its color.If you get it wrong—call a red function withblue after the parenthesesor vice versa—it does something bad. Dredge up some long-forgottennightmare from your childhood like a clown with snakes for arms hiding underyour bed. That jumps out of your monitor and sucks out your vitreous humour.

Annoying rule, right? Oh, and one more:

3. You can only call a red function from within another red function.

Youcan call a blue function from within a red one. This is kosher:

red_functiondoSomethingCarnelian(){doSomethingAzure()blue;}

But you can’t go the other way. If you try to do this:

blue_functiondoSomethingAzure(){doSomethingCarnelian()red;}

Well, you’re gonna get a visit from old Spidermouth the Night Clown.

This makes writing higher-order functions like ourfilter() example trickier.We have to pick a color forit and that affects the colors of the functionswe’re allowed to pass to it. The obvious solution is to makefilter() red.That way, it can take either red or blue functions and call them. But then werun into the next itchy spot in the hairshirt that is this language:

4. Red functions are more painful to call.

For now, I won’t precisely define “painful”, but just imagine that theprogrammer has to jump through some kind of annoying hoops every time they calla red function. Maybe it’s really verbose, or maybe you can’t do it insidecertain kinds of statements. Maybe you can only call them on line numbers thatare prime.

What matters is that if you decide to make a function red, everyone using yourAPI will want to spit in your coffee and/or deposit some even less savory fluidsin it.

The obvious solution then is tonever use red functions. Just make everythingblue and you’re back to the sane world where all functions have the same color,which is equivalent to them all having no color, which is equivalent to ourlanguage not being entirely stupid.

Alas, the sadistic language designers—and we all know all programminglanguage designers are sadists, don’t we?—jabbed one final thorn in our side:

5. Some core library functions are red.

There are some functions built in to the platform, functions that weneed touse, that we are unable to write ourselves, that only come in red. At thispoint, a reasonable person might think the language hates us.

It’s functional programming’s fault!#its-functional-programmings-fault

You might be thinking that the problem here is we’re trying to use higher-orderfunctions. If we just stop flouncing around in all of that functional fripperyand write normal blue collar first-order functions like God intended, we’dspare ourselves all the heartache.

If we only call blue functions, make our function blue. Otherwise, make it red.As long as we never make functions that accept functions, we don’t have to worryabout trying to be “polymorphic over function color” (“polychromatic”?) or anynonsense like that.

But, alas, higher order functions are just one example. This problem ispervasive any time we want to break our program down into separate functionsthat get reused.

For example, let’s say we have a nice little blob of code that, I don’t know,implements Dijkstra’s algorithm over a graph representing how much your socialnetwork are crushing on each other. (I spent way too long trying to decide whatsuch a result would even represent. Transitive undesirability?)

Later, you end up needing to use this same blob of code somewhere else. You dothe natural thing and hoist it out into a separate function. You call it fromthe old place and your new code that uses it. But what color should it be?Obviously, you’ll make it blue if you can, but what if it uses one of thosenasty red-only core library functions?

What if the new place you want to call it is blue? You’ll have to turn it red.Then you’ll have to turn the function that callsit red. Ugh. No matter what,you’ll have to think about color constantly. It will be the sand in yourswimsuit on the beach vacation of development.

A colorful allegory#a-colorful-allegory

Of course, I’m not really talking about color here, am I? It’s an allegory, aliterary trick. The Sneetches isn’t about stars on bellies, it’s about race. Bynow, you may have an inkling of what color actually represents. If not, here’sthe big reveal:

Red functions are asynchronous ones.

If you’re programming in JavaScript on Node.js, everytime you define a functionthat “returns” a value by invoking a callback, you just made a red function.Look back at that list of rules and see how my metaphor stacks up:

1. Synchronous functions return values, async ones do not and instead invokecallbacks.

2. Synchronous functions give their result as a return value, async functionsgive it by invoking a callback you pass to it.

3. You can’t call an async function from a synchronous one because you won’t beable to determine the result until the async one completes later.

4. Async functions don’t compose in expressions because of the callbacks, havedifferent error-handling, and can’t be used withtry/catch or inside a lotof other control flow statements.

5. Node’s whole shtick is that the core libs are all asynchronous. (Though theydid dial that back and start adding___Sync() versions of a lot ofthings.)

When people talk about “callback hell” they’re talking about how annoying it isto have red functions in their language. When they create4,089 libraries fordoing asynchronous programming, they’re trying to cope at the librarylevel with a problem that the language foisted onto them.

I promise the future is better#i-promise-the-future-is-better

People in the Node community have realized that callbacks are a pain for a longtime, and have looked around for solutions. One technique that gets a bunch ofpeople excited ispromises, which you may also know by theirrapper name “futures”.

These are sort of a jacked up wrapper around a callback and an error handler. Ifyou think of passing a callback and errorback to a function as aconcept, apromise is basically areification of that idea. It’s a first-class objectthat represents an asynchronous operation.

I just jammed a bunch of fancy PL language in that paragraph so it probablysounds like a sweet deal, but it’s basically snake oil. Promisesdo make asynccode a little easier to write. They compose a bit better, so rule #4 isn’tquite so onerous.

But, honestly, it’s like the difference between being punched in the gut versusbeing punched in the privates. Technically less painful, yes, but I don’t thinkanyone should really get thrilled about the value proposition.

You still can’t use them with exception handling or other control flowstatements. You still can’t call a function that returns a future fromsynchronous code. (Well, youcan, but if you do, the person who latermaintains your code will invent a time machine, travel back in time to themoment that you did this and stab you in the face with a #2 pencil.)

You’ve still divided your entire world into asynchronous and synchronous halvesand all of the misery that entails. So, even if your language features promisesor futures, its face looks an awful lot like the one on my strawman.

(Yes, that means evenDart, the language I work on. That’s why I’m soexcited some of the team areexperimenting with other concurrencymodels.)

I’m awaiting a solution#im-awaiting-a-solution

C# programmers are probably feeling pretty smug right now (a condition they’veincreasingly fallen prey to as Hejlsberg and company have piled sweet featureafter sweet feature into the language). In C#, you can usetheawaitkeyword to invoke anasynchronous function.

This lets you make asynchronous calls just as easily as you can synchronousones, with the tiny addition of a cute little keyword. You can nestawaitcalls in expressions, use them in exception handling code, stuff them insidecontrol flow. Go nuts. Make it rainawait calls like a they’re dollars in theadvance you got for your new rap album.

Async-awaitis nice, which is why we’re adding it to Dart. It makes it a loteasier towrite asynchronous code. You know a “but” is coming. It is.But… you still have divided the world in two. Those async functions areeasier to write, butthey’re still async functions.

You’ve still got two colors. Async-await solves annoying rule #4: they make redfunctions not much worse to call than blue ones. But all of the other rules arestill there:

1. Synchronous functions return values, async ones returnTask<T> (orFuture<T> in Dart) wrappers around the value.

2. Sync functions are just called, async ones need anawait.

3. If you call an async function you’ve got this wrapper object when youactually want theT. You can’t unwrap it unless you makeyour functionasync and await it. (But see below.)

4. Aside from a liberal garnish ofawait, we did at least fix this.

5. C#’s core library is actually older than async so I guess they never hadthis problem.

Itis better. I will take async-await over bare callbacks or futures any dayof the week. But we’re lying to ourselves if we think all of our troubles aregone. As soon as you start trying to write higher-order functions, or reusecode, you’re right back to realizing color is still there, bleeding all overyour codebase.

What languageisn’t colored?#what-language-isnt-colored

So JS, Dart, C#, and Python have this problem. CoffeeScript and most otherlanguages that compile to JS do too (which is why Dart inherited it). Ithinkeven ClojureScript has this issue even though they’ve tried really hard to pushagainst it with theircore.async stuff.

Wanna know one that doesn’t?Java. I know right? How often do you get to say,“Yeah, Java is the one that really does this right.”? But there you go. Intheir defense, they are actively trying to correct this oversight by moving tofutures and async IO. It’s like a race to the bottom.

C# also actuallycan avoid this problem too. They optedin to having color.Before they added async-await and all of theTask<T> stuff, you just usedregular sync API calls. Three more languages that don’t have this problem: Go,Lua, and Ruby.

Any guess what they have in common?

Threads. Or, more precisely:multiple independent callstacks thatcan beswitched between. It isn’t strictly necessary for them to be operatingsystem threads. Goroutines in Go, coroutines in Lua, and fibers in Ruby areperfectly adequate.

(That’s why C# has that little caveat. You can avoid the pain of async in C# byusing threads.)

Remembrance of operations past#remembrance-of-operations-past

The fundamental problem is “How do you pick up where you left off when anoperation completes”? You’ve built up some big callstack and then you call someIO operation. For performance, that operation uses the operating system’sunderlying asynchronous API. Youcannot wait for it to complete because itwon’t. You have to return all the way back to your language’s event loop andgive the OS some time to spin before it will be done.

Once operation completes, you need to resume what you were doing. The usual waya language “remembers where it is” is thecallstack. That tracks all of thefunctions that are currently being invoked and where the instruction pointer isin each one.

But to do async IO, you have to unwind and discard the entire C callstack. Kindof a Catch-22. You can do super fast IO, you just can’t do anything with theresult! Every language that has async IO in its core—or in the case of JS,the browser’s event loop—copes with this in some way.

Node with its ever-marching-to-the-right callbacks stuffs all of thosecallframes in closures. When you do:

functionmakeSundae(callback){scoopIceCream(function(iceCream){warmUpCaramel(function(caramel){callback(pourOnIceCream(iceCream,caramel));});});}

Each of those function expressionscloses over all of its surroundingcontext. That moves parameters likeiceCream andcaramel off the callstackand onto the heap. When the outer function returns and the callstack istrashed, it’s cool. That data is still floating around the heap.

The problem is you have tomanually reify every damn one of these steps.There’s actually a name for this transformation:continuation-passingstyle. It was invented by language hackers in the 70s as an intermediaterepresentation to use in the internals of their compilers. It’s a really bizarroway to represent code that happens to make some compiler optimizations easier todo.

No one ever for a second thought that a programmer wouldwrite actual codelike that. And then Node came along and all of the sudden here we arepretending to be compiler backends. Where did we go wrong?

Note that promises and futures don’t actually buy you anything, either. Ifyou’ve used them, you know you’re still hand-creating giant piles of functionliterals. You’re just passing them to.then() instead of to the asynchronousfunction itself.

Awaiting a generated solution#awaiting-a-generated-solution

Async-awaitdoes help. If you peel back your compiler’s skull and see whatit’s doing when it hits anawait call you’d see it actually doing theCPS-transform. That’swhy you need to useawait in C#: it’s a clue to thecompiler to say, “break the function in half here”. Everything after theawaitgets hoisted into a new function that the compiler synthesizes on your behalf.

This is why async-await didn’t need anyruntime support in the .NETframework. The compiler compiles it away to a series of chained closures thatit can already handle. (Interestingly, closures themselves also don’t needruntime support.They get compiled to anonymous classes. In C#, closuresreallyare apoor man’s objects.)

You might be wondering when I’m going to bring up generators. Does yourlanguage have ayield keyword? Then it can do something very similar.

(In fact, Ibelieve generators and async-await are isomorphic. I’ve got a bitof code floating around in some dark corner of my hard disc that implements agenerator-style game loop using only async-await.)

Where was I? Oh, right. So with callbacks, promises, async-await, andgenerators, you ultimately end up taking your asynchronous function andsmearing it out into a bunch of closures that live over in the heap.

Your function passes the outermost one into the runtime. When the event loop orIO operation is done, it invokes that function and you pick up where you leftoff. But that means everything above youalso has to return. You still haveto unwind thewhole stack.

This is where the “red functions can only be called by red functions” rulecomes from. You have to closurify the entire callstack all the way back tomain() or the event handler.

Reified callstacks#reified-callstacks

But if you have threads (green- or OS-level), you don’t need to do that. Youcan just suspend the entire thread and hop straight back to the OS or eventloopwithout having to return from all of those functions.

Go is the language that does this most beautifully in my opinion. As soon asyou do any IO operation, it just parks that goroutine and resumes any otherones that aren’t blocked on IO.

If you look at the IO operations in the standard library, they seemsynchronous. In other words, they just do work and then return a result whenthey are done. But it’s not that they’re synchronous in the sense that it wouldmean in JavaScript. Other Go code can run while one of these operations ispending. It’s that Go haseliminated the distinction between synchronous andasynchronous code.

Concurrency in Go is a facet of howyou choose to model your program, and nota color seared into each function in the standard library. This means all ofthe pain of the five rules I mentioned above is completely and totallyeliminated.

So, the next time you start telling me about some new hot language and howawesome its concurrency story is because it has asynchronous APIs, now you’llknow why I start grinding my teeth. Because it means you’re right back to redfunctions and blue ones.