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

Monads and Effects

Sponsored · Your Podcast. Everywhere. Effortlessly. Share. Educate. Inspire. Entertain. You do you. We'll handle the rest. →
myuon
May 26, 2019

Monads and Effects

myuon

May 26, 2019

Transcript

32 slides
  1. Table of Contents 1. Effect System in General • What’s

    the Effect? • Example: Memory-state effect 2. Koka • Effect in Koka • Syntax in Koka • Some details 3. Effect as Parametric Monad • Structures in Effects • Monads and Effects 3
  2. Table of Contents 1. Effect System in General • What’s

    the Effect? • Example: Memory-state effect 2. Koka • Effect in Koka • Syntax in Koka • Some details 3. Effect as Parametric Monad • Structures in Effects • Monads and Effects 4
  3. What’s the Effect? Γ M : A ! e •

    Γ: Context • M: Term • A: Type • e: effect Idea: “The type system estimates the effect of computation M to be (at most) e” 5
  4. What’s the Effect? (Observation) What effects are potentially caused during

    the execution? M1 , M2 : A × B let x = M in N : B λx. M : A → B (λx. M)N : B 6
  5. What’s the Effect? (Answer-1) Let (·) be an “accumulating” operator

    (or an effect product). Me1 1 , Me2 2 : A × B ! e1 · e2 let x = Me1 in Ne2 : B ! e1 · e2 Observation: effects can be stacked We will discuss the others later. 7
  6. Memory-state Effect Effect J ⊆ Addr means the computation contains

    I “memory” effect (at most). • readi () : nat ! {i} • n : nat writei (n) : 1 ! {i} Example let x = readi () in writej (x) : 1 ! {i, j} 8
  7. Existing Effect System • Koka • Eff • Frank •

    Multicore OCaml • and more. . . What are the effects of those languages? 9
  8. Table of Contents 1. Effect System in General • What’s

    the Effect? • Example: Memory-state effect 2. Koka • Effect in Koka • Syntax in Koka • Some details 3. Effect as Parametric Monad • Structures in Effects • Monads and Effects 10
  9. Koka Deveoped by Daan Leijen in Microsoft Research since 2012.

    Koka is a function-oriented programming language that seperates pure values from side-effecting computations, where the effect of every function is automatically inferred. 11
  10. Koka Base Effects Computation in Real-world are decomposed into effects:

    • exn: exception • div: divergence (infinite loop) • ndet: non-determinism (random value) • alloc(h), read(h), write(h): memory operation (h for some heap) In Koka, effect order does not matter. 12
  11. Koka Effect Aliases • total ≡ • pure ≡ exn,

    div • st(h) ≡ alloc(h), read(h), write(h) • io ≡ st(io), pure, ndet Example • print : string io − → 1 • error : ∀α. string exn − − → α • (:=) : ∀α. (ref(h, a), a) write(h) − − − − − → 1 13
  12. Koka Syntax* (kind) kinds: • ∗: type of values •

    e: effect rows • k: effect constraints • h: heap • _ → _: constructor 14
  13. Koka Syntax* (type) type: • α: type variable • ():

    unit type • _ e − → _: function type with effects • ref(h, ∗): reference 15
  14. Koka Effect Rows* “Row-polymorphic” effect: exn | µ Example) catch

    : ∀αµ. (1 exn|µ − − − − → α, exception µ − → α) µ − → α Figure 2: effect equivalence 16
  15. Koka ST Types (Alloc) Γ ref : τ st(h)|ε −

    − − − − → ref(h, τ) ! ε (Read) Γ (!) : ref(h, τ) st(h)|ε − − − − − → τ ! ε (Write) Γ (:=) : (ref(h, τ), τ) st(h)|ε − − − − − → 1 ! ε (Run) Γ e : τ ! st(h) | ε =⇒ Γ run(e) : τ ! ε 17
  16. Koka ST Types (Fib Example) function fib(n: int) { val

    x = ref(0); val y = ref(1); repeat(n) { val y0 = !y; y := !x + !y; x := y0; } !x } fib : int st(h) − − − → int ! ∅ 18
  17. Koka Effects** (Effect Duplication) Allows effect duplication: exn, exn ≡

    exn Thanks to effect equivalence and the effect duplication, Koka can solve the following equation. exn | µ ≡ exn =⇒ µ ≡ 19
  18. Table of Contents 1. Effect System in General • What’s

    the Effect? • Example: Memory-state effect 2. Koka • Effect in Koka • Syntax in Koka • Some details 3. Effect as Parametric Monad • Structures in Effects • Monads and Effects 20
  19. Laws in Effect System (Monad) Effect can be viewed as

    “Parametric” computation. =⇒ So does the laws? Monad laws: • (assoc) (let x = M in (let y = N in L)) ≡ (let y = (let x = M in N) in L • (left id) (let x = x in M) ≡ M • (right id) (let x = M in x) ≡ M 22
  20. Laws in Effect System** For (let x = x in

    Me) ≡ Me, we should assume: • Variable x has no effect, namely ∅ • Right-hand side, the effect is e • Left-hand side, the effect should be ∅ · e We should have left identity law of effect: ∅ · e = e 23
  21. Inevitable Over-estimation* Effect system estimates its effect of the computation.

    =⇒ Compiler can always estimate the correct effect? =⇒ The answer is “No” (if x = 0 then raise "error" else x) : nat ! {exn} Figure 5: (cast) 24
  22. Structure in Effects Let E be an effect set. •

    Have an unit ∅ ∈ E • Have a binary operator (·) : E × E → E • E, (·), ∅ is a monoid • Have a preorder (≤) ⊆ E × E • The (monoid/preorder) operators are compatible 25
  23. Memory-state Monad Monad T(−) means the computation contains some “memory”

    effect. (like IO in Haskell) We have memory operations: • readi () : Tnat • n : nat writei (n) : T1 26
  24. Memory-state Effects Structure Let Addr be a set of addresses.

    In this example, an effect set is P(Addr). • ∅: The emptyset • (·) = (∪): The union of sets • (≤) = (⊆): Set inclusion 27
  25. “Parametric” Memory-state (Semantics) Let Mem(J) be the memory state which

    the address set J might be modified from the initial state. TI (A) = ∀J ∈ P(Addr). Mem(J) → (Mem(I ∪ J) × A) Interpret Γ M : A ! e as M : Γ → Te (A) • readi : 1 → T{i}nat • writei : nat → T{i} 1 28
  26. Further topics • Semantics • Graded Monad (for the formal

    semantics) • Recursion • Algebraic Effects and Effect Handlers • Effect Inference • Polymorphic Effect 29
  27. Recursive Effects** map : (A e − → B) →

    (List(A) ??? − → List(B)) Simple idea Introduce (possibly many-times) multiplied effect, e†. Then, how do we give the semantics of the fixpoint? mfix : (A e − → A) e† − → A 31
  28. References • Daan Leijen. 2016. “Koka: Programming with Row-polymorphic Effect

    Types” • Shin-ya Katsumata. 2014. “Parametric effect monads and semantics of effect systems” • Andrej Bauer and Matija Pretnar. 2012. “Programming with Algebraic Effects and Handlers” • Sam Lindley, Conor McBride, Craig McLaughlin. 2016. “Do Be Do Be Do” 32

More Decks by myuon

Other Decks in Technology