Go: Translation scheme

Martin Sulzmann

Overview

Compilation of source language features (methods, interfaces, generics) to a more primitive language.

Translating methods and structural subtyping
Translating Generic Go

Translating methods, interfaces and structural subtyping

Go supports overloaded methods, interfaces and structural subtyping.
We wish to translate Go programs into a more primitive language (= Go without method definitions).

Translating overloaded methods

Each method definition can be uniquely identified via

the method name
the type of the receiver

Translating method definitions is easy. Simply introduce unique function names.

For our running example, we find the following.

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

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

Translating interfaces and structural subtying

How to translate generic functions that make use of interfaces? Recall

func sumArea(x, y shape) int {
    return x.area() + y.area()
}

Run-time method lookup

Values carry type information
Query the type of values to select the appropriate method
Structural subtyping translates to t <= interface{}

Dictionary translation (inspired by Haskell’s type class translation scheme)

Interface values represented as a pair
The actual value plus the dictionary of method definitions
Structural subtyping translates to the construction of interface values

Both translation methods rely on interface{}!

Run-time method lookup (by example)

func area_Lookup(x interface{}) int {
    var y int

    switch v := x.(type) {
    case square:
        y = area_Sq(v)
    case rectangle:
        y = area_Rec(v)
    }
    return y

}

func sumArea_Lookup(x, y interface{}) int {
    return area_Lookup(x) + area_Lookup(y)
}

Dictionary translation (by example)

type shape_Value struct {
    val  interface{}
    area func(interface{}) int
}

func sumArea_Dict(x, y shape_Value) int {
    return x.area(x.val) + y.area(y.val)
}

val is the receiver value
area is the matching method definition (represented as a function where the receiver is the first argument)

Calling sumArea

    area_Rec_Wrapper := func(v interface{}) int {
        return area_Rec(v.(rectangle))

    }

    area_Sq_Wrapper := func(v interface{}) int {
        return area_Sq(v.(square))

    }

    rDictShape := shape_Value{r, area_Rec_Wrapper}

    sDictShape := shape_Value{s, area_Sq_Wrapper}

    sumArea_Dict(rDictShape, sDictShape)

Wrapper functions are needed for the following reason.

area_Rec has type func(rectangle) int
We need to store area_Rec in the “area” dictionary entry which has type func(interface{}) int
We cast area_Rec to the approrpriate type

Complete source

package main

import "fmt"

// Example

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 (r *rectangle) scale(x int) {
    r.length = r.length * x
    r.width = r.width * x
}

func (s *square) scale(x int) {
    s.length = s.length * x
}

type shape interface {
    area() int
}

type shapeExt interface {
    shape
    scale(int)
}

func sumArea(x, y shape) int {
    return x.area() + y.area()
}

func sumAreaScaleBefore(n int, x, y shapeExt) int {
    x.scale(n)
    y.scale(n)
    return x.area() + y.area()
}

func test() {
    var r rectangle = rectangle{1, 2}
    var s square = square{3}

    x1 := r.area() + s.area()

    fmt.Printf("%d \n", x1)

    x2 := sumArea(r, s)

    fmt.Printf("%d \n", x2)

    pt := &r

    x3 := pt.area()
    // Implicit conversion to
    // (*pt).area()
    //
    // Hence, any "value" receiver also implies the corresponding "pointer" receiver.

    fmt.Printf("%d \n", x3)

    //  x3 := sumAreaScaleBefore(3, r, s)
    //
    // "rectangle does not implement shapeExt (scale method has pointer receiver)"
    // same applies to square

    x4 := sumAreaScaleBefore(3, &r, &s)

    fmt.Printf("%d \n", x4)

}

// Introducing unique function names for overloaded methods

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

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

// "value" method implies "pointer" method
func area_RecPtr(r *rectangle) int {
    return area_Rec(*r)
}

func area_SqPtr(s *square) int {
    return area_Sq(*s)
}

func scale_RecPtr(r *rectangle, x int) {
    r.length = r.length * x
    r.width = r.width * x
}

func scale_SqPtr(s *square, x int) {
    s.length = s.length * x
}

// Run-time method lookup

func area_Lookup(x interface{}) int {
    var y int

    switch v := x.(type) {
    case square:
        y = area_Sq(v)
    case rectangle:
        y = area_Rec(v)
    }
    return y

}

func sumArea_Lookup(x, y interface{}) int {
    return area_Lookup(x) + area_Lookup(y)
}

func test_Lookup() {

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

    x1 := area_Rec(r) + area_Sq(s)

    fmt.Printf("%d \n", x1)

    x2 := sumArea_Lookup(r, s)
    // rectangle <= interface{}
    // square <= interface{}

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

// Dictionary translation

type shape_Value struct {
    val  interface{}
    area func(interface{}) int
}

type shapeExt_Value struct {
    val   interface{}
    area  func(interface{}) int
    scale func(interface{}, int)
}

// shapExt <= shape
func fromShapeExtToShape(x shapeExt_Value) shape_Value {
    return shape_Value{x.val, x.area}
}

func sumArea_Dict(x, y shape_Value) int {
    return x.area(x.val) + y.area(y.val)
}

func sumAreaScaleBefore_Dict(n int, x, y shapeExt_Value) int {
    x.scale(x.val, n)
    y.scale(y.val, n)
    return x.area(x.val) + y.area(y.val)
}

func test_Dict() {
    var r rectangle = rectangle{1, 2}
    var s square = square{3}

    // 1. Plain method calls

    x1 := area_Rec(r) + area_Sq(s)

    fmt.Printf("%d \n", x1)

    x2 := sumArea(r, s)

    fmt.Printf("%d \n", x2)

    pt := &r

    x3 := area_Rec(*pt)
    // Implicit conversion from pointer to value

    fmt.Printf("%d \n", x3)

    //  x3 := sumAreaScaleBefore(3, r, s)
    //
    // "rectangle does not implement shapeExt (scale method has pointer receiver)"
    // same applies to square

    // 2. Calling sumArea

    // Wrapper functions are needed for the following reason.
    // (a) area_Rec has type func(rectangle) int
    // (b) We need to store area_Rec in the "area" dictionary entry which has type func(interface{}) int
    // (c) We cast area_Rec to the approrpriate type

    area_Rec_Wrapper := func(v interface{}) int {
        return area_Rec(v.(rectangle))

    }

    area_Sq_Wrapper := func(v interface{}) int {
        return area_Sq(v.(square))

    }

    rDictShape := shape_Value{r, area_Rec_Wrapper}

    sDictShape := shape_Value{s, area_Sq_Wrapper}

    x4 := sumArea_Dict(rDictShape, sDictShape)

    fmt.Printf("%d \n", x4)

    // 3. Calling sumAreaScaleBefore

    area_RecPtr_Wrapper := func(v interface{}) int {
        return area_RecPtr(v.(*rectangle))

    }

    area_SqPtr_Wrapper := func(v interface{}) int {
        return area_SqPtr(v.(*square))

    }

    scale_RecPtr_Wrapper := func(v interface{}, x int) {
        scale_RecPtr(v.(*rectangle), x)

    }

    scale_SqPtr_Wrapper := func(v interface{}, x int) {
        scale_SqPtr(v.(*square), x)

    }

    // Construct the appropriate interface values
    rDictShapeExt := shapeExt_Value{&r, area_RecPtr_Wrapper, scale_RecPtr_Wrapper}

    sDictShapeExt := shapeExt_Value{&s, area_SqPtr_Wrapper, scale_SqPtr_Wrapper}

    x5 := sumAreaScaleBefore_Dict(3, rDictShapeExt, sDictShapeExt)

    fmt.Printf("%d \n", x5)

    // 4. Calling sumArea with a shapeExt value

    x6 := sumArea_Dict(fromShapeExtToShape(rDictShapeExt), fromShapeExtToShape(sDictShapeExt))

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

func main() {

    test()

    test_Lookup()

    test_Dict()

}

Translating type assertions

type square struct {
    length int
}

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

type shape interface {
    area() int
}

func sumAreaVariant(x, y shape) int {
    z := y.(square)
    // Not every shape value can be turned into a square.
    // Above might fail at run-time.
    return x.area() + y.area() + z.length
}

func testSumAreaVariant() {
    fmt.Printf("%d", sumAreaVariant(square{1}, square{2}))
    // Type checks cause  square <= shape
}

Details are here

Translating type bounds

type node[T any] struct {
    val  T
    next *node[T]
}


func showNode[T Show](n *node[T]) string {
    var s string

    for n != nil {
        s = s + n.val.show() + " -> "
        n = n.next

    }

    s = s + " nil"

    return s

}

Details are here

Translating “generics”

We consider the translaton of programs with universal type parameters (aka “generics”). We assume that there are no type bounds and no uses of structural subtyping.

There are two established translation methods where source Go programs with generics are translated to a more simple target language.

Monomorphization where we generate type-specific instances
Generic translation where each type parameter is replaced by ‘interface{}’.

Go uses monomorphization whereas Java uses a generic translation scheme. We explain both methods via an example.

Example linked list

Original source program

type node[T any] struct {
    val  T
    next *node[T]
}

func mkNode[T any](v T) *node[T] {
    return &node[T]{val: v, next: nil}
}

func insert[T any](n *node[T], v T) {
    n.next = mkNode[T](v)
}

// n > 0
func mkList[T any](n int, v T) *node[T] {

    head := mkNode(v)
    current := head

    for i := 0; i < n-1; i++ {
        insert(current, v)
        current = current.next

    }
    return head

}

func len[T any](n *node[T]) int {
    i := 0

    for n != nil {
        i++
        n = n.next

    }

    return i

}

func testNode() {
    n1 := mkList[int](10, 1)
    fmt.Printf("\n%d", len(n1))

    n2 := mkList[bool](10, true)
    fmt.Printf("\n%d", len(n2))

}

Translation

// Generic translation (sketch)

type node_G struct {
    val  interface{}
    next *node_G
}

func mkNode_G(v interface{}) *node_G {
    return &node_G{val: v, next: nil}
}

// Monomorphization (sketch)

type node_int struct {
    val  int
    next *node_int
}

func mkNode_int(v int) *node_int {
    return &node_int{val: v, next: nil}
}

Full details here

Further examples (exercise)

Summing up numeric values

func sum[T int | float32](xs []T) T {
    var x T
    x = 0
    for _, v := range xs {

        x = x + v
    }

    return x

}

Swapping values

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

Summary

Go is different

Dictionary-translation scheme
Monomorphization

Further details on Go.