Re:Common Expression Language
by contravariant on Thursday December 10, 2020 @07:19PM
(#25380689)
On the one hand you're right, though at some point 'arbitrarily long' and Turing complete become pretty similar. In fact an ordinary computer isn't entirely a Turing machine either, as its memory is limited.
Also it means you need to be careful about malicious input, you need to take countermeasures when you evaluate an expression from an untrusted source.
Re:Common Expression Language
by blonde_ocean on Thursday December 10, 2020 @07:39PM
(#25380848)
How do you mean sub-Turing languages don’t allow recursion? Aren’t context-free languages, for example, literally recursive?
"Arbitrary recursion" is the correct claim; e.g. Coq allows recursion, but has restrictions so all programs terminate.
I assume GP means general recursion.
Recursion in a pushdown automata (the equivalent machine for a CFL) is bounded by the input words being consumed, since each state transition consumes one input token. Since all input words are finite, indefinite recursion is excluded.
It's still useful for a config language because it makes it harder to accidentally make a config that (in practice) never terminates, and usually allows for easier static analysis and refactoring of the config files through immutability and purity.