## Exercises

### Following the evolution of the heap

In order to follow the evolution of the heap, we suggest writing a function that keeps information on the heap in the form of a record with the following format:
```# type` `tr_gc` ``=`` `{state` ``:`` `Gc.stat;` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `time` ``:`` `float;` `number` ``:`` `int};;

```
The time corresponds to the number of milliseconds since the program began and the number serves to distinguish between calls. We use the function Unix.time (see chapter 18, page ??) which gives the running time in milliseconds.
1. Write a function trace_gc that returns such a record.
```# type` `tr_gc` ``=`` `{etat` ``:`` `Gc.stat;` `` `temps` ``:`` `float;` `numero` ``:`` `int}` `;;`type tr_gc = { etat: Gc.stat; temps: float; numero: int }`# let` `trace_gc` `` ``=`` `` `` `let` `num` ``=`` `ref` ``0`` `in` `` `` `` `function` `()` `->` `incr` `num;` `` `` `` `` `{` `etat` ``=`` `Gc.stat` `();` `` `temps` ``=`` `Unix.time();` `numero` ``=`` ``!`num}` `;;`val trace_gc : unit -> tr_gc = <fun>`

```

2. Modify this function so that it can save a value of type tr_gc in a file in the form of a persistant value. This new function needs an output channel in order to write. We use the Marshal module, described on page ??, to save the record.
```# let` `trace_out_gc` `oc` `` ``=`` `` `` `` `let` `trgc` ``=`` `trace_gc` `in` `` `` `` `` `` `Marshal.to_channel` `oc` `` `trgc` `[];;`val trace_out_gc : out_channel -> unit = <fun>`

```

3. Write a stand-alone program, taking as input the name of a file containing records of type of tr_gc, and displaying the number of major and minor garbage collections.
```type` `tr_gc` ``=`` `{etat` ``:`` `Gc.stat;` `temps` ``:`` `float;` `numero` ``:`` `int}` `;;let` `rec` `last` `l` ``=`` `match` `l` `with` `` `` `[]` `->` `failwith` ``"last"``|`` ``[`e`]`` `->` `e`|`` `t::q` `->` `last` `` `q;;let` `visu` `ltgc` ``=`` `` `` `let` `fst` ``=`` `List.hd` `ltgc` `` `` `and` `lst` ``=`` `last` `ltgc` `in` `` `` `let` `nb_minor` ``=`` `lst`.`etat`.`Gc.minor_collections` ``-`` `fst`.`etat`.`Gc.minor_collections` `` `` `and` `nb_major` ``=`` `lst`.`etat`.`Gc.major_collections` ``-`` `fst`.`etat`.`Gc.major_collections` `in` `` `` `` `` `Printf.printf` ``"Nombre de Gc: mineur = %d, majeur = %d\n"`` `nb_minor` `nb_major` `;;let` `rec` `read_trace` `ic` ``=`` `` `` `try` `` `` `` `` `let` `tgc` ``=`` `(` `(Marshal.from_channel` `ic)` ``:`` `tr_gc)` `in` `` `` `` `` `tgc` `::` `(read_trace` `ic)` `` `` `with` `` `` `` `` `End_of_file` `->` `close_in` `ic;` `[];;` `let` `usage` `()` ``=`` `` `` `Printf.printf` ``"usage: visu filename\n"`;;let` `main` `()` ``=`` `` `` `if` `Array.length` `(Sys.argv)` ``<`` ``2`` `then` `usage()` `` `else` `` `` `` `let` `ltgc` ``=`` `read_trace` `(open_in` `Sys.argv`.`(`1`))` `in` `` `` `` `` `visu` `ltgc;;main();;

```

4. Test this program by creating a trace file at the interactive loop level.

### Memory Allocation and Programming Styles

This exercise compares the effect of programming styles on the growth of the heap. To do this, we reconsider the exercise on prime numbers from chapter 8 page ??. We are trying to compare two versions, one tail-recursive and the other not, of the sieve of Eratosthenes.

1. Write a tail-recursive function erart (this name needs fixing) that calculates the prime numbers in a given interval. Then write a function that takes an integer and returns the list of smaller prime numbers. fichier eras2.ml :

````(* fichier eras2.ml *)`let` `erart` `l` `` ``=`` `` `` `let` `rec` `erart_aux` `l` `r` ``=`` `match` `l` `with` `` `` `` `` `[]` `->` `List.rev` `r` `` ``|`` `p::q` `->` `erart_aux` `` `(List.filter` `(` `fun` `x` `->` `x` `mod` `p` ``<>`` ``0`)` `q)` `(p::r)` `` `` `in` `` `` `` `` `erart_aux` `l` `[]` `;;let` `erart_go` `n` ``=`` `` `` `erart` `(Interval.interval` `(`<`)` `` `(fun` `x` `->` `x` ``+`` ``1`)` ``2`` `n)` `;;

```

2. By using the preceding functions, write a program (change the name) that takes the name of a file and a list of numbers on the command line and calculates, for each number given, the list of prime numbers smaller than it. This function creates a garbage collection trace in the indicated file. Trace commands from previous exercice are gathered in file trgc.ml fichier era2_main.ml :

````(* fichier : era2_main.ml *)`open` `Trgc;;let` `usage` `()` ``=`` `Printf.printf` ``"Usage: testgc filename n1 [n2 n3 ... np]n\n"`;;let` `main` `f` `` ``=`` `` `` `if` `Array.length` `(Sys.argv)` ``<`` ``3`` `then` `usage()` `` `else` `` `` `` `` `let` `fn` ``=`` `Sys.argv`.`(`1`)` `` `` `` `` `and` `vn` ``=`` `Array.map` `int_of_string` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `(Array.sub` `Sys.argv` ``2`` `(Array.length` `Sys.argv` ``-`` ``2`))` `` `in` `` `` `` `` `` `let` `oc` ``=`` `open_out` `fn` `in` `` `` `` `` `` `` `` `` `Array.map` `(fun` `n` `->` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `let` `r` ``=`` `f` `` `n` `in` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `trace_out_gc` `oc;` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `` `r)` `vn` `` `;` `` `` `` `` `` `` `close_out` `oc` `;;

```

fichier main_rt.ml :

````(* fichier main_rt.ml *)`Era2_main.main` `Eras2.erart_go;;

```
````(* fichier trgc.ml *)`type` `tr_gc` ``=`` `{etat` ``:`` `Gc.stat;` `temps` ``:`` `float;` `numero` ``:`` `int}` `;;let` `trace_gc` `` ``=`` `` `let` `num` ``=`` `ref` ``0`` `in` `` `` `function` `()` `->` `incr` `num;` `` `` `` `{` `etat` ``=`` `Gc.stat` `();` `` `temps` ``=`` `Unix.time();` `numero` ``=`` ``!`num}` `;;let` `trace_out_gc` `oc` `` ``=`` `` `` `let` `trgc` ``=`` `trace_gc` `()` `in` `` `` `` `` `Marshal.to_channel` `oc` `` `trgc` `[];;

```

3. Compile these files and create a stand-alone executable; test it with the following call, and display the result.
```                                                           %
erart trace_rt 3000 4000 5000 6000
```
Compilation pour Unix :
```\$ ocamlc -custom -o erart unix.cma interval.ml trgc.ml eras2.ml era2_main.ml main_rt.ml -cclib -lunix

```
Test :
```\$ erart traceRT 3000 4000 5000 6000
```
Résultats :
```\$ visu traceRT
Nombre de Gc: mineur = 130, majeur = 22
```

4. Do the same work for the non tail recursive function. On reprend le fichier eras.ml, de la page ??, contenant une fonction de calcul non récursive terminale.

Puis on crée le fichier main_nrt.ml suivant :
````(* fichier main_nrt.ml *)`Era2_main.main` `Eras.era_go;;

```

Compilation :
```\$  ocamlc -custom -o eranrt unix.cma interval.ml trgc.ml eras.ml era2_main.ml main_nrt.ml -cclib -lunix
```
Test :
```\$ eranrt traceNRT 3000 4000 5000 6000
```
Résultats (version 2.04/Unix) :
```\$ visu traceNRT
Nombre de Gc: mineur = 130, majeur = 10
```

5. Compare trace results. Les deux programmes allouent les mêmes données : ils ont le même nombre de GC mineurs. La version récursive terminale effectue plus de GC majeurs. En effet, l'accumulateur r de la fonction erart_rt est évalué dans l'appel récursif et sa tête de liste est rangée dans la zone des valeurs anciennes à chaque GC mineur. Le filtrage des multiples d'un nombre peut entraîner un GC mineur qui fait vieillir la liste filtrée en cours de construction. Les anciennes listes filtrées sont libérées pendant un GC majeur. Ainsi l'espace mémoire de la génération ancienne qui contient la liste des nombres premiers déjà trouvés est plus petit ce qui augmente le nombre de GC majeurs.

Ce cas est particulier

L'écriture d'une fonction récursive sous forme récursive terminale fait gagner en allocation de pile, mais pas forcément en nombre de GC.