How to algebraic effects

Transcript

2. How to algebraic effects 2/130
3. Me Nikita Shilnikov I write code in Ruby 3/130
4. What are algebraic effects? 4/130
5. 5/130
6. Category theory? 6/130
7. Algebraic effects12 2 2009, G.Plotkin, M.Pretnar 1 2003, G.Plotkin, J.Power 7/130
8. 2003 8/130
9. 2009 9/130
10. 1989–2020 10/130
11. Effects for the masses 11/130
12. 2018 — React Hooks 12/130
13. 2018 — React Hooks Brought to us by 1 person more or less* * Sebas(an Markbåge 13/130
14. Algebraic effects generalize all sorts of things —Dependency injec,on —Context passing —Excep,ons —Caching —Retry strategies —Non-determinism (A/B tes,ng, randomness) —Mul%threading —Scheduling (async/ await) —Generators —Timeouts —Configura%on —Locking 14/130
15. Be#er than DI 15/130
16. Be#er than async/await 16/130
17. Be#er than dozens of special-purposed libraries 17/130
18. Example: JavaScript —Async func*ons —Generator func*ons —Async generator func*ons (new feature!) —What's next? ☠ 18/130
19. Why? —It's proven to be working —Unified solu7on —Good for reasoning 19/130
20. Previously (RubyRussia 2019) How to use algebraic effects 20/130
21. Today How to implement algebraic effects 21/130
22. You can use this talk as a troubleshoo1ng guide 22/130
23. Spoiler alert ⚠ lots of code 23/130
24. Using algebraic effects is like riding a bike 24/130
25. But there are two parts Effects Handlers 25/130
26. Part 1 of 2 Effects (opera-ons) 26/130
27. Opera&on is an effect constructor 27/130
28. Opera&on is an effect constructor def greeting "Hello #"Get("Your name?")}!" end 28/130
29. Opera&on is an effect constructor def greeting "Hello #"Get("Your name?")}!" end It's just an addi,on to your code. 29/130
30. Opera&on is an effect constructor def greeting "Hello #" ! Get("Your name?")}!" end 30/130
31. Part 2 of 2 Effect handlers 31/130
32. Handler example (seman.cs) def run_greeting begin greeting when Get(what), resume then resume.("RubyRussia") return =" message message.center(21, "-") end end 32/130
33. def run_greeting begin greeting when Get(what), resume then resume.("RubyRussia") return =" message message.center(21, "-") end end 33/130
34. def run_greeting begin greeting when Get(what), resume then resume.("RubyRussia") return =" message message.center(21, "-") end end 34/130
35. def run_greeting begin greeting when Get(what), resume then resume.("RubyRussia") return =" message message.center(21, "-") end end 35/130
36. def run_greeting begin greeting when Get(what), resume then resume.("RubyRussia") return =" message message.center(21, "-") end end 36/130
37. def run_greeting begin greeting when Get(what), resume then resume.("RubyRussia") return =" message message.center(21, "-") end end 37/130
38. def run_greeting begin greeting when Get(what), resume then resume.("RubyRussia") return =" message message.center(21, "-") end end 38/130
39. def run_greeting begin greeting when Get(what), resume then resume.("RubyRussia") return =" message message.center(21, "-") end end 39/130
40. How it works 40/130
41. 41/130
42. 42/130
43. 43/130
44. 44/130
45. Handler def run_greeting begin greeting when Get(what), resume then resume.("RubyRussia") return =" message message.center(21, "-") end end Code def greeting name = ! Get("Your name?") "Hello #"name}!" end 45/130
46. Handler def run_greeting begin greeting when Get(what), resume then resume.("RubyRussia") return =" message message.center(21, "-") end end Code def greeting name = ! Get("Your name?") "Hello #"name}!" end 46/130
47. Handler def run_greeting begin greeting when Get(what), resume then resume.("RubyRussia") return =" message message.center(21, "-") end end Code def greeting name = ! Get("Your name?") "Hello #"name}!" end 47/130
48. Handler def run_greeting begin greeting when Get(what), resume then resume.("RubyRussia") return =" message message.center(21, "-") end end Code def greeting name = ! Get("Your name?") "Hello #"name}!" end 48/130
49. Handler def run_greeting begin greeting when Get(what), resume then resume.("RubyRussia") return =" message message.center(21, "-") end end Code def greeting name = ! Get("Your name?") "Hello #"name}!" end 49/130
50. Handler def run_greeting begin greeting when Get(what), resume then resume.("RubyRussia") return =" message message.center(21, "-") end end run_greeting # =" "-$Hello RubyRussia!-$" Code def greeting name = ! Get("Your name?") "Hello #"name}!" end 50/130
51. Let's make it real 51/130
52. return can be inlined def run_greeting begin message = greeting message.center(21, "-") when Get(what), resume then resume.("RubyRussia") end end def greeting name = ! Get("Your name?") "Hello #"name}!" end 52/130
53. How to jump back? def run_greeting begin message = greeting message.center(21, "-") when Get(what), resume then resume.("RubyRussia") end end def greeting name = ! Get("Your name?") "Hello #"name}!" end 53/130
54. Using blocks def run_greeting message = greeting do |effect| case effect in Get(what) "RubyRussia" end end message.center(21, "-") end def greeting name = yield Get("Your name?") "Hello #"name}!" end 54/130
55. Using blocks def run_greeting message = greeting do |effect| case effect in Get(what) "RubyRussia" end end message.center(21, "-") end def greeting name = yield Get("Your name?") "Hello #"name}!" end 55/130
56. Using blocks def run_greeting message = greeting do |effect| case effect in Get(what) "RubyRussia" end end message.center(21, "-") end def greeting name = yield Get("Your name?") "Hello #"name}!" end 56/130
57. Using global variables def run_greeting $handler = proc do |effect| case effect in Get(what) "RubyRussia" end end message = greeting message.center(21, "-") ensure $handler = nil end def greeting name = $handler.( Get("Your name?") ) "Hello #"name}!" end 57/130
58. Using global variables This is how React works /" ReactFiberHooks.new.js /# ..% *' /" The work-in-progress fiber. let currentlyRenderingFiber: Fiber = (null: any); /" Hooks are stored as a linked list on the fiber's memoizedState field. The /" current hook list is the list that belongs to the current fiber. The /" work-in-progress hook list is a new list that will be added to the /" work-in-progress fiber. let currentHook: Hook | null = null; let workInProgressHook: Hook | null = null; /# ..% *' 58/130
59. But you need to ensure def run_greeting $handler = proc do |effect| case effect in Get(what) "RubyRussia" end end message = greeting message.center(21, "-") ensure $handler = nil end 59/130
60. Global variables work for single-threaded environments main -" run_greeting -" greeting 60/130
61. Global variables work for single-threaded environments main -" run_greeting -" greeting 61/130
62. Global variables work for single-threaded environments main -" run_greeting #- greeting 62/130
63. Global variables work for single-threaded environments main -" run_greeting #- greeting Otherwise, it's not equivalent to the idea, seman5cally 63/130
64. Leveling up: fibers 64/130
65. Fiber: goto + extra features 65/130
66. Parent fiber def run_greeting fiber = Fiber.new do greeting end ..# end Child fiber def greeting .." end 66/130
67. 67/130
68. Fiber handler def run_greeting fiber = Fiber.new { greeting } message = case fiber.resume in Get(what) fiber.resume("RubyRussia") end message.center(21, "-") end def greeting name = Fiber.yield( Get("Your name?") ) "Hello #"name}!" end 68/130
69. Fiber handler def run_greeting fiber = Fiber.new { greeting } message = case fiber.resume in Get(what) fiber.resume("RubyRussia") end message.center(21, "-") end def greeting name = Fiber.yield( Get("Your name?") ) "Hello #"name}!" end 69/130
70. Fiber handler def run_greeting fiber = Fiber.new { greeting } message = case fiber.resume in Get(what) fiber.resume("RubyRussia") end message.center(21, "-") end def greeting name = Fiber.yield( Get("Your name?") ) "Hello #"name}!" end 70/130
71. Fiber handler def run_greeting fiber = Fiber.new { greeting } message = case fiber.resume in Get(what) fiber.resume("RubyRussia") end message.center(21, "-") end def greeting name = Fiber.yield( Get("Your name?") ) "Hello #"name}!" end 71/130
72. We need to loop 72/130
73. Looping def greeting fname = Fiber.yield("first name") lname = Fiber.yield("last name") "Hello ##fname} ##lname}!" end 73/130
74. Handling all effects def run_greeting fiber = Fiber.new { greeting } effect = fiber.resume loop do case effect in Get(what) effect = fiber.resume("RubyRussia") in message if !fiber.alive? break message.center(21, "-") end end end 74/130
75. Handling all effects def run_greeting fiber = Fiber.new { greeting } effect = fiber.resume loop do case effect in Get(what) effect = fiber.resume("RubyRussia") in message if !fiber.alive? break message.center(21, "-") end end end 75/130
76. Composability def greeting name = Fiber.yield(Get(:name)) year = Fiber.yield(Year()) "Hello #"name} #"year}!" end 76/130
77. Dispatching effects 77/130
78. Dispatching effects 78/130
79. Dispatching effects 79/130
80. Dispatching effects 80/130
81. Handler of Get loop do case effect in Get(what) effect = fiber.resume("RubyRussia") else if fiber.alive? effect = fiber.resume(Fiber.yield(effect)) else break effect end end end 81/130
82. Handler of Get loop do case effect in Get(what) effect = fiber.resume("RubyRussia") else if fiber.alive? effect = fiber.resume(Fiber.yield(effect)) else break effect end end end 82/130
83. Handler of Year loop do case effect in Year() effect = fiber.resume(2020) else if fiber.alive? effect = fiber.resume(Fiber.yield(effect)) else break effect end end end 83/130
84. Handler of Year loop do case effect in Year() effect = fiber.resume(2020) else if fiber.alive? effect = fiber.resume(Fiber.yield(effect)) else break effect end end end 84/130
85. Most effects can be handled by both fibers and global handlers —DI —Caching —Clock —Random —State —... 85/130
86. Global Get handler def handle_get handlers = (Thread.current[:handlers] |"= []) last_handler = handlers.last handlers <% proc do |effect| case effect in Get(what) # return result else last_handler.(effect) end end run_code ensure handlers.pop end 86/130
87. Fibers vs Global handlers 87/130
88. loop do case effect in Get(what) effect = fiber.resume("RubyRussia") else if fiber.alive? effect = fiber.resume(Fiber.yield(effect)) else break effect end end end 88/130
89. Scheduling fibers case effect in Await(rs) if rs.ready? fiber.resume(rs.result) else queue <# [:wait, rs, fiber] # resume another fiber end end 89/130
90. How it works def greeting name = Fiber.yield( Get("Your name?") ) "Hello #"name}!" end 90/130
91. Other ways: - delimited con4nua4ons - generators - call/cc, require 'continuation' ( ) 91/130
92. More effects with mul0-shot con0nua0ons 92/130
93. Mul$-shot con$nua$ons In full correspondence with the theory. Only with: - delimited con1nua1ons - call/cc Cons: - primi,ves don't exist in all languages - implementa,ons are not efficient - kinds of effects are really obscure: amb, backtracking 93/130
94. Global Fibers (one-shot con2nua2ons) Delimited con2nua2ons (mul2-shot con2nua2ons) State DI Locking Cache Random Context Timeouts Parallel processing ... Async/await Generators Retry (simple) ExcepEons Retry (full) amb Backtracking 94/130
95. Algebraic effects vs. real world 95/130
96. Handlers are stored on the stack. 96/130
97. Handlers are stored on the stack. Any stack manipula6on may break things badly. 97/130
98. Handlers are stored on the stack. Any stack manipula6on may break things badly. In most cases, workarounds are trivial (in Ruby). 98/130
99. Problem 1: missing handlers 99/130
100. Missing handlers —You forgot to add a handler —Stack was dropped 100/130
101. handle_year do Thread.new do Fiber.yield(Year()) end end 101/130
102. handle_year do Thread.new do # stack is reset Fiber.yield(Year()) end end 102/130
103. handle_year do Thread.new do Fiber.yield(Year()) end end 103/130
104. Solu%on: copy handler stack 104/130
105. Transferring handlers 105/130
106. Transferring handlers This is what React does when you call setState 106/130
107. Copying can be expensive but you may save some alloca4ons with immutable handlers 107/130
108. Missing handlers —You forgot to add a handler —Stack was dropped —Leaked effects 108/130
109. Leaked effects —Tricky indeed —Are not common for Ruby 109/130
110. def lazy_greeting -" { "Hello #$Get("name?")}" } end 110/130
111. def run_greeting greeting = handle_get { lazy_greeting } greeting.() end 111/130
112. def run_greeting greeting = handle_get { lazy_greeting } greeting.() ! end 112/130
113. Leaking effects may be a limita1on 113/130
114. Problem 2: interop 114/130
115. Interop —Thread-local variables are actually fiber-local in Ruby —Some libraries may be very opinionated (avoid) 115/130
116. Thread-local storage Thread.current[:value] = :foo Fiber.new { Thread.current[:value] }.resume # =" nil 116/130
117. Thread-local storage Solu%on: monkey patches :( 117/130
118. Problem 3: new kinds of bugs Frozen (me, caching, locking, etc 118/130
119. Problem 4: debugging 119/130
120. Debugging Call stacks may become messy (but it depends) 120/130
121. Debugging Some tools may be required (e.g. handlers stack inspec9on) 121/130
122. Problem 5: code requires handlers 122/130
123. Code requires handlers greeting ! 123/130
124. Problem 6: performance limita2ons? 124/130
125. Some final thoughts —Generalizing things helps a bunch —You can add new effects as you go —You can always be sure they will be compa:ble with each other —Tes:ng is a breeze (even for complex stuff) —Fewer bugs in general? —It's fun 125/130
126. Fibers/con+nua+ons become more available 126/130
127. Effect libraries will follow 127/130
128. Other languages? 128/130
129. At least in Ruby we have dry-effects ;) 129/130
130. Thank you —github.com/yallop/effects-bibliography —twi7er.com/NikitaShilnikov —dry-rb.org/gems/dry-effects —t.me/flash_gordon 130/130