News for hackers. Stuff that matters.
Re:Rust's Type System Is Turing-Complete: Type-Level Program... by digikata on Friday March 10, 2017 @08:27PM (#13843588)
From having dipped into C++ at a point in my history, it make me think of C++ templates which were also turing complete. Many of skilled people with templates could go overboard into a point where a significant implementation of the program was in an very separated "template metaprogram space" where it was difficult to manage and debug. You would have to read some primary code, then start doing template transforms in your head to figure out what was actually happening. The compile and run-time errors that could pop out were also terrible and long, giant dumps of template syntax trees..

You can get absolutely phenomenal performance, but any major template capability has a high risk of becoming a DSL with terrible debugging ability and slow comprehensibility.

Judicious use could be very nice though...

Re:Rust's Type System Is Turing-Complete: Type-Level Program... by tathougies on Friday March 10, 2017 @08:39PM (#13843642)
That's a problem with c++ in particular though. Languages like Idris and and even Haskell make working with the type system a joy.
Re:Rust's Type System Is Turing-Complete: Type-Level Program... by Oxitendwe on Friday March 10, 2017 @09:35PM (#13843859)
Haskell's type system isn't Turing-complete or even particularly sophisticated. There are extensions to its type system implemented in GHC that in theory give you unbounded computation, but a) those aren't actually Haskell and b) nobody does any real work with them and c) it gives up trying to typecheck if it takes too long. I don't know much about Idris but a few seconds of searching tells me its type theory is not Turing-complete either.[1]

[1] http://cs.stackexchange.com/questions/19577/what-can-idris-n...

Re:Rust's Type System Is Turing-Complete: Type-Level Program... by tathougies on Saturday March 11, 2017 @03:09AM (#13844746)
UndecidableInstances is used in more libraries than you would think. In general, it doesn't inpact safety although certain programs may fail to compile because the compiler gives up after a while. However, this won't result in the acceptance of ill typed programs. Ultimately, the compiler is just acting like any other language run time -- at some point, your Python interpreter will give up (run time type error), your browser will give up (that annoying stop script pop up), and your operating system will give up (out of memory exception).

Also, your link indicates idris's type system is Turing complete.

Re:Rust's Type System Is Turing-Complete: Type-Level Program... by Oxitendwe on Saturday March 11, 2017 @09:21PM (#13848551)
>Idris won't reduce partial functions at the type level, in order to keep type checking decidable.

Totality precludes Turing-completeness. Specifically, functions that don't terminate are by definition partial, and if you can't express functions that don't terminate then it isn't Turing-complete.

Re:Rust's Type System Is Turing-Complete: Type-Level Program... by mrkgnao on Saturday March 11, 2017 @12:42AM (#13844415)
If you're talking about things like UndecidableInstances or FlexibleContexts, um, they are n't exactly uncommon!

In any case, saying that Haskell 98 is the One True Haskell(TM) isn't accurate. Almost all code (beyond the LYAH level) written today uses a few Haskell 2010 extensions, mostly for ergonomics (things like OverloadedStrings are a good example of this), not to mention all the extensions that make mtl let you write "lift whatever" instead of "lift . lift . lift ..." and infer how "high" you want to go up the monad transformer stack.

Re:Rust's Type System Is Turing-Complete: Type-Level Program... by dvt on Friday March 10, 2017 @09:39PM (#13843869)
The "performance" you get by using templates is offset by binary size and/or compilation time. You can't get something for nothing.
Re:Rust's Type System Is Turing-Complete: Type-Level Program... by digikata on Saturday March 11, 2017 @01:38AM (#13844536)
Agreed, and then for example when you go to further reexamine performance and maybe try to fit parts of the binaries into cache, then you're trying to possibly optimize at two-different levels at the same time. This isn't to say that Rust will have the same problem, I hope it avoids it entirely. But if the question is why is there a vague feeling of dread when Rust declares a turing complete type system - a C++ template meta-programming ghost is the reason for me.
Re:Rust's Type System Is Turing-Complete: Type-Level Program... by kibwen on Saturday March 11, 2017 @02:23AM (#13844637)
As tatterdemalion's top comment in this thread states, the deliberate restrictions imposed by the Rust compiler prevent type-level programming from being used for the arcane tasks that TMPL achieves in C++. To say nothing of the fact that Rust has far easier and better ways of achieving metaprogramming than abusing the type system...
Re:Rust's Type System Is Turing-Complete: Type-Level Program... by pjmlp on Saturday March 11, 2017 @02:07AM (#13844596)
Compilation time is a consequence of lack of modules.

In C++11 you can pre-instantiate common used templates (extern template)and hopefully C++20 will finally get modules.

Until then, those that are able to use just VS C++ 2015 and 2017, can make use of incremental linking and experimental modules, to ease the pain a bit.