Generics in Golang

Generics in Golang

Bereits 24 Stunden nach der Veröffentlichung der Programmiersprache Go am 10. November 2009 wurde ein Kommentar zum Einsatz von Generics in der Golang-Mailingliste veröffentlicht. Es wurde behauptet, daß moderne Programmiersprachen Generics benötigen.

Seitdem wurde viel über Generics für Go diskutiert und in den jährlich vom Go-Team durchgeführten Online-Umfragen zur Programmiersprache, den sogenannten User-Surveys (2016, 2017, 2018, 2019), wurden die Generics immer wieder als Wunschfeature der Entwickler aufgeführt. Im Jahr 2019 beantworteten 79% der Befragten zum Beispiel die Frage “Which critical language features do you need that are not available in Go?” mit: Generics.

Auf der Wiki-Seite des Golang Projektes befinden sich zusätzlich einige Einträge, die dies nocheinmal unterstreichen: https://github.com/golang/go/wiki/ExperienceReports#generics

Nach vielen Diskussionen und einer langen Wartezeit sollen Generics in Go nun tatsächlich im Sommer bis Ende 2021 mit Golang Version 1.18 kommen. So zumindest der Plan zum Zeitpunkt als dieser Artikel entsteht. Die Umsetzung wird sich wohl am verfügbaren Design Draft und dem zugehörigem Github Proposal Issue orientieren. Beide werden immer wieder angepasst und überarbeitet bzw. kommentiert. Ich möchte den aktuellen Stand in diesem Artikel vorstellen.

Was sind Generics überhaupt?

Mit dem Einsatz von Generics wird eine sogenannte generische Programmierung ermöglicht. Funktionen werden hierbei möglichst allgemeingültig und ohne feste Bindung an einen konkreten Datentypen entwickelt.

Möchten Sie z. B. in Go die Reihenfolge von Elementen in einem Slice umkehren, können Sie für ein []int die folgende Funktion implementieren:

func ReverseInts(s []int) {
    first := 0
    last := len(s) - 1
    for first < last {
        s[first], s[last] = s[last], s[first]
        first++
        last--
    }
}

Stehen Sie vor der Aufgabe ein []string umzukehren, können Sie auf folgende Funktion zurückgreifen:

func ReverseStrings(s []string) {
    first := 0
    last := len(s) - 1
    for first < last {
        s[first], s[last] = s[last], s[first]
        first++
        last--
    }
}

In beiden Fällen handelt es sich um den selben Algorithmus, mit dem die Slices umgekehrt werden. Leider kann die Umsetzung dieser Logik bzw. des Algorithmus im vorliegenden Beispiel wegen den unterschiedlichen Datentypen nicht wiederverwenden werden. Schleicht sich in die Implementierung ein Fehler ein, wird dieser eventuell, da ähnliche Implementierungen für andere Datentypen kopiert wurden, weiter verteilt und muss dann zeitaufwändig an sämtlichen Stellen behoben werden. Der zusätzliche Aufwand für die mehrfache Implementierung ist ebenso nicht von der Hand zu weisen. Golang will doch Tippaufwand minimieren…

Der vorliegende Fall zeigt einen klassischen Anwendungsfall für Generics. Die beiden Implementierungen unterscheiden sich nur im eingesetzten Datentyp. Der eigentliche Algorithmus ist in beiden Varianten identisch und könnte bei einer Trennung von Algorithmus und Datentyp weiterverwendet werden.

Bei einer generischen Umsetzung über die Programmiersprache wird mit einem sogenannten generischen Datentypen bzw. Template gearbeitet, der anstelle eines konkreten Datentyps, sozusagen als Platzhalter, bei der Implementierung verwendet wird. Durch Angabe eines Typ-Parameters durch den Entwickler beim Aufruf oder spätestens zum Kompilierungszeitpunkt wird dieser Platzhalter durch einen konkreten Datentypen ersetzt.

Für diesen generischen Typen können gewisse (Mindest-) Anforderungen definiert werden, die die später eingesetzten Datentypen mindestens zu erfüllen haben. Man spricht bei den Anforderungen auch von Constraints.

Eine, nicht auf Generics aufbauende, Möglichkeit der Umsetzung besteht darin Interfaces als Funktionsparameter einzusetzen und die oben genannten Constraints darüber auszudrücken. Beispiele findet man z. B. im sort Package der Standardbibliothek. Hierzu wäre keine Anpassung an der Sprache Go notwendig.

// A type, typically a collection, that satisfies sort.Interface can be
// sorted by the routines in this package. The methods require that the
// elements of the collection be enumerated by an integer index.
type Interface interface {
	// Len is the number of elements in the collection.
	Len() int
	// Less reports whether the element with
	// index i should sort before the element with index j.
	Less(i, j int) bool
	// Swap swaps the elements with indexes i and j.
	Swap(i, j int)
}

// Sort sorts data.
// It makes one call to data.Len to determine n, and O(n*log(n)) calls to
// data.Less and data.Swap. The sort is not guaranteed to be stable.
func Sort(data Interface) {
	n := data.Len()
	quickSort(data, 0, n, maxDepth(n))
}

Der gezeigte Ansatz über die Verwendung von Interfaces besitzt allerdings den Nachteil, dass für jeden Funktionsaufruf ein Interface vorhanden sein muss, das eventuell nur für diesen einen Aufruf benötigt wird. Der Aufwand für die Definition eines Interface, weil man ein Slice umkehren möchte, ist hoch. Für das Beispiel von oben mit dem Umkehren des Slice wäre dies wohl zu viel.

Da in der obigen Sort-Funktion mit Methoden der übergebenen Parameterwerte gearbeitet wird, scheint es eventuell noch vertretbar ein spezielles Interface zu nutzen. In einem weiteren, nicht über Generics gelöstem, Beispiel wird das Problem des Einsatzes von z. B. des allgemeinen Typs interface{} deutlich:

func doSth(val interface{}) interface{} {
	//wichtiger Code...
	return val
}

//irgendwo ein Aufruf
strings := []string{"1", "2", "3"}

fmt.Println(len(strings))
val := doSth(strings)
fmt.Println(len(val)) //GEHT NICHT! - Typinformation verloren!

//erst ein Typcast macht Aufruf möglich
fmt.Println(len(val.([]string)))

Die “generische” Funktion doSth besitzt als Parameter- und Rückgabetyp interface{}. Sie nimmt also sämtliche Parametertypen an und als Rückgabetyp wird ebenfalls interface{} eingesetzt. Das bedeutet, dass dem Rückgabewert “eine Typinformation fehlt” und somit nicht mehr typsicher gearbeitet werden kann. Im Beispiel kann die len Funktion nicht mehr ohne Type-Cast auf den eigentlichen Datentypen verwendet werden, da das Ergebnis nicht mehr als Array bzw. Slice verwendet werden kann.

Bei einer Umsetzung mittels Generics würde, wie oben bereits erwähnt, ein Type-Platzhalter verwendet, der ausgewertet und verwendet wird. Ein “Pseudocode” könnte so aussehen:

func doSthGeneric(val MEINTYP_GENERISCHER_TYP) MEINTYP_GENERISCHER_TYP {
	//wichtiger Code...
	return val
}

//irgendwo ein Aufruf
strings := []string{"1", "2", "3"}

fmt.Println(len(strings))
val := doSthGeneric(strings)
fmt.Println(len(val))

In diesem Beispiel wird für die Funktion der Bezeichner MEINTYP_GENERISCHER_TYP als Typplatzhalter verwendet. Dieser wird dann im jeweiligen Kontext zu einem entsprechendem “echten” Typen ausgewertet und dementsprechend verwendet. Im Beispiel würde der Bezeichner MEINTYP_GENERISCHER_TYP als []string Typ ausgewertet. Die Funktion doSthGeneric würde in obigen Beispiel dementsprechend ein []string zurückliefern.

Wie sehen Generics in Go aus?

Das Pseudocode-Beispiel ist schon sehr nahe an der tatsächlichen Umsetzung des Golang Design Drafts, der die Grundlage für die spätere Umsetzung sein soll. In Go werden sogenannte Type Parameter verwendet, die einem Type-Platzhalter einen Namen und ein Constraint zuordnen. Diese werden bei entsprechenden Funktionen nach deren Namen und vor der Parameterliste aufgenommen. Der Syntax ist in folgendem Beispiel gezeigt:

func doSth[Elem any](val []Elem)
	      ^^^^^^^^^^
	das ist der Type-Parameter

Ein Type-Parameter enthält dementsprechend einen Namen (im Beispiel Elem) und eine entsprechende Einschränkung, das sogenannte Constraint (im Beispiel any). Ein eingesetzter Parameter bei der Verwendung ist dann valide wenn er dem angegebenen Constraint entspricht. Der weitere Aufbau der Angabe entspricht dem einer normalen Parameterliste: mehrere Angaben werden durch Kommata getrennt [Elem1 any, Elem2 any], bei gleichen Constraints kann eine Kurzform verwendet werden [Elem1, Elem2 any]. Umklammert werden die Type-Parameter durch eckige Klammern [].

In Go handelt es sich bei den Constraints um Interfaces. Der neue vordefinierte Name bzw. Type any beschreibt ein Constraint, bei dem alle Typen zugelassen sind (analog zu interface{}). Die Arbeit mit Interfaces schauen wir uns weiter unten noch an.

Generische Funktionen

Für das initiale Reverse-Beispiel heißt das, das wir nicht für jeden Datentypen eine neue Funktion erstellen müssen, sondern dass eine generische Funktion ausreicht:

func Reverse[T any](s []T) {
    first := 0
    last := len(s) - 1
    for first < last {
        s[first], s[last] = s[last], s[first]
        first++
        last--
    }
}

...
strings := []string{"1", "2", "3"}
Reverse(strings)
fmt.Println(strings)

Die zweite doSth-Funktion würde dementsprechend so aussehen und wir müssen keinen Type-Cast verwenden um die len Funktion zu nutzen:

func doSthGeneric[T any](val T) T {
	//somthing important...
	return val
}

...
//generic return type
fmt.Println(len(strings))
val := doSthGeneric(strings)
fmt.Println(len(val))

Für das Sortieren von Elementen benötigt der Algorithmus mindestens eine Funktion mit der die Elemente verglichen werden können. In folgendem Beispiel wird innerhalb des Type-Parameters direkt ein Constraint in Form eines Interfaces definiert. Das Interface besitzt eine Methode Less(val Elem) bool, die wiederrum einen Parameter vom Typ Elem entgegen nimmt und mit dem eigenen Wert vergleicht:

func Sort[Elem interface{ Less(val Elem) bool}](list []Elem) {
	...
}

Für das Beispiel heißt das, dass die Funktion Sort mit jedem Datentypen als Parameter aufgerufen werden kann solange er eine Less Methode besitzt, mit der Werte verglichen werden können. Die Sichtbarkeit des Constraint-Type ist auf die jeweilige Funktion beschränkt, für die er definiert wurde. Das heißt, dass der Typ Elem auch (und nur) innerhalb der vorliegenden Sort Funktion verwendet werden kann. Die Sichtbarkeitsgrenze beginnt übrigens mit der eckige Klammer [ mit der die Type-Parameter eingeleitet werden und endet des (Funktions-) Blocks.

Versucht man die Sort Funktion mit einem []string aufzurufen, wird dies mit folgender Fehlermeldung des Compilers quittiert:

Aufruf:

strings := []string{"1", "2", "3"}

Sort(strings)  //Geht nicht!
fmt.Println(strings)

Fehlermeldung des Compilers:

string does not satisfy interface{Less(val Elem) bool} (missing method Less)

Ein komplettes, valides Beispiel sieht so aus:

type ObjectToSort struct {
    name string
}

func (ots ObjectToSort) Less(toCompare ObjectToSort) bool {
    return ots.name < toCompare.name
}

func Sort[Elem interface{ Less(val Elem) bool}](list []Elem) {
	//somthing important...
	return
}

func TestingSort() {
    values := []ObjectToSort{{"1"}, {"2"}, {"3"}}
    Sort(values)
	fmt.Println(values)
}

Die Thematik der Type-Inferenz, also das automatische bestimmen des zu verwendenden Datentypen, habe ich in diesem Artikel absichtlich ausgeklammert bzw. wie in den obigen Beispielen vorausgesetzt. Wie der eingesetzte Datentyp tatsächlich bestimmt wird können Sie im Design Draft - Type inference nachschlagen.

Zur Vollständigkeit: Funktioniert die Type-Inferenz nicht, kann bzw. muss der entsprechende Typ beim Aufruf der Funktion mitgegeben werden:

Sort[ObjectToSort](values)

Wie arbeitet der Compiler

Bei der Verwendung der Generics werden zwei Schritte unterschieden:

  • Instantiation

  • Invocation

Im ersten Schritt der Instantiation werden die generischen Type-Argumente durch konkrete Typen ersetzt. Dieser Schritt findet zum Zeitpunkt der Übersetzung des Sourcecodes durch den Compiler statt und wandelt intern die generische Funktion in eine konkrete, typisierte Funktion um, die im Anschluss wie eine ganz normale Funktion verwendet werden kann. In diesem Schritt wird vom Compiler zusätzlich überprüft, ob der angegebene Typ die ebenfalls definierten Constraints erfüllt. Die durch die Instantiation entstandene interne Funktion unterliegt den bekannten Regeln der Programmiersprache Go.

Der zweite Schritt der Invocation läuft wie in jeder anderen Go-Anwendung ab. Parameter werden auf ihre Typen überprüft und der Funktionsaufruf findet wie gewohnt statt.

Wenn man so möchte generiert der Compiler im Hintergrund im ersten Schritt eine Menge neuer, passender Funktionen, die im zweiten Schritt aufgerufen werden können.

Generische Datentypen

Auch Datentypen können generisch aufgebaut werden und es gelten die selben Regeln, auch zur Sichtbarkeit von Type-Parametern. Das folgende Beispiel zeigt das generische Interface Lesser, das einen Type-Parameter Elem mit einem any Constraint definiert und diesen in der Methode Less verwendet.

type Lesser[Elem any] interface {
    Less(val Elem) bool
}

Der Einsatz dieses generischen Interfaces in einer generischen Funktion sieht dann dementsprechend aus. Achten Sie hier auf die nötige Instantiation des generischen Typen Lesser durch Lesser[Elem]. Jede generische Typ und jede generische Funktion müssen vor einer Verwendung instantiiert werden. Mit dem Feature der Type-Inferenz kann unter Umständen der Datentype zur Instanziierung automatisch ermittelt werden und muss nicht explizit mit angegeben werden (siehe Design Draft - Type inference).

func SortInterface[Elem Lesser[Elem]](list []Elem) {
	//somthing important...
	return
}

Wie im Beispiel zu sehen, müssen Interfaces nicht direkt als Type-Parameter verwendet werden, sondern können auch extern definiert werden. In diesem Fall handelt es sich sogar um ein generisches Interface.

Das komplette Beispiel sieht so aus:

type Lesser[Elem any] interface {
    Less(val Elem) bool
}

func SortInterface[Elem Lesser[Elem]](list []Elem) {
	//somthing important...
	return
}

func TestingInterfaceSort() {
    values := []ObjectToSort{{"1"}, {"2"}, {"3"}}
    Sort(values)
    SortInterface[ObjectToSort](values)
	fmt.Println(values)
}

Generische Implementierungen

Innerhalb einer generischen Funktion kann der übergebene Type-Parameter ebenfalls verwendet werden, da dessen Sichtbarkeit immer noch gegeben ist. Wichtig hierbei ist zu beachten, dass der Datentyp von list[i] der Typ Elem ist und dieser einem konkreten Typen entspricht und kein Interface darstellt. Das Constraint von Elem wird zwar über ein Interface beschrieben, stellt aber selbst kein Interface dar. Für den Typ Elem ist ausschließlich klar, dass er eine Methode Less besitzt.

Ein Type-Parameter ist ein echter Typ und kein Interface-Type.

func SortInterface[Elem Lesser[Elem]](list []Elem) {
	var i, j int
	//Der Typ von list[i] ist Elem
	//Elem ist kein Interface-Type!
    if list[i].Less(list[j]) {
        //somthing important...
    }
}

Generics für Go ausprobieren

Möchten Sie Go Generics vorab, also vor der Veröffentlichung der finalen Go-Version, ausprobieren haben Sie die Möglichkeit den vom Go-Team bereitgestellten Playground zu nutzen oder die entsprechende Go-Version selbst zu kompilieren um damit eine lokale Entwicklung durchzuführen.

Das Kompilieren des Go-Sourcecodes klingt im ersten Moment vielleicht etwas kompliziert und zeitaufwändig. Das ist glücklicherweise nicht der Fall.

Ich habe in Github ein kleines Go-Generics Projekt mit den Beispielen aus dem Artikel angelegt. Dort befindet sich auch ein Dockerfile mit dem die entsprechende Go-Runtime übersetzt werden kann. Außer Docker sind keine weiteren Abhängigkeiten zu erfüllen.

Um eine Go-Generics Umgebung zu bauen ist mit dem Dockerfile nur dieses Kommando nötig:

docker build --no-cache -t go-generics-playground .

Ausgecheckt und kompiliert wird der Branch Git-Branch dev.go2go, der die Go-Generics Erweiterungen enthält. Da der Sourcecode ausgecheckt wird hängt die Dauer des Imagebaus stark von der Übertragungsrate ab. Auf meinen normalen Entwickler-Laptop mit einer DSL Leitung ist das Image nach ca. 2 Minuten fertig gebaut. Dann kann man lokal mit den Generics loslegen!

Der Generic Sourcecode muss sich in dieser Version, wie im Beispiel-Repo zu sehen, in *.go2 Dateien befinden. Wenn Sie den Github-Workspace ausgecheckt haben und das Docker-Image erfolgreich erstellt wurde, kann mit folgendem Kommando das Beispiel kompiliert und ausgeführt werden:

docker run -it -v `pwd`:/samples/src/github.com/sourcefellows/go-generics-samples/ go-generics-playground /bin/bash -c 'go tool go2go run cmd/main.go2'

Das obige Kommando bezieht sich auf die Beispiele aus Github! Die in Docker gemappten Pfade sind entsprechend angegeben. Sie können die Übersetzung eigenen Codes auch direkt über einen Aufruf starten. Das erfolgt über das go2go Tool, das explizit aufgerufen werden muss.

go tool go2go run cmd/main.go2

Viel Spaß mit den Generics!

22.01.2021

 

Der Author auf Twitter: