Programmation Avancée

TP3: effets

Exercice 1: effets espions

Une fonction est totale si elle termine normalement (sans lever une exception) sur toute entrée. Elle est pure si elle ne manipule pas d'état, d'exceptions, etc. Dans ce cas son résultat dépend uniquement de la valeur passée en entrée.

Question 1

Ecrire une fonction qui calcule l'égalité extensionnelle entre deux prédicats purs et totaux sur bool: f (p:bool->bool) (q:bool->bool) vaut true si et seulement si p x = q x pour tout booléen x.

Question 2

On représente un flux de booléens par une fonction de type stream = int -> bool, et on veut maintenant calculer l'égalité entre prédicats purs et totaux sur stream.

Sur une entrée donnée, un tel prédicat va évidemment accéder seulement à un nombre fini de valeurs du stream, dépendant potentiellement du stream. Montrez que ce nombre est en fait borné indépendamment du contenu du flux.

Pour s'échauffer, implémentez à l'aide du mécanisme d'exceptions un objet de type stream qui permette de détecter si un prédicat sur stream accède au contenu du stream passé en argument ou s'il s'agit d'une fonction constante.

En généralisant, "décompilez" le prédicat en un arbre de décision binaire décrivant le comportement du prédicat: un chemin dans l'arbre correspondra à une description partielle d'un stream jusqu'à un certain rang, et les feuilles donnent les valeurs du prédicat.

Vous pouvez maintenant écrire un test vérifiant qu'un prédicat est toujours vrai, et donc implémenter l'égalité extensionnelle.

Question 3

Adaptez votre code pour utiliser un état plutôt que les exceptions.

Exercice 2: récursion sans rec

Nous allons voir que l'on peut simuler la définition de fonction récursive, permise par let rec, à l'aide de références sur des fonctions. Ainsi, état et fonctions de première classe suffisent à obtenir un langage Turing puissant.

Notre objectif est de démontrer ce point de façon générique. Pour cela, on rappelle qu'une fonction récursive a une fonctionnelle associée, dont la fonction récursive est le (plus petit) point fixe. Etant donné une fonctionnelle ff : (int -> int) -> (int -> int), on peut définir ce point fixe comme suit:

let f_of_ff ff =
  let rec f x = ff f x in
    f

Par exemple, pour la factorielle:

# let ffact fact x = if x = 0 then 1 else x * fact (x-1) ;;
val ff : (int -> int) -> int -> int = <fun>
# let fact = f_of_ff ffact ;;
val fact : int -> int = <fun>
# fact 3 ;;
- : int = 6

Question 1

Refaire la même chose sans let rec, mais en utilisant un état. Pas le droit à l'objet, etc. seulement aux références.

Exercice 3: en long et en large

Cet exercice n'est pas un exercice sur les effets. Le but est même de tout réaliser de façon "pure", avec des structures de données persistantes.

Les différentes stratégies de parcours d'arbre peuvent être codées de façon uniforme en utilisant la structure de file de priorité, avec différents ordres. Dans cet exercice on s'intéresse seulement à deux cas particuliers: les parcours en profondeur et en largeur (de gauche à droite dans les deux cas) correspondant aux structures de file et de pile.

On considère la signature suivante:

module type Priority = sig
  type 'a t
  exception Empty
  val singleton : 'a -> 'a t
  val put : 'a * 'a t -> 'a t
  val take : 'a t -> 'a * 'a t
  val put2 : 'a * 'a * 'a t -> 'a t
  val take2 : 'a t -> 'a * 'a * 'a t
end

Le type t représente une collection ordonnée, put est l'ajout et take prend une collection non-vide et renvoie le premier élement et la collection à laquelle cet élément a été enlevé; cette fonction lève l'exception Empty si on lui passe une collection vide.

La fonction put2 (resp. take2) effectue deux put (resp. take) dans un ordre bien choisi, qu'on ajustera dans la dernière question.

Question 1

Réaliser deux module de type Priority: Stack qui implémente les piles et Queue qui implémente les files. (Pour les files, on peut éviter un put en temps linéaire, en amortissant.)

Question 2

On considère le type d'arbres suivant:

type 'a t = Leaf of 'a | Node of 'a * 'a t * 'a t

(** 0
  * |\
  * 1 6
  * |\
  * 2 3
  *   |\
  *   4 5  *)
let t =
  Node (0, Node (1, Leaf 2, Node (3, Leaf 4, Leaf 5)), Leaf 6)

Ecrire un foncteur qui prend en argument un module de type Priority, et implémente la fonction to_list qui parcourt un arbre à l'aide de la file de priorité donnée et renvoie la liste des valeurs (de type 'a) rencontrées sur les noeuds et feuilles dans l'ordre du parcours.

On teste, où Depth est l'instance de votre foncteur sur Stack et Breadth son instance sur Queue:

# Depth.to_list t ;;
- : int list = [0; 1; 2; 3; 4; 5; 6]
# Breadth.to_list t ;;
- : int list = [0; 1; 6; 2; 3; 4; 5]

Question 3

Ajouter une fonction relabel à votre foncteur, qui prend un arbre en entrée et calcule en sortie un arbre de même structure mais dont les noeuds et feuilles ont été re-étiquetés selon leur ordre de parcours. (Cela peut aider de commencer par coder la fonction identité qui déconstruit un arbre en le parcourant, puis le reconstruit en remontant la pile des appels récursifs.)

On teste:

# Depth.relabel t ;;
- : int Traversals.t =
Node (0, Node (1, Leaf 2, Node (3, Leaf 4, Leaf 5)), Leaf 6)
# Breadth.relabel t ;;
- : int Traversals.t =
Node (0, Node (1, Leaf 3, Node (4, Leaf 5, Leaf 6)), Leaf 2)