Comment by tatterdemalion | Hacker News Reader

Comment by tatterdemalion | Hacker News Reader

Hey I'm the person who raised the question (and I work on Rust, mainly on the trait system discussed in this post).

I agree with the author that while this is interesting, for users it doesn't matter much. In particular, the folks (with respect) pontificating about whether this is a good or bad thing are quite exagerating its consequences. In practice, you can neither conveniently use this property for metaprogramming, nor will you ever get a nonterminal typechecking (not only is there a recursion limit, it is extremely unlikely you will write the kinds of impls that hit that limit except in extreme typelevel programming like documented here).

The most interesting thing is that the two examples we have now of turing completeness both use only features available in Haskell without making typechecking undecidable. The reason our system is Turing complete is that we allow certain impls that Haskell wouldn't, which are in practice very useful.

For example, we have an impl of "ToString for T where T: Display" (in Haskellese "instance Display a => ToString a"); that is, anything that can be pretty printed also has a to_string method. This would be disallowed without the -XUndecidableInstances flag in Haskell. However, if your type can't be pretty printed, you can separately add a ToString impl for it (even with undecidable instances, Haskell wouldn't consider this coherent because Haskell coherence ignores constraints).

If you're interested, the exact sorts of impls we allow that Haskell wouldn't are covered by what's called the "Paterson condition" in Haskell docs.

I have managed to hit the recursion limit in rust before: https://is.gd/7IH5gE

What happens in rust closures have a unique type[1]. So the recursive call in cps_factorial, instantiates a new cps_factorial which contains a new unique closure type which instantiates a new cps_factorial...

[1] This is done so that closure calls can be determined statically reducing run-time overhead and helps optimisation.

I'm quite of my depth here, and while I can sort of understand the recursive construction of new types, it seems as if the type checker should be able to almost trivialy 'shortcut' the recursion unless the return type is unconstrained in some sense that it can be a recursive type with some type arguments.

Most likely there is something obvious I'm missing as I don't know a lot about rust, but unless the compiler isn't doing what is essentially a type level equivalent of tail call elimination, which it almost certainly does, finding the type of that function should be trivial unless the return type can become recursive with unbounded depth.

> unless the compiler isn't doing what is essentially a type level equivalent of tail call elimination

It doesn't, why would it? That's a pretty niche thing to have.

> finding the type of that function should be trivial unless the return type can become recursive with unbounded depth.

The return type is recursive with unbounded depth. The typechecker doesn't know the value of `n`, so to it this returns an infinitely recursive type.

Closures are statically dispatched. If you want something like this to work, you should box them as a trait object so that they get dynamically dispatched.

This example code must be monomorphized at compile time, meaning that each closure will have a different representation. "Tail call optimization at the type level" is not possible with this compilation model.

(The problem is solved by using a trait object to dynamically dispatch the inner call. https://play.rust-lang.org/?gist=0d3c0a5f1291eb34ba61bd39449...)

From memory I solved it using more CPS and currying. Well manually currying with functions like curry1, curry2, etc...

Although I'm pretty sure you can overload the Fn* traits to implement currying in Rust. (Fn traits are unstable). Which is neat.

    // Something like this:
    impl<F, A, B, R> (FnOnce(A) -> Curry<F, A, B>)  for  F
        where F: FnOnce(A, B) -> R,
    { ... }

    // and
    impl<F, A, B, R> (FnOnce(B) -> R) for Curry<F, A, B>
        where F: FnOnce(A, B) -> R

I think I got it working... but you would need some work for more arguments. (And it worked different on different versions of rust-nightly :/)

That was a fun few minutes :)

https://downloads.haskell.org/~ghc/7.0.1/docs/html/users_gui...

In GHC, you can get the "this is the default when it satisfies those constraints" behavior with DefaultSignatures.

Reply on news.ycombinator.com