Programmation Avancée
TP6: encore des continuations
Exercices conçu par David Baelde
Une transformation renversante
On applique 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.
L'affiche
Il se passe en OCaml des choses étranges, auxquelles on ne pense presque jamais. Les chaînes de formattage ont l'air de chaînes de caractères, mais sont résolument plus complexes du point de vue du typage:
# "%d" ;;
- : string = "%d"
# Printf.printf "%d" ;;
- : int -> unit = <fun>
# Printf.printf "%s" ;;
- : string -> unit = <fun>
# Printf.printf ;;
- : ('a, out_channel, unit) format -> 'a = <fun>
Le compilateur interprète ici les chaînes de formattage comme des valeurs spéciales, dont le type dépend des arguments attendus par la chaîne de format. Une astuce de ce type n'est pas réalisable en OCaml sans avoir à bricoler le compilateur lui-même, mais ce n'est au fond qu'une question de confort d'utilisation.
Nous nous intéresserons ici à comprendre comment le typage des chaînes de format fonctionne, et à redéfinir, dans le langage même, un mini-module Printf.
On considère la signature suivante:
module type PRINTF = sig
type ('a,'r) fmt
(** En pratique on va garantir que 'a = T1 -> ... -> Tn -> 'r
* où les Ti sont soit int soit string. *)
val fmt_i : (int -> 'r, 'r) fmt
val fmt_lit : string -> ('r,'r) fmt
val fmt_concat : ('a,'b) fmt -> ('b,'r) fmt -> ('a,'r) fmt
val print : ('a,unit) fmt -> 'a
end
On attend que fmt_i corresponde à la chaîne de formattage "%d"
qui permet d'afficher un entier passé en argument,
que fmt_lit s corresponde à la chaîne de formattage constante égale à
s qui permet d'afficher s,
et que fmt_concat corresponde à la concaténation de chaînes
de formattage.
Par exemple, print (fmt_concat (fmt_lit "20") fmt_i) 16 devra afficher
2016.
Implémentez un module satisfaisant la signature et la spécification précédentes.
Indice: utilisez un style par continuation.