News for hackers. Stuff that matters.
Re:Common Expression Language by chc4 on Thursday December 10, 2020 @06:32PM (#25380241)
There's a difference between pathologically high complexity functions and Turing completeness. Sub-Turing languages generally don't allow recursion or unbounded loops - your program is always making progress. Solving 3-SAT doesn't sound like it precludes sub-Turing completeness, since you'd have a finite number of solutions you're iterating over.

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.

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?
Re:Common Expression Language by remexre on Thursday December 10, 2020 @09:07PM (#25381416)
"Arbitrary recursion" is the correct claim; e.g. Coq allows recursion, but has restrictions so all programs terminate.
Re:Common Expression Language by codebje on Thursday December 10, 2020 @09:13PM (#25381448)
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.