Stack overflow on recursive type

[terpstra]

I was trying to write a statically dispatched fixed-point function (aka Y combinator) in rust. My hope was to use it to make recursive closures. While implementing it, I triggered a compiler stack overflow which can be reproduced with this small example code:

struct Helper<'a,F:'a>(&'a F);

fn fix<F>(f: F) -> i32
  where F: Fn(Helper<F>, i32) -> i32      
{
  f(Helper(&f), 8) 
}

fn main() {  
  fix(|_,x| x);  
}

This was on "rustc 1.0.0-beta (9854143 2015-04-02) (built 2015-04-02)", but it still happens on nightly.

I've seen there are a couple other stack overflow bugs related to recursive types. The examples I saw, however, were situations where the compiler should have just given a nicer error message. In my case, I think this is a legitimate piece of code that should compile.

This is analagous to the SML datatype 'a t = T of 'a t -> 'a

Rust should be able to do this, too.

[Stebalien]

This works:

struct Helper<'a>(&'a Fn(Helper, i32) -> i32);

fn fix<F>(f: F) -> i32
  where F: Fn(Helper, i32) -> i32      
{
  f(Helper(&f), 8) 
}

fn main() {  
  fix(|_,x| x);  
}

Rust allows types to refer to themselves in the body but not in the signature. In this case, f's type signature is recursive: SomeFn(Helper<SomeFn(Helper<....

[terpstra]

While your version does not kill the compiler, it is inadequate to implement a statically dispatched fixed point combinator. I already have a version that uses dynamic dispatch.

I really do want the infinitely recursive type. ML can do it.

[Stebalien]

Sorry. You're right; I'm wrong. This works:

fn fix<F>(f: F) -> i32
  where F: Fn(&F, i32) -> i32      
{
  f(&f, 8) 
}

fn main() {  
  fix(|_,x| x);  
}

It seems like using F as a type parameter (in Helper) is confusing rust?

[arielb1]

Does not crash 1.3+

[steveklabnik]

Oh I guess i will leave open for E-needstest