6 ms·

And that's a bad thing. It means not only that some sed programs never complete, but it's not even possible to tell whether any given sed program hangs or not.

by Grue3 8y ago

And that's a bad thing. It means not only that some sed programs never complete, but it's not even possible to tell whether any given sed program hangs or not. Not something you want from a text substitution utility.

eponeponepon 8y ago
If you just want a text substitution utility, then this is proof that you can implement that by using sed in a controlled manner. Why bemoan something for doing more things than you need it to right now? This is what general-purpose computing is all about.
- Toenex 8y ago
  I do like the thought experiment that I might not want Turing completeness from a language in a specific use case.
jhanschoo 8y ago
No, it's not possible to tell if arbitrary programs hang. But it is possible to tell if a program is of a restricted form that is known to terminate. This is how we know the many standard algorithms we frequently use terminate.
ben0x539 8y ago
Never in my life have I been more concerned about whether a simple text substitution is going to halt than whether I can write it down reasonably concisely without having to resort to a more powerful scripting/programming language.
dahart 8y ago
Out of curiosity, have you ever been concerned to have a guarantee whether any program you’ve written or run would finish, regardless of run time? The halting problem is an abstract theoretical result that I’ve personally never been concerned about, in any language at all. Not even once in practice in 30 years of coding have I worried that I didn’t know whether a correct bug-free program would finish. I worry that programs take too long all the time, but that’s completely separate from the halting problem. If sed is a “bad thing”, just understand that string replacement is a “bad thing” and computers are a “bad thing”. There isn’t an alternative to doing any real computation without having Turing completeness.
- Grue3 8y ago
  Yes, I have personally designed several guaranteed-to-halt DSLs for the exact reason that allowing Turing completeness where it's not needed is a bad idea. If you have a scripting language in another software, you don't want to allow the scripts to go into indefinite loops, that's just bad UI. You can't guarantee the user will write bug free code that halts. One of my non-Turing complete languages is Animstack [1]. It's a script within GIMP image editing software. Imagine accidentally creating an infinite loop while you're working on an image and having your image editor freeze forever. Well, you can't create an infinite loop in Animstack. It's guaranteed to finish in linear time (of the number of layers). That's intentional and I was careful to preserve this guarantee. [1] http://tshatrov.github.io/animstack.html http://tshatrov.github.io/animstack.html
  - dahart 8y ago
    Your project looks really cool, but I’m unconvinced by your take on Turing completeness. It’s a mistake to conflate UI with computability, and a mistake to confuse computability with the ability to make programming mistakes or to write bugs. The academic idea of the halting problem is not to make good UI or save people from themselves or from bugs, it’s just a theoretical math problem, and it doesn’t mean anything useful in practice. You can write an infinite loop in C, and still hit Ctrl-C to kill it. You can screw up JavaScript and still close the tab. Turing completeness is not a problem in practice. If GIMP’s scripting or plugin environment doesn’t support killing a runaway script, then the bad UI is GIMP, not Turing completeness. Plus, lack of Turing completeness is no guarantee that a script will be fast and that it won’t be bad UI. The halting guarantee is not a user guarantee on responsiveness or on run time at all. Lack of Turing completeness might, on the other hand, severely limit real functionality, it might keep users of your language from being able to do cool things. You’re taking at least some kinds of higher level function composition off the table. Anyway, that said, I will try to check out your project, I’m a big fan of image generation DSLs (having written a couple myself for CG film production) as well as compositing and animation projects.
    - Grue3 8y ago
a1369209993 8y ago
Frankly, I really don't care about the supposed difference between: while(1) hang # and for(i < 9^9999) hang

by Grue3 8y ago

eponeponepon 8y ago

If you just want a text substitution utility, then this is proof that you can implement that by using sed in a controlled manner. Why bemoan something for doing more things than you need it to right now? This is what general-purpose computing is all about.

Toenex 8y ago
I do like the thought experiment that I might not want Turing completeness from a language in a specific use case.

jhanschoo 8y ago

No, it's not possible to tell if arbitrary programs hang. But it is possible to tell if a program is of a restricted form that is known to terminate. This is how we know the many standard algorithms we frequently use terminate.

ben0x539 8y ago

Never in my life have I been more concerned about whether a simple text substitution is going to halt than whether I can write it down reasonably concisely without having to resort to a more powerful scripting/programming language.

dahart 8y ago

Out of curiosity, have you ever been concerned to have a guarantee whether any program you’ve written or run would finish, regardless of run time? The halting problem is an abstract theoretical result that I’ve personally never been concerned about, in any language at all. Not even once in practice in 30 years of coding have I worried that I didn’t know whether a correct bug-free program would finish. I worry that programs take too long all the time, but that’s completely separate from the halting problem. If sed is a “bad thing”, just understand that string replacement is a “bad thing” and computers are a “bad thing”. There isn’t an alternative to doing any real computation without having Turing completeness.

Grue3 8y ago
Yes, I have personally designed several guaranteed-to-halt DSLs for the exact reason that allowing Turing completeness where it's not needed is a bad idea. If you have a scripting language in another software, you don't want to allow the scripts to go into indefinite loops, that's just bad UI. You can't guarantee the user will write bug free code that halts. One of my non-Turing complete languages is Animstack [1]. It's a script within GIMP image editing software. Imagine accidentally creating an infinite loop while you're working on an image and having your image editor freeze forever. Well, you can't create an infinite loop in Animstack. It's guaranteed to finish in linear time (of the number of layers). That's intentional and I was careful to preserve this guarantee. [1] http://tshatrov.github.io/animstack.html http://tshatrov.github.io/animstack.html
- dahart 8y ago
  Your project looks really cool, but I’m unconvinced by your take on Turing completeness. It’s a mistake to conflate UI with computability, and a mistake to confuse computability with the ability to make programming mistakes or to write bugs. The academic idea of the halting problem is not to make good UI or save people from themselves or from bugs, it’s just a theoretical math problem, and it doesn’t mean anything useful in practice. You can write an infinite loop in C, and still hit Ctrl-C to kill it. You can screw up JavaScript and still close the tab. Turing completeness is not a problem in practice. If GIMP’s scripting or plugin environment doesn’t support killing a runaway script, then the bad UI is GIMP, not Turing completeness. Plus, lack of Turing completeness is no guarantee that a script will be fast and that it won’t be bad UI. The halting guarantee is not a user guarantee on responsiveness or on run time at all. Lack of Turing completeness might, on the other hand, severely limit real functionality, it might keep users of your language from being able to do cool things. You’re taking at least some kinds of higher level function composition off the table. Anyway, that said, I will try to check out your project, I’m a big fan of image generation DSLs (having written a couple myself for CG film production) as well as compositing and animation projects.
  - Grue3 8y ago

a1369209993 8y ago

Frankly, I really don't care about the supposed difference between: while(1) hang # and for(i < 9^9999) hang