News for hackers. Stuff that matters.
Re:Why is Idris 2 so much faster than Idris 1? by zitterbewegung on Monday May 25, 2020 @04:06PM (#23304417)
You can implement any language in any language that is Turing complete. Or practically anything with conditionals, looping and recursion.

So yes to all of your questions.

Re:Why is Idris 2 so much faster than Idris 1? by chongli on Monday May 25, 2020 @04:13PM (#23304482)
You mean you could write a compiler for Idris (or any other dependent typed language) in a Turing complete language. That’s fine but it’s not a very useful statement.

If you want dependent types IN Rust or Swift then Turing-completeness won’t help you, because neither of them have Turing-complete type checkers. You’d have to modify the compiler for them (and thus change the language itself).

Re:Why is Idris 2 so much faster than Idris 1? by dependenttypes on Monday May 25, 2020 @04:24PM (#23304567)
> because neither of them have Turing-complete type checkers

https://sdleffler.github.io/RustTypeSystemTuringComplete/

Re:Why is Idris 2 so much faster than Idris 1? by Jweb_Guru on Monday May 25, 2020 @06:25PM (#23305567)
Sure, and there exists a dependent type system in Rust's trait system. It is wildly impractical to actually use, interacts poorly with the actual language, and a great example of why Turing Completeness of a type system means very little in practice.
Re:Why is Idris 2 so much faster than Idris 1? by chongli on Monday May 25, 2020 @04:40PM (#23304731)
That's almost certainly a bug. At any rate, a proper language with dependent types does not have a Turing-complete type checker and that's what makes it magical. You get incredible power without having to worry about non-termination in your type checker.
Re:Why is Idris 2 so much faster than Idris 1? by devit on Monday May 25, 2020 @04:46PM (#23304792)
It's not a bug, it's due to the trait (aka typeclass) system.

Apparently Haskell has some restrictions that make typeclasses decidable (if -XUndecidableInstances is not set), but Rust has no such mechanism other than numeric iteration limits.

Re:Why is Idris 2 so much faster than Idris 1? by mokus on Monday May 25, 2020 @06:05PM (#23305429)
Guaranteed termination of a sound dependent type system is only useful as a mathematical property, not a practical one (yes, I know the mathematical consequences have practical benefit but I mean directly it doesn’t say anything about what a typical user thinks of as “termination”). You could still trivially write an algorithm at the type level which is Turing-complete in a practical sense.

For example, write a type that implements a Turing machine parameterized by a program and a natural number N of evaluation steps to take. Apply that type to Graham’s number or some suitably large natural number. You now have a type that is, for all practical purposes, Turing-complete, even though it is theoretically guaranteed to terminate.

Re:Why is Idris 2 so much faster than Idris 1? by chongli on Monday May 25, 2020 @06:57PM (#23305768)
For example, write a type that implements a Turing machine parameterized by a program and a natural number N of evaluation steps to take. Apply that type to Graham’s number or some suitably large natural number.

To do that you’d first need to be able to fit Graham’s number into your source code which unfortunately is never going to happen.

Idris has a termination checker which in practice rejects non-primitive recursion. If you can’t prove to the type checker that your recursive function deferments toward a base case at every step then your program won’t type check. So there’s no back-door method to get Graham’s number or other silliness like the Ackerman function into your types.

Re:Why is Idris 2 so much faster than Idris 1? by mokus on Monday May 25, 2020 @08:35PM (#23306314)
I’ve done it in Agda - it’s not even hard. The naive definitions are accepted without issue.

https://github.com/mokus0/junkbox/blob/master/Agda/ack.agda