YCombinator issues "Stack overflow" on C++ & HL

[0b1kn00b]

typedef Recursive<P> = Recursive<P> -> P; 
typedef Y<P,R>       = Recursive<P -> R>; 

Recursive works fine on it's own, but Y breaks on cpp, java, jar, c# and hashlink.

Y does have it's uses factoring out the structure of ADTs when doing traversals.

[Simn]

Please post a complete example that triggers this. I cannot reproduce the issue by simply adding these typedefs to a main.

[0b1kn00b]

I thought it was in the definitions, it's the implementation.

typedef YDef<P,R>               = Recursive<P -> R>; 
typedef Recursive<P>            = Recursive<P> -> P; 

@:callable abstract Y<P,R>(YDef<P,R>) from YDef<P,R> to YDef<P,R>{
  static public function unit<P,R>():Y<P,R>{
    return function(fn:Recursive<P->R>):P->R return fn(fn);
  }
  @:noUsing static public function pure<P,R>(f:P->R):Y<P,R>{
    return function(fn:Recursive<P->R>) return f;
  }
  public function new(self:YDef<P,R>){
    this = self;
  }
  public function reply():P -> R{
    return this(this);
  }
}

[0b1kn00b]

It's the unit function that does it.

[Simn]

This (with an empty main) crashes HL and stack-overflows C++, but it works fine on Java/JVM/C#. So there's definitely some problem, but I'm not sure if it shows the problem you're having.

[0b1kn00b]

Two bugs in my code? never. I swear a couple days ago the jvm/java broke, it's only really luck that I picked up on the source here, and the last time I checked Java was breaking the same way. This is within the period of a couple weeks, so maybe that would help.

[0b1kn00b]

Yeah, it's (at least) two problems. This bug is C++ and HL only, I think.

[Simn]

The C++ stacktrace points to the TFun case of this code in gencpp.ml:

let rec unreflective_type t =
    match follow t with
       | TInst (klass,_) ->  Meta.has Meta.Unreflective klass.cl_meta
       | TFun (args,ret) ->
           List.fold_left (fun result (_,_,t) -> result || (unreflective_type t)) (unreflective_type ret) args;
       | _ -> false
;;

This suggests that we end up with a self-recursive function type.

[Simn]

Well yes, of course there's a self-recursive function type because that's what Recursive expands to:

typedef Recursive<P> = Recursive<P>->P;

class Main {
    static var problem:Recursive<String>;

    static function main() {}
}

This is a problem in the generators because their algorithms loop indefinitely.

For HL it's the to_type function that does this here:

    | TFun (args, ret) ->
        HFun (List.map (fun (_,o,t) ->
            let pt = to_type ctx t in
            if o && not (is_nullable pt) then HRef pt else pt
        ) args, to_type ctx ret)

I think it has to keep a stack of visited types in order to avoid infinite recursion.