20160314:TP:Go:Introduction

Introduction

L'objectif de cette séance de TP est de faire vos premiers pas en Go. La séance commencera par un peu de set-up, puis vous réaliserez quelques petits programmes simple.

Mise-en-place

Répertoires

Pour travailler en Go, normalement vous devriez avoir un répertoire dédié qui contiendra votre code source, vos binaires et vos packages compilés. En théorie, les répertoires versionnés peuvent (partiellement) gérés par Go, mais ce n'est pas pratique pour ce que nous voulons faire ici.

La stratégie est la suivante: vous allez mettre votre GOPATH dans votre dépot. Il faudra juste faire attention à ne pas versionner les sous-répertoires bin et pkg.

Pour l'exemple suivant, vous vous placerez dans votre dépot de TP.

On va d'abord créer l'architecture, il vous faut les répertoires suivants:

• gowork/
  • bin/
  • pkg/
  • src/
    • tutorial20160314/

Vous allez ensuite fixer votre variable d'environnement GOPATH avec le chemin complet vers gowork. Pensez à rajouter cette définition dans votre configuration shell.

On va maintenant ajouter un fichier gowork/.gitignore pour éviter d'avoir bin et pkg dans le dépot. Le contenu du fichier doit ressembler à ça:

bin/
pkg/

En Go, lorsque vous créer un package main (un programme quoi) le nom de l'exécutable est déterminé non pas par le nom du fichier mais par le nom du répertoire de travail. Par exemple, si j'ai un fichier ${GOPATH}/src/my_app/foo.go et que je le compile, j'obtiendrai l'exécutable my_app et non pas foo. On notera également que depuis n'importe où (tant que vous pouvez écrire dans le répertoire courant) vous pouvez construire un programme Go se trouvant dans votre GOPATH. Par exemple, si j'ai un programme dans ${GOPATH}/src/my_project_path/my_app/some_source_code.go, je peux le compiler avec go build my_project_path/my_app ce qui produira dans le répertoire courant le binaire my_app.

Pour la suite, chaque exercice sera donc dans son sous-répertoire (indiqué au début de l'exercice.)

Hello World

Pour tester notre set-up, nous allons faire un petit Hello, World!. Go aime bien que tout soit ranger, vous allez donc créer un sous-répertoire hello dans le répertoire tutorial20160314 dans lequel vous pourrez écrire votre fichier hello.go:

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

Placez vous dans le répertoire créer pour tester votre set-up:

# Ces tests devraient marcher même si votre GOPATH n'est pas bon
shell> go run hello.go
Hello, World !
shell> go build hello.go
shell> ./hello
Hello, World !
shell> go clean
# Ces tests nécessitent un GOPATH correct
shell> go build
shell> ./hello
Hello, World !
shell> go clean
shell> go install
shell> ${GOPATH}/bin/hello
Hello, World !
# remove produced AND installed files
shell> go clean -i

Vous pouvez maintenant ajouter votre fichier à votre dépot:

shell> git add hello.go
shell> git commit -m "Adding a first hello world"
...
shell> git push
...

Présentation du code et commentaires de documentation

Go fourni deux outils pratique go fmt et go doc pour formater votre code et récupérer la documentation d'un package.

Prenons l'exemple suivant, on travaillera dans un répertoire my_app peut importe où, c'est un exemple.

/*
  my_app: a simple demo
*/
package main
 
import (
"math/rand"
"fmt"
)
 
// Foo(n): prints n returns it
func Foo(n int) int {
fmt.Println(n)
return n
}
 
func main() {
fmt.Println("Hello, World !")
Foo(42)
fmt.Println(rand.Int())
}

On peut mettre en forme notre code avec go fmt et obtenir:

/*
  my_app: a simple demo
*/
package main
 
import (
	"fmt"
	"math/rand"
)
 
// Foo(n): prints n returns it
func Foo(n int) int {
	fmt.Println(n)
	return n
}
 
func main() {
	fmt.Println("Hello, World !")
	Foo(42)
	fmt.Println(rand.Int())
}

Maintenant testons go doc:

shell> go doc
my_app: a simple demo
shell> go doc Foo
func Foo(n int) int
    Foo(n): prints n returns it
shell> go doc -cmd
package main // import "tutorial01/my_app"

my_app: a simple demo

func Foo(n int) int
shell>

Le principe est simple: les commentaires précédants une définition (sans saut de ligne) sont considérés comme de la doc pour cette définition. Ça marche pour les fonctions comme pour les packages. Dans la suite, les bouts de code fournis sont accompagnés des commentaires de documentation et vous pouvez donc essayer go doc dessus.

Un peu de code

Nous allons implémenter une fonction simple (guess what: factorielle) et nous en profiterons pour accéder aux arguments de votre programme.

Pour cet exercice nous travaillerons dans le répertoire tutorial20160314/fact.

Un petit factorielle pour la route

• Implémenter la fonction suivante:

// Fact(n) computes factorial of n
// n should be a positive integer, if not, behavior is undefined.
func Fact(n int) (r int)

Nous verrons le choix du package

Tester

Pour tester, nous allons construire un package main contenant votre fonction Fact et une fonction main qui va récupérer un entier dans ses arguments et appeler correctement votre fonction.

Un peu de structure pour commencer, voici le squelette du fichier fact.go:

/*
  An simple factorial implementation in Go.
 
  Use os.Args to take input value for the function.
*/
package main
 
// imports
import (
	"fmt"
	"log"
	"os"
	"strconv"
)
 
// Fact(n) computes factorial of n
// n should be a positive integer, if not, behavior is undefined.
func Fact(n int) (r int) {
  // FIX ME
}
 
// main(): read an integer on the input and call Fact with it.
func main() {
  // FIX ME
}

Pour la gestion d'erreur, nous utiliserons la fonction Fatalln(...) du package log [1], cette fonction fonctionne comme fmt.Println(...) sauf qu'elle quite le programme. Voici un petit exemple:

func main() {
	if len(os.Args) < 2 {
		log.Fatalln("missing arguments")
	}
        fmt.Println(os.Args)
}

Pour récupérer les arguments du main, le package os fourni le classique tableau d'arguments: os.Args. On peut récupérer sa longueur via len(os.Args) et comme pour argv en C celui-ci contient le nom du programme suivi des ses arguments.

Comme en C, les arguments sont des chaînes de caractères et il faut donc convertir le premier argument (s'il existe) en entier. Pour ça nous utiliserons strconv.ParseInt(str, base, bit_size) [2]. Cette fonction renvoie une paire formée de l'entier lu et d'une valeur d'erreur. On l'utilise donc comme suit:

        n, err := strconv.ParseInt(os.Args[1], 10, 32)

Si err ne vaut pas nil (l'équivalent de NULL en C) il y a eu un problème.

• Compléter le fichier fact.go

Binary Search

Nous allons maintenant faire un premier exercice avec des slices: Binary Search (dichotomie).

Comme pour factorielle, ce sera l'occasion de découvrir un autre package de Go: flag [3] qui permet de gérer simplement plusieurs paramêtres sur la ligne de commande.

Le bout de code suivant présente un exemple d'utilisation:

// flagex [-flag int] [-help|--help|-h]
//
//   flagex takes a flag (default value 0) and displays it.
package main
 
import (
	"flag"
	"fmt"
)
 
func main() {
	var f int
	flag.IntVar(&f, "flag", 0, "a simple integer flag")
	flag.Parse()
	fmt.Println("flag:", f)
}

Cet exercice est à réaliser dans le répertoire tutorial20160314/bin_search.

Voici le squelette pour votre programme bin_search.go:

// bin_search.go: simple binary search in sorted array of integer.
package main
 
import (
	"flag"
	"fmt"
	"math/rand"
)
 
// BinSearch(tab, x) search for x in tab using efficient binary searching
// algorithm
// Returns a pair made of a position and a boolean, the boolean is false if x
// is not in the array, true otherwise.
func BinSearch(tab []int, x int) (int, bool) {
	// ** FIX ME ***
}
 
// genSortedArray(size) build a random sorted array of len size
func genSortedArray(size int) []int {
	tab := make([]int, size)
	cur := rand.Intn(32)
	for i := 0; i < size; i++ {
		tab[i] = cur
		cur += rand.Intn(16) + 1
	}
	return tab
}
 
// bin_search: test binary searching
func main() {
	var size int
	var seed int64 // mandatory for rand.Seed()
	// Flags
 
	// ** FIX ME **
	// take 2 flags: size and seed setting the value for variable size and seed
	// use flag.IntVar() et flag.Int64Var()
	// use some reasonable default values for size and seed.
	// see https://golang.org/pkg/flag
 
	// Init random generator
	rand.Seed(seed)
 
	tab := genSortedArray(size)
	fmt.Println(tab)
	pos := rand.Intn(size)
	x := tab[pos]
	fmt.Println("\nSearch for existing element:", x)
	pos_res, found := BinSearch(tab, x)
	fmt.Printf("BinSearch(tab, x): (%v, %v)\n", pos_res, found)
 
	x = tab[0] + rand.Intn(tab[len(tab)-1]-tab[0])
	fmt.Println("\nSearch for random element:", x)
	pos_res, found = BinSearch(tab, x)
	fmt.Printf("BinSearch(tab, x): (%v, %v)\n", pos_res, found)
}

• Compléter le code …

Quick Sort

Sur le même principe que l'exercice précédent, vous devez implémenter un quick sort avec le programme de tests correspondant.

• Compléter le squelette de code fourni

Le répertoire est tutorial20160314/quick_sort. Voici le squelette du code:

/*
quick_sort.go: a simple quick sort on slice of int
 
  usage: quick_sort [-size size] [-seed seed]
 
    builds a random vector of integers, sorts the vector using QuickSort
    function and checks that it's really sorted, if size < 20 also prints the
    vector
 
  see quicksort -help for details
*/
package main
 
import (
	"flag"
	"fmt"
	"math/rand"
)
 
// smax(v, a, b) returns which index betweem a and b corresponds to a greater value in v
func smax(v []int, a, b int) int {
	if v[a] > v[b] {
		return a
	}
	return b
}
 
// smin(v, a, b) returns which index betweem a and b corresponds to a smaller value in v
func smin(v []int, a, b int) int {
	if v[a] < v[b] {
		return a
	}
	return b
}
 
// choose_pivot(v) chooses a pivot a pivot index in v
func choose_pivot(v []int) int {
	fst, med, last := 0, len(v)/2, len(v)-1
	a, b, c := smax(v, fst, med), smax(v, fst, last), smax(v, med, last)
	return smin(v, smin(v, a, b), c)
}
 
// partition(v) partitions v and returns the pivot index
func partition(v []int) (pivot int) {
	// ** FIX ME **
}
 
// QuickSort(v) sorts in place v
func QuickSort(v []int) {
	// ** FIX ME **
}
 
// random_vector(size) builds a random vector of size integer
// values are in the range [0, 1000)
func random_vector(size int) (v []int) {
	v = make([]int, size)
	for i, _ := range v {
		v[i] = rand.Intn(1000)
	}
	return
}
 
// is_sorted(v) returns true if v is sorted in increasing order
func is_sorted(v []int) bool {
	// ** FIX ME **
}
 
func main() {
	size := 8
	seed := int64(42)
	// ** FIX ME **
 
	rand.Seed(seed)
	v := random_vector(size)
 
	if size < 20 {
		fmt.Println(v)
	}
 
	fmt.Println("Running quick sort ...")
 
	QuickSort(v)
 
	if size < 20 {
		fmt.Println(v)
	}
 
	fmt.Println("is sorted: ", is_sorted(v))
}

Rappel: algorithme du quick sort, dans tous les algos left est inclu et right est exclue.

choose_pivot(v, left, right): returns a "good" pivot index

partition(v, left, right):
  pivot = choose_pivot(v, left, right)
  pval = v[pivot]
  swap(v[pivot], v[right - 1])
  pivot = left
  for i = left to right - 2 do:
    if v[i] < pval:
      swap(v[i], v[pivot])
      pivot += 1
    end if
  done
  swap(v[pivot], v[right - 1])
  return pivot

QuickSort(v, left, right):
  if right - left > 1:
    pivot = partition(v, left, right)
    QuickSort(v, left, pivot)
    QuickSort(v, pivot + 1, right)
  end if