News for hackers. Stuff that matters.
Re:Rust's Type System Is Turing-Complete: Type-Level Program... by dvt on Friday March 10, 2017 @09:36PM (#13843861)
This is cool but generally a bad idea. It introduces weird edge-case scenarios where you have to 'artificially' halt the compiler, as type-resolution (in these kinds of systems) is undecidable. Rust halts type-resolution by limiting recursion, for example. This is sensible, as @tatterdemalion argues, but it feels like a necessary fix created by an unnecessary problem.

This code, for example, will never stop compiling in gcc 4.4.1[0]:

  template<int I>
  struct Infinite
  {
    enum { value = (I & 0x1)? Infinite<I+1>::value : Infinite<I-1>::value };
  };

  int main ()
  {
    int i = Infinite<1>::value;
  }

[0] http://stackoverflow.com/questions/6079603/infinite-compilat...
Re:Rust's Type System Is Turing-Complete: Type-Level Program... by kentonv on Friday March 10, 2017 @09:53PM (#13843912)
So don't do that.

As programmers, we can indeed write infinite loops. Why is it "a bad idea" if the loop happens at compile time rather than runtime? Why should we reduce the expressiveness of our language to avoid this possibility?

Re:Rust's Type System Is Turing-Complete: Type-Level Program... by dvt on Friday March 10, 2017 @10:15PM (#13844005)
Because it's not necessary. If a Turing-complete programming language can't be expressive enough without a Turing-complete metalanguage, then it's probably not designed very well.

What next? Will we start seeing meta-metalanguages because, hey, it makes compilation less error-prone (but adds something we'll call pre-compilation)?

Re:Rust's Type System Is Turing-Complete: Type-Level Program... by pcwalton on Saturday March 11, 2017 @01:31PM (#13846497)
> If a Turing-complete programming language can't be expressive enough without a Turing-complete metalanguage, then it's probably not designed very well.

What is your proposed alternative to the Paterson conditions (described in the top comment)?

Re:Rust's Type System Is Turing-Complete: Type-Level Program... by clock_tower on Friday March 10, 2017 @10:44PM (#13844095)
I think C/C++ #ifdefs could qualify as a meta-meta-language. I've certainly found that there are situations where static analysis can't comprehend C++ without pre-compilation...
Re:Rust's Type System Is Turing-Complete: Type-Level Program... by dvt on Friday March 10, 2017 @10:56PM (#13844129)
Yes, I think you're right, actually. I doubt the C/C++ pre-processor is Turing-complete, though.
Re:Rust's Type System Is Turing-Complete: Type-Level Program... by jepler on Friday March 10, 2017 @11:50PM (#13844293)
"yes-ish" it is turing complete http://stackoverflow.com/questions/3136686/is-the-c99-prepro... (read the second answer, not the accepted answer)
Re:Rust's Type System Is Turing-Complete: Type-Level Program... by dvt on Saturday March 11, 2017 @12:01AM (#13844317)
Wow, TIL. Good find!
Re:Rust's Type System Is Turing-Complete: Type-Level Program... by naasking on Sunday March 12, 2017 @11:17AM (#13851018)
> Why is it "a bad idea" if the loop happens at compile time rather than runtime?

Because you need at least one reliable tool to tell you when there's a problem, and if that tool isn't a compiler, what are you left with? When do you realize that a long compilation is actually in an infinite loop and not simply a long compilation? How do you debug the cause of an infinite compilation?

These questions may have answers, but current compilers aren't designed to address them.

Re:Rust's Type System Is Turing-Complete: Type-Level Program... by derefr on Friday March 10, 2017 @10:06PM (#13843972)
We (perhaps stupidly) make the assumption that compilers halt all the time, such as in shared CI environments.
Re:Rust's Type System Is Turing-Complete: Type-Level Program... by eridius on Saturday March 11, 2017 @12:57AM (#13844450)
Shared CI environments should always impose some sort of resource limit.

Even without turing-complete type systems, you can still make compilation take effectively forever. It's been a while since I tested, but by my recollection, creating a fixed-length array of sufficiently large size in Rust would make compilation hang indefinitely (well, for much longer than I was ever willing to let it run). Of course this particular behavior may have been fixed (or maybe not; I'm not in a position to test right now), but I'm sure there's other ways to produce artificially long compilation times as well.

Re:Rust's Type System Is Turing-Complete: Type-Level Program... by tejasmanohar on Friday March 10, 2017 @09:56PM (#13843932)
Rule of Least Power
Re:Rust's Type System Is Turing-Complete: Type-Level Program... by kentonv on Friday March 10, 2017 @10:05PM (#13843965)
The Rule of Least Power leads people to lock themselves into low-power languages, only to find that they need more power, which leads to extending the language incrementally to support incrementally more power, which inevitably leads to a mess. Most heavily-used file formats (even "config" formats) eventually evolve into turing-complete languages, but inevitably they are bad languages, because they were not designed with this end-state in mind.
Re:Rust's Type System Is Turing-Complete: Type-Level Program... by cronjobber on Saturday March 11, 2017 @02:52AM (#13844700)
> So don't do that

Sure boss, I'll fix it. Would have fixed it already, if only nontermination wasn't the most unhelpful kind of compiler error message, ever...

Re:Rust's Type System Is Turing-Complete: Type-Level Program... by lomnakkus on Saturday March 11, 2017 @06:18AM (#13845093)
I'd agree, but consider this counter-point: Turing Completeness is so easy to achieve that it's often acheived accidentally. (C++ templates, now Rust, Scala type-level computation via implicits/singletons. I think Haskell's type system is TC via the "correct" extensions?).

Actually, I'd rather want a system that was really designed around this -- well, OK, maybe not TC[1], but perhaps Pacman Completeness.

[1] Purely to avoid decidability problems.