Re:Rust's Type System Is Turing-Complete: Type-Level Program...
by krapht on Friday March 10, 2017 @08:22PM
(#13843573)
Non-Turing complete systems can also allow extremely strong constraints to be embedded, while also allowing the type system to be decidable. Remember, while Rust makes a lot of noise about being safe, it isn't Ada Ravenspark, or ATS, or Idris/Agda.
[ Parent
| on HN ]
Re:Rust's Type System Is Turing-Complete: Type-Level Program...
by tathougies on Friday March 10, 2017 @08:38PM
(#13843633)
Decidability is not really important for type systems. As long as the type system is sound, you're good. If your compilation is taking too long, I would classify that as a bug.
Thanks for the obvious point that rust isn't agda. However, certainly you can agree that agdas type system is able to capture a strictly greater set of constraints than a typed language without a Turing complete type system
Re:Rust's Type System Is Turing-Complete: Type-Level Program...
by Drup on Friday March 10, 2017 @09:21PM
(#13843804)
Agda's type system is not turing complete, you can only run on the type-level functions that are proven to be terminating [1] (using well-founded induction or co-induction).
Same for Coq, and probably Idris.
[1]: http://wiki.portal.chalmers.se/agda/pmwiki.php?n=ReferenceMa...
Re:Rust's Type System Is Turing-Complete: Type-Level Program...
by tathougies on Saturday March 11, 2017 @03:05AM
(#13844730)
You are right about agda. Idris however is not total by default.
Re:Rust's Type System Is Turing-Complete: Type-Level Program...
by Ar-Curunir on Friday March 10, 2017 @11:57PM
(#13844311)
What do Idris and Agda have to do with safety? They have a GC RUNTIME; Rust leverages the type system to get ergonomic, safe and fast code without a runtime.
Re:Rust's Type System Is Turing-Complete: Type-Level Program...
by pjmlp on Saturday March 11, 2017 @11:58AM
(#13846089)
Idris does not have one exclusively.
Allocations can be removed just like in Rust thanks to uniqueness types:
http://docs.idris-lang.org/en/latest/reference/uniqueness-ty...
Also funny that you mention ergonomics, given that improving the current state is one of the main goals of 2017's roadmap.