Fun fact: execution is not only deterministic, but guaranteed to terminate eventually. I.e. no indefinite loops or recursion is allowed. Quite useful for a configuration language. Of course, that means it's not Turing-complete.
A loop over a billion items (for example, due to a bad SQL statement) can hang your system indefinitely, just like an infinite loop. You still need timeouts, or a progress bar and a way to cancel. If running the code costs money, this is especially important.
A static termination guarantee is most useful in a proof language, when you're not going to run the code, just prove things by compiling it. That's when you really need it. You assume the function returns a value, and if there's any way it could fail, the proof is wrong. But performance is irrelevant if you're not going to run it.
For a configuration language, banning recursion might still make sense, though, since it's another way to write confusing code.
$> def f(g): g(g)
$> f(f)
Traceback (most recent call last):
* expression:1, in <module>
f(f)
* expression:1, in f
def f(g): g(g)
* expression:1, in f
def f(g): g(g)
* expression:1, in f
def f(g): g(g)
<many stack frames omitted>
* expression:1, in f
def f(g): g(g)
error: Starlark call stack overflow
--> expression:1:11
|
1 | def f(g): g(g)
| ^^^^
|
(this is the starlark-rust repl, which is the only one I have currently installed)
You could easily implement the Y combinator like this, and boom, Turing completeness.
In practice, it doesn't matter, because the way they've been implemented is with limited enough stack space that it's not really relevant. But arguably, that is an implementation detail, and you could implement Starlark with either TCO or growable stacks or whatever. Just like normal Turing complete languages doesn't have infinite memory, Starlark doesn't have infinite stack space. I would strongly argue that the language itself is very much Turing complete.
(I agree it doesn't matter that much in practice)
Yeah, important to note, in practice it is always finite, since if you try to do anything "real" using this trick, you blow the stack immediately. This was mostly just a fun fact about how easy it is for Turing-completeness to sneak in. I seem to remember reading something about how Algol-60 was similar, they intended it not to allow recursive procedures, but permitted function pointers (or something) and you could do a similar thing.