[contravariant]

I'd be a bit suspicious about the claim that it is not Turing complete. To be fair I can't yet find a way to allow arbitrary computation (though it seems easy to add one with fairly innocuous features). Although you can get it to solve 3-SAT, though only for some predefined number of variables (which it assures can be at least 32). Combinatorics stuff like printing all possible sudokus also seems like it should be feasible.

Don't expect your config files to terminate when they use macros, that's all I'm saying.

[chc4]

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.

[contravariant]

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.

[blonde_ocean]

How do you mean sub-Turing languages don’t allow recursion? Aren’t context-free languages, for example, literally recursive?

[remexre]

"Arbitrary recursion" is the correct claim; e.g. Coq allows recursion, but has restrictions so all programs terminate.

[codebje]

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.

[asciimike]

As the former PM, can confirm it's not Turing complete, and there's a reason many of those innocuous features haven't been added ;)

[progval]

> Although you can get it to solve 3-SAT, though only for some predefined number of variables (which it assures can be at least 32). Combinatorics stuff like printing all possible sudokus also seems like it should be feasible.

How is this compatible with their claim that "CEL evaluates in linear time"?

[codebje]

The only place I can find that makes the 3-SAT claim is this comment thread.

Nevertheless, there's two answers I can think of here. The first is simple (but IMO probably not right): 3-SAT is (probably) exponential, but the language definition document qualifies the linear claim by saying that macro expansion can also be exponential.

The second is probably more accurate, though. General 3-SAT is (probably) exponential, but we're dealing with 3-SAT for a constant number of variables. You can solve 3-SAT by producing all combinations of values for the variables and testing the expression for each one, but while testing an expression should be linear there's an exponential number of combinations. If your combination count is constant, though, the whole complexity becomes linear ... with a shockingly bad constant factor.

[partialstate]

Hi, I'm Tristan (@TristonianJones), the lead of the CEL project here at Google which has a few core maintainers as well as a number of regular contributors: https://github.com/google/cel-spec/blob/master/MAINTAINERS.m...

Macros are considered an optional feature of the language because they can: a) easily be disabled, b) have no dedicated syntax beyond that defined for core CEL.

CEL supports subsetting and extension which means you can actually turn off built-in features in order to guarantee a sort of maximal compute / memory impact that an expression might have while still augmenting the core feature set in order to tailor it to your use case.

Bounded iteration is possible via macros, and such iterations can be nested; thus, you can have high polynomial time expressions, but only if you choose to permit them and many use cases (like IAM Conditions) don't. This is different from OPA Rego or HashiCorp Sentinel in that these features are baked into the syntax and impossible to turn off with 100% certainty.

Since you can't declare functions or variables within CEL, the environment of an expression (the variables and functions it can use) is completely controlled by the host process. The environment acts like a sandbox of sorts, but one specifically chosen by the application and not a general purpose mechanism like a hypervisor or sandbox like WebAssembly.

[SgtPinback]

Hi, I'm Jim (@JimLarson), another CEL maintainer. Yes, the full language spec is more clear about the performance limits, and macros can easily result in exponential time or space complexity. The original claim could be for either the macro version or the equivalent expanded version, e.g. "[true, false].exists(v1, [true, false].exists(v2, ... [true, false].exists(vN, (v1 || !v2 || v3) && (v2 || v3 || !v4) && ...)...))", etc. But it doesn't require much power in the language to express this kind of "solver" - there's still no general recursion.