Codage des objets en programmation fonctionnelle
Le codage est fait en OCaml (utiliser l’option -rectypes).
On se donne les types primitifs int et string pour avoir des exemples plus parlants.
Codage des listes
Point fixe de Turing
let zed = fun z -> fun x -> x (fun _ -> ((z z) x));;
let t x = (zed zed) x;;
Exemple somme des entiers
let h_som = fun f -> (fun n -> if n=0 then 0 else n + (f ()) (pred n));;
let sum n = t h_som n;;
assert (15 = sum 5);;
Constructeurs de listes
let nil = fun fe fht -> fe
;;
let cons h t = fun fe fht -> fht h t
;;
La liste 1;2;3 comme exemple
let l1 x y = cons 1 (cons 2 (cons 3 nil)) x y;;
La liste 4;5;6 comme exemple
let l2 x y = cons 4 (cons 5 (cons 6 nil)) x y;;
Longueur d’une liste
let h_length = fun f -> (fun l -> l 0 (fun h tl -> 1 + (f ()) tl));;
let length l = t h_length l;;
assert (0 = length nil);;
assert (3 = length l1);;
Somme des éléments d’une liste d’entiers
let h_sumlist = fun f -> (fun l -> l 0 (fun h tl -> h + (f ()) tl));;
let sumlist l = t h_sumlist l;;
assert (0 = sumlist nil);;
assert (6 = sumlist l1);;
Un petit fold left
let h_fold_l = fun fold -> (fun f acc l -> l acc (fun h tl -> fold () f (f acc h) tl));;
let fold_left f acc l = t h_fold_l f acc l;;
La longueur codée par un fold
assert (3 = fold_left (fun acc e -> acc + 1) 0 l1);;
La somme codée par un fold
assert (15 = fold_left (fun acc e -> acc + e) 0 l2);;
Concaténation de listes
let h_concat = fun f -> (fun l1 l2 -> l1 l2 (fun h tl -> cons h (f () tl l2)));;
let concat l1 l2 = t h_concat l1 l2;;
(* et un petit test *)
assert (21 = sumlist (concat l1 l2));;
Codage des objets
Un objet est une liste de champs et de méthodes. Pour accéder à un champ / une méthode, on accède au bon élément dans la liste.
On prendra comme exemple des classes Python et on montrera comment les traduire en utilisant uniquement des fonctions et les opérations sur les types primitifs.
Une classe avec deux méthodes
L’objet fonctionne comme un record avec des méthodes dans les champs.
Pour le moment, on ne voit pas trop à quoi sert le self passé en argument de la méthode.
class A:
def m_1(self):
return "Je suis A"
def m_2(self, x):
return "Bonjour " + x
a = A()
assert (a.m_1() == "Je suis A")
assert (a.m_2("Toto") == "Bonjour Toto")
Le codage en OCaml
(* Le code de m_1 *)
let f_1_A self = "Je suis A"
(* Le code de m_2 *)
let f_2_A self x = "Bonjour " ^ x
(* un objet de classe A est une liste [ f_1_A; f_2_A ] *)
(* le constructeur prend x et y car la liste est codée avec des fonctions *)
let class_A x y = cons f_1_A (cons f_2_A nil) x y
(* Appeler m_1 consiste à appeler la fonction qui est le premier élément de la liste.
On peut remarquer qu'on passe l'objet en argument au code de m_1 *)
let dot_m_1 o = o "erreur" (fun m1 _ -> m1 o)
(* Appeler m_1 consiste à appeler la fonction qui est le deuxième élément de la liste. *)
let dot_m_2 o x = o "erreur" (fun _ tl -> tl "erreur" (fun m2 _ -> m2 o x))
(* Tests *)
let a x y = class_A x y;;
assert (dot_m_1 a = "Je suis A");;
assert (dot_m_2 a "Toto" = "Bonjour Toto")
Une classe avec un champ utilisé dans une méthode
On utilise maintenant un champ dans une des méthodes. On voit que self est une version explicite du this de JS et Java.
class B:
def m_1(self):
return "Je suis " + self.nom_3
def m_2(self, x):
return "Bonjour " + x
def __init__(self, nom):
self.nom_3 = nom
b = B("Titi")
assert (b.m_1() == "Je suis Titi")
assert (b.m_2("Toto") == "Bonjour Toto")
assert (b.nom_3 == "Titi")
Codage en OCaml. On réutilise les fonctions dot_m_1 et dot_m_2 par les
méthodes m_1 et m_2 ont la même position dans la liste d’une instance de B
que dans la liste d’une instance de A.
(* Accès au champ nom en 3eme position dans la liste.
Comme c'est un champ on ne lui passe pas d'argument. *)
let dot_nom_3 o = o "erreur" (fun _ tl -> tl "erreur" (fun _ tl2 -> tl2 "erreur" (fun nom3 _ -> nom3)))
(* code de m_1 *)
let f_1_B self = "Je suis " ^ dot_nom_3 self
(* code de m_2 *)
let f_2_B self x = "Bonjour " ^ x
(* Le constructeur prend maintenant le nom en argument *)
let class_B nom x y =
cons f_1_B (cons f_2_B (cons nom nil)) x y
(* Tests *)
let b x y = class_B "Titi" x y;;
assert (dot_m_1 b = "Je suis Titi");;
assert (dot_m_2 b "Toto" = "Bonjour Toto");;
assert (dot_nom_3 b = "Titi")
Une classe qui appelle une méthode depuis une autre
On appelle maintenant la méthode m_1 depuis le code de m_2. On peut avoir
l’intuition que faire l’appel de m_1 sur self permet de garder le champ
nom_3, mais on imagine pouvoir faire la même chose sans mettre les méthodes
dans champs (i.e. pour le moment un struct avec un champ nom_3 suffirait).
class C:
def m_1(self):
return "Je suis " + self.nom_3 + "."
def m_2(self, x):
return "Bonjour " + x + ". " + self.m_1()
def __init__(self, nom):
self.nom_3 = nom
c = C("Titi")
assert (c.m_1() == "Je suis Titi.")
assert (c.m_2("Toto") == "Bonjour Toto. Je suis Titi.")
assert (c.nom_3 == "Titi")
Codage en OCaml
(* Code de m_1 *)
let f_1_C self = "Je suis " ^ dot_nom_3 self ^ "."
(* Code de m_2 *)
let f_2_C self x =
"Bonjour " ^ x ^ ". " ^
dot_m_1 self (* Ici on appelle m_1 presque comme en Python *)
(* Le constructeur est similaire à ce qu'on a fait pour B *)
let class_C nom x y =
cons f_1_C (cons f_2_C (cons nom nil)) x y
(* Tests *)
let c x y = class_C "Titi" x y;;
assert (dot_m_1 c = "Je suis Titi.");;
assert (dot_m_2 c "Toto" = "Bonjour Toto. Je suis Titi.");;
assert (dot_nom_3 c = "Titi")
Appels récursifs
On a rien à changer au codage pour faire des appels récursifs.
class C2:
def m_1(self, x, n):
if n <= 1:
return x
else:
return x + ", " + self.m_1(x, n-1)
c2 = C2()
assert (c2.m_1("bla", 3) == "bla, bla, bla")
Codage en OCaml
(* Appel récursif *)
let f_1_C2 self x n =
if n <= 1
then x
else x ^ ", " ^ dot_m_1 self x (n-1)
(* dot_m_1 est un appel récursif si f_1_C2 est le code de m_1 *)
(* Constructeur similaires à ce qu'on a déjà fait *)
let class_C2 x y = cons f_1_C2 nil x y;;
(* Test *)
let c2 x y = class_C2 x y ;;
assert (dot_m_1 c2 "bla" 3 = "bla, bla, bla")
On peut remarquer des similarités entre le code de l’opérateur de point fixe de Turing et le code de dot_m_1:
let zed = fun z -> fun x -> x (fun _ -> ((z z) x));;
let t x = (zed zed) x;;
let dot_m_1 o = o "erreur" (fun m1 _ -> m1 o);;
En particulier:
- Dans
zed,xest appelé avec un argument qui dépend dexet c’est aussi le cas pourodansdot_m_1. - Les fonctions récursives et les méthodes attendent en argument quelque chose (fonction ou “objet”) qui permet de faire l’appel récursif.
Liaison retardée
Liaison retardée: dans le code de m_2, on appelle m_1 et c’est bien la
méthode m_1 de D qui est utilisée. Dans le code de m_2 c’est le self qui
permet d’aller chercher la bonne implémentation de m_1.
class D(C):
def m_1(self):
return "Je suis " + self.nom_3 + " mais dans D."
def __init__(self, nom):
super().__init__(nom)
d = D("Titi")
assert (d.m_1() == "Je suis Titi mais dans D.")
assert (d.m_2("Toto") == "Bonjour Toto. Je suis Titi mais dans D.")
assert (d.nom_3 == "Titi")
Codage en OCaml
(* Code de m_1 *)
let f_1_D self = "Je suis " ^ dot_nom_3 self ^ " mais dans D."
(* On ne donne pas de code pour m_2 car on va hériter la méthode de C. *)
(* Cette fonction code l'héritage: elle change la méthode m_1 d'un objet.
Techniquement, on remplace le premier élément de la liste. *)
let remplace_m_1 f o x y =
cons f
(o (fun _ -> failwith "objet sans m_1") (fun _ tl -> tl))
x y
(* Le constructeur de D commence par appeler le constructeur de C puis remplace
le code de m_1 par f_1_D.
Ici le code de m_2 reste donc inchangé. *)
let class_D nom x y = remplace_m_1 f_1_D (class_C nom) x y
(* Tests *)
let d x y = class_D "Titi" x y;;
assert (dot_m_1 d = "Je suis Titi mais dans D.");;
assert (dot_m_2 d "Toto" = "Bonjour Toto. Je suis Titi mais dans D.");;
assert (dot_nom_3 d = "Titi")
