Top all-time · #7073
Shea Leffler
Personal blog · sdleffler.github.ioprogrammingmath
Shea Leffler writes Recursive Descent into Madness, a personal blog at sdleffler.github.io about programming and math. Since 2017, 11 different Hacker News readers have linked it 11 times, most often “Rust's Type System Is Turing-Complete: Type-Level Programming in Rust”. The last post was in 2018, but the archive is still widely read.
Too few sampled comments (7) to say how often HN recommends it.?
Why HN links it
Linked on HN as the source for the claim that the Rust type system is Turing complete, cited in threads on Rust, Zig, Idris and generics. Commenters cite it without judging it.
Summarised by Claude from a sample of 7 HN comments that link here. Each comment is marked recommending, critical or neutral (citing without judging); how this works.
A countable set of sanities and insanities, by Shea Leffler.
Most-linked posts?
- Rust's Type System Is Turing-Complete: Type-Level Programming in Rust11 people · 11 mentions · first linked 2017-03-11
What Hacker News says?
> There are exceptions of course for a definition of "exceptions" being "virtually all languages with a non-trivial static type system and non-zero userbase" as shown in your link. Java ( https://arxiv.org/abs/1605.05274 ), C# ( https://blog.hediet.de/post/how-to-stress-the-csharp-compile... ), Scala ( https://michid.wordpress.com/2010/01/29/scala-type-level-enc... ), Haskell, Rust ( https://sdleffler.github.io/Rust…
Comment linking /RustTypeSystemTuringComplete/
on “Compiling Rust is NP-hard”Submitted Rust's Type System Is Turing-Complete: Type-Level Programming in Rust as a story · 280 points
HN discussion> but it's not true of generics in most languages not sure how true that is. * TypeScript: https://github.com/microsoft/TypeScript/issues/14833 * Rust: https://sdleffler.github.io/RustTypeSystemTuringComplete/ * Haskell (GHC): https://mail.haskell.org/pipermail/haskell/2006-August/01835... * Scala: https://michid.wordpress.com/2010/01/29/scala-type-level-enc... * Java: https://arxiv.org/abs/1605.05274
Comment linking /RustTypeSystemTuringComplete/
on “A Review of the Zig Programming Language (Using Advent of Code 2021)”Submitted Rust's type system is Turing-complete (2017) as a story · 114 points
HN discussion> because neither of them have Turing-complete type checkers https://sdleffler.github.io/RustTypeSystemTuringComplete/
Comment linking /RustTypeSystemTuringComplete/
on “Why is Idris 2 so much faster than Idris 1?”Submitted Rust's Type System Is Turing-Complete (2017) as a story · 1 points
HN discussionRather than traits like what Rust has, the approaches I've generally seen for polymorphic behavior are explicit "interface" structs that hold a vtable, or comptime "duck-typing". I'm still rather new to Zig so there may be other approaches, but this is what I have seen so far. One positive side effect is that there is only one "language" to learn as opposed to two different syntaxes like Rust does. While most people…
Comment linking /RustTypeSystemTuringComplete/
on “Some Thoughts on Zig”Submitted Rust's Type System Is Turing-Complete as a story · 1 points
HN discussionI don't think Rust polymorphism is decidable: https://sdleffler.github.io/RustTypeSystemTuringComplete/
Comment linking /RustTypeSystemTuringComplete/
on “Sayonara, C++, and Hello to Rust”Rust type system is also Turing complete: https://sdleffler.github.io/RustTypeSystemTuringComplete/ It has allowed us to emulate (numeric) const generics in crates like typenum ( https://docs.rs/typenum ) long before they were implemented as a proper language feature. Even today, typenum is more powerful in some regards than the stable version of const generics.
Comment linking /RustTypeSystemTuringComplete/
on “Accidentally Turing-Complete”Rust’s type system is also Turing complete: https://sdleffler.github.io/RustTypeSystemTuringComplete/
Comment linking /RustTypeSystemTuringComplete/
on “Switching from C++ to Rust”