Polymorphic recursion breaks monomorphization

[JonathanStarup]

pub def main(): Bool = f(32, 12)

pub def f(x: t, n: Int32): Bool = {
    if (n == 0) true else f(x :: Nil, n - 1)
}

Exception in thread "ForkJoinPool-3-worker-7" java.lang.OutOfMemoryError: Java heap space
    at ca.uwaterloo.flix.language.ast.Type.map(Type.scala:167)
    at ca.uwaterloo.flix.language.ast.Type.map$(Type.scala:164)
    at ca.uwaterloo.flix.language.ast.Type$Apply.map(Type.scala:451)
    at ca.uwaterloo.flix.language.ast.Type.map(Type.scala:167)
    at ca.uwaterloo.flix.language.ast.Type.map$(Type.scala:164)
    at ca.uwaterloo.flix.language.ast.Type$Apply.map(Type.scala:451)
    at ca.uwaterloo.flix.language.ast.Type.map(Type.scala:167)
    at ca.uwaterloo.flix.language.ast.Type.map$(Type.scala:164)
    at ca.uwaterloo.flix.language.ast.Type$Apply.map(Type.scala:451)
    at ca.uwaterloo.flix.language.ast.Type.map(Type.scala:167)
    at ca.uwaterloo.flix.language.ast.Type.map$(Type.scala:164)
    at ca.uwaterloo.flix.language.ast.Type$Apply.map(Type.scala:451)
    at ca.uwaterloo.flix.language.ast.Type.map(Type.scala:167)
    at ca.uwaterloo.flix.language.ast.Type.map$(Type.scala:164)
    at ca.uwaterloo.flix.language.ast.Type$Apply.map(Type.scala:451)

Notice this can also happen through mutual recursion

pub def main(): Bool = f(32, 12)

pub def g(x: t, n: Int32): Bool = f(x, n)

pub def f(x: t, n: Int32): Bool = {
    if (n == 0) true else g(x :: Nil, n - 1)
}

[magnus-madsen]

Sad. Is this in monomorph? Maybe we need a different map function.

[JonathanStarup]

It is conceptually impossible

[magnus-madsen]

It is conceptually impossible

Oh

[magnus-madsen]

So I guess you want an error message instead. But its tricky to produce, I think?

[JonathanStarup]

Yes, hard to spot, especially with the mutual example. And possibly worse with lambdas

My guess is that the best we can do is cycle detection in MonoDefs

f(Int32) requires f(List[Int32]) requires f(List[List[Int32]]) etc

[JonathanStarup]

One way to solve it is to monomorphize to erased types, this would break the cycle. This would however also break typematch