Voir la source de 20160314:TP:Go:Introduction

[[category:EPITA:TP:20152016]]

== 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 <tt>GOPATH</tt> dans votre dépot. Il faudra juste faire attention à ne pas versionner les sous-répertoires <tt>bin</tt> et <tt>pkg</tt>.

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:

* <tt>gowork/</tt>
** <tt>bin/</tt>
** <tt>pkg/</tt>
** <tt>src/</tt>
*** <tt>tutorial20160314/</tt>

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

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

<pre>
bin/
pkg/
</pre>

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 <tt>${GOPATH}/src/my_app/foo.go</tt> et que je le compile, j'obtiendrai l'exécutable <tt>my_app</tt> et non pas <tt>foo</tt>. 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 <tt>GOPATH</tt>. Par exemple, si j'ai un programme dans <tt>${GOPATH}/src/my_project_path/my_app/some_source_code.go</tt>, je peux le compiler avec <tt>go build my_project_path/my_app</tt> ce qui produira dans le répertoire courant le binaire <tt>my_app</tt>.

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 <tt>hello</tt> dans le répertoire <tt>tutorial20160314</tt> dans lequel vous pourrez écrire votre fichier <tt>hello.go</tt>:

<source lang="go">
package main

import "fmt"

func main() {
	fmt.Println("Hello, World !")
}
</source>

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

<pre>
# 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
</pre>

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

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

=== Présentation du code et commentaires de documentation ===

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

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

<source lang="go">
/*
  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())
}
</source>

On peut mettre en forme notre code avec <tt>go fmt</tt> et obtenir:

<source lang="go">
/*
  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())
}
</source>

Maintenant testons <tt>go doc</tt>:

<pre>
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>
</pre>

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 <tt>go doc</tt> 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 <tt>tutorial20160314/fact</tt>.

=== Un petit factorielle pour la route ===

* '''Implémenter la fonction suivante:'''

<source lang="go">
// Fact(n) computes factorial of n
// n should be a positive integer, if not, behavior is undefined.
func Fact(n int) (r int)
</source>

Nous verrons le choix du package

=== Tester ===

Pour tester, nous allons construire un package main contenant votre fonction <tt>Fact</tt> et une fonction <tt>main</tt> 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 <tt>fact.go</tt>:

<source lang="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
}
</source>

Pour la gestion d'erreur, nous utiliserons la fonction <tt>Fatalln(...)</tt> du package <tt>log</tt> [https://golang.org/pkg/log/#Fatalln], cette fonction fonctionne comme <tt>fmt.Println(...)</tt> sauf qu'elle quite le programme. Voici un petit exemple:

<source lang="go">
func main() {
	if len(os.Args) < 2 {
		log.Fatalln("missing arguments")
	}
        fmt.Println(os.Args)
}
</source>

Pour récupérer les arguments du main, le package <tt>os</tt> fourni le classique tableau d'arguments: <tt>os.Args</tt>. On peut récupérer sa longueur via <tt>len(os.Args)</tt> et comme pour <tt>argv</tt> 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 <tt>strconv.ParseInt(str, base, bit_size)</tt> [https://golang.org/pkg/strconv/#ParseInt]. Cette fonction renvoie une paire formée de l'entier lu et d'une valeur d'erreur. On l'utilise donc comme suit:

<source lang="go">
        n, err := strconv.ParseInt(os.Args[1], 10, 32)
</source>

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

* '''Compléter le fichier <tt>fact.go</tt>'''

== 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: <tt>flag</tt> [https://golang.org/pkg/flag/] 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:

<source lang="go">
// 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)
}
</source>

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

Voici le squelette pour votre programme <tt>bin_search.go</tt>:

<source lang="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)
}
</source>

* '''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 <tt>tutorial20160314/quick_sort</tt>. Voici le squelette du code:

<source lang="go">
/*
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))
}
</source>

'''Rappel:''' algorithme du quick sort, dans tous les algos <tt>left</tt> est inclu et <tt>right</tt> est exclue.

<pre>
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
</pre>