Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Type for leak detection in a session-oriented f...

Type for leak detection in a session-oriented functional programming language

Type for leak detection in a session-oriented functional programming language
--
The talk I gave for the dissertation of my bachelor degree.

Andrea Tosatto

October 19, 2012
Tweet

More Decks by Andrea Tosatto

Other Decks in Research

Transcript

  1. Types for leak detection in a session-oriented functional programming language

    Candidato: Andrea Tosatto Relatore: Corelatore: Dott. Luca Padovani Prof. Viviana Bono Tesi di Laurea Triennale in Informatica Types for leak detection in a session-oriented functional programming language Andrea Tosatto 1 / 12
  2. Sing# : Copyless message passing E1 E2 msg queue Exchange

    heap (µ) Threads Types for leak detection in a session-oriented functional programming language Andrea Tosatto 2 / 12
  3. Sing# : Copyless message passing E1 E2 msg queue Exchange

    heap (µ) Threads Types for leak detection in a session-oriented functional programming language Andrea Tosatto 2 / 12
  4. Sing# : Copyless message passing E1 E2 msg queue Exchange

    heap (µ) Threads Types for leak detection in a session-oriented functional programming language Andrea Tosatto 2 / 12
  5. A dangerous communication model let (a, b) = open ()

    in close (send a b) Types for leak detection in a session-oriented functional programming language Andrea Tosatto 3 / 12
  6. A dangerous communication model let (a, b) = open ()

    in close (send a b) E Types for leak detection in a session-oriented functional programming language Andrea Tosatto 3 / 12
  7. A dangerous communication model let (a, b) = open ()

    in close (send a b) a b E Types for leak detection in a session-oriented functional programming language Andrea Tosatto 3 / 12
  8. A dangerous communication model let (a, b) = open ()

    in close (send a b) a E b Types for leak detection in a session-oriented functional programming language Andrea Tosatto 3 / 12
  9. A dangerous communication model let (a, b) = open ()

    in close (send a b) E b Types for leak detection in a session-oriented functional programming language Andrea Tosatto 3 / 12
  10. Endpoint Types ?Bool.end !Bool.?Bool.end ?T.end Types for leak detection in

    a session-oriented functional programming language Andrea Tosatto 4 / 12
  11. Types Type t ::= Bool | Unit | t →

    t | t t | t ⊗ t | T Endpoint Type T ::= end (termination) | !t.T (input) | ?t.T (output) | α (type variable) | rec α.T (recursive type) Types for leak detection in a session-oriented functional programming language Andrea Tosatto 5 / 12
  12. Looking at types for detecting leaks let (a, b) =

    open () in close (send a b) t ::= Bool | Unit | t → t | t t | t ⊗ t | T T ::= end | !t.T | ?t.T | α | rec α.T Types for leak detection in a session-oriented functional programming language Andrea Tosatto 6 / 12
  13. Looking at types for detecting leaks let (a, b) =

    open () in close (send a b) T = !S.end t ::= Bool | Unit | t → t | t t | t ⊗ t | T T ::= end | !t.T | ?t.T | α | rec α.T Types for leak detection in a session-oriented functional programming language Andrea Tosatto 6 / 12
  14. Looking at types for detecting leaks let (a, b) =

    open () in close (send a b) T = !S.end S = ?S.end t ::= Bool | Unit | t → t | t t | t ⊗ t | T T ::= end | !t.T | ?t.T | α | rec α.T Types for leak detection in a session-oriented functional programming language Andrea Tosatto 6 / 12
  15. A problematic example let (a, b) = open () in

    close (send a (g b)) Types for leak detection in a session-oriented functional programming language Andrea Tosatto 7 / 12
  16. A problematic example let (a, b) = open () in

    close (send a (g b)) E Types for leak detection in a session-oriented functional programming language Andrea Tosatto 7 / 12
  17. A problematic example let (a, b) = open () in

    close (send a (g b)) a b E Types for leak detection in a session-oriented functional programming language Andrea Tosatto 7 / 12
  18. A problematic example let (a, b) = open () in

    close (send a (g b)) g b a E Types for leak detection in a session-oriented functional programming language Andrea Tosatto 7 / 12
  19. A problematic example let (a, b) = open () in

    close (send a (g b)) g b E Types for leak detection in a session-oriented functional programming language Andrea Tosatto 7 / 12
  20. A problematic example let (a, b) = open () in

    close (send a (g b)) g b E Types for leak detection in a session-oriented functional programming language Andrea Tosatto 7 / 12
  21. A problematic example let (a, b) = open () in

    close (send a (g b)) Unit Unit g b E Types for leak detection in a session-oriented functional programming language Andrea Tosatto 7 / 12
  22. A problematic example let (a, b) = open () in

    close (send a (g b)) Unit Unit g = λx.λy.(fix(λf .λz.f z)x) g b E Types for leak detection in a session-oriented functional programming language Andrea Tosatto 7 / 12
  23. Type weight (1) • t = “maximum length of chains

    of pointers starting from object of type t” • only pointers whose type has finite weight can be sent T = ?Bool.end T = 1 T = ?T.end T = ∞ t = s1 s2 t = ? Types for leak detection in a session-oriented functional programming language Andrea Tosatto 8 / 12
  24. Type weight (1) • t = “maximum length of chains

    of pointers starting from object of type t” • only pointers whose type has finite weight can be sent T = ?Bool.end T = 1 T = ?T.end T = ∞ t = s1 s2 t = ? Types for leak detection in a session-oriented functional programming language Andrea Tosatto 8 / 12
  25. Type weight (1) • t = “maximum length of chains

    of pointers starting from object of type t” • only pointers whose type has finite weight can be sent T = ?Bool.end T = 1 T = ?T.end T = ∞ t = s1 s2 t = ? Types for leak detection in a session-oriented functional programming language Andrea Tosatto 8 / 12
  26. Type weight (1) • t = “maximum length of chains

    of pointers starting from object of type t” • only pointers whose type has finite weight can be sent T = ?Bool.end T = 1 T = ?T.end T = ∞ t = s1 s2 t = ? Types for leak detection in a session-oriented functional programming language Andrea Tosatto 8 / 12
  27. Type weight (1) • t = “maximum length of chains

    of pointers starting from object of type t” • only pointers whose type has finite weight can be sent T = ?Bool.end T = 1 T = ?T.end T = ∞ t = s1 w s2 t = w Types for leak detection in a session-oriented functional programming language Andrea Tosatto 8 / 12
  28. Type weight (2) (T-AbsW) Γ, x : t E :

    s ∀u ∈ dom(Γ) Γ(u) ≤ w Γ λx.E : t w s Types for leak detection in a session-oriented functional programming language Andrea Tosatto 9 / 12
  29. Type weight (2) (T-AbsW) Γ, x : t E :

    s ∀u ∈ dom(Γ) Γ(u) ≤ w Γ λx.E : t w s Types for leak detection in a session-oriented functional programming language Andrea Tosatto 9 / 12
  30. Type weight (3) let (a, b) = open () in

    close (send a (g b)) Types for leak detection in a session-oriented functional programming language Andrea Tosatto 10 / 12
  31. Type weight (3) let (a, b) = open () in

    close (send a (g b)) Unit ∞ Unit Types for leak detection in a session-oriented functional programming language Andrea Tosatto 10 / 12
  32. Type weight (3) let (a, b) = open () in

    close (send a (g b)) Unit ∞ Unit (T-Send) Γ1 E1 : !t.T Γ2 E2 : t t < ∞ Γ1 + Γ2 send E1 E2 : T Types for leak detection in a session-oriented functional programming language Andrea Tosatto 10 / 12
  33. Conclusions We have deployed a type system to prevent memory

    leaks... . . . BUT. . . Does it really work?! Theorem (Soundness) If E is well typed, then E is leak free. Possible extensions • Subtyping... Types for leak detection in a session-oriented functional programming language Andrea Tosatto 11 / 12
  34. Conclusions We have deployed a type system to prevent memory

    leaks... . . . BUT. . . Does it really work?! Theorem (Soundness) If E is well typed, then E is leak free. Possible extensions • Subtyping... Types for leak detection in a session-oriented functional programming language Andrea Tosatto 11 / 12
  35. Conclusions We have deployed a type system to prevent memory

    leaks... . . . BUT. . . Does it really work?! Theorem (Soundness) If E is well typed, then E is leak free. Possible extensions • Subtyping... Types for leak detection in a session-oriented functional programming language Andrea Tosatto 11 / 12
  36. Conclusions We have deployed a type system to prevent memory

    leaks... . . . BUT. . . Does it really work?! Theorem (Soundness) If E is well typed, then E is leak free. Possible extensions • Subtyping... Types for leak detection in a session-oriented functional programming language Andrea Tosatto 11 / 12
  37. The End Grazie dell’attenzione! Types for leak detection in a

    session-oriented functional programming language Andrea Tosatto 12 / 12