Quick Go Tour

24 March 2015

Marwan Burelle

Overview

Introduction to the go programming language:

Sample code and build system
Nice features
Data structures
go-routine and channels

What's Google Go

Static and typed imperative language
Main idea: simple and evolved language
Userland system and network programming
Integrated build system
GC, dynamic interface, goroutines, channels …

OK …

package main

import "fmt"

func main() {
    fmt.Println("Hello World !")
}

Some details

Almost C syntax
- rational variables declarations

Few extra keywords

No semi-colon (;)
- opening braces at end of line are mandatory

No headers
- exported symbols start with capital letter
- packages can be split in multiple files

Build and Run

go command provides most build operations
it also provides install and remote source fetch
it can run your code
no configuration file needed …

Source Organization

You need to organize your dirs
Setup GOPATH env variable
Source organized by packages

godirs/
  bin/
  pkg/
  src/
    git.example.com/
      extra_path/
        project/
          sub_package1/
            file1.go file2.go
          sub_package2/
            sub_sub_package/
              file1.go file2.go
          entry_point/
            file1.go

Package and Import

package myPackage

import (
    // System wide package
    "fmt"
    // project specific package
    "git.example.com/extra_path/project/sub_package1"
)

Exported names must start with an upper case letter !

Build commands

build: build a file or the current package
run: build and run a file
clean: remove compilation product

shell> cd helloworld
shell> ls
hello.go
shell> go build
shell> ls
hello.go  helloworld
shell> ./helloworld
Hello World !
shell> go build hello.go
shell> ls
hello  hello.go  helloworld
shell> ./hello
Hello World !
shell> go clean
shell> ls
hello.go
shell> go run hello.go
Hello World !

Let's go …

We use a simple case study: quick sort

Some syntax details
Start thinking go style
Introduction to slices

Quick Sort

Package, imports and entry point

package main

import (
    "fmt"
    "math/rand"
)

func main() {
    tab := make([]int, 10)
    for i := 0; i < 10; i++ {
        tab[i] = rand.Intn(100)
    }
    fmt.Println(tab)
    qsort(tab)
    fmt.Println(tab)
}

Quick Sort

Quick Sort main function

func qsort(tab []int) {
    if len(tab) > 1 {
        pivot := partition(tab)
        qsort(tab[0:pivot])
        qsort(tab[pivot:])
    }
}

Quick Sort

Quick Sort partition function

// Simple Quick Sort

package main

import (
	"fmt"
	"math/rand"
)

func main() {
	tab := make([]int, 10)
	for i := 0; i < 10; i++ {
		tab[i] = rand.Intn(100)
	}
	fmt.Println(tab)
	qsort(tab)
	fmt.Println(tab)
}

func partition(tab []int) (pivot int) {
    pivot = len(tab) / 2
    pval := tab[pivot]
    tab[pivot], tab[len(tab)-1] = tab[len(tab)-1], tab[pivot]
    pivot = 0
    for i := 0; i < len(tab)-1; i++ {
        if tab[i] <= pval {
            tab[i], tab[pivot] = tab[pivot], tab[i]
            pivot++
        }
    }
    tab[pivot], tab[len(tab)-1] = tab[len(tab)-1], tab[pivot]
    return
}


func qsort(tab []int) {
	if len(tab) > 1 {
		pivot := partition(tab)
		qsort(tab[0:pivot])
		qsort(tab[pivot:])
	}
}

Returning more than one value

You can return a tuple:

func anon_tuple_return(a, b int) (int, int) {
    return a / b, a % b
}

You can name your returned values:

func named_return(a, b int) (q, r int) {
    q = a / b
    r = a % b
    return
}

Getting the result

func get_tuple(a, b int) {
    q, r := named_return(a, b)
}

Error management

No exceptions but an error type

func Euclid(a, b int) (q, r int, err error) {
    if b == 0 {
        err = fmt.Errorf("Attempt to divide by 0 !")
        return
    }
    q = a / b
    r = a % b
    return
}

Error management

Nice syntactic sugar

package main

import (
	"fmt"
	"io"
	"os"
)

func Euclid(a, b int) (q, r int, err error) {
	if b == 0 {
		err = fmt.Errorf("Attempt to divide by 0 !")
		return
	}
	q = a / b
	r = a % b
	return
}

func FileCopy(in_name, out_name string) (err error) {
	var in_file, out_file *os.File
	if in_file, err = os.Open(in_name); err != nil {
		return
	}
	defer in_file.Close() // HL
	if out_file, err = os.Create(out_name); err != nil {
		return
	}
	defer out_file.Close() // HL
	buf := make([]byte, 1024)
	for err == nil {
		n, rerr := in_file.Read(buf)
		if rerr != nil {
			if rerr == io.EOF {
				break
			}
			return rerr
		}
		_, err = out_file.Write(buf[0:n])
	}
	return
}

func main() {
    a, b := 5, 0
    if _, _, err := Euclid(a, b); err != nil {
        fmt.Println(err)
    } else {
        fmt.Println("We should not be there !")
    }
    a, b = 2501, 7
    if q, r, err := Euclid(a, b); err != nil {
        fmt.Println(err)
    } else {
        fmt.Printf("%d = %d * %d + %d\n", a, b, q, r)
    }
}

Deferring Execution

func FileCopy(in_name, out_name string) (err error) {
    var in_file, out_file *os.File
    if in_file, err = os.Open(in_name); err != nil {
        return
    }
    defer in_file.Close()
    if out_file, err = os.Create(out_name); err != nil {
        return
    }
    defer out_file.Close()
    buf := make([]byte, 1024)
    for err == nil {
        n, rerr := in_file.Read(buf)
        if rerr != nil {
            if rerr == io.EOF {
                break
            }
            return rerr
        }
        _, err = out_file.Write(buf[0:n])
    }
    return
}

Types, Receiver and Methods

OO in go is pretty light: no class, no inheritance, no bullshit
You can name a type
Named types can have attached methods

package main

import "fmt"

type Counter int
func (c Counter) get() int {
    return int(c)
}
func (c *Counter) increment() {
    *c += 1
}
func (c *Counter) decrement() {
    *c -= 1
}
func demo() {
    var c Counter = 0
    c.increment()
    fmt.Println(c.get())
    c.increment()
    fmt.Println(c.get())
}


func main() {
	demo()
}

Interfaces

Interfaces provides a simple form of polymorphism

type Counter interface {
    Increment()
    Set(c int)
    Get() int
}

func example(count Counter) {
    count.Set(0)
    for i := 0; i < 8; i++ {
        count.Increment()
    }
    fmt.Println(count.Get())
}

Interfaces

Structural subtyping: a value implements an interface as long as it has the expected methods

package main

import "fmt"

// START 1 OMIT
type Counter interface {
	Increment()
	Set(c int)
	Get() int
}

func example(count Counter) {
	count.Set(0)
	for i := 0; i < 8; i++ {
		count.Increment()
	}
	fmt.Println(count.Get())
}

// END 1 OMIT

type IntCounter int

func (c *IntCounter) Increment() { *c += 1 }
func (c *IntCounter) Set(x int)  { *c = IntCounter(x) }
func (c IntCounter) Get() int    { return int(c) }

func demo() {
    c := new(IntCounter)
    example(c)
}


func main() {
	demo()
}

Pointers or not ?

When receiver of a method is a pointer, you need a pointer
When receiver of a method is value, you can use both
When receiver is a left-value (addressable) the compiler take the address for you

So why new(IntCounter) ?
- Methods Set and Increment only accept *IntCounter
- Thus, the type that matches the interface Counter is *IntCounter, not IntCounter

Interfaces and Standard Function

io.Writer interface describes target of output function
Any object with the expected function (Write) can be a writer

// file: inverted_writer.go
package inverted_writer

type InvertedBuf []byte

func (b *InvertedBuf) Write(data []byte) (int, error) {
    l := len(data)
    slice := make([]byte, l)
    copy(slice, data)
    for i := 0; i < l/2; i++ {
        slice[i], slice[l-i-1] = slice[l-i-1], slice[i]
    }
    *b = append(slice, *b...)
    return l, nil
}

Testing with go-test

// file: inverted_writer_test.go
// Test file to be used with 'go test'
package inverted_writer

import (
    "fmt"
    "testing"
)

func TestWrite(t *testing.T) {
    b := InvertedBuf(make([]byte, 0))
    fmt.Fprintf(&b, "%d :tnetnoc emos htiw ,txet emoS", 24)
    fmt.Println(string(b))
}

shell> go test
Some text, with some content: 42
PASS
ok      _/home/feanor/project/prez/lectures/inverted_writer    0.006s

Switch

switch can work as in C
switch can be used with conditions

package main

import (
	"fmt"
	"math/rand"
	"time"
)

func is_digit(c byte) bool {
	switch c {
	case '0', '1', '2', '3', '4', '5', '6', '7', '8', '9': // HL
		return true
	}
	return false
}

func grade_message(x float32) {
    fmt.Printf("Grade %g: ", x)
    switch {
    case x < 0 || x > 20:
        fmt.Println("Out of bound grade.")
    case x < 8:
        fmt.Println("Failure")
    case x < 10:
        fmt.Println("Take another chance ...")
    default:
        fmt.Println("Success")
    }
}

func main() {
    rand.Seed(time.Now().Unix())
    for i := 0; i < 10; i++ {
        grade_message(float32(rand.Intn(250)-50) / 10)
    }
}

Multiple Values

Multiple values can be grouped on a single case

func is_digit(c byte) bool {
    switch c {
    case '0', '1', '2', '3', '4', '5', '6', '7', '8', '9':
        return true
    }
    return false
}

Arrays and Slices

Arrays:
- similar to C arrays
- passed by value (copy)

Slices:
- Wrapper around an array
- Automagic dynamic resizing
- Offer array slicing

Slices in action

package main

import "fmt"

func demo() {
    var tab [8]int
    for i := 0; i < len(tab); i++ {
        tab[i] = i
    }
    fmt.Printf("tab : %+v\n", tab)
    fst_half := tab[:4]
    snd_half := tab[4:]
    fmt.Printf("fst_half: %+v\n", fst_half)
    fmt.Printf("snd_half: %+v\n", snd_half)
    for i := 0; i < len (snd_half); i++ {
        snd_half[i] = i
    }
    fmt.Printf("snd_half: %+v\n", snd_half)
    fmt.Printf("tab : %+v\n", tab)
}


func demo2() []int {
	// START OMIT
	// Create a slice of size 4 and capacity 8
	s := make([]int, 4, 8) // HL
	// END OMIT
	return s
}

func main() {
	demo()
}

Using Slices as Stack

package main

import "fmt"

type Stack []int

func (s *Stack) Push(x int) {
    *s = append(*s, x)
}

func (s *Stack) Pop() (x int, err error) {
    if len(*s) == 0 {
        err = fmt.Errorf("Empty stack")
    }
    x = (*s)[len(*s)-1]
    *s = (*s)[:len(*s)-1]
    return
}

func demo() {
    var s Stack
    for i := 0; i < 8; i++ {
        s.Push(i)
    }
    for len(s) > 0 {
        x, _ := s.Pop()
        fmt.Println(x)
    }
}


func main() {
	demo()
}

Using Slices as Queue

package main

import "fmt"

type Queue []int
func (q *Queue) Enqueue(x int) {
    *q = append(*q, x)
}
func (q *Queue) Dequeue() (x int, err error) {
    if len(*q) == 0 {
        err = fmt.Errorf("Empty queue")
        return
    }
    x = (*q)[0]
    *q = (*q)[1:]
    return
}
func demo() {
    var q Queue
    for i := 0; i < 4; i++ {
        q.Enqueue(i)
    }
    for len(q) > 0 {
        x, _ := q.Dequeue()
        fmt.Println(x)
    }
}


func main() {
	demo()
}

Building Slice with make

new only allocates memory with 0 initialization
Creating a slice needs allocations and specific initialization
make do the job

    // Create a slice of size 4 and capacity 8
    s := make([]int, 4, 8)

The size of the slice is the size of view
The capacity is the size of array storage behind
append realloc as needed our slice
append is able to realloc a nil slice

For-each

package main

import "fmt"

func demo() {
    s := make([]int, 4)
    for i := 0; i < len(s); i++ {
        s[i] = i
    }
    for index, val := range s {
        fmt.Printf("s[%d] = %d\n", index, val)
        val += 1
    }
    fmt.Println(s)
}


func main() {
	demo()
}

for index, val := range slice

iterate on all cell of slice
index ranges over positions
val is the value of slice[index]

Homework

Goal:
- training to replace practical sessions
- build a go program
- manipulate slices
- use http://golang.org docs

Assignements:
- write a heap-sort using slices and package container/heap
- your heap-sort should be provided as a package
- your heap-sort should sort slices of int
- you should use go test (read the doc) in order to test your code

Homework are not mandatory but highly advised

Associative mapping

map are classical generic hash-tables
Key can be any value with defined equality operator

package main

import "fmt"

func demo() {
    dict := map[string]string{
        "hello":   "bonjour",
        "goodbye": "au revoir",
        "cat":     "chat",
    }
    fmt.Println("cat:", dict["cat"])
    fmt.Println("cta:", dict["cta"])
    for key, val := range dict {
        fmt.Println(key, ":", val)
    }
}


func main() {
	demo()
}

More on maps

Map initialization with make

package main

import "fmt"

func demo() {
    dict := make(map[string]int)
    for i := 0; i < 8; i++ {
        dict[fmt.Sprint(i)] = i
    }
    fmt.Printf("%+v\n", dict)
}


func main() {
	demo()
}

Not present key cases

package main

import "fmt"

func demo() {
    dict := map[string]string{"cat": "chat"}
    if val, ok := dict["cta"]; ok {
        fmt.Println("cta:", val)
    } else {
        fmt.Println("cta not there")
    }
}


func main() {
	demo()
}

Set implementation with map

type Set map[int]bool

func (s Set) member(x int) bool {
    return s[x]
}
func (s Set) add(x int) {
    s[x] = true
}
func (s Set) remove(x int) {
    if _, present := s[x]; present {
        s[x] = false
    }
}
func (s Set) intersection(s2 Set) (r Set) {
    r = make(map[int]bool)
    for k, v := range s {
        if v && s2[k] {
            r[k] = true
        }
    }
    return
}

Set implementation with map

package main

import "fmt"

// START 1 OMIT
type Set map[int]bool

func (s Set) member(x int) bool {
	return s[x]
}
func (s Set) add(x int) {
	s[x] = true
}
func (s Set) remove(x int) {
	if _, present := s[x]; present {
		s[x] = false
	}
}
func (s Set) intersection(s2 Set) (r Set) {
	r = make(map[int]bool)
	for k, v := range s {
		if v && s2[k] {
			r[k] = true
		}
	}
	return
}

// END 1 OMIT

func (s Set) print(name string) {
    fmt.Printf("%s = [ ", name)
    for k, v := range s {
        if v {
            fmt.Printf("%d ", k)
        }
    }
    fmt.Printf("]\n")
}

func demo() {
    var s2, s3 Set = make(map[int]bool), make(map[int]bool)
    for i := 0; i < 10; i++ {
        s2.add(2 * i)
        s3.add(3 * i)
    }
    s2.print("s2")
    s3.print("s3")
    s2.intersection(s3).print("s2 /\\ s3")
}


func main() {
	demo()
}

Structures

package main

import "fmt"

func (l *Cell) length() (r int) {
	r = 0
	for ; l.Next != nil; l = l.Next {
		r += 1
	}
	return
}

type Cell struct {
    Val  int
    Next *Cell
}

func NewList() *Cell             { return &Cell{0, nil} }
func (l *Cell) push_front(x int) { l.Next = &Cell{x, l.Next} }

func (l *Cell) print() {
    for l = l.Next; l.Next != nil; l = l.Next {
        fmt.Printf("%d -> ", l.Val)
    }
    fmt.Printf("%d\n", l.Val)
}

func demo() {
    l := NewList()
    for i := 0; i < 4; i++ {
        l.push_front(i)
    }
    l.print()
}


func main() {
	demo()
}

Embedded Structures

type Time struct {
    Hours, Min, Sec int
}

type Date struct {
    Month     string
    Year, Day int
}

type FullDate struct {
    Time
    Date
}

func NewTime(h, m, s int) Time        { return Time{h, m, s} }
func NewDate(m string, y, d int) Date { return Date{m, y, d} }
func NewFullDate(h, min, s int, m string, y, d int) FullDate {
    return FullDate{Time{h, min, s}, Date{m, y, d}}
}

Embedded Structures

package main

import "fmt"

// START OMIT
type Time struct {
	Hours, Min, Sec int
}

type Date struct {
	Month     string
	Year, Day int
}

type FullDate struct {
	Time
	Date
}

func NewTime(h, m, s int) Time        { return Time{h, m, s} }
func NewDate(m string, y, d int) Date { return Date{m, y, d} }
func NewFullDate(h, min, s int, m string, y, d int) FullDate {
	return FullDate{Time{h, min, s}, Date{m, y, d}}
}

func (t Time) Seconds() int {
    return t.Sec + 60*(t.Min+60*t.Hours)
}

func (d Date) USDate() string {
    return fmt.Sprintf("%s %d, %d", d.Month, d.Day, d.Year)
}

func main() {
    fd := NewFullDate(13, 37, 0, "April", 2015, 27)
    fmt.Println(fd)
    fmt.Println(fd.Seconds())
    fmt.Println(fd.USDate())
}

Closures

A closure can be assigned to a variable and run later

func Example() {
    f := func(x int) int {
        fmt.Printf("> %d <\n", x)
        return x + 1
    }
    for i := 0; i < 10; {
        i = f(i)
    }
}

Closures have access to their embedding scope

package main

import "fmt"

func Scope() {
    a, b := 0, 0
    f := func(x int) int {
        a += x
        b += a
        return a * b
    }
    fmt.Println(f(2), a, b)
    fmt.Println(f(2), a, b)
}


func Example() {
	f := func(x int) int {
		fmt.Printf("> %d <\n", x)
		return x + 1
	}
	for i := 0; i < 10; {
		i = f(i)
	}
}

func main() {
	Example()
	Scope()
}

Function as value

We can pass functions to functions

package main

import (
	"fmt"
	"math/rand"
	"time"
)

func Build() func(c byte) byte {
	rand.Seed(time.Now().Unix())
	perm := rand.Perm(256)
	f := func(c byte) byte {
		return byte(perm[int(c)])
	}
	return f
}

func Iter(data []int, f func(x int)) {
    for _, v := range data {
        f(v)
    }
}

func main() {
    data := make([]int, 8)
    for i, _ := range data {
        data[i] = i
    }
    fmt.Println(data)
    Iter(data, func(x int) { fmt.Println(x) })
}

Function as value

We can return functions

func Build() func(c byte) byte {
    rand.Seed(time.Now().Unix())
    perm := rand.Perm(256)
    f := func(c byte) byte {
        return byte(perm[int(c)])
    }
    return f
}

go-routine concept

Go parallel model follows CSP model
Main idea: communicate rather than sharing
go-routine: run an independant sub-process (light thread)
channels: a kind or typed pipe

Simple Example

package main

import (
	"fmt"
	"time"
)

func main() {
    c1, c2 := make(chan int), make(chan int)
    go func() {
        for i := 0; i < 5; i++ {
            fmt.Println("Go 1: Hello", i)
            time.Sleep(10)
        }
        c1 <- 1
    }()

    go func() {
        for i := 0; i < 5; i++ {
            fmt.Println("Go 2: Hello", i)
            time.Sleep(10)
        }
        c2 <- 1
    }()
    <-c1
    <-c2
    fmt.Println("Done")
}

Parallel Divide and Conquer

package main

import (
	"fmt"
)

func seq_fibo(n int) int {
    if n < 2 {
        return n
    }
    return seq_fibo(n-1) + seq_fibo(n-2)
}

func Fibo(n int) (r int, err error) {
    if n < 0 {
        err = fmt.Errorf("Rank %d is negative", n)
        return
    }
    if n < 5 {
        r = seq_fibo(n)
        return
    }
    f1, f2 := make(chan int), make(chan int)
    sub := func (n int, c chan int) {
        f, _ := Fibo(n)
        c <- f
    }
    go sub(n - 1, f1)
    go sub(n - 2, f2)
    r = <-f1 + <-f2
    return
}


func main() {
	if f, err := Fibo(20); err != nil {
		fmt.Println(err)
	} else {
		fmt.Printf("> %d\n", f)
	}
}

Summing a vector

package main

import (
	"fmt"
	"runtime"
)

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func seq_sum(v []float64) (r float64) {
    for _, i := range v {
        r += i
    }
    return
}

func ParallelSum(v []float64) (res float64) {
    runtime.GOMAXPROCS(runtime.NumCPU())
    nbroutine := runtime.NumCPU() * 4
    fmt.Println("Using", nbroutine, "go routine on", nbroutine/4, "cores")
    c := make(chan float64, nbroutine)
    step := len(v) / nbroutine
    for i := 0; i < nbroutine; i++ {
        go func(i int) {
            end := min((i+1)*step, len(v))
            c <- seq_sum(v[i*step : end])
        }(i)
    }
    for i := 0; i < nbroutine; i++ {
        res += <-c
    }
    return res
}


const (
	DATA_SIZE = 1e8
)

func main() {
	v := make([]float64, DATA_SIZE)
	for i := 0; i < DATA_SIZE; i++ {
		v[i] = 1.0
	}
	fmt.Println(ParallelSum(v))
}

Quick Go Tour

24 March 2015

Overview

Modern System Programming

What's Google Go

OK …

Some details

Build and Run

Source Organization

Package and Import

Build commands

Let's go !

Let's go …

Quick Sort

Quick Sort

Quick Sort

Go return style

Returning more than one value

Error management

Error management

Deferring Execution

Light Objects

Types, Receiver and Methods

Interfaces

Interfaces

Pointers or not ?

Interfaces and Standard Function

Testing with go-test

Switch

Multiple Values

Slices

Arrays and Slices

Slices in action

Using Slices as Stack

Using Slices as Queue

Building Slice with make

For-each

Homework

Maps

Associative mapping

More on maps

Set implementation with map

Set implementation with map

Structures

Structures

Embedded Structures

Embedded Structures

Higher Order

Closures

Function as value

Function as value

Going Concurrent

go-routine concept

Simple Example

Parallel Divide and Conquer

Summing a vector

Thank you