4 ms·

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 conf

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.

itayd 2y ago
the go implementation, at least, allows you to enable while loops among others, which makes it turing complete and not guaranteed to complete. obviously you should never turn this on for configuration, but it is useful for general scripting usage.
skybrian 2y ago
It's nice if a language has a static check to prevent infinite loops when they're unnecessary, but this guarantee is less useful in practice if you're going to run the code. 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.
- benhoyt 2y ago
  [deleted]
  - rwiggins 2y ago
    Page not found - is that a private repo?
    - benhoyt 2y ago
      Oops, yes. I'd better not post that yet. Thanks. :-)
OskarS 2y ago
It actually is, because it allows functions as first class objects. That means you can use the fixed-point combinators from lambda calculus (which doesn't have direct recursion either). For instance, the Omega combinator (sort-of): $> 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.
- laurentlb 2y ago
  The Java and the Go implementation of Starlark should detect the recursive call in the example. I'd say it's an implementation bug in the Rust interpreter. (I agree it doesn't matter that much in practice)
  - OskarS 2y ago
    Ah, fair enough. I've only tested the Rust version. 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.

itayd 2y ago

the go implementation, at least, allows you to enable while loops among others, which makes it turing complete and not guaranteed to complete. obviously you should never turn this on for configuration, but it is useful for general scripting usage.

skybrian 2y ago

It's nice if a language has a static check to prevent infinite loops when they're unnecessary, but this guarantee is less useful in practice if you're going to run the code. 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.

benhoyt 2y ago
[deleted]
- rwiggins 2y ago
  Page not found - is that a private repo?
  - benhoyt 2y ago
    Oops, yes. I'd better not post that yet. Thanks. :-)

OskarS 2y ago

It actually is, because it allows functions as first class objects. That means you can use the fixed-point combinators from lambda calculus (which doesn't have direct recursion either). For instance, the Omega combinator (sort-of): $> 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.

laurentlb 2y ago
The Java and the Go implementation of Starlark should detect the recursive call in the example. I'd say it's an implementation bug in the Rust interpreter. (I agree it doesn't matter that much in practice)
- OskarS 2y ago
  Ah, fair enough. I've only tested the Rust version. 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.