A JavaScript Quine, and the recursion theorem

I saw the following JavaScript quine (modern JavaScript: ES6 and up) presented in Dylan Beatie's talk at NDC London 2020:

$=_=>`$=${$};$()`;$()

The same approach can be rendered with a few more parentheses as an IIFE:

($=()=>`($=${$})()`)()

Either way, although this quine is brilliantly short, it's actually fairly easily parseable at sight. The only genuine bit of obfuscation is that $ is being used as a variable name. You might reasonably assume this is a trick to get the variable name to match up with the template literal string (the sort of thing that does actually happen frequently with quines), but here it doesn't actually serve any purpose apart from obfuscation. We could use another variable name and we'd still have a quine just the same:

(func=()=>`(func=${func})()`)()

Pop open a console in your web browser and try it out.

We can parse it by hand a bit more clearly if we look first at this bit of code:

func=_=>`func=${X};func();`;func();

If X were a defined expression in our source code, this would be valid JavaScript code. The first statement (terminated by the semi-colon) assigns an arrow function to the variable name func. The second statement executes the function we just stored in func.

The arrow function itself ignores its input and just returns what looks like a JavaScript assignment from a template placeholder to the variable named func, followed by an execution statement.

Plugging in func itself:

func=_=>`func=${func};func();`;func();

Now we have a fully valid piece of JavaScript code. The thing that makes this quine actually work, and makes the JavaScript language almost a cheating language for writing quines in, is JavaScript's Function.prototype.toString() method, described here in the ECMAScript 262 specification:

If Type(func) is Object and func has a SourceText internal slot and func SourceText is a sequence of Unicode code points and ! HostHasSourceTextAvailable(func) is true, then Return ! UTF16Encode(func.[[SourceText]]).

In other words, when we load our arrow expression into the variable func, the Function constructor gets called and remembers the source-code within the SourceText internal slot of the new Function object constructed. Then that source code just gets printed out when we call the toString method on the function or, in this case, when the template literal's placeholder calls the toString() method implicitly.

However, this "cheating" makes JavaScript a perfect example language for proving Kleene's Recursion Theorem. Let's first look at the formal statement of the recursion theorem:

Let \(f:\omega\rightarrow\omega\) be computable. There is an index \(e\in\omega\) such that \(\varphi_e=\varphi_{f(e)}\).

Now let's suppose we take JavaScript functions as our model of computation (which assumes we've looked after some pesky details, like that we've implemented some suitable class to handle arbitrarily large integer inputs, JavaScript's memory bound of \(2^{32}\) notwithstanding our imagination).

How is our indexing of partial-computable functions defined? To obtain the \(e'th\) partial-computable function \(\varphi_e\), render \(e\) in base \(1,112,064\), interpret it as a UTF-16 string, and run it as JavaScript source through a JavaScript interpreter. (There are a number of reasonable ways to define input and output here, or for a cleaner take, we could abstract away input-ouput and view the \(e'th\) program as representing the \(e'th\) computably-enumerable set.)

Since JavaScript has a .toString() method built into its functions, finding fixed points is easy: given a total computable function \(f\), let source be some source code fed into our algorithm (however we've decided to handle input), compute \(f(f.toString())\) and execute it like so:

source = { source }
f=eval(${source});
f(f.toString())();

Interpret this source code as the UTF-16 string f=${_e}$;\n f(f.toString())(); representing a number \(e\) in base \(1,112,064\). Then by definition \(\varphi_e=\varphi_{f(e)}\).

Of course, if you don't want to ordain JavaScript as our distinguished model of computation, you might complain about this proof: JavaScript after all is just cheating by storing the source code of our functions. But in fact, if we can prove Kleene's recursion theorem for JavaScript, then any othe language or computation model will follow by a simple lifting argument, assuming either model can simulate computations in the other.

The essence of this argument is a pattern of mind-bending reasoning that comes up frequently in computability theory: because the recursion theorem might as well hold, it in fact must hold. But those details are for another post.