Programmation Fonctionnelle, TP

On se propose dans ce TP d'utiliser une technique algorithmique appelée zipper, permettant de parcourir une structure de donnée, typiquement un arbre, en appliquant des transformations locales. Nous regarderons le cas du zipper de liste, un peu plus simple. Nous donnerons une première implémentation du zipper de liste. Ensuite, nous lui donnerons une interface de monade d'état. Nous utiliserons cette interface pour implémenter une machine de Turingcalculant des additions, ou une autre machine qui est une solution du problème de Busy Beaver.

Zipper de liste.

Nous avons appris que les listes s'utilisent en manipulant uniquement une extrémité. Cela exclut les applications nécessitant de manipuler des éléments au milieu de la liste. Les zippers apportent une solution partielle à ce problème : plutôt que de coder directement la liste, un zipper code une position dans une liste. Par exemple :

être en tête (position $0$) de la liste [11;32;57;29;41], c'est-à-dire pointer sur la valeur 11 , et avoir les valeurs 32 , 57 , 29 , 41 à droite,
être en position $2$ de cette liste, c'est-à-dire pointer sur la valeur 57 , avec les valeurs 32 et 11 à gauche et 2 et 4 à droite,
ou être en position $4$ de cette liste, c'est-à-dire pointer sur la valeur 41 , et avoir les valeurs 29 , 57 , 32 et 11 à droite, aucune à gauche.
etc.

Nous pouvons donc définir un zipper comme :

un élément pointé (nous l'appelerons tête, bien qu'il ne s'agisse pas nécessairement de la tête de la liste au sens usuel),
une liste des éléments à gauche (en ordre inverse, pour garder proche dans le zipper les éléments proches dans la liste par rapport à l'élément pointé),
une liste des éléments à droite.

Une façon de comprendre le zipper de liste est d'imaginer un ruban magnétique, et une tête de lecture qui lit un endroit particulier du ruban, comme dans un vieux magnétophone. La tête magnétique peut lire ou modifier le ruban à l'endroit où elle pointe, si elle veut lire ou modifier un autre endroit, il faut déplacer le ruban dans un sens ou dans l'autre.

Nous pourrions avoir le même raisonnement pour un arbre. Un zipper d'arbre est :

un nœud pointé,
le sous-arbre droit et le sous-arbre gauche de ce nœud,
la liste des nœuds entre le nœud pointé et la racine, et pour chacun de ces nœuds, le sous-arbre ne contenant pas le nœud pointé, et une information indiquant si le nœud pointé est à droite ou à gauche.

Ainsi, ces informations permettent de connaitre exactement la structure complète de l'arbre, du point de vue du nœud pointé.

Revenons aux listes, et implémentons les principales fonctions du zipper de liste.

Le type des zippers de listes.

Créer un nouveau répertoire pour ce TP, puis dans ce répertoire créer un fichier zipperList.ml. Dans ce fichier, proposer un type pour les zipper de listes.

type 'elt t (* A type for list zippers *)

(** [zipper reversed_left head right] represents the list
[List.rev left @ [head] @ right], with head [head].
*)
val zipper : 'elt list -> 'elt -> 'elt list -> 'elt t
(** Returns the head of the zipper. *)
val read : 'elt t -> 'elt
(** Returns the list of elements left of the head, in reversed
order. *)
val left : 'elt t -> 'elt list
(** Returns the list of elements right of the head. *)
val right : 'elt t -> 'elt list

Modification de la tête.

Écrire une fonction remplaçant l'élément pointé par la tête par une autre valeur.

(** Replaces the head of the zipper with the given value. *)
val write : 'elt -> 'elt t -> 'elt t

Déplacement de la tête de lecture/écriture.

Pour pouvoir lire et modifier d'autres éléments, il faut pouvoir se déplacer dans la liste représentée par le zipper. Pour cela, nous codons des fonctions élémentaires nous permettant de nous déplacer vers l'élément d'à-côté, s'il existe. Nous voulons aussi pouvoir tester si une extrémité de la liste est atteinte. Coder les fonctions suivantes.

(** Checks whether the head is at the right end of the list. *)
val is_at_right_end : 'elt t -> bool
(** Checks whether the head is at the left end of the list. *)
val is_at_left_end : 'elt t -> bool
(** Returns the zipper with the head moved one position left.
If the head is already in the leftmost position,
[step_left zipper = zipper].
*)
val step_left : 'elt t -> 'elt t
(** Returns the zipper with the head moved one position right.
If the head is already in the rightmost position,
[step_right zipper = zipper].
*)
val step_right : 'elt t -> 'elt t

Un zipper d'une liste infinie.

On peut facilement créer une liste infinie en OCaml par une définition récursive :

let rec const_zero = 0 :: const_zero

Utiliser cette possibilité pour ajouter une fonction créant un zipper représentant une liste infinie des deux côtés, mais dont tous les éléments ont la même valeur.

(** This represents an infinite constant list with head in arbitrary
position. *)
val infinite_constant : 'elt -> 'elt t

Ajouter un fichier d'interface.

Créer dans le même répertoire que zipperList.ml un fichier zipperList.mli.

Écrire l'interface de toutes les fonctions du zipper dans ce nouveau fichier :

(** the type for zipper of list, representing a list with a special
element somewhere, the head. Access to the head is easy, while
access to the elements far from the head takes time proportional
to the distance from the head. *)
type 'elt t
(** [zipper reversed_left head right] represents the list
[List.rev left @ [head] @ right], with head [head].
*)
val zipper : 'elt list -> 'elt -> 'elt list -> 'elt t
(** This represents an infinite constant list with head in arbitrary
position. *)
val infinite_constant : 'elt -> 'elt t
(** Checks whether the head is at the right end of the list. *)
val is_at_right_end : 'elt t -> bool
(** Checks whether the head is at the left end of the list. *)
val is_at_left_end : 'elt t -> bool
(** Returns the head of the zipper. *)
val read : 'elt t -> 'elt
(** Replaces the head of the zipper with the given value. *)
val write : 'elt -> 'elt t -> 'elt t
(** Returns the list of elements left of the head, in reversed
order. *)
val left : 'elt t -> 'elt list
(** Returns the list of elements right of the head. *)
val right : 'elt t -> 'elt list
(** Returns the zipper with the head moved one position left.
If the head is already in the leftmost position,
[step_left zipper = zipper].
*)
val step_left : 'elt t -> 'elt t
(** Returns the zipper with the head moved one position right.
If the head is already in the rightmost position,
[step_right zipper = zipper].
*)
val step_right : 'elt t -> 'elt t

Compiler.

Ajouter un fichier .merlin dans votre répertoire, contenant ;

B _build/

Puis compiler votre module de zipper :

ocamlbuild zipperList.cmo

Corriger les éventuelles erreurs. Vérifier ensuite le contenu du répertoire courant et du sous-répertoire _build/.

Compléter l'interface des zippers. (Optionnel)

Si vous avez le temps à la fin du TP, ajouter les fonctions suivantes aux zippers de listes :

(** [move_left n] repeats [step_left] [n] times, hence it moves the
head by up to [n] positions to the left. *)
val move_left : int -> 'elt t -> 'elt t
(** [move_left n] repeats [step_left] [n] times, hence it moves the
head by up to [n] positions to the right. *)
val move_right : int -> 'elt t -> 'elt t
(** inserts an new element right of the head *)
val insert_right : 'elt -> 'elt t -> 'elt t
(** inserts an new element left of the head *)
val insert_left : 'elt -> 'elt t -> 'elt t
(** Removes the first element at the right of the head (if any). *)
val drop_right : 'elt t -> 'elt t
(** Removes the first element at the left of the head (if any). *)
val drop_left : 'elt t -> 'elt t
(** [drop_n_right n] removes the up to [n] first elements at the right
of [head]. *)
val drop_n_right : int -> 'elt t -> 'elt t
(** [drop_n_left n] removes the up to [n] first elements at the
left of [head]. *)
val drop_n_left : int -> 'elt t -> 'elt t
(** Removes all elements left of head. *)
val drop_all_left : 'elt t -> 'elt t
(** Removes all elements right of head. *)
val drop_all_right : 'elt t -> 'elt t

Une interface monadique pour les zippers.

Un algorithme sur un zipper de liste peut être décrit comme une succession d'opérations, par exemple : aller à droite, lire la valeur en tête, écrire telle valeur, aller à gauche, aller à gauche, etc. Dans une telle description, à aucun moment nous n'avons eu à mentionner explicitement le zipper lui-même, nous avons seulement parler de comment le manipuler.

Les monades d'états sont des interfaces permettant de décrire des suites d'opérations affectant un état (ici le zipper), sans mentionner l'état directement. Ils sont utilisés notamment en programmation fonctionnelle pour simuler des références ou permettre de retrouver un style de programmation proche des langages impératifs. Ici nous les utilisons pour simplifier la manipulation du ruban.

Module de monades d'états.

Récupérer les fichier :

Les ajouter à votre répertoire. Compiler stateMonad.cmo et stateMonadExample.native. Puis exécuter ce dernier.

> ocamlbuild stateMonadExample.native
> ./stateMonadExample.native

Prenez connaissance de l'interface donnée dans stateMonad.mli, et familiarisez-vous avec les exemples de stateMonadExample.ml, par exemple en les modifiant.

Rendre le zipper monadique.

Pour créer une monade sur un état de type nom_type, il suffit de passer l'identifiant de ce type au foncteur Make de StateMonad :

module MyType = struct type t = nom_type end
module MyStateMonad = StateMonad.Make(MyType)

Ici on veut créer un zipper de liste paramêtré par un type element. Nous voulons donc écrire un foncteur prenant un type Elt.t en argument (tout comme StateMonad.Make), et retournant une interface de monade d'état avec state = Elt.t zipper.

Recopier le code suivant, et expliquer pourquoi c'est ce que nous voulons.

type 'elt zipper = 'elt t
module MakeMonadic = functor (Elt : sig type t end) ->
struct
module M = StateMonad.Make(struct type t = Elt.t zipper end)
include M
end

Une fonction lift.

Si nous en restons là, tout manipulation du zipper nous demanderait de passer par les fonctions get ou apply. Nous allons donc redéfinir les fonctions de l'interface de zipper pour pouvoir les utiliser facilement avec le zipper. Pour cela, il suffit de transformer les fonctions déjà écrites. Il y a deux cas :

les fonctions prenant un zipper en argument et retournant un autre zipper, dont le type est Elt.t zipper -> Elt.t zipper. Un exemple est step_left. Puisqu'une telle fonction ne fait qu'agir sur l'état, il faut la transformer en une fonction de type unit M.t. Pour cela, il suffit d'utiliser la fonction apply :

let step_left = apply step_left

les fonctions prenant un zipper en argument et retournant une valeur, dont le type est Elt.t zipper -> 'value, par exemple head. Ces fonctions ne modifient pas le zipper, mais retournent une valeur, nous voulons donc leur donner le type 'value M.t. Pour cela, nous aimerions écrire :

let head = lift head

Nous devons donc écrire une fonction lift respectant :

val lift : (Elt.t zipper -> 'value) -> 'value ZipperMonad.t

qui récupère le zipper, calcule le résultat et le retourne. Écrire cette fonction lift.

Compléter le foncteur.

Compléter le foncteur MakeMonadic, pour obtenir cette interface. Ajouter cette interface dans zipperList.mli.

(** An alias for the type of zipper *)
type 'elt zipper = 'elt t
(** An interface for zipper of [Elt.t] as a state monad. *)
module MakeMonadic : functor (Elt : sig type t end) ->
sig
include StateMonad.S with type state = Elt.t zipper
val is_at_right_end : bool t
val is_at_left_end : bool t
val read : Elt.t t
val write : Elt.t -> unit t
val get_left : Elt.t list t
val get_right : Elt.t list t
val step_left : unit t
val step_right : unit t
(* Ajouter les 10 suivantes en fin de TP si vous avez le temps : *)
val move_left : int -> unit t
val move_right : int -> unit t
val insert_right : Elt.t -> unit t
val insert_left : Elt.t -> unit t
val drop_left : unit t
val drop_right : unit t
val drop_n_left : int -> unit t
val drop_n_right : int -> unit t
val drop_all_left : unit t
val drop_all_right : unit t
end

Application : simuler une machine de Turing.

Les machines de Turing sont un modèle de calcul, qui permet en informatique théorique d'étudier ce qui peut ou ne peut pas être calculer, et si oui avec quelle efficacité. Nous allons simplement montrer comment simuler une machine de Turing grâce à un zipper de liste.

Une machine de Turing peut se décrire par un automate à états finis munis d'un ruban. Le ruban est une sorte de tableau infiniment long, découpé en cases successives pouvant chacune contenir un symbole parmi une liste finie de symboles possibles. La machine dispose d'une tête de lecture disposée sur une case du ruban. Elle peut lire ou écrire sur cette case, se déplacer d'une case à droite ou d'une case à gauche. Naturellement le zipper va nous servir à coder le ruban.

Une machine de Turing s'exécute par étapes, appelées transitions. Pendant une transition, la machine lit le symbole se trouvant sous la tête de lecture, puis, selon l'état dans lequel elle se trouve et le caractère lu :

écrit un symbole sous la tête de lecture,
choisit de se déplacer d'une case vers la droite ou vers la gauche,
et choisit son prochain état.

On pourrait donc résumer les transitions par une fonction :

état_initial * symbole_lu -> symbole_écrit * déplacement * nouvel_état

Les transitions s'enchaînent jusqu'à atteindre l'état spécial Arrêt.

Nous proposons de simuler au choix :

un additionneur binaire,
un busy-beaver à $n$ états : une machine de Turing avec seulement $n$ états (plus Arrêt), qui effectue un nombre maximum de transitions avant de s'arrêter.

Le second devrait être plus simple à coder.

Symboles et états.

Dans un nouveau fichier d'extension .ml, proposer un type pour les symboles du ruban et un type pour les états.

Pour l'additionneur, le ruban contiendra des cases soit vides, soit contenant deux bits à additionner, soit le résultat de l'addition. La machine a deux états en plus de Arrêt: AvecRetenu et SansRetenu.

Pour le busy-beaver, le ruban contient des 1 et des 0 uniquement (pas de cases vides), et possède des états A, B, C, D et Arrêt.

Ruban initial.

Pour le busy-beaver, le ruban initial est composé uniquement de 0 . Pour l'additionneur, seules les cases sous la tête et à sa droite sont non-vides, et contiennent des paires de deux bits : la $k^\textrm{e}$ paires à droite contient les bits de poids $k$ des deux entiers à additionner.

Écrire un valeur calculant le ruban initial de votre machine.

Créer la monade.

Appliquer le foncteur StateMonad.MakeMonadic pour obtenir un module Tape de monade dont l'état est un ruban pour votre machine.

La fonction de transition.

Écrire la fonction de transition de votre machine :

val transition : state -> state Tape.t

Pour cela, utiliser Tape.read, Tape.write, Tape.step_right, etc, et les opérateurs infixes de Tape

Voici le tableau des transitions pour busy-beaver :

un *busy-beaver*
État initial	Symbole lu	Symbole Écrit	Déplacement	Nouvel état
A	0	1	Droite	B
A	1	1	Gauche	B
B	0	1	Gauche	A
B	1	0	Gauche	C
C	0	1	Droite	Halte
C	1	1	Gauche	D
D	0	1	Droite	D
D	1	0	Droite	A

Et celui pour l'additionneur

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

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

Une évaluation de la machine.

Depuis le ruban initial et un état initial, les transitions sont répétés jusqu'à atteindre l'état Arrêt. Écrire une fonction prenant l'état initial et simulant l'exécution de la machine de Turing.

val evaluate : state -> unit Tape.t

Nous pouvons aussi en proposer une qui calcule aussi le nombre de transitions effectuées :

val evaluate_with_step_count : int -> state -> int Tape.t

Lancer l'évaluation et afficher le résultat final.

Utiliser run avec le ruban initial pour provoquer l'évaluation de la machine de Turing. Afficher le ruban produit (ou plutôt une partie finie du ruban).

Amélioration.

Il serait intéressant d'afficher le ruban et l'état courant avant chaque transition, ainsi que le déplacement relatif de la tête de lecture depuis le début de l'évaluation. C'est possible en utilisant une autre monade d'état pour stocker le déplacement et le nombre de transitions effectuées par exemple, et faire le produit de cette monade avec la monade de ruban, grâce au foncteur StateMonad.Product

À vous de jouer.

Proposer d'autres machines de Turing.
Compléter l'interface des zippers de listes.
Proposer un affichage graphique illustrant l'exécution pas-à-pas du calcul.