Programmation Avancée

TP7: défonctionalisation

Exercice 1: transformations de programmes

On commence par appliquer deux transformations vues en cours pour "découvrir" de nouveaux programmes... même s'il ne s'agit pas ici de grandes découvertes.

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 l'algorithme?

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: le retour des itérateurs

Dans cet exercice, vous allez devoir implémenter un maximum d'énumérations, codées comme des itérateurs persistants, sous la contrainte que votre code ne devra pas utiliser d'ordre supérieur. Pour arriver à vos fins, vous aurez la liberté d'utiliser votre intuition ou les techniques vues en cours.

Préliminaires

Récupérer le squelette de code exo2skel.ml. Il définit une signature pour les itérateurs persistants rencontrés au TP5, ainsi qu'une implémentation générique de la recherche des sous-séquences de somme 100, sous la forme d'un foncteur Find.

Ce foncteur prend en argument un module de type ITER, où l'on retrouve la signature de nos itérateurs/énumérateurs, avec quelques fonctions en plus:

module type ITER = sig
  type t
  type collection
  type elt

  val init : collection -> t
  val next : t -> (elt*t) option

  val eval : elt -> int
  val pp : Format.formatter -> elt -> unit
  val test : collection
end

Au début de cette signature, le type t correspond aux itérateurs, le type collection est celui des objets sur lesquels on initialise un itérateur, et elt le type des éléments qu'on énumère. Dans la dernière partie de la signature, on demande des opérations eval, pour évaluer un élément en un entier, pp pour afficher un élément, et test qui est une valeur de test que le foncteur Find utilisera pour initialiser un itérateur.

A titre d'exemple, le fichier squelette contient la définition d'un itérateur sur les éléments d'une liste, et instancie le foncteur Find sur ce type d'énumération. Le code est exécutable.

Dans la fin du fichier, on définit un type d'expressions arithmétiques expr ainsi que quelques opérations dessus, notamment eval et pp. On définit aussi quelques arbres pour les tests.

Objectif

L'objet de l'exercice est de définir des itérateurs persistants pour divers types d'énumérations, sous la forme de modules de type ITER, qu'on testera sur Find. Il y a cependant une contrainte: le type t des itérateurs devra toujours être de premier ordre, i.e., ne pas comporter de type flèche.

Pour chaque question, on pourra produire directement une solution, ou appliquer une méthode systématique pour ce faire: (1) implémenter une fonction iter : (elt -> unit) -> collection -> unit en utilisant toute la puissance du langage; (2) la transformer en une fonction pure en CPS; (3) défonctionaliser, et utiliser le type des continuations défonctionalisées comme type t.

Question 1

Enumérer les entiers situés aux feuilles d'une expression arithmétique.

Question 2

Enumérer les sous-expressions (sous-arbres) d'une expression arithmétique donnée.

Question 3

Enumérer les expressions se plongeant dans une expression donnée, c'est à dire qu'elles s'obtiennent en supprimant certains noeuds. Par exemple, dans (1+2)*(3+(4*5)) on peut plonger les expressions 1*4, (1+2)*(3+5), etc.

Question 4

Enumérer les sous-expressions (sous-arbres) d'une expression arithmétique, cette fois-ci selon un parcours en largeur préfixe. Par exemple, (1+2)+3 doit donner l'expression elle même, suivie de 1+2, 3, 1 et enfin 2.