Go-li language user manual

func Compar(a, b *) int

func Transpose(matrix [], stride int) (o [], newstride int)

func Sort(compar func(*,*), slice [])

Introduction

Go Li also known as go language improved is a prototype programming language to test a limited “generics” features added to go language. It allows to use parameterized functions also known as generic functions. Each such a function is parametrized by exactly one type, known as the wildcard type.

Installation

Visit http://go-li.github.io/xgtest.html# to use an online playground. Or download a source to source translator from the url https://github.com/go-li/transpiler. This translator is able to translate source code packages from go-li to golang. It is invoked ./transpiler -P /source/arbitrary/package/directory -T /destination/package/directory.

Alternatively, you can try the experimental gccgo based compiler below.

Basic usage

In this example we demonstrate a reverse(args ...) generic function. Reverse is a generic function, because it has a parameter of a generic type.

What is a generic type? What generic types exist?

Generic type is any type that contains the omitted type placeholder, or one that contains another generic type. The following table lists examples of commonly used generic types:

Any named type with underlying generic type is also a generic type.

What is a generic function or method?

Each generic function must satisfy the following two rules:

1. It must be toplevel (in the file scope). Generic closures are invalid.
2. It must have at least one parameter with generic type. (Generic result is not sufficient.)

The reason for the first rule is that generic closures are currently disallowed because generic closures are rarely if never useful. The reason for the second rule is that it must be possible to derive the wildcard type from every single callsite. Without a generic function parameter, this is impossible. For this reason top-level functions having only generic typed results and no generic typed parameters are invalid. The following table lists several examples of generic and non generic top-level functions together with validity:

Suppose we want to return nil slice of arbitrary type? How do we fix the function 3? It’s simple, we add some generic typed parameter. When we call the function, we can pass a typed nil.

Calling top-level generic functions

When calling top-level generic function, for every call site, there are these rules:

1. It must be possible to derive the wildcard type
2. It must be possible to derive the concrete named return types for every generic named return type (if any).
3. There can not be any wildcard type conflict (with the exception of interface{} wildcard and concrete varargs passed as … typed variadic parameters )

In the following wildcard type derivation examples, we are going to call this top-level function:

We are going to call Wildcards function using these callsites. We assume the function Wildcards is called from a non-generic function. Validity and explanation why follow the call site code:

What follows is we are going to call top-level generic function Varargs.

Generic named type callsites with concrete type mappings

It’s possible to pass named concrete types as named generic parameters. This demonstrates this feature. In this scenario, from argument x and parameter a it can be derived that the type Tint is the concrete type that implements the generic type T

The following demo is invalid. The translator has no way to know what concrete type should the variable y in main have. In other words, the possibility that generic type Y shall become concrete type Yint is unrelated to the fact that the generic type X becomes the concrete type Xint.

Operations allowed in generic functions

Examples of compile time type safe operations

Examples of run time “type safe” operations

So what can we use this “generics” for

This is not a well studied area. A surprising uses of this mechanism could be discovered. Let’s first try to summarise what is known to be possible today. By possible we mean it’s done in a compile time type safe way.

Sorting of slices. Binary heap built from a slice. Byte array keyed arbitrary valued sorted sets (AVL tree). Max(a,b), Min(a,b) functions for arbitrary types. Double slice arbitrary keyed arbitrary valued hashtable that is only 20% slower than builtin map. Type safe doubly linked list. Leaky pool. Ring buffer “queue” made from a slice. Map[foo]struct{} set. float64/float32 agnostic math functions like transpose, matrix multiply by constant.

Not compile time type safe:

Deduplicate a slice by throwing things into a map. Convert a slice using function to arbitrary another type slice.

Unknown:

Call traits. Graphs for instance immediate dominator. Bimap. Multiple indexes over a collections. data accessors in Dietmar Kühl's Masters Thesis on generic graph algorithms. Caches. Compile-time type-safe sync.Pool. Set operations over collections.

Errors and solutions

undetermined wildcard from missing varargs in call to foo

You have a varargs only function like:

You can’t call it like: foo()

You need to provide at least one argument from which the wildcard type can be determined. For instance you can pass typed nil to the function: foo((*int)(nil)) . Or you can pass some concrete (the same) types, for instance foo("a","b","c") . Or foo(1,2,3)

cannot convert nil (untyped nil value) to untyped void

You can’t call it like: foo(nil)

You need to provide some argument from which the wildcard type can be determined. For instance you can pass typed nil to the function: foo((*int)(nil))

wildcard cannot be untyped nil (untyped nil value)

You have a generic pointer accepting function like:

You can’t call it like: accept(nil)

You need to provide some argument from which the wildcard type can be determined. For instance you can pass typed nil to the function: accept((*int)(nil))

GCCGO-li user manual

Installation - x86-64 Linux only

1.        Download the gccgo-8.0.1-006.tar.xz from the generics slack chat channel. The URL of the channel is: https://gophers.slack.com/messages/C88U9BFDZ/

2.        After downloading, verify the authenticity of the file.

$ sha256sum gccgo-8.0.1-006.tar.xz

337c04797b7c2c0fc7e586b309fad19cac864dfd9f7ef4420f0f427123db3ccd  gccgo-8.0.1-006.tar.xz

3.        Unpack the archive ether from the file browser or using command:

$ tar -xf gccgo-8.0.1-006.tar.xz

You can unpack it to any location. But the rest of the guide assumes you moved the unpacked gccgo folder to /opt. The file structure should be like this:

Now it’s installed. You can skip to testing the installation.

Installation from source

You need gcc source from gcc.gnu.org, and the generics patches from github.

For example I’ve downloaded gcc-8-20180325.tar.xz and these patches:

https://github.com/go-li/gofrontend/commit/1f227e14dd73acff48a8909bbef0ff4b9da73f53.patch

https://github.com/go-li/gofrontend/commit/b448b08e273af75ffd007b76230306c88d9e6f50.patch

You also need the backend patch, known as patch zero.patch:

https://pastebin.com/raw/VhNtCvbY

Create a folder gccgo and inside a folder emptydir and gofrontend. Unpack the gcc archive to emptydir. In gofrontend create two folders go and libgo. Put the patches to gofrontend.

This guide assumes you are building in /tmp/gccgo. If you plan to shut down your computer, pick an alternate location for example in your home folder.

Copy over everything from /tmp/gccgo/emptydir/gcc-8-20180325/gcc/go/gofrontend/ to /tmp/gccgo/gofrontend/go/. Also copy everything from /tmp/gccgo/emptydir/gcc-8-20180325/libgo/ to /tmp/gccgo/gofrontend/libgo/

Now run this in the gofrontend folder to apply the changes from github:

In folder emptydir run this recipe

Now, in emptydir, you can configure.

Now after configure went ok, run make (this could take up to two hours!!)

Once that’s succeeded, run sudo make install. Your gccgo will appear in /opt/gccgo/

Testing

You can download basic test programs to determine if the generics work. These programs are available at https://github.com/go-li/demo.

This tested the bubblesort demo. Other demos from this repo should work as well.

Gccgo bugs

This gccgo frontend has many bugs. However this does not necessarily mean that your programs will fail in production. If your program successfully compiles, it’s usually safe to run it. These bugs limit the possible generics features that you can use in your program. If you use a buggy feature, your program will fail to compile or the compiler will crash.

Varargs does not work

You cannot create and use generic varargs functions. The demo from the top of this document does not work.

Unsafe packages cannot use generics

If you import unsafe, your generic functions won’t be recognized to be generic. Therefore you should never import unsafe while using this proposal.

Import/export does not work for generics

If you create a generic function with a capitalized name, you are asking for a trouble. It will never work.

Wildcard substitution bugs

The type returned by a generic-type-result function is sometimes not the one it should be. This is because wildcard substitution is buggy. In particular parameter-related named types are not returned and not substituted into the result type. You can workaround by casting the function result variable to the right type manually. Also if you use unusual return types like a generic map it will crash because substitution is not implemented.

Only a few generic operations are supported

Only operations supported is copying wildcard-typed value using a pointer:

*dst = *src

And a generic slice index address dereference expression

pointer = &slice[5]

Furthermore you can make generic slices:

make([], 4)

Cannot assign generic variables to interface{}

This doesn’t work and never will.

Cannot cast interface{} to a generic type, like slice := foo.([])

This doesn’t work and never will.

The protection against using of generic types outside of generic context is missing

You should always first develop and test your generic program using the transpiler / playground. Only when you get no errors, you can attempt to compile using gccgo. If you use generic types outside of generic context (top-level generic function) there is no safety and no guarantees.