Go: Examples and further details

Martin Sulzmann

Overview

Gimmick: Variadic functions in Go

func sumAreas(shs ...shape) int {
    var a int = 0
    for _, elem := range shs {
        a = a + elem.area()
    }
    return a
}

We can define arguments with a variable number of arguments (of the some type) and iterate over them via a for loop.

In the above we don’t care (_) about the index position.

Variadic functions simply provide some syntactic sugar compared to using slices as arguments.

// Expects a list of shapes (slice).
// Pretty much the same compared to sumAreas.
// Only difference is that we first need to create a slice to call shapes2.
func sumAreas2(shs []shape) int {
    var a int = 0
    for _, elem := range shs {
        a = a + elem.area()
    }
    return a
}

Complete example

package main

type shape interface {
    area() int
}

type rectangle struct {
    length int
    width  int
}

type square struct {
    length int
}

func (r rectangle) area() int {
    return r.length * r.width
}

func (s square) area() int {
    return s.length * s.length
}

func sumAreas(shs ...shape) int {
    var a int = 0
    for _, elem := range shs {
        a = a + elem.area()
    }
    return a
}

func sumAreas2(shs []shape) int {
    var a int = 0
    for _, elem := range shs {
        a = a + elem.area()
    }
    return a
}

func main() {

    r := rectangle{1, 2}
    s := square{3}

    sumAreas(r, s, s, r)

    sumAreas2([]shape{r, s, s, r})

}

Abstract data types via interfaces/methods

An abstract data type is defined in terms of its behavior. For example, operations performed on this type etc. Implementation details (of this type) are left abstract (hidden).

We build an abstract data type Set via interfaces. The below is an example where we use recursive interfaces. Recursive means that the interface type appears in some type declaration of some method.

package main

import "fmt"

type Set interface {
    empty() Set
    isEmpty() bool
    insert(int) Set
}

type SetImpl []int

func (xs SetImpl) empty() Set {
    return (SetImpl)([]int{})
}

func (xs SetImpl) isEmpty() bool {
    return len(xs) == 0
}

func (xs SetImpl) insert(x int) Set {
    ys := append(xs, x)
    return (SetImpl)(ys)
}

// This is a function, not a method.
func mkEmptySet() Set {
    xs := []int{}
    return (SetImpl)(xs)
}

func main() {
    // We consider sets of integers here
    s := SetImpl{1, 2, 3}

    fmt.Printf("%t", s.isEmpty())
}

Important.

Consider

func (xs SetImpl) empty() Set {
    return (SetImpl)([]int{})
}

We must apply the cast (SetImpl)([]int{}).

[]int{} is of type []int but this type is not compatible with Set.

SetImpl satisfies Set and therefore SetImpl≤SetSetImpl \leq Set.

Hence, isEmpty returns a value of type Set.

Algebraic data types and pattern matching via interfaces/methods

Algebraic data types are build by composition via other types. Examples are tuples and structs. Tuples and structs correspond to AND. For example, consider

type Result struct {
    val int
    status bool
}

The struct Point consists of a value of type int and a value of type bool.

Further examples of algebraic data types are sum types (also referred to as disjoint union, variant type). Values of sum types are created via distinct constructors. Hence, a sum type corresponds to OR. Languages with support for sum types usually allow for a form of pattern matching via which we can analyse and extract the data connected to each value case of a sum type.

Go has no direct support for sum types and pattern matching. However, we can emulate both with the help of interfaces/methods.

Maybe (Option) type

The maybe type (also kown as the option type is typical example of a sum type. The maybe type supports two value cases: Either nothing (representing failure) or just something (representing success). In Go, the maybe type can be represented as follows.

type Nothing struct{}

type Just struct {
    val int
}

type Maybe interface {
    isNothing() bool
    isJust() bool
    fromJust() (int, bool)
}

func (x Nothing) isNothing() bool {
    return true
}

func (x Just) isNothing() bool {
    return false
}

func (x Nothing) isJust() bool {
    return false
}

func (x Just) isJust() bool {
    return true
}

func (x Nothing) fromJust() (int, bool) {
    return 1, false
}

func (x Just) fromJust() (int, bool) {
    return x.val, true
}

We introduce named types Nothing and Just to represent the two cases (failure and success). The Maybe interface and method instances for Nothing and Just imply that Maybe is a sum type with constructors Nothing and Just. Pattern matching in Go is emulated via overloaded method definitions.

Linked lists

As another example of a sum type, we consider linked lists.

type Nil struct{}
type Cons struct {
    elem int
    next List
}

type List interface {
    len() int
}

func (x Nil) len() int { return 0 }

func (x Cons) len() int {
    return 1 + x.next.len()
}

There two constructors. Nil to create the empty list and Cons via which we add an element to an existing list. What is interesting here is that in the type definition for Cons we declare that next is some List where List is any type that supports the len method.

Expression language

Via algebraic data types we can describe context-free/EBNF grammars.

Consider the following simple expression language

N ::= ... | -1 | 0 | 1 | ...

E ::= N | E + E | E * E

and its representation in Go represented as an algebraic data type.

type Exp interface {
    eval() int
}

type Num int
type Mult [2]Exp
type Plus [2]Exp

func (x Num) eval() int {
    return (int)(x)
}

func (e Mult) eval() int {
    n1 := e[0].eval()
    n2 := e[1].eval()
    return n1 * n2
}

func (e Plus) eval() int {
    n1 := e[0].eval()
    n2 := e[1].eval()
    return n1 + n2
}

We not only represent the expression language in Go. In addition, we also provide for some methods that operate on expressions. In the above, we introduce an eval method that evaluates expressions.

Abstract syntax trees (ASTs)

The above expression grammar represents an abstract representation of the syntactic structure of expressions. As we know from theoretical computer science, derivations that verify that an expression is well-formed (part of language described by the above grammar) can also be represented as trees. Hence, the representation of the expression grammar in Go allows us to represent abstract syntax trees (ASTs).

Comparison to Java

// OO sketch

class Exp {
   int eval();
}

class Num : Exp {
   int x;
   Num(int y) { x = y ; }
   int eval( return x; }

class Plus : Exp {
   Exp left, right;
   Plus(Exp x, y) { left = x; right = y; }
   int eval() { return left.eval() + right.eval(); }
}

class Mult : Exp {
   Exp left, right;
   Plus(Exp x, y) { left = x; right = y; }
   int eval() { return left.eval() * right.eval(); }
}

Complete examples

Maybe and linked lists

package main

import "fmt"

type Nothing struct{}

type Just struct {
    val int
}

type Maybe interface {
    isNothing() bool
    isJust() bool
    fromJust() (int, bool)
}

func (x Nothing) isNothing() bool {
    return true
}

func (x Just) isNothing() bool {
    return false
}

func (x Nothing) isJust() bool {
    return false
}

func (x Just) isJust() bool {
    return true
}

func (x Nothing) fromJust() (int, bool) {
    return 1, false
}

func (x Just) fromJust() (int, bool) {
    return x.val, true
}

func myDiv(x int, y int) Maybe {
    if y == 0 {
        return Nothing{}
    }

    return Just{x / y}
}

// Linked lists
type Nil struct{}
type Cons struct {
    elem int
    next List
}

type List interface {
    len() int
}

func (x Nil) len() int { return 0 }

func (x Cons) len() int {
    return 1 + x.next.len()
}

func main() {

    // maybe
    r, _ := myDiv(3, 2).fromJust()
    fmt.Printf("\n %d", r)

    // lists
    list := Cons{1, Cons{2, Cons{3, Nil{}}}}

    fmt.Printf("\n %d", list.len())

}

Expression language

package main

import "fmt"

type Exp interface {
    eval() int
}

type Num int
type Mult [2]Exp
type Plus [2]Exp

func (x Num) eval() int {
    return (int)(x)
}

func (e Mult) eval() int {
    n1 := e[0].eval()
    n2 := e[1].eval()
    return n1 * n2
}

func (e Plus) eval() int {
    n1 := e[0].eval()
    n2 := e[1].eval()
    return n1 + n2
}

// Helper functions to build ASTs by hand

func number(x int) Exp {
    return Num(x)
}

func plus(x, y Exp) Exp {
    return (Plus)([2]Exp{x, y})

    // The type Plus is defined as the two element array consisting of Exp elements.
    // Plus and [2]Exp are isomorphic but different types.
    // We first build the AST value [2]Exp{x,y}.
    // Then cast this value (of type [2]Exp) into a value of type Plus.

}

func mult(x, y Exp) Exp {
    return (Mult)([2]Exp{x, y})
}

func main() {

    ex := plus(number(1), mult(number(2), number(3)))

    fmt.Printf("\n %d", ex.eval())
}

Generic Go examples

Bounded type parameters (with trivial bounds)

func swap[T any](x *T, y *T) {
    tmp := *x
    *x = *y
    *y = tmp
}

The generic swap function.

T is a type parameter.

In Go, type parameters always come with a bound (aka constraint).

We refer to this as bounded type parameters (or bounded types for short). Constrained type parameters is another appropriate name.

In the above example, T is constrained by any where any is a short-hand for interface{} (the empty interface).

Any type satisfies the empty interface. Hence, we can swap values of any type.

Type instances

We can use the swap function to swap Integer values, Boolean values, …

To do so, we need to explicitely provide the type instance.

    x := 1 // x is of type int
    y := 3

    swap[int](&x, &y)

In the above, we wish to swap int values.

The program text swap[int] states that the type parameter T in the definition of swap will be instantiated by int.

Interfaces

Interfaces are another means to write generic functions in Go.

type Show interface {
    show() string
}

type boolean struct {
    val bool
}

func (this boolean) show() string {
    if this.val {
        return "true"
    } else {
        return "false"
    }
}

type number struct {
    val int
}

func (this number) show() string {
    return strconv.Itoa(this.val)
}

The receiver types boolean and number implement the Show interface.

Interfaces are types.

Hence, we can argue that for example a value of type boolean can be used in a context where we expect a value of type Show.

This is referred to as structural subtyping.

Consider the following generic showTwice1 function.

func showTwice1(x Show, y Show) {
    fmt.Printf("\n %s", x.show()+y.show())
}

func testShow() {
    n := number{1}
    b := boolean{true}
    // We write number <= Show to denote that number is a structural subtype of Show.
    // Similarly, we write boolean <= Show.

    showTwice1(n, b)
    showTwice1(n, n)
    showTwice1(b, b)

}

Function showTwice1 is generic because we can apply this function on numbers and booleans.

Bounded type parameters (non-trivial bound)

We take a look at the combination of interfaces and type parameters.

Consider the following generic showTwice2 function.

func showTwice2[T Show](x T, y T) {
    fmt.Printf("\n %s", x.show()+y.show())
}

We find type parameter T where any type instance must satisfy the Show interface.

Consider

func testShow() {
    n := number{1}
    b := boolean{true}

    showTwice2(n, n)
    showTwice2[boolean](b, b)

}

We know that number and boolean both satisfy Show.

Hence, we can call showTwice2 on numbers and booleans.

Go supports simple forms of type inference that extends to type instances.

For example, in the call showTwice2(n, n). Type instance [int] is automatically inferred.

The call showTwice2(n,b) is not accepted. Why?

Type parameter T must be either instantiated to number or boolean. If we pick number, the second argument b leads to a type error. If we pick boolean, the first argument n leads to a type error.

Type sets

Consider

type intOrfloat interface {
    int | float32
}

The above describes the union of types int and float32. Hence, we call this a type set.

Type sets can be used in type bounds.

func myAdd[T intOrfloat](x T, y T) T {
    return x + y
}

However, there’s no value of type intOrfloat and therefore the following variant is rejected

func myAdd[T intOrfloat](x T, y T) intOrfloat {
    return x + y
}

Points to note:

We can use user-defined types such as structs in type sets.

type intOrfloat2 interface {
    int | float32 | number
}

We cannot use interface types in type sets. The following is rejected

type intOrfloat3 interface {
    int | float32 | Show
}

Complete source code

package main

import (
    "fmt"
    "strconv"
)

// Generic swap function.
// Points to note.
//
// 1. T is a type parameter.
// 2. Type parameter come with a bound (aka constraint).
// 3. Bounds are types.
// 4. "any" is a short-hand for "interface{}".
// 5. Any type T satisfies the empty interface.
// 6. Hence, we can swap values of any type.

func swap[T any](x *T, y *T) {
    tmp := *x
    *x = *y
    *y = tmp
}

func testSwap() {
    x := 1
    y := 3

    fmt.Printf("\n x = %d, y = %d", x, y)

    swap[int](&x, &y)

    fmt.Printf("\n x = %d, y = %d", x, y)

}

// Showing values by turning them into strings.
type Show interface {
    show() string
}

type boolean struct {
    val bool
}

func (this boolean) show() string {
    if this.val {
        return "true"
    } else {
        return "false"
    }
}

type number struct {
    val int
}

func (this number) show() string {
    return strconv.Itoa(this.val)
}

// Interfaces are types.
// Valid arguments are values of some type that implement the Show interface.
func showTwice1(x Show, y Show) {
    fmt.Printf("\n %s", x.show()+y.show())
}

// Type parameter T is constrained by Show.
func showTwice2[T Show](x T, y T) {
    fmt.Printf("\n %s", x.show()+y.show())
}

func testShow() {
    n := number{1}
    b := boolean{true}

    showTwice1(n, b)
    showTwice1(n, n)
    showTwice1(b, b)

    // Not accepted, can you guess why?
    // showTwice2(n,b)
    showTwice2(n, n)
    showTwice2[boolean](b, b)

}

// Type sets.

type intOrfloat interface {
    int | float32
}

func myAdd[T intOrfloat](x T, y T) T {
    return x + y
}

/*
// There's no value of type intOrfloat.

func myAdd2[T intOrfloat](x T, y T) intOrfloat {
    return x + y
}
*/

func testAdd() {
    fmt.Printf("\n %d", myAdd[int](1, 2))
    fmt.Printf("\n %f", myAdd[float32](1, 2.0))

    /*
       // x is of type int, there's no automatic conversion to float32 in Go.
        x := 1
        fmt.Printf("\n %f", myAdd[float32](x,2.0))
    */

}

func main() {
    testSwap()
    testShow()
    testAdd()

}

Summary

Go is different