Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

cmd/go2go: Recursive generics hang the playground. #39688

Open
beoran opened this issue Jun 18, 2020 · 15 comments
Open

cmd/go2go: Recursive generics hang the playground. #39688

beoran opened this issue Jun 18, 2020 · 15 comments
Assignees
Milestone

Comments

@beoran
Copy link

@beoran beoran commented Jun 18, 2020

I tried this on the playground:

package main

import (
	"fmt"
)

type Nil struct {
}

type Tuple(type A, B) struct {
	A A
	B B 
}

func (u Tuple(A,B)) Head() A {
	return u.A
}

func (u Tuple(A,B)) Tail() B {
	return u.B
}

func New(type A,B)(a A, b B) Tuple(A, B) {
	return Tuple(A, B){a, b}
}


func (u Tuple(A,B)) Append(v A) Tuple(Tuple(A,B), A) {
	return Tuple(Tuple(A,B), A){u, v}
}

func NewList(type T)(v T) Tuple(T, Nil) {
	return Tuple(T, Nil){v,Nil{}}
}


func main() {
	t := Tuple(int,Tuple(int,Tuple(int,Nil))){}
	l := NewList(7) 
	fmt.Printf("Foo: %v!\n%v\n", t, l)
}

But it hung the playground instance I was working on indefinitely without crashing. Hopefully it didn't break anything serious, a new instance of the pleyground seems ok. I'm not sure if such recursion as in Append should be allowed or not, although it would be handy. If not, then the recursion should e detected promptly somehow to prevent such hangs.

@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Jun 19, 2020

At the moment it doesn't hang on the dev.go2go branch, but it also doesn't build. I don't really see how it could ever build.

@griesemer
Copy link
Contributor

@griesemer griesemer commented Jun 19, 2020

This type-checks now on the dev.go2go branch and it also runs if the Append method (which is never called) is removed:

$ go tool go2go run main.go2 
Foo: {0 {0 {0 {}}}}!
{7 {}}

When the Append method is present, the translation step fails:

$ go tool go2go run main.go2 
# command-line-arguments
/var/folders/pz/56j0n0xd15xctngkh8rw64d80004gv/T/go2go-run649741278/main.go2:28: cannot use u (type instantiate୦୦Tuple୦int୦main୮aTuple୮8int୮3୮0main୮aTuple୮8int୮3୮0main୮aNil୮9୮9) as type instantiate୦୦Tuple୦int୦main୮aTuple୮8int୮3୮0main୮aNil୮9 in field value
/var/folders/pz/56j0n0xd15xctngkh8rw64d80004gv/T/go2go-run649741278/main.go2:28: cannot use u (type instantiate୦୦Tuple୦int୦main୮aNil) as type instantiate୦୦Tuple୦int୦main୮aTuple୮8int୮3୮0main୮aNil୮9 in field value
/var/folders/pz/56j0n0xd15xctngkh8rw64d80004gv/T/go2go-run649741278/main.go2:28: cannot use u (type instantiate୦୦Tuple୦main୮aTuple୮8int୮3୮0main୮aNil୮9୦main୮aTuple୮8int୮3୮0main୮aNil୮9) as type instantiate୦୦Tuple୦main୮aTuple୮8int୮3୮0main୮aNil୮9୦int in field value
/var/folders/pz/56j0n0xd15xctngkh8rw64d80004gv/T/go2go-run649741278/main.go2:28: cannot use v (type instantiate୦୦Tuple୦main୮aTuple୮8int୮3୮0main୮aNil୮9୦int) as type instantiate୦୦Tuple୦int୦main୮aTuple୮8int୮3୮0main୮aNil୮9 in field value
/Users/gri/go/bin/go [run main.go] failed: exit status 2

I fail to see at the moment what's wrong with the Append method and why it should matter.
@ianlancetaylor ?

@beoran
Copy link
Author

@beoran beoran commented Jun 19, 2020

Well I'm not sure if this type of recursion should be allowed, I was just trying to play around and see if I could implement compile time Lisp-like lists using generics. But if it is allowed then it should of course also work correctly.

@gopherbot
Copy link

@gopherbot gopherbot commented Jun 20, 2020

Change https://golang.org/cl/239137 mentions this issue: [dev.go2go] go/go2go: don't drop type arguments in instantiateType

@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Jun 20, 2020

The Append method in this test case can't work. It always creates a new instantiation of Tuple. And that new instantiation has its own Append method. This never ends.

Probably the type checker should catch this. We have a rule saying that a generic type can't refer to itself with different arguments. That rule has to apply not just to the body of the type, but also to the methods of the type. In this case I think the Append method should be invalid.

The translator had a bug that caused the infinite loop to terminate, generating code that had a type error. I've fixed that bug, and I've introduced a type instantiation loop check, so now this test case will fail with the translator reporting an infinite loop.

Reassigning to @griesemer to decide whether he should implement the suggested check for a recursive type reference.

gopherbot pushed a commit that referenced this issue Jun 20, 2020
It's not correct to do it here, as we aren't instantiating this
particular type.

Also had a loop check to avoid endless instantiating a recursive type.

Fixes #39688

Change-Id: Ief4c57bb5cea3013501e33ab5bc82a29707af5be
Reviewed-on: https://go-review.googlesource.com/c/go/+/239137
Reviewed-by: Ian Lance Taylor <iant@golang.org>
@beoran
Copy link
Author

@beoran beoran commented Jun 23, 2020

The interesting thing, though, it that if works as a function, at least for one level of tuples, though not for two levels, where the translator fails.
https://go2goplay.golang.org/p/EzRfpNlejP9

package main

import (
	"fmt"
)

type Nil struct {
}

type Tuple(type A, B) struct {
	A A
	B B 
}

func (u Tuple(A,B)) Head() A {
	return u.A
}

func (u Tuple(A,B)) Tail() B {
	return u.B
}

func New(type A,B)(a A, b B) Tuple(A, B) {
	return Tuple(A, B){a, b}
}


func AppendTuple(type A, B)(u Tuple(A,B), v B) Tuple(Tuple(A,B), B) {
	return Tuple(Tuple(A,B), B){u, v}
}

func NewList(type T)(v T) Tuple(Nil,T) {
	return Tuple(Nil, T){Nil{},v}
}


func main() {
	t := Tuple(int,Tuple(int,Tuple(int,Nil))){}
	l := NewList(7) 
	l2 := AppendTuple(l, 8)
	// l3:= AppendTuple(Tuple(Nil,int), int)(l2, 9)
	fmt.Printf("Foo: %v!\n%v\n%v\n", t, l, l2)
}

It would be nice if it worked at least as a function, also at depths greater than 1.

@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Jun 23, 2020

@beoran The test case in #39688 (comment) works for me using the current dev.go2go branch. The playground is probably not yet up to date with the latest changes.

@beoran
Copy link
Author

@beoran beoran commented Jun 24, 2020

Ok, that's great. However, this does lead me to this question: Why can it work with a function but not with a method? We could probably break the recursion in the method case by treating it as if it was a function.

@jimmyfrasche
Copy link
Member

@jimmyfrasche jimmyfrasche commented Jun 24, 2020

@beoran

If you instantiate Tuple with X and Y, then Tuple(X, Y) has an AppendTuple method but for that to exist its return type needs to exist so it needs to instantiate Tuple(Tuple(X, Y), Y).

But that has an AppendTuple method which needs to instantiate Tuple(Tuple(Tuple(X, Y), Y), Y) and so on.

The function not being directly bound to the type avoids this loop. It only needs to be instantiated when called.

@beoran
Copy link
Author

@beoran beoran commented Jun 24, 2020

Thanks for the explanation, however, I fail to see why the method has to be instantiated on definition while the function is instantiated on call. Should generic methods not also be instantiated on call?

@jimmyfrasche
Copy link
Member

@jimmyfrasche jimmyfrasche commented Jun 24, 2020

Methods are part of the type.

@beoran
Copy link
Author

@beoran beoran commented Jun 24, 2020

Hmm, yes that is right. If we consider it like that, recursion in methods should not be allowed by the type checker.

It does mean that lisp like lists will likely be possible at compile time using functions. Does this make the Go generics Turing complete, and is that desirable?

@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Jun 24, 2020

It is not desirable that Go generics be Turing complete. If you are able to demonstrate that, please do share it. Thanks.

@beoran
Copy link
Author

@beoran beoran commented Jul 3, 2020

I tried to see if the generics themselves could be made Turing complete, based on C++, but because there is no partial template instantiation, and type arguments may not be a variable arugment list, which makes it more difficult with this generics proposal than with C++ for generics to be Turing complete at compile time.

However, I found this article on Java that may be relevant: https://arxiv.org/pdf/1605.05274.pdf . It shows that the Java generic type checker is Turing complete. I wasn't able to construct the same in Go yet, but it might be that constrains suffer from the same problem.

@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Jul 3, 2020

The result for Java seems to hinge on covariant typing, which Go does not support with or without the generics described in the design draft, so I'm not too worried.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
5 participants
You can’t perform that action at this time.