Programmation Fonctionnelle, TP8

Figure
Version & licenses
Creative Commons License

Programmation Fonctionnelle, TP8 : Évaluation paresseuse et machines de Turing

Guyslain Naves

Nous allons définir un type des listes infinies, contenant donc une infinité de valeurs. Bien sûr, nous ne voulons pas calculer toutes les valeurs d'une liste infinie, notre temps est trop précieux. Du coup, nous allons le faire avec paresse. L'évaluation paresseuse d'une valeur consiste à ne calculer la valeur définie par une expression que si le programme en a vraiment besoin.

Introduction aux expressions paresseuses.

OCaml intègre un mécanisme pour définir des expressions paresseuses. On peut écrire :

  1. # let hello = lazy (Unix.sleep 2; "Hello world!\n")

lazy est un mot-clé permettant de construire une expression paresseuse. Il se comporte comme un constructeur du type Lazy.t.

  1. (* it is almost as if this was defined : *)
  2. type 'value Lazy.t =
  3. | lazy of 'value

Pour utiliser une valeur paresseuse, on peut l'observer, comme d'habitude (ou bien utiliser la fonction Lazy.force) :

  1. # let print_lazy_string (lazy str) = print_string str;;
  2. val print_lazy_string : string lazy_t -> unit = <fun>
  3. # print_lazy_string hello;;

(attendre deux secondes)

  1. Hello world!
  2. - : unit = ()

On constate bien avec cette exemple que l'évaluation de l'expression paresseuse est reportée au moment où on utilise son contenu.

Listes infinies.

Récupérez cette archive qui contient quelques fichiers sources fournis gracieusement.

Nous pouvons grâce à ce mécanisme d'évaluation paresseuse, créer des listes infinies. Créez un fichier colist.ml et son interface colist.mli. Nous voulons avoir à la fin cette interface :

  1. type 'elt t

  2. (** Construction *)

  3. (** [const e = [e; e; ...]] *)
  4. val const : 'elt -> 'elt t

  5. (** [iterate e ~f = [e; f e; f (f e); ...]] *)
  6. val iterate : 'elt -> f:('elt -> 'elt) -> 'elt t

  7. (** [unfold state0 ~f = [ e0; e1; e2; ...]]
  8. where [f state_i = (e_i,state_(i+1))]
  9. *)
  10. val unfold : 'state -> f:('state -> ('state * 'elt)) -> 'elt t


  11. (** Observation *)

  12. (** observe the head and tail of an infinite list *)
  13. val observe : 'elt t -> ('elt * 'elt t)


  14. (** Manipulation *)

  15. val append : 'elt -> 'elt t -> 'elt t

  16. (** [take k list] is the list of the first [k] elements of [list] *)
  17. val take : int -> 'elt t -> 'elt list

  18. (** [drop k list] is the list with the first [k] elements removed from [list] *)
  19. val drop : int -> 'elt t -> 'elt t

  20. val zip : 'left t -> 'right t -> ('left * 'right) t


  21. (** Higher-order functions *)

  22. val map : 'elt t -> f:('elt -> 'im) -> 'im t

  23. val filter : 'elt t -> f:('elt -> bool) -> 'elt t

  24. (** [scan ~f ~init:state_0 [ e0; e1; e2; ...]] is
  25. [state_0; state_1; ...] where [state_(i+1) = f state_i e_i]
  26. *)
  27. val scan : f:('state -> 'elt -> 'state) -> init:'state -> 'elt t -> 'state t

On utilise le type :

  1. type 'elt cell = Cons of ('elt * 'elt t)
  2. and 'elt t = 'elt cell Lazy.t

On peut par exemple définir ainsi iterate :

  1. let rec iterate init ~f =
  2. lazy (Cons (init, iterate (f init) f))

Complétez le module Colist.

Rubans.

Le plus difficile est fait. On se propose d'utiliser les colistes pour construire des rubans, c'est-à-dire des listes bi-infinies, sans début ni fin. Pour cela, il nous faut un élément (la tête) et deux colistes (les éléments avant la tête, par convention à gauche, les éléments après la tête, par convention à droite de la tête). Les têtes des deux colistes sont alors les deux éléments voici de la tête du ruban. Avec cette représentation, il est facile de déplacer la tête vers le prochain élément vers la droite ou vers la gauche.

Créez des fichiers tape.ml et tape.mli. Ce dernier devra contenir :

  1. type 'elt t

  2. (** [create [ l1; l2; ...] head [ r1; r2; ...]] is
  3. [...; l2; l1; head; r1; r2; ...]
  4. *)
  5. val create : 'elt Colist.t -> 'elt -> 'elt Colist.t -> 'elt t

  6. val move_left : 'elt t -> 'elt t
  7. val move_right : 'elt t -> 'elt t

  8. val move : [ `Left | `Right | `Stay ] -> 'elt t -> 'elt t

  9. (** [set new_head [... l2; l1; h; r1; r2;...] is
  10. [... l2; l1; new_head; r1; r2; ...]
  11. *)
  12. val set : 'elt -> 'elt t -> 'elt t

  13. (** returns the head of the tape *)
  14. val get : 'elt t -> 'elt

  15. val pp :
  16. ?length:int ->
  17. (Format.formatter -> 'elt -> unit) ->
  18. Format.formatter -> 'elt t -> unit

Voici l'implémentation pour pp :

  1. (* replace by Format.pp_print_list with OCaml 4.02 or above *)
  2. let format_pp_print_list ?(pp_sep=Format.pp_print_cut) pp_elt ppf list =
  3. let rec loop ppf = function
  4. | [] -> ()
  5. | [single] -> pp_elt ppf single
  6. | first::others ->
  7. Format.fprintf ppf "%a%a%a"
  8. pp_elt first
  9. pp_sep ()
  10. loop others
  11. in
  12. loop ppf list

  13. let pp ?(length=10) pp_elt ppf tape =
  14. let prefix = Colist.take length tape.left |> List.rev in
  15. let suffix = Colist.take length tape.right in
  16. let pp_sides =
  17. format_pp_print_list
  18. ~pp_sep:(fun ppf () -> Format.fprintf ppf "@ | ")
  19. pp_elt
  20. in
  21. Format.fprintf ppf "%a >>@ %a@ << %a"
  22. pp_sides prefix
  23. pp_elt tape.head
  24. pp_sides suffix

Quel est le type utilisé pour Tape.t ?

Complétez le module Tape.

Machines de Turing

Avec des rubans, il devient facile de faire des machines de Turing. Ce sont des automates finis disposant d'un ruban. À chaque pas de temps, la machine lit la lettre sur la tête du ruban, et choisit une transition correspondant à cette lettre. Chaque transition peut aussi écrire une lettre sur le ruban, puis déplacer le ruban d'un cran vers la gauche ou vers la droite.

Le module TuringMachine est fourni. Prenez connaissance de son interface.

Nous voulons créer deux machines de Turing : le busy-beaver à 4 états (c'est la machine de Turing qui met le plus de temps à s'arrêter sur 4 états, avec un alphabet de deux lettres et un ruban contenant initialement uniquement la même lettre), et l'additionneur de nombres binaires.

Voici le tableau des transitions pour busy-beaver :

un busy-beaver
État initial Symbole lu Symbole Écrit Déplacement Nouvel état
A01DroiteB
A11GaucheB
B01GaucheA
B10GaucheC
C01DroiteHalte
C11GaucheD
D01DroiteD
D10DroiteA

Et celui pour l'additionneur

Un additionneur
État initial Symbole lu Symbole Écrit Déplacement Nouvel état
AvecRetenu $(0,0)$ 1Gauche SansRetenu
AvecRetenu $(1,0)$ 0Gauche AvecRetenu
AvecRetenu $(0,1)$ 0Gauche AvecRetenu
AvecRetenu $(1,1)$ 1Gauche AvecRetenu
SansRetenu $(0,0)$ 0Gauche SansRetenu
SansRetenu $(1,0)$ 1Gauche SansRetenu
SansRetenu $(0,1)$ 1Gauche SansRetenu
SansRetenu $(1,1)$ 0Gauche AvecRetenu
AvecRetenu Vide1Gauche Halte
SansRetenu VideVideGauche Halte

(dans tous les autres cas, écrire 0, se déplacer à gauche et passer dans l'état Halt).

Créez deux exécutables: l'un montrant toutes les étapes de l'exécution du busy-beaver, l'autre montrant toutes les étapes de l'addition de deux entiers, où les deux entiers sont pris en argument du programme (Sys.argv.(1) : string et Sys.argv.(2) : string.

À vous de jouer.

Une autre application intéressante des rubans est de créer des automates cellulaires. On peut commencer par les automates cellulaires élémentaires. Pour cela, il faudra ajouter une fonction sur les rubans, qui remplace chaque élément par le ruban dont la tête est cet élément.

On peut aussi programmer le jeu de la vie, pour cela il faut non un ruban, mais une grille infinie. On peut la représenter par un ruban (horizontal) donc chaque élément est un ruban (vertical).