Programmation Avancée

TP4: exercices de style

Exercice 1: transformations de programmes

Question 1

Ecrire le renversement de liste de façon naïve, non récursive terminale et de complexité quadratique. Transformer ensuite votre code en passage par continuations (CPS). Enfin, défonctionnaliser: il s'agit ici d'introduire un type de premier ordre cont pour représenter les fonctions crées comme continuations, et une fonction apply qui simule l'application des continuations.

A quel type bien connu correspond cont? Que calcule apply? Simplifiez votre code grâce à ces observations. Qu'avez-vous obtenu? A quel moment a-t-on changé la complexité de notre code?

Question 2

Implémentez le renversement de liste de façon itérative avec un accumulateur et une boucle while. Transformer la boucle while en une fonction récursive, de façon générique. Eliminer enfin les références en passant l'état explicitement comme vu en cours.

Exercice 2: effets espions

Question 1

Une fonction est totale si elle termine normalement (sans lever une exception) sur toute entrée. Elle est pure si son résultat ne dépend pas d'un état, mais seulement de la valeur passée en entrée.

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 une suite infinie 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. On supposera de plus que les prédicats ne rattrapent pas d'exceptions.

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 stream.

Pour s'échauffer, utilisez les exceptions pour implémenter un stream "magique" qui permette de détecter si un prédicat accède à au moins une valeur du stream.

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

Comme la question 2, mais en utilisant un état plutôt que des exceptions.

Exercice 3: générateurs

On se donne le type d'arbres suivant:

type tree =
  | Leaf of int
  | Node of tree*tree

Question 1

Ecrire un itérateur en style impératif qui appelle une fonction sur toutes les feuilles de l'arbre, suivant un parcours en profondeur. Votre fonction iter aura le type tree -> (int -> unit) -> unit. Tester:

let t =
  Node (
    Node (Leaf 25,
          (Node (Node (Leaf 41, Leaf 9), Leaf 12))),
    Node (Leaf 8, Node (Leaf 25, Leaf 55)))

let () =
  iter t (Printf.printf "%d ") ;
  Printf.printf "\n"

Question 2

Transformer cet itérateur en CPS, pour obtenir un générateur iter_k de type tree -> (int -> cont -> ret) -> cont -> ret avec cont = unit -> ret. Tester:

let () =
  Printf.printf "\n" ;
  iter_k
    (fun i k -> Printf.printf "%d " i ; k ())
    t
    (fun () -> Printf.printf "\n")

Question 3

Coder une fonction qui, étant donnée une séquence sous la forme d'un générateur en CPS, renvoie le nombre de sous-séquences dont la somme des éléments fasse 100. Par simplicité, la fonction sera spécialisée à l'itération sur les arbres codée à la question précédente.

On procèdera par backtracking en relançant l'itération, à partir de la fonction itérée, grâce à de multiples appels à la continuation. Pour ne pas faire la même chose à chaque appel, on utilisera un état.

Sur l'arbre de test, on devra trouver trois solutions.