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.

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 ?

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.

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

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.

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.

@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.

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.

@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.

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?

Methods are part of the type.

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?

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

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.

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.

No longer relevant