Programmation 2 : Modules

Etienne Lozes

Comment imiter les modules pour le type int ?

module CType = sig
  val inc : unit -> int
end

module C : CType = struct

  let c = ref 0
  let inc () = c:= 'a+1; !c
end

let createc () =
  let x = ref 0 in

  fun () -> (
  x := !x + 1; !x)

let inc1 = createc ()
let inc2 = createc ()

⟶ inc1 et inc2 ont leur propre compteur

• Similaire à ce qu’on fait avec des modules

• MAIS : marche bien pour des int, mais pas pour d’autres types

Multi-ensembles

type 'a multiset = ('a*int) list

Dans le .mli :

type 'a multiset

val empty : 'a multiset

val add : 'a -> 'a multiset -> 'a multiset

Puis : on compile le .mli puis le .ml

ocamlc multiset.mli
ocamlc multiset.ml

Foncteurs

module type SET

Ensemble : on le muni d’une fonction d’ordre, pour pouvoir faire une recherche dichotomique

---

Programmation fonctionnelle :

pour raisonner en termes de fonctionnalités

Programmation orientée objet :

pour raisonner en termes d’objets

Mixin Classes

Classe abstraite :

pas d’implémentation de méthodes, on ne peut pas l’instancier

Multiple dispatch

Surcharge des méthodes en fonction des types des arguments

⟶ implémenté de base dans Perl6 :

class Test {
  multi method identity(Int $x){
    return "$x is an integer";
  }
  multi method identity(Str $x){
    return qq<"$x" is a string.>;
  }
}
my Test $t .= new();
$t.identify(42);
$t.identify("weasel");

Dispatch partiel aussi possible !

class Test {
  multi method identity(Int $x ;; Str $text){
    ...
  }
  multi method identity(Str $x ;; Str $text){
    return qq<"$x" is a string.>;
  }
}

⟶ ;; Str $text pas utilisé pour déterminer dynamiquement quelle subroutine/méthode utiliser.

---

En OCamL : références pas polymorphes :

let id = ref (function x = x) in
  id:=succ;
  id "foo";;

⟶ Problème : ⟹ variables monomorphes (notées '_a) : instanciées définitivement dès la première utilisation.

Idem : Les références sont des objets qui ont

• un attribut : le contenu
• deux méthodes : lecture et écriture

⟶ donc si on permet d’avoir des objets ou références polymorphes, on ne peut plus assurer la conservation des types lors de la $𝛽$-réduction.

NB : on peut avoir des variables d’instances mutables mais privées

Ex:

Si un objet a la méthode polymorphe :

map : ∀𝛼, (𝛼->𝛽) -> 𝛼 list -> 𝛽 list

l’objet n’est pas lui-même polymorphe.

---

Attention :

< dépôt : float -> unit; ..> -> float -> < dépôt : float -> unit; ..>

n’est pas le même type que

(< dépôt : float -> unit; ..> as 'a) -> float -> 'a

---

\[S ⟶ T ≤ U ⟶ V \\ ⟺ \begin{cases} U ≤ S \text{ (contravariant)}\\ T ≤ V \text{ (covariant)}\\ \end{cases}\]

et

\[𝜇X.⟨m : X ⟶ unit; ..⟩ ≤ 𝜇Y.⟨m : Y ⟶ unit; ..⟩\]

ssi il y a égalité des types.

---

Si $X ≤ Y$ :

\[𝜇X.⟨m : X; n: int; ..⟩ ≤ 𝜇Y.⟨m : Y; ..⟩\]

DONC :

Si $X ≤ Y$ :

\[𝜇X.⟨m : X ⟶ unit; n: int; ..⟩ ≤ 𝜇Y.⟨m : Y ⟶ unit; ..⟩ ⟺ X ≥ Y ⟺ X = Y\]

---

\[E := [ ] \mid Ea \mid vE\] \[(𝜆x. e)((𝜆y.y)3) \\ E[] = (𝜆x.e)([]) \\ E[(𝜆y.y)3] ⟶ E[3]\]

$(𝜆y.y)3⟶3$
	$E[(𝜆y.y)3] ⟶ E[3]$

---

Continuations

E[callcc v] → E[v(λx.E[x])]

E[throw k v] → kv

1 + (callcc 𝜆k. k 3) = 1 + (1 + 3)

callcc (𝜆k. 1 + throw k 3) = 3

callcc (𝜆k'. 1 + (callcc 𝜆k. k' 3)) = 3

1 + callcc(𝜆k. 3) = 4

Monades

OCamL :

let bind f (gx,gs) = let fx, fs = f gx in (fx, gs^fs)

let return x  = (x, "")

En Haskell :

import Data.Complex

bind :: (Complex Float -> [Complex Float]) -> ([Complex Float] -> [Complex Float])

bind f l = concat (map f l)

return x = [x]

lift f = return . f

g :: c -> a
f :: a -> b

f' :: a -> StdGen -> (b, StdGen)
g' :: c -> StdGen -> (a, StdGen)

g'(x) :: StdGen -> (a, StdGen)

-- On veut pouvoir définir f'.g'

bind :: (a -> StdGen -> (b, StdGen)) -> (StdGen -> (a, StdGen)) -> (StdGen -> (b, StdGen))
bind f x seed = let (a', seed') = x seed in f a' seed'

return a seed = (a, seed)

lift f = return . f

---

empty = Semaphore(1)
maleSwitch = Lightswitch()
femaleSwitch = Lightswitch()
maleMultiplex = Semaphore(3)
femaleMultiplex = Semaphore(3)

femaleSwitch.lock(empty)
femaleMultiplex.wait()
# bathroom for women
femaleMultiplex.signal()
femaleSwitch.unlock(empty)


maleSwitch.lock(empty)
maleMultiplex.wait()
# bathroom for men
maleMultiplex.signal()
maleSwitch.unlock(empty)

⟹ Starvation possible :

Solution :

turnstile.wait()
femaleSwitch.lock(empty)
turnstile.signal()
femaleMultiplex.wait()
# bathroom for women
femaleMultiplex.signal()
femaleSwitch.unlock (empty)


turnstile.wait()
maleSwitch.lock(empty)
turnstile.signal()
maleMultiplex.wait()
# bathroom for men
maleMultiplex.signal()
maleSwitch.unlock (empty)