5 ms·

I doubt those are more complex to parse than C++, as C++ parsing is undecidable. http://blog.reverberate.org/2013/08/parsing-c-is-literally-undecidable.html ht

I doubt those are more complex to parse than C++, as C++ parsing is undecidable. http://blog.reverberate.org/2013/08/parsing-c-is-literally-undecidable.html http://blog.reverberate.org/2013/08/parsing-c-is-literally-u...

tigershark 8y ago
C# compiler can generate a huge amount of code from simple and small programs: https://mattwarren.org/2017/11/08/A-DoS-Attack-against-the-C-Compiler/ https://mattwarren.org/2017/11/08/A-DoS-Attack-against-the-C... But you can very easily get the AST. Obviously it may happen that you have to wait until the hell is frozen to get a result, but generally it doesn’t happen in code that you see day to day..
mehrdadn 8y ago
There's something that's unsatisfying about most of these examples which is that a sane person wouldn't write code that multiplies two objects and throws away the result, so people might think that if you added extra constraints to prevent depending on silly side effects, the issue would go away. This is definitely false, but it's not exactly obvious if you don't think about it too hard... I wish people actually paid attention to it when constructing counterexamples. So, for anyone else feeling similarly unsatisfied, here's another example that might be more satisfying in that respect: y = f(g<T, U>(x)); In conjunction with the fact that templates are already Turing-complete, we can see that detecting whether this is a call to a templated g or two comparisons is a Turing-complete question. Also notice a similar parsing issue arises in C# as well, but I don't think generics there can be used to perform Turing-complete computation... though not sure.
- ygra 8y ago
  You can use generics and overload resolution to solve satisfiability problems in C# and Java. But not in the way like templates in C++ allow for compile-time computation.
  - mehrdadn 8y ago
    Yup I've seen that aspect haha.

tigershark 8y ago

C# compiler can generate a huge amount of code from simple and small programs: https://mattwarren.org/2017/11/08/A-DoS-Attack-against-the-C-Compiler/ https://mattwarren.org/2017/11/08/A-DoS-Attack-against-the-C... But you can very easily get the AST. Obviously it may happen that you have to wait until the hell is frozen to get a result, but generally it doesn’t happen in code that you see day to day..

mehrdadn 8y ago

There's something that's unsatisfying about most of these examples which is that a sane person wouldn't write code that multiplies two objects and throws away the result, so people might think that if you added extra constraints to prevent depending on silly side effects, the issue would go away. This is definitely false, but it's not exactly obvious if you don't think about it too hard... I wish people actually paid attention to it when constructing counterexamples. So, for anyone else feeling similarly unsatisfied, here's another example that might be more satisfying in that respect: y = f(g<T, U>(x)); In conjunction with the fact that templates are already Turing-complete, we can see that detecting whether this is a call to a templated g or two comparisons is a Turing-complete question. Also notice a similar parsing issue arises in C# as well, but I don't think generics there can be used to perform Turing-complete computation... though not sure.

ygra 8y ago
You can use generics and overload resolution to solve satisfiability problems in C# and Java. But not in the way like templates in C++ allow for compile-time computation.
- mehrdadn 8y ago
  Yup I've seen that aspect haha.