- Section I: Why it is impossible...
- Section II: How to do it anyway
- Section III: Is there a cure for CPS Ugliness?
- Summary: Ephemeral values makes CPS appear natural and readable
An Identity function is a function that does nothing. It just returns what it receives. It's like the number zero, it's just there to fill the place without doing anything, and sometimes that is exactly what is needed.
const id = (x) => x;
Let's try it out
id(42) /* => 42 */ id("forty-two") /* => "forty-two" */
Our identity function works perfectly, doesn't it?
But what about this?
id(42, 43) /* => 42 */
...Ouch! We forgot the case where there are multiple input values. Lets fix that.
const id = (...xs) => (...xs); /* Syntax error */ const id = (...xs) => xs; /* Not identity any more */
Clearly this is not going well. What is the problem?
The problem is that there is no such thing as "multiple values" outside of function invocations. Unlike natural languages, there is no plural.
You know that you are talking about plural when a "plural" of one is the same thing as that one thing. This is for example not true for an array of one.
 is not the same as
42. So arrays doesn't qualify as plural. Function invocation syntax is typicly the only place where plural is expressed in a programming langauge. (In Haskell it's complicated though.)
You probably don't have plural and thus can't express an identity function in your favourite language too
This is actually true for almost all programming languages. These is an asymmetry. A function can in no way return exactly what it received. Of course a function can return an array of it's arguments, but that is not the same thing. Doing that, the function then depends on the programmer to remember to splash the array when used as input to the next function call. But convention is not the same as language support. It simply can't be done as part of the language, only as part of an ad-hoc convetion, upheld by programmer discipline. The only language I know of that has plural in some meaningful sense is APL/J. I think.
So to summarize: You can't have a real identity function in most programming languages, because plural is not first class, and do not exist outside of function invocation syntax.
I don't know about you, but this blatant asymmetry of the most fundamental building block is kind of not-so-beautiful, I think. It would be quite nice to be able to fix this!
CPS is short for Continuation Passing Style. CPS is often described considered as counter-intuitive and hard to wrap your head around. The basic idea is straight-forward, though. In stead of just returning a value, every function takes as an argument its continuation (the next function); and then it applies the continuation to whatever it wants to pass on. And since the applying is done by the giving function, it has a much greater freedom that a function that just returns value; one could sensibly call this is function application with consent. More precisely this collaboration between function and arguments is in fact so powerful, that any kind of control flow can be expressed under Continuation passing style. This is awesome: Among the new superpowers that we have gained are the ability to return any number of values! Plural is resurrected! We have symmetric functions that can express any control flow without any built-in language support. Programmers are now empowered and liberated, and resides on the same level as the language creators. Empowered is an understatement! It should come as no surprise that we can actually express our identity function:
/* `K` is often used to name the Continuation */ const cps_id = (...xs) => (K) => K(...xs); const log = (...xs) => console.log(...xs); cps_id(42, 43)(log); /* console: 42 43 */
So, with some caveats, we have actually a real identity function! Two problems are:
- All of our code must be written in CPS style
- CPS style code is harder to read and thus adds incidental complexity
CPS is actually not only incomparably more empowering and powerful than than traditional applicative code, but also at least as readable! Let's refactor the above formulation of
/* Traditional CPS style: */ const old_cps_id = (...xs) => (K) => K(...xs); /* Ephemeral CPS style: */ const Tuple = (...xs) => (K) => K(...xs); const cps_id = (...xs) => Tuple(..xs);
OK, let's break that down!
First we defined a helper function that encapsulates the Continuation passing. It happens to be identical to the cps version of the identity function that we were looking for all along! That's a bit confusing but it will be clearer with a couple of examples. But first note how the
cps_id went from mind-bending to normal, using just this helper (actually a rebranded version of itself).
Sometimes a function just naturally returns two values, e.g.
divrem; a function that returns the integer quotient as well as the modulo.
/* Ephemeral CPS style: */ const divrem = (x, y) => Tuple( Math.floor(x/y), x%y ); /* The CPS application chain is more uniform if we start with `Tuple` */ Tuple(14,3)(divrem)(log); /* console: 4 2 */
Now we see how much more natural and readable the code gets if we encapsulate the continuation-passing in a function. N.B. that we need not call the Ephemeral value constructor
Tuple, we could just as well call it
String (if those names were not already used), if what we return is a Number or String, or we could do runtime type-checking using a typed variant of
const plus = (x,y) = Number(x+y); const divrem = (x,y) = Tuple(Int, Int)( Math.floor(x/y), x%y );
So we can see that in actual code, we can encapsulate the continuation-passing. This means that we have an intermediate value in the middle of the computation that is a closure waiting for a function that wants to be applied. For this intermediate closure, I propose the term ephemeral value, because conceptually it is a value, while in practice it's just a closure waiting to concensualy accept a function in the way it self chooses to do it. CPS expressed using ephemeral values is readable and fits naturally into the programmers mental model of the computation.
We saw that CPS can both easy to read and easy to grasp when we encapsulate it as ephemeral values. We can contemplate a chain of function applications as a duality between the functions and the intermediate values that has a brief existence in between function applications (or not so brief, if we want to wait for some reason).
Well that's enough for now. Kinda cool how a simple identity function can encapsulate CPS like that!
- Can we to implement AMB as an ephemeral value? And then export it back to real js, so we can actually use it?
- Can we make hierarchical ephemeral values? Dispatching trunkward, applying leafward? What are the differences? Similarities?
- Can we parameterize ephemeral values with boundary actions thus mimicking State as in State Machines? We probably need a lot more for that to work out?
- Can we build a minimal embedded language for Hierarchical state machines using ephemeral values with boundary actions if we just add situated transitions?
- Can we add some DOM manipulation and get Hierarchical UI machines, where the fundamental component in stead of being a State is a UI?
- What is your favourite open question? Please Comment!
Note: In a follow-up post I use the term Reified Continuation Passing Style to describe CPS encapsulated in Ephemeral values