$> 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)
| ^^^^
|
Infinite recursion, fun!(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.