go: cmd/compile: endless compilation for code that cannot be monomorphised

This code corresponds to Fig. 10 in the paper “Featherweight Go” (“FGG”); it’s an example of a program that cannot be monomorphised.

The type checker (types2, go/types) accept this fine, but the compiler runs “forever”.

package main

type Box[A any] struct {
	value A
}

func Nest[A any](b Box[A], n int) interface{} {
	if n == 0 {
		return b
	}
	return Nest(Box[Box[A]]{b}, n-1)
}

func main() {
	Nest(Box[int]{0}, 10)
}

The FGG paper suggests a check to detect such cases. We may want to implement that eventually. For 1.18, maybe we can have some sort of “time-out” with a suitable error message for now.

cc: @randall77

About this issue

Original URL
State: closed
Created 3 years ago
Reactions: 3
Comments: 15 (12 by maintainers)

Commits related to this issue

cmd/compile: add extra test for the non-mono pass Just add a test for another function that is not monomorphisable, which comes from the Featherweight Go paper. Updates #48018 Change-Id: I664e3f484... — committed to golang/go by danscales 3 years ago

Most upvoted comments

See link in first comment. Or search for “featherweight go” using your favorite search engine.

griesemer on Aug 28, 2021

I am not suggesting that we make this work (certainly not in the near term). Ideally, the type checker detects this case, but in the interest of expediency (we don’t need to support everything for 1.18 - there’s more urgent issues at the moment) it’s probably much easier to just have an upper limit for dictionary depth/size and bail out with an error message if the bound is exceeded.

A depth limit may be prudent to add anyway. There is probably not much difference between a very large type and an infinite type from a user point of view. Maybe it’s easier to create an infinite type by accident.

For example, this program requires more than 60G of memory to compile (as of 9e6ad46bccfa7a63e768236bcd1fd54dab38e4d1), and its types are finite.

package main

type Q[T1 any, T2 any, T3 any, T4 any] struct {
	t1 T1
	t2 T2
	t3 T3
	t4 T4
}

func F[T any](x T) Q[*[1]T, *[2]T, *[3]T, *[4]T] {
	return Q[*[1]T, *[2]T, *[3]T, *[4]T]{
		&[1]T{x}, &[2]T{x,x}, &[3]T{x,x,x}, &[4]T{x,x,x,x}}
}

func main() {
	F(F(F(F(F(F(F(F(F(F(F(F(F(F(1))))))))))))))
}

fweimer-rh on Nov 8, 2021

Is it reasonable for go/types / types2 to implement the “nomono” check from the paper? If monomorphisation is supposed to be an acceptable implementation strategy for generic Go, then it seems like the type checker should enforce that for consistency across implementations.

mdempsky on Aug 27, 2021