8000 GitHub - faiface/generics: A proof-of-concept implementation of my generics proposal for Go
[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to content

faiface/generics

BranchesTags

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

33 Commits
degen
degen
 
 
examples
examples
 
 
go
go
 
 
LICENSE
LICENSE
 
 
README.md
README.md
 
 
go.mod
go.mod
 
 
main.go
main.go
 
 

Repository files navigation

A proof-of-concept implementation of my generics proposal for Go

This program translates a Go file that uses generics into a regular Go file that can be run.

$ go get github.com/faiface/generics

Then navigate to the repo folder and run:

$ go install

This will install the generics command and you should be able to use it just by typing its name (if you have your $PATH set up correctly).

I have taken measur 8000 es to prevent you from running this in production. Please, do not run this in production. The single measure taken is that this program only translates a single file. This means that generic functions and types are only usable within that one file.

Here's a trivial example.

// reverse.go

package main

import "fmt"

func Reverse(a []type T) {
    for i, j := 0, len(a)-1; i < j; i, j = i+1, j-1 {
        a[i], a[j] = a[j], a[i]
    }
}

func main() {
    a := []int{1, 2, 3, 4, 5}
    b := []string{"A", "B", "C"}
    Reverse(a)
    Reverse(b)
    fmt.Println(a)
    fmt.Println(b)
}

Here we have a file called reverse.go that uses generics. Here's how we translate it:

$ generics -out out.go reverse.go

And here's what we get!

package main

import "fmt"

func Reverse_int(a []int) {
    for i, j := 0, len(a)-1; i < j; i, j = i+1, j-1 {
        a[i], a[j] = a[j], a[i]
    }
}

func Reverse_string(a []string) {
    for i, j := 0, len(a)-1; i < j; i, j = i+1, j-1 {
        a[i], a[j] = a[j], a[i]
    }
}

func main() {
    a := []int{1, 2, 3, 4, 5}
    b := []string{"A", "B", "C"}
    Reverse_int(a)
    Reverse_string(b)
    fmt.Println(a)
    fmt.Println(b)
}

Then, of course, we can run out.go:

$ go run out.go
[5 4 3 2 1]
[C B A]

More example

That was just a silly little example. For more complex examples, take a look into the examples directory:

The proposal

This is a refined version of a proposal I submitted a few weeks ago. You can find the original version here.

This version is very similar to the original proposal, it only differs in three things:

  1. The gen keyword has been replaced with two keywords: type and const. This implementation only implements the type keyword, const will be described below nonetheless.
  2. An ord type restriction in addition to the previously described eq and num.
  3. The type keyword now must also appear in the declarations of generic types.

Now I will describe the proposal as concisely as I can. If you have questions, scroll down to the FAQ section.

The type keyword

Let's start with generic functions. Here's a pseudocode of a generic Map function on slices:

// PSEUDOCODE!!
func Map(a []T, f func(T) U) []U {
    result := make([]U, len(a))
    for i := range a {
        result[i] = f(a[i])
    }
    return result
}

In case you don't know, a Map function takes a slice and a function and returns a new slice with each element replaced by the result of the function applied to the original element.

For example: Map([]float64{1, 4, 9, 16}, math.Sqrt) returns a new slice []float64{1, 2, 3, 4}, taking the square root of each of the original numbers.

To make this a valid Go code under my proposal, all you need to do is to mark the first (and only the first) occurrence of each type parameter (= an unknown type) in the signature with the type keyword. The Map function has two:

//           here              here
//            \/                \/
func Map(a []type T, f func(T) type U) []U {
    result := make([]U, len(a))
    for i := range a {
        result[i] = f(a[i])
    }
    return result
}

Nothing else changed.

The type keyword basically declares a type parameter in a signature. The name is then visible in the entire scope of the function.

There are three rules about the placement of the type keyword in signatures:

  1. It's only allowed in package-level function declarations.
  2. In functions, it's only allowed in the list of parameters. Particularly, it's disallowed in the list of results.
  3. In methods, it's only allowed in the receiver type.

The last two rules can be remembered together: type is only allowed inside the first pair of parentheses.

Unnamed type parameters

Okay, so no type in the list of results. But how do we make a function like this Read? The only occurrence of the T type is in the result:

// DISALLOWED!!
func Read() type T {
    var x T
    fmt.Scan(&x)
    return x
}

To make this function work, we need to use an unnamed type parameter. It's basically a dummy generic parameter:

func Read(type T) T {
    var x T
    fmt.Scan(&x)
    return x
}

The value of the unnamed parameter is irrelevant. We're only interested in the type. That's why when calling the Read function, we pass in the type directly:

func main() {
    name := Read(string)
    age := Read(int)
    fmt.Printf("%s is %d years old.", name, age)
}

Don't worry, this doesn't send us to the dependent typing land because we can't return types, only accept them.

It's simple, if a parameter is an unnamed generic parameter, you pass a type directly. Otherwise, you pass a value and the type system will infer the type.

This notation also makes it possible to give a type to the built-in new function:

func new(type T) *T {
    var x T
    return &x
}

One important rule: generic functions cannot be used as values. They can't be assigned to variables and they can't be passed as arguments. To pass a specialized version of a generic function as an argument, wrap it in an anonymous function, like this:

SomeFunction(func() int {
    return Read(int)
})

Restricting types

Some functions (or types) want to declare that they don't work with all types, but only with ones that satisfy some conditions. For example, the keys of a map must be comparable. That is a restriction. A Min function only works on types that are orderable (i.e. can be compared with <).

Initially, my proposal excluded any support for restricting types for the purpose of simplicity. The contracts proposal by the Go team has received (justifiable) criticism for introducing complexity by supporting contracts, which make it possible to specify arbitrary restrictions on types.

But some restrictions are extremely useful. That's why I eventually decided to include three possible restrictions that should cover the majority of use-cases. This decision is governed by the 80/20 principle.

Here are the three possible restrictions:

  1. eq - Comparable with == and !=. Usable as map keys.
  2. ord - Comparable with <, >, <=, >=, ==, !=. A subset of eq.
  3. num - All numeric types: int*, uint*, float*, and complex*. Operators +, -, *, /, ==, !=, and converting from untyped integer constants works. Not a subset of ord.

To use a type restriction, place it right after the first occurrence of the type parameter.

For example, here's the generic Min function:

//                   here
//                    v
func Min(x, y type T ord) T {
    if x < y {
        return x
    }
    return y
}

Notice that num is not a subset of ord. This is because the complex number types are not comparable with <. To accept only the numeric types that are also orderable, combine the two restrictions like this: type T ord num.

The eq, ord, and num words have no special meaning outside of the generic definitions. They are not keywords.

Generic types

We've covered everything about generic functions, let's move on to generic types.

To define a generic type, simply list the type parameters in parentheses right after the type name. Like this:

// List is a generic singly-linked list.
type List(type T) struct {
    First T
    Rest  *List(T)
}

And as you can already see in the definition, to use a generic type, list the arguments in parentheses after the type name. For example List(int) is a list of integers, and List(string) is a list of strings.

When defining a type with multiple generic parameters, mark each one with type:

// SyncMap is a generic hash-map usable from multiple goroutines simultaneously.
type SyncMap(type K eq, type V) struct {
    mu sync.Mutex
    m  map[K]V
}

Methods work as usual:

func (sm *SyncMap(type K eq, type V)) Store(key K, value V) {
    sm.mu.Lock()
    sm.m[key] = value
    sm.mu.Unlock()
}

But don't forget that the type keyword is only allowed in the receiver type. For explanation, see FAQ.

Generic array lengths (unimplemented)

The original proposal also included generic array lengths. There is still an intention to support them, but I haven't implemented them yet, because this has been enough work so far. They'd work like this:

func Reverse(a *[const n]type T) {
    for i, j := 0, n-1; i < j; i, j = i+1, j-1 {
        a[i], a[j] = a[j], a[i]
    }
}

And that's all! Happy hacking!

FAQ