Method overloading, interfaces and structural subtyping

Go does not support classes. Instead, Go supports:

Method overloading based on the receiver type
Interfaces to declare a set of methods that share the same receiver.
Structural subtyping
- A receiver type is a (structural) subtype of an interface type if the receiver implements all methods as declared by the interface.
- Two interface types are in a structural subtype relation if the set of methods declared by the first interface is a superset of the methods declared by the second interface.

type Show interface {
    show() string
}

type Bool bool

func (this Bool) show() string {
    if this {
        return "true"
    } else {
        return "false"
    }
}

Bool is isomorphic to the primitive type bool
Methods can only be overloaded on “named” types

Further cases.

type Pair struct {
    left  interface{}
    right interface{}
}

func (this Pair) show() string {
    return "(" + this.left.(Bool).show() + ", " + this.right.(Bool).show() + ")"
}

func showTwice(x Show, y Show) string {
    return x.show() + y.show()
}

func testShow() {
    fmt.Printf("%s", showTwice(Bool(true), Pair{Bool(true), Bool(false)}))

}

Bool and Pair are structural subtypes of Show. Both implement the show method.
Any type is a structural subtype of interface{}
.(Bool) is a type assertion (type cast)
By using generics (as we see later) we can avoid the use of interface{} (and type assertions)

Lambdas and local type inference

“Add”

func myAdd(x int, y int) int {
    return x+y
}


func testAdd() {
    fmt.Printf("\n %d", myAdd(1,3))

    myAdd2 := func(x int, y int) int { return x+y }

    fmt.Printf("\n %d", myAdd2(1,3))
}

Go lambda notation:

func(parameters) return_type { function_body }

Capture list specifies non-local variables used in function body (more on this below)
List of parameters, first comes the name then the type
Return type comes after parameters
Function type

x := 1

Infer type of local variable x
No semicolon (“;”) necessary assuming we have one statement per line

“Plus”

func myPlus(x int) func(int) int {
    return func(y int) int { return x+y }
}

func testPlus() {
    fmt.Printf("\n %d", myPlus(1)(3))

    inc := myPlus(1)

    fmt.Printf("\n %d", inc(3))

    myPlus2 := func(x int) func(int) int { return func(y int) int { return x+y }}

    fmt.Printf("\n %d", myPlus2(1)(3))
}

Partial function application, see inc(3).

Capture by reference

func testLambdaCapture() {
  x := 1

  f := func(y int) int { return x+y }

  fmt.Printf("\n %d", f(3))
  x = 2
  fmt.Printf("\n %d", f(3))
}

Variable x is used in the lambda function f.

Go always assumes capture by reference. That is, each access to x will retrieve its current value.

Generics

Simple example

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

func testSwap() {
    var x int
    var y int
    x = 1; y = 3

    mySwap[int](&x,&y)
    fmt.Printf("\n %d %d",x,y)
}

T is a type parameter

Type parameters always come with a bound.

any is satisfied by all types.

Monomorphisation

Go type checks the “generic” program code and then creates a copy of the code for each specific instance. This process is called monomorphisation.

That is, translates roughly to the following code.

func mySwap_int(x *int, y *int) {
    tmp:= *x
    *x = *y
    *y = tmp
}

func testSwap_int() {
    var x int
    var y int
    x = 1; y = 3

    mySwap_int(&x,&y)
    fmt.Printf("\n %d %d",x,y)
}

“Show” with overloaded methods and interfaces

type Show interface {
    show() string
}

type Bool bool
func (x Bool) show() string {
    if x {
        return "true"
    } else {
        return "false"
    }
}

type Slice[T Show] []T
func (xs Slice[T]) show() string {
    s := "["
    for index, elem := range xs {
        s = s + elem.show()
        if index < len(xs) - 1 {
        s = s + ","
        }
        }
    s = s + "]"

    return s
}

func testShow() {
    var xs Slice[Bool]
    xs = make([]Bool,2)
    xs[0] = true
    xs[1] = false
    fmt.Printf("\n %s",xs.show())
}

Method overloading in Go is restricted to the receiver (object on which the method operates)
An interface describes a collection of methods (for the same receiver)
Type Bool implements Show
Above roughly corresponds to the “Show” instances we have seen in Haskell.

It would be nicer to be able to write

type Slice[T any] []T
func (xs Slice[T Show]) show() string { ... }

The current Go Generics design forbids the above

QuickCheck again

We only consider type-specific test data generation.

We make use of lambdas to emulate lazy evaluation of generators.
We make use of overloading to implement “arbitrary”.

Overloading in Go is restricted to the receiver. Hence, we cannot directly represent “arbitrary”. We introduce an interface with an “arbitrary” method where we assume that “arbitrary” operates on proxy values.

type Gen[T any] struct {
    gen func() T
}

func (g Gen[T]) generate() T {
    return g.gen()
}

func mkGen[T any](g func() T) Gen[T] {
    return Gen[T]{g}
}

type Arbitrary[T any] interface {
    arbitrary() Gen[T]
}

// Generators.

func elements[T any](xs []T) Gen[T] {
    return mkGen[T](func() T {
            i := rand.Intn(len(xs))
                return xs[i] })
}

func vector[T any](g Arbitrary[T], n int) Gen[[]T] {
    return mkGen[[]T](func() []T {
           xs := make([]T, n)

        for i := 0; i < n; i++ {
            xs[i] = g.arbitrary().generate()
            }

            return xs})
}


// Instances

// Characters.
// charArb serves as a proxy to generate some character.
type charArb struct{}

func (_ charArb) arbitrary() Gen[byte] {
    return mkGen[byte](func() byte { return (byte)(65 + rand.Intn(25)) })
}

type numArb struct{}

func (_ numArb) arbitrary() Gen[int] {
     return mkGen[int](func() int { return rand.Intn(1001) })
}

// Pairs.
// Pair proxy comes with sub proxies to generate left and right values.
type pairArb[T,S any] struct {
    left  Arbitrary[T]
    right Arbitrary[S]
}

type pair[T, S any] struct {
    left  T
    right S
}

func (q pairArb[T,S]) arbitrary() Gen[pair[T,S]] {
    return mkGen[pair[T,S]](func() pair[T,S] {
        return pair[T,S]{left: q.left.arbitrary().generate(), right: q.right.arbitrary().generate()}
    })
}


// Slice.
type sliceArb[T any] struct {
    s Arbitrary[T]
}

func (sl sliceArb[T]) arbitrary() Gen[[]T] {
    return vector[T](sl.s,5)
}


// Derived generators.
// For strings and pairs of numbers.
func genStrings() string {
    var charProxy charArb
    strProxy := sliceArb[byte]{charProxy}

        xs := strProxy.arbitrary().generate()
        str := ""
        for i:=0; i<len(xs); i++ {
        str += string(xs[i])
}
  return str
}

func genAndPrintPairsOfNumbers() {
    var numProxy numArb
    pairProxy := pairArb[int,int]{numProxy, numProxy}

    p := pairProxy.arbitrary().generate()

    fmt.Printf("\n (%d,%d)", p.left, p.right)
}


func testGen() {
    fmt.Printf("\n%s", genStrings())
        genAndPrintPairsOfNumbers()
}

Complete source code

Requires Go with Generics.

package main

import "fmt"
import "math/rand"

// Show, overloaded methods, interfaces, structural subtyping

type Show interface {
    show() string
}

type Bool bool

func (this Bool) show() string {
    if this {
        return "true"
    } else {
        return "false"
    }
}

type Pair struct {
    left  interface{}
    right interface{}
}

func (this Pair) show() string {
    return "(" + this.left.(Bool).show() + ", " + this.right.(Bool).show() + ")"
}

func showTwice(x Show, y Show) string {
    return x.show() + y.show()
}

func testShow() {
    fmt.Printf("%s", showTwice(Bool(true), Pair{Bool(true), Bool(false)}))

}

//////////////////////////////////////////////////
// Lambdas and local type inference (:=)

func myAdd(x int, y int) int {
    return x + y
}

func testAdd() {
    fmt.Printf("\n %d", myAdd(1, 3))

    myAdd2 := func(x int, y int) int { return x + y }

    fmt.Printf("\n %d", myAdd2(1, 3))
}

// More lambdas.
func myPlus(x int) func(int) int {
    return func(y int) int { return x + y }
}

func testPlus() {
    fmt.Printf("\n %d", myPlus(1)(3))

    inc := myPlus(1)

    fmt.Printf("\n %d", inc(3))

    myPlus2 := func(x int) func(int) int { return func(y int) int { return x + y } }

    fmt.Printf("\n %d", myPlus2(1)(3))
}

// Capture by reference
func testLambdaCapture() {
    x := 1

    f := func(y int) int { return x + y }

    fmt.Printf("\n %d", f(3))
    x = 2
    fmt.Printf("\n %d", f(3))
}

///////////////////////////////
// Generics

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

func testSwap() {
    var x int
    var y int
    x = 1
    y = 3

    mySwap[int](&x, &y)
    fmt.Printf("\n %d %d", x, y)
}

func mySwap_int(x *int, y *int) {
    tmp := *x
    *x = *y
    *y = tmp
}

func testSwap_int() {
    var x int
    var y int
    x = 1
    y = 3

    mySwap_int(&x, &y)
    fmt.Printf("\n %d %d", x, y)
}

// Show with generics

type Slice[T Show] []T

func (xs Slice[T]) show() string {
    s := "["
    for index, elem := range xs {
        s = s + elem.show()
        if index < len(xs)-1 {
            s = s + ","
        }
    }
    s = s + "]"

    return s
}

func testShowGeneric() {
    var xs Slice[Bool]
    xs = make([]Bool, 2)
    xs[0] = true
    xs[1] = false
    fmt.Printf("\n %s", xs.show())
}

// QuickCheck in Go

// We wish to generate an arbitrary value only when need.
// For this purpose, we make use of lambdas to represent "by need/lazy" evaluation of generators.

type Gen[T any] struct {
    gen func() T
}

func (g Gen[T]) generate() T {
    return g.gen()
}

func mkGen[T any](g func() T) Gen[T] {
    return Gen[T]{g}
}

// Overloading in Go is restricted to the receiver.
// Hence, we cannot directly represent "arbitrary".

// We introduce an interface with an "arbitrary" method where
// we assume that "arbitrary" operates on proxy values.

type Arbitrary[T any] interface {
    arbitrary() Gen[T]
}

// Generators.

func elements[T any](xs []T) Gen[T] {
    return mkGen[T](func() T {
        i := rand.Intn(len(xs))
        return xs[i]
    })
}

func vector[T any](g Arbitrary[T], n int) Gen[[]T] {
    return mkGen[[]T](func() []T {
        xs := make([]T, n)

        for i := 0; i < n; i++ {
            xs[i] = g.arbitrary().generate()
        }

        return xs
    })
}

// Instances

// Characters.
// charArb serves as a proxy to generate some character.
type charArb struct{}

func (_ charArb) arbitrary() Gen[byte] {
    return mkGen[byte](func() byte { return (byte)(65 + rand.Intn(25)) })
}

type numArb struct{}

func (_ numArb) arbitrary() Gen[int] {
    return mkGen[int](func() int { return rand.Intn(1001) })
}

// Pairs.
// Pair proxy comes with sub proxies to generate left and right values.
type pairArb[T, S any] struct {
    left  Arbitrary[T]
    right Arbitrary[S]
}

type pair[T, S any] struct {
    left  T
    right S
}

func (q pairArb[T, S]) arbitrary() Gen[pair[T, S]] {
    return mkGen[pair[T, S]](func() pair[T, S] {
        return pair[T, S]{left: q.left.arbitrary().generate(), right: q.right.arbitrary().generate()}
    })
}

// Slice.
type sliceArb[T any] struct {
    s Arbitrary[T]
}

func (sl sliceArb[T]) arbitrary() Gen[[]T] {
    return vector[T](sl.s, 5)
}

// Derived generators.
// For strings and pairs of numbers.
func genStrings() string {
    var charProxy charArb
    strProxy := sliceArb[byte]{charProxy}

    xs := strProxy.arbitrary().generate()
    str := ""
    for i := 0; i < len(xs); i++ {
        str += string(xs[i])
    }
    return str
}

func genAndPrintPairsOfNumbers() {
    var numProxy numArb
    pairProxy := pairArb[int, int]{numProxy, numProxy}

    p := pairProxy.arbitrary().generate()

    fmt.Printf("\n (%d,%d)", p.left, p.right)
}

func testGen() {
    fmt.Printf("\n%s", genStrings())
    genAndPrintPairsOfNumbers()
}

func main() {
    testShow()
    testAdd()
    testPlus()
    testLambdaCapture()
    testSwap()
    testShowGeneric()
    testGen()
}

Go : Lambdas, local type inference, overloading, interfaces, generics, …

The Go programming language