loading...
Cover image for [ The Art of the State ] Why it is impossible to write an Identity Function in JavaScript, and how to do it anyway

[ The Art of the State ] Why it is impossible to write an Identity Function in JavaScript, and how to do it anyway

rekreanto profile image rekreanto Updated on ・6 min read

Table Of Contents

Section I: Why it is impossible...

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.

So let's try to write an identity function in JavaScript.

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?

You can't write a real identity function in JavaScript nor in most languages

The problem is that there is no such thing as "multiple values" outside of function invocations. Unlike natural languages, there is no plural.

What is 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. [42] 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.

Section II: How to do it anyway

Now it seems quite impossible to write an identity function in JavaScript. Surely only the ECMA-committee can fix that?

The lack of symmetry, and how to fix it

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!

So is there a way around it? Is there a way that we can program in JavaScript using perfectly symmetrical functions that has the ability, the super-power of not only accepting multiple values, but also returning them?

CPS to the rescue

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:

  1. All of our code must be written in CPS style
  2. CPS style code is harder to read and thus adds incidental complexity

Lets save the problem of how to lift all of JavaScript into the CPS world for another post, and focus on the readability problem.

Section III: Is there a cure for CPS Ugliness?

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 real_id:

/* 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).

First a real example of the usefulness of Ephemeral CPS

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 Number or 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 Tupleetc:

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.

Summary: Ephemeral values makes CPS appear natural and readable

We saw that a real identity function can be expressed in a restricted variant of JavaScript, called CPS, and that this identity function can be used to construct what we chose to call an "ephemeral value", that is something we can think of as a value but that in practice is a closure taking as its argument the Function that wants to be applied to the value, thus encapsulating CPS.
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!

Open questions:

  • Can we lift the whole of JavaScript into Ephemeral CPS? Would we want to?
  • 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

Posted on by:

Discussion

pic
Editor guide
 

I think there's a typo in your code example:

/* Ephemeral CPS style: */
const Tuple = (...xs) => (K) => (...xs);

That's still a syntax error. I think you meant:

/* Ephemeral CPS style: */
const Tuple = (...xs) => (K) => K(...xs);

Fascinating article by the way!

 

You are 100% correct! Thanks for pointing that out!