Le crible en détail, partie 1

Mon post précédent était un poil laconique, je vais donc reprendre quelques détails d'implémentation, et en profiter pour vous convaincre que OCaml, ça roxe.

Les premières lignes sont simplement la définition d'un set sur les entiers. Les sets en OCaml fonctionnent via des modules paramétrés par d'autres modules suivant une certaine signature. L'on créé donc un module définissant un type t et sa comparaison, avec lequel on paramétrise le module Set.Make.

module OrderedInt =
struct
  type t = int
  let compare = compare
end

module IntSet = Set.Make(OrderedInt)

Ceci va donc définir un module tout neuf, que j'appelle IntSet, et qui fournit des fonctions pour travailler sur des sets fonctionnels, c'est à dire sans effets de bords. Ainsi, ajouter un élément au set retourne en fait un nouveau set contenant l'élément. C'est plus efficace qu'il n'y parait, et surtout, cela permet de raisonner à plus haut niveau, d'une manière plus mathématique.

Ensuite, définissons une fonction qui nous sera utile plus tard, qui retourne une liste d'entiers entre deux entiers définis, avec un pas.

let seq_step a b t = 
  let rec do_seq_step a acc = 
    if a > b then 
      acc
    else
      do_seq_step (a + t) (a::acc)
  in
  List.rev (do_seq_step a [])

La fonction définit une sous-fonction do_seq_step, prenant l'entier courant a, et la liste d'entiers accumulés jusque là acc. La récursion est triviale: si mon entier courant a atteint ma borne supérieure, retournons la liste accumulée jusque là. Sinon, appelons récursivement la fonction, avec mon entier courant incrémenté du pas, et ma liste à laquelle j'aurais ajouté mon entier courant.

Depuis la fonction externe, l'on appelle la sous-fonction en passant la borne inférieure, et une liste vide. Enfin, parce que l'on a accumulé les entiers à l'envers (en partant de 3 de 2 en 2: [3], puis [5; 3], puis [7; 5; 3]...), l'on inverse la liste avec List.rev. Le résultat:

# seq_step 3 10 2;;
- : int list = [3; 5; 7; 9]

Notez que l'on aurait pu implémenter la fonction d'un coup, de cette façon:

let rec seq_step2 a b t = 
  if a > b then
    []
  else
    a::(seq_step2 (a + t) b t)

Le résultat semble strictement le même, et pourtant:

# seq_step 1 1000000 1;;
- : int list =
[1; 2; 3; 4; 5; 6; 7; 8; 9; ...]

# seq_step2 1 1000000 1;;
Stack overflow during evaluation (looping recursion?).

La deuxième version est arrêtée nette par un dépassement de pile. C'est que la première version est une récursion terminale (ou tail-recursion en anglais), c'est à dire qu'elle peut être trivialement transformée en une fonction itérative, ce que fait le compilateur. La deuxième, elle, utilise la pile comme accumulateur implicite, et provoque donc un dépassement de pile lorsque le nombre de récursions devient trop important.

Pour des raisons de performances et d'extensibilité, il est donc recommandé d'implémenter ses fonctions de manière récursive terminale à chaque fois que cela est possible.

Voilà, suivant l'approche ascendante qui sied bien à OCaml et aux langages fonctionnels, c'est à dire la construction de fonctions de base, puis de fonctions plus haut niveau utilisant ces briques, les utilitaires utilisés pour le crible. Dans la deuxième partie, je reprendrait plus en détails l'algorithme du crible lui-même.