5 ms·

I think this article is missing a description of the phenomenon "accidentially turing-complete". Configurations langues or DSLs that over the time evolved and s

by 1ris 11y ago

I think this article is missing a description of the phenomenon "accidentially turing-complete". Configurations langues or DSLs that over the time evolved and somehow got turing complete. I suspect these are the most common turing tarpits. And it's a horrible smell.

RyanZAG 11y ago
That's kind of an interesting one: consider two configuration languages. The first is not turing complete and can be considered a good language. The second is an identical copy of the first, but includes the ability to have recursive definitions which ends up making it turing complete. Is the second language really worse than the first? They can both be used the same way, but the second one can allow for some shortcuts in configuration by abusing turing completeness. I'd guess the arguments would be: the 2nd language is better, it can create an identical configuration in less lines. Alternatively: the 1st language is better as should allow for easier parsing and is simpler to verify for correctness.
- Retra 11y ago
  > the 2nd language is better, it can create an identical configuration in less lines. A simple macro or syntax sugar could save you the same lines. A good language will give you a good, terse syntax for representing common configurations, and enough flexibility for clearly denoting the uncommon ones. If your configuration is particularly obscure, it should need more lines to express. It is not worth sacrificing verifiable correctness to induce this kind of gain when there are better ways of doing it.
  - TeMPOraL 11y ago
    Be careful, 'lest your macro language itself turn Turing-complete. > It is not worth sacrificing verifiable correctness to induce this kind of gain when there are better ways of doing it. It's also important to remember it's not always worth sacrificing power to gain verifiable correctness. Not every class of problems needs it. "Freedom for security", something something. ;).
- RodgerTheGreat 11y ago
  The 1st language isn't just simpler to verify for correctness, the 1st language is possible to verify, while the 2nd is not verifiable. Turing complete languages are a singularity beyond which we cannot reason about behavior for arbitrary programs. For many tasks- installation scripts, serialized data, etc- it is extremely undesirable from a security standpoint and for the purposes of writing tooling to permit arbitrary computation.
- Too 11y ago
  There was an interesting submission about your qustion earlier today, https://news.ycombinator.com/item?id=10567408 https://news.ycombinator.com/item?id=10567408 There the author is arguing that simpler is better, I guess the discussion there eventually spawned the submission of this one.
sevensor 11y ago
I can think of a couple examples off the top of my head --- TeX and template metaprogramming. Although I think Knuth protests too much when he says that he tried not to make TeX Turing complete. At any rate, in both cases, Turing-completeness should be considered a hazard. There should be a warning label on TeX, particularly: WARNING: TeX is Turing complete. Proceed with caution!

by 1ris 11y ago

RyanZAG 11y ago

That's kind of an interesting one: consider two configuration languages. The first is not turing complete and can be considered a good language. The second is an identical copy of the first, but includes the ability to have recursive definitions which ends up making it turing complete. Is the second language really worse than the first? They can both be used the same way, but the second one can allow for some shortcuts in configuration by abusing turing completeness. I'd guess the arguments would be: the 2nd language is better, it can create an identical configuration in less lines. Alternatively: the 1st language is better as should allow for easier parsing and is simpler to verify for correctness.

Retra 11y ago
> the 2nd language is better, it can create an identical configuration in less lines. A simple macro or syntax sugar could save you the same lines. A good language will give you a good, terse syntax for representing common configurations, and enough flexibility for clearly denoting the uncommon ones. If your configuration is particularly obscure, it should need more lines to express. It is not worth sacrificing verifiable correctness to induce this kind of gain when there are better ways of doing it.
- TeMPOraL 11y ago
  Be careful, 'lest your macro language itself turn Turing-complete. > It is not worth sacrificing verifiable correctness to induce this kind of gain when there are better ways of doing it. It's also important to remember it's not always worth sacrificing power to gain verifiable correctness. Not every class of problems needs it. "Freedom for security", something something. ;).
RodgerTheGreat 11y ago
The 1st language isn't just simpler to verify for correctness, the 1st language is possible to verify, while the 2nd is not verifiable. Turing complete languages are a singularity beyond which we cannot reason about behavior for arbitrary programs. For many tasks- installation scripts, serialized data, etc- it is extremely undesirable from a security standpoint and for the purposes of writing tooling to permit arbitrary computation.
Too 11y ago
There was an interesting submission about your qustion earlier today, https://news.ycombinator.com/item?id=10567408 https://news.ycombinator.com/item?id=10567408 There the author is arguing that simpler is better, I guess the discussion there eventually spawned the submission of this one.

sevensor 11y ago

I can think of a couple examples off the top of my head --- TeX and template metaprogramming. Although I think Knuth protests too much when he says that he tried not to make TeX Turing complete. At any rate, in both cases, Turing-completeness should be considered a hazard. There should be a warning label on TeX, particularly: WARNING: TeX is Turing complete. Proceed with caution!