Is JMESPath Turing Complete?

[springcomp]

Overview

I have been asked on Gitter whether JMESPath is Turing Complete? This got me interested in its own right.
At the same time, this may lead us to warrant some new features to achieve this "goal" 😁.

I’ve started this discussion to prompt the community to chime in and provide pointers and insights as I have actually no idea where to start 😱

Edit: it turns out I do, in fact, have some idea where to start. Maybe this post from the discussion is a bit too abstract or literal. A more promising thought experiment might be to rely on λ-calculus. See that post later in the discussion.

From this answer, criteria for Turing completeness look like so:

To check to see if something is Turing complete, see if you can implement a Turing machine inside it. In other words, check to see if it can simulate the following:

1. The ability to read and write "variables" (or arbitrary data): Pretty much self explanatory.

2. The ability to simulate moving the read/write head: It isn't enough to just be able to retrieve and store variables. It must also be possible to simulate the ability to move the tape's head in order to reference other variables. This can often be simulated within programming languages with the usage of array data structures (or equivalent) or, in the case of certain languages such as machine code, the ability to reference other variables through the use of "pointers" (or equivalent).

3. The ability to simulate a finite state machine: Although not mentioned often, Turing machines are actually a variation of the finite state machines often used within AI development. Alan Turing said the purpose of the states is to simulate a person's "various modes of problem solving".

4. A "halt" state: Although it's often mentioned a set of rules must be able to repeat itself in order to count as being Turing complete, that isn't really a good criteria since the formal definition of what an algorithm is state algorithms must always eventually conclude. If they can't conclude in some way, either it isn't Turing complete, or said algorithm isn't a computable function. Turing complete systems that technically can't conclude due to the way they work (like game consoles, for example) get around this limitation by being able to "simulate" a halting state in some fashion. Not to be confused with the "halting problem", an undecidable function that proves it's impossible to build a system that could detect with 100% reliability if a given input will cause another system to not conclude.

So Is JMESPath Turing Complete?

Reading and writing arbitrary data

The original JMESPath specification did not have any way to refer to arbitrary lexical scope. This JMESPath Community effort actually includes the let function and the $ root-node operator. Both of which allows to refer to any arbitrary lexical scope.

I suspect this goes a long way towards ticking that box.

Now that I think about this, maybe the fact that third-party functions can be registered – although it has not been included in the current version yet – would be a kind of escape mechanism and would allow us to do virtually anything.

As for writing arbitrary data, I think that multi-select-hash and multi-select-list constructs are what enables a JMESPath expression to produce – or "write" – arbitrary data.

In a Turing Macine, the tape acts as both the input and output. The states, their transitions and associates conditions and instructions are encoded in the machine itself.

In the case of JMESPath, this would be the expression itself.

I think one of the key requirements is to be able to write into a given "cell" of the Turing machine state. While JMESPath can produce arbitrary data thanks to the two constructs mentioned above, I think a more powerful equivalent would be to hold some state and be able to write to it.

JMESPath currently does not have such ability. However, a potential future reduce function could be a promising step.

Indeed, JMESPath has an internal scope object that can be initialized to an arbitrary object using the let function.

The reduce function builds upon this concept and has the ability to hold a accumulator object that can be read and written to based upon some expression that is evaluated with inputs from a specified array.

Maybe we need to have a more generic mechanism to access and change in the internal scope independently from the reduce function?

Ability to simulate moving the read/write head

JMESPath does have comparison operators and is also capable of branching so I suspect this sort of ticks this box.

Ability to simulate a finite state machine

I suspect that – and the next item – will be the most challenging item to cover. In essence, we need to be able to go back and perform some processing on existing "data". Basically, a first challenge would be able to create a simple counter up to a specified value for instance.

Armed with an hypothetical reduce function, one could create a simple counter like so:

reduce([`null`, `null`, `null`, `null`, `null`], {acc: `0`}, &acc + `1` )

• Ignoring the input JSON document, this function loops on its first argument array and evaluates the third argument expression.
• The second argument initializes a seed state named acc with value 0.
• On each iteration, the expression increments the acc value and the result is stored in acc for later processing.

The expression therefore returns 5.
This is a simple counter up to 5.

Note: While most examples from this page are using hypothetical functions, the reduce function is indeed implemented in the preview page and you can try this specific example there.

The first argument array [`null`, `null`, `null`, `null`, `null`] feels kludgey.
Maybe this would be a good use case for an hypothetical range function.

A "halt" state

References

• itchyny – May 10 2019 – JSON Formatter written in JQ - Medium
• Tom Wildenhain – April 02 2017 – On The Turing Completeness of PowerPoint (SIGBOVIK) – YouTube

[springcomp]

Maybe a more promising thought experiment is to rely on the fact that λ-calculus is capable of simulating a Turing Machine. In other words, a functional programming language is Turing complete [citation required] I have actually no idea what I’m talking about 🙊.

JMESPath is already a sort of functional language.

It has the built-in ability to call functions.
Its peculiar projection mechanism enables to iterate on input "collections".

Therefore I think adding the ability to define your own functions in a JMESPath instruction would get us most of the way towards Turing completeness.

Assuming a new function like so:

any define(string identifier, expression->any expr)

We could write the following expression:

let(
  { input: `none` },
  define(
    'fibonacci',
    &(@ == `0` && `0`) || ((@ == `1` && `1`) || fibonacci(@ - `1`) + fibonacci(@ - `2`)
  ),
  &fibonacci(@)
)

This example does not actually need the {input: `none`} scope. But the let() function currently does not allow to declare an empty scope object. It relies on the (x && y) || z ternary conditional expression to implement the fibonacci computation recursively.

Notes:

• The define function is interesting as it is the first time JMESPath would need the ability to express a function that does not return a result. Instead, it is a function that somehow registers a new function for later processing. Does this require defining the void type for function return types? What about leaving any as the return type. Should an expression ever assign the result of calling define() what should the concrete return value be?
• The define function accepts its first parameter as a string. It would somehow be more user-friendly to accept an identifier instead ; but this is difficult as it would mean accepting identifier as a kind of expression without evaluating it. Tests must be performed to make sure we can actually parse the example expression, as the fibonacci function is likely not defined while parsing the expression-type argument.

References

A Byte of Code – September 04 2022 – Why functions are Turing complete (Lambda Calculus) – YouTube
Adam Vartanian – April 2018 – It doesn’t have to be Turing complete to be useful –  increment

[springcomp]

The consensus is that a DSL – as JMESPath is – can still be extremely useful without being Turing complete. In fact, conscious decision to avoid Turing completeness might be the way to provide more guarantees without necessarily sacrificing features.

In its current state, JMESPath seems to be definitely not Turing complete.
I would wager a guess that JMESPath Community still is not Turing complete either.

However, it is well possible that allowing registration of third-party functions is only what’s required to bootstrap Turing completeness. However, we will try and make sure we do not unnecessarily introduce complexity within the bounds of the language and the built-in function library.