Share
Embed
Monads and Effects
myuon
May 26, 2019
Transcript
32 slides
-
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 -
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 -
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 -
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 -
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 -
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 -
Existing Effect System • Koka • Eff • Frank •
Multicore OCaml • and more. . . What are the effects of those languages? 9 -
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 -
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 -
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 -
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 -
Koka Syntax* (kind) kinds: • ∗: type of values •
e: effect rows • k: effect constraints • h: heap • _ → _: constructor 14 -
Koka Syntax* (type) type: • α: type variable • ():
unit type • _ e − → _: function type with effects • ref(h, ∗): reference 15 -
Koka Effect Rows* “Row-polymorphic” effect: exn | µ Example) catch
: ∀αµ. (1 exn|µ − − − − → α, exception µ − → α) µ − → α Figure 2: effect equivalence 16 -
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 -
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 -
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 -
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 -
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 -
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 -
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 -
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 -
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 -
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 -
“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 -
Further topics • Semantics • Graded Monad (for the formal
semantics) • Recursion • Algebraic Effects and Effect Handlers • Effect Inference • Polymorphic Effect 29 -
Recursion** map : (A e − → B) → (List(A)
??? − → List(B)) 30 -
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 -
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