Share
Embed
Transcript
75 slides
-
self.inspect id: @joker1007 name: Tomohiro Hashidate Repro inc. CTO I
familiar with ... Ruby/Rails Ruby Black Magic (TracePoint) Speaker of RubyKaigi2018, RubyConf2018 -
We provide a web service as ... Analytics of Mobile
Apps, Web Apps. Marketing Automation. Of course, We're hiring!! -
RubyVM::AST.of can receive a Proc pr = proc { puts
:foo } ast = RubyVM::AbstractSyntaxTree.of(pr) pp ast (SCOPE@1:10-1:23 tbl: [] args: nil body: (FCALL@1:12-1:21 :puts (ARRAY@1:17-1:21 (LIT@1:17-1:21 :foo) nil))) -
TracePoint#enable can receive a Proc pr = proc do puts
:foo puts :bar end trace = TracePoint.new(:line) do |tp| p tp.lineno end trace.enable(target: pr) pr.call 2 foo 3 bar -
"Proc" is object of Procedure In other words, Function object.
pr = proc { puts :hello_proc } p pr #<Proc:0x00000000025fad50@/home/joker/slides/rubykaigi2019/proc.rb:1> -
"Proc" is closure. def counter x = 0 proc {
x += 1 } end c = counter counter.call # => 1 counter.call # => 2 Proc keeps the environment of the scope where it is created. -
Method can receive a "Proc" as block def with_retry(exception, &block)
block.call rescue exception retry end -
In fact, Ruby ... has function object as First-class object
can receive functions as return value can pass functions as method arguments In other words, Ruby has a factor of functional programming. -
Monad In functional programming, a monad is a design pattern[1]
that allows structuring programs generically while automating away boilerplate code needed by the program logic. Monads achieve this by providing their own data type, which represents a specific form of computation, along with one procedure to wrap values of any basic type within the monad (yielding a monadic value) and another to compose functions that output monadic values (called monadic functions). from Wikipedia https://en.wikipedia.org/wiki/Monad_(functional_programming). -
But, Monad is very simple and useful pattern actually. And
syntax sugar is very important for monad. -
I thinked. "I can implement true Monad syntax sugar by
Ruby black magics." -
Agenda Functor in Ruby Applicative Functor in Ruby Monad in
Ruby Syntax sugar for monad Implement monadic syntax in Ruby Examples, DEMO Today, I will not explain mathematics. I will talk about only the programming technique. ここまでで5 〜6 分ぐらいだと良いなあ -
Functor Functor ... is a container has a context for
specific purpose. is a object that can be mapped by any function. The most popular functor in Ruby is "Array". [1,2,3].map { |i| i.to_s } In Haskell, map for Functor is called fmap . -
Why is Functor useful Without functor and map, a container
needs to implement all methods for any object that it may contain. Functor makes a container enable to collaborate with any methods. -
Functor requires some laws functor.fmap(&:itself) == functor functor.fmap(&(proc_a >> proc_b))
== functor.fmap(&proc_a).fmap(&proc_b) These laws ensure that the behaviors of a functor are proper. -
Applicative Functor (1) If you want to process with more
than two functor objects, But fmap cannot handle more than two functors. [1,2,3].map do |i| [5,6,7].map do |j| i + j end end This sample outputs nested array. Of course, we can use flatten and flat_map . But we have a more functional approach. -
Applicative Functor (2) Applicative Functor can contain functions. And contained
functions apply other objects contained by each functor. array_plus = [:+.to_proc] array_plus.ap([2, 3], [4]) # => [6, 7] array_plus.ap([2, 3], [5, 6, 7]) # => [7, 8, 9, 8, 9, 10] array_plus.ap([2, 3], []) # => [] -
Applicative Functor (3) def ap(*targets) curried = ->(*extracted) do fmap
{ |pr| pr.call(*extracted) } end.curry(targets.size) applied = targets.inject(pure(curried)) do |pured, t| pured.flat_map do |pr| t.fmap { |v| pr.call(v) } end end applied.flat_map(&:itself) end -
Applicative also requires some laws But laws of Applicative Functor
are more complicated than ones of Functor. Sorry, I omit explaining details. -
What is difference between Applicative and Monad Applicative Functor cannot
express multiple dependent effects. For example, a calculation that may fail depends on whether previous calculations succeeded or failed. In such cases, Monad is useful. -
Monad Monad is a container like Functor and Applicative. In
Haskell, Monad requires some implementations. class Monad m where (>>=) :: m a -> (a -> m b) -> m b (>>) :: m a -> m b -> m b return :: a -> m a fail :: String -> m a Especially, (>>=) is most important. it is called "bind operator". -
What is >>= (bind operator) ? In the case of
Array, Array#bind receives a function that receives an item contained by the array and outputs new array. Example. ["foo","bar"].bind { |s| s.split(//) } # => ["f","o","o","b","a","r"] In fact, it's flat_map -
Monad in Scala Scala has a syntax sugar for monad.
for { x <- Some(10) y <- functionMaybeFailed() } yield x + y // Return Some(10 + y) or None Scala transforms this code to flat_map style internally. Like below. Some(10).flatMap { x => functionMaybeFailed().flatMap { y => x + y } } -
Syntax sugar for monad Some functional languages have syntax sugar
for monad. Haskell has do-syntax, Scala has for-syntax. Because the main purpose of monad is a chain of contextual computation, and syntax sugar is very effective to use it more easily. -
Nested flatMap is not readable Some(10).flatMap { x => functionA(x).flatMap
{ y => fuctionB.flatMap { z => z.process } } } The frequent appearance of flatMap is very noisy. { , } is the same. indent++. -
Scala is hybrid paradigm language Ruby is similar to Scala
in a sense I copied code transformation from Scala -
Monad syntax in Ruby https://github.com/joker1007/monar calc = ->(*val) do val.monadic_eval
do |x| a = x.odd? ? x : x / 2 y <<= [a + 14] z <<= [y, y + 1, y + 2] end end expect(calc.call(7, 8)).to \ eq([21, 22, 23, 18, 19, 20]) This code is valid syntax!! There is no warning. -
My idea is very simple. a <<= <statement> transform to
flat_map do |a| <statement> It's all. <<= is important discovery!! -
<<= is assignment with operator a <<= foo equals a
= a << foo This is valid ruby code. And Ruby treats a as assigned local variable! Moreover, most ruby programmers have not written such codes. In other words, I can change the behavior freely!! -
Review the code transformation [1,2,3].monadic_eval do |i| j <<= [i,
i*2] j.select(&:odd?) end transforms to [1,2,3].flat_map do |i| [i, i*2].flat_map do |j| j.select(&:odd?) end end -
It is difficult to resolve nested do-end by method chain.
OK, AST Transformation!! We already have RubyVM::AST.of . It is a new feature of Ruby-2.6 and very useful for handling AST. -
Breakdown of my implementation Extract AST from given block by
RubyVM::AST.of Detect a pattern like a <<= foo Extract fragments of source code Reconstruct source code Wrap into new proc (to cache reconstructed code) instance_eval new source code ここまでで20 分弱だと良いなあ -
Detect the pattern def __is_bind_statement?(node) (node.type == :DASGN || node.type
== :DASGN_CURR) && node.children[1].type == :CALL && node.children[1].children[1] == :<< end -
Extract fragments of codes # @param source [Array<String>] lines of
source code def extract_source(source, first_lineno, first_column, last_lineno, last_column) lines = source[(first_lineno - 1)..(last_lineno-1)] first_line = lines.shift last_line = lines.pop if last_line.nil? first_line[first_column..last_column] else first_line[first_column..-1] + lines.join + last_line[0..last_column] end end -
Reconstruct codes def __transform_node(source, buf, node, last_stmt: false) if __is_bind_statement?(node)
lvar = node.children[0] rhv = node.children[1].children[2] origin = Monad.extract_source( source, rhv.first_lineno, rhv.first_column, rhv.last_lineno, rhv.last_column).chomp buf[0].concat( "(#{origin}).flat_map do |#{lvar}|\n" ) buf[1] += 1 else buf[0].concat("(#{Monad.extract_source( source, node.first_lineno, node.first_column, node.last_lineno, node.last_column ).chomp})\n") end end -
Wrap into a new proc gen = "proc { |#{caller_local_variables.map(&:to_s).join(",")}|
begin; " + buf[0] + "rescue => ex; rescue_in_monad(ex); end; }\n" pr = instance_eval(gen, caller_location.path, caller_location.lineno) Monad.proc_cache["#{block_location[0]}:#{block_location[1]}"] = pr instance_eval outputs a proc object which contains transformed process. And I cached it to avoid source code transformation repeatedly. -
Handling local variables Reconstructing codes lose local variables, because the
environment contained by block is lost. Binding is required to handle local variables. -
That is when TracePoint is effective! I found a technique
to get Binding of a given block -
proc_binding = nil trace = TracePoint.new(:line) do |tp| # this
block is called Just before evaluating proc's first line proc_binding = tp.binding throw :escape end catch(:escape) do # In Ruby-2.6, TracePoint can limit tracking target. trace.enable(target: block) block.call ensure trace.disable end -
I got a Binding of Proc!! And Binding has everything
for black magic. -
ast = RubyVM::AbstractSyntaxTree.of(block); # SCOPE args_tbl = ast.children[0] args_node =
ast.children[1] caller_local_variables = proc_binding.local_variables - args_tbl gen = "proc { |#{caller_local_variables.map(&:to_s).join(",")}| ...." I got local_variables and copy into generated proc. -
At last, instance_exec generates proc with local variables of the
caller. instance_exec( *(caller_local_variables.map { |lvar| proc_binding.local_variable_get(lvar) }), &generated_pr ) -
Show powers of monad syntax by some examples. Maybe Either
Future State ParserCombinator ここまでで30 分ぐらい -
Maybe (Just) class Just include Monad include Monar::Maybe def initialize(value)
@value = value; end def flat_map(&pr) pr.call(@value); end def monad_class Monar::Maybe; end end -
Maybe (Nothing) class Nothing include Monad include Monar::Maybe def initialize(*value);
end def flat_map(&pr) self; end def monad_class Monar::Maybe; end end -
Maybe example key1 = "users/#{user.id}/posts/#{post.id}" key2 = "posts/#{post.id}/comments" # lookup_cache
returns Maybe lookup_cache(key1).monadic_eval do |cached_post| cached_comments <<= lookup_cache(key2) # If lookup_cache(key2) fails, # below processes are not executed post = Oj.load(cached_post) comments = Oj.load(cached_comments) post.comments = comments pure post end # return Just(post) or Nothing -
Either (Left) Left is the same as Nothing . But
Left has a exception. -
Either example either { Balance.find_by!(user: user_a) }.monadic_eval do |balance_a| _
<<= balance_a.ensure_amount!(amount) # return Either balance_b <<= either { Balance.find_by!(user: user_b) } TransferMoneyService.new(from: user_a, to: user_b, amount: amount) .process # return Either end # return Right(result) or Left(exception) Either hides error handling behind monad syntax. And it has a high affinity with pattern matching. Pattern matching is very hot topic. -
Future (extend concurrent-ruby) Concurrent::Promises::Future.include(Monad) class Concurrent::Promises::Future def flat_map(&pr) yield value!
rescue => ex if rejected? self else Concurrent::Promises.rejected_future(ex) end end end -
Future example Concurrent::Promises.make_future(5).monadic_eval do |x| a = x.odd? ? x
: x / 2 b = Concurrent::Promises.future { sleep 2; 11 } c = Concurrent::Promises.future { sleep 1; 3 } d <<= b # wait b e <<= c # wait c pure(a + d + e) end # Return Future(19) like async syntax of JavaScript. -
State (constructor) State has a proc that receives current state
and outputs value and next state. class State include Monad # @param next_state [Proc (s -> [a, s])] def initialize(next_state) raise ArgumentError.new("need to respond to :call") unless next_state.respond_to?(:call) @next_state = next_state end end -
State (flat_map) def flat_map(&pr0) self.class.new( proc do |s0| x, s1
= run_state(s0) new_state_monad = pr0.call(x) new_state_monad.next_state.call(s1) end ) end run_state(s0) -> [a, s2] -> block.call(a) -> new state monad -> run_state(s1) These processes are wrapped by the new State class. -
State (helper function) def get State.new(proc { |s| [s, s]
}) end def put(st) State.new(proc { |_| [nil, st] }) end -
State example state = State.pure(5).monadic_eval do |n| status <<= get
# Return initial state _ <<= if status != :saved result = n * 10 put(:saved) # Update state else pure(nil) end pure(result) end val, st = state.run_state(:not_saved) # val == 50, st == :saved val, st = state.run_state(:saved) # val == nil, st == :saved -
ParserCombinator Parser also contains a proc. that proc receives String
and returns [[Object, String]] . Object is a result of parsing. String is remained characters. flat_map expresses parser combination. | expresses selective parser. -
Parser#flat_map def flat_map(&pr) self.class.new( proc do |str0| result0 = run_parser(str0)
# return Array result0.flat_map do |output, remained| next_parser = pr.call(output) next_parser.run_parser(remained) end end ) end Below processes is wrapped by Proc . Get result -> given proc processes result -> Get New Parser -> parse remained chars. -
Parser#| def |(other) self.class.new( proc do |str| result0 = run_parser(str)
result0.empty? other.run_parser(str) : result0 end ) end -
Parser examples 1 def anychar new( proc do |string| string
== "" ? [] : [[string[0], string[1..-1]]] end ) end # @param cond [Proc (Char -> TrueClass | FalseClass)] def satisfy(cond) anychar.flat_map do |char| if cond.call(char) new(proc { |string| [[char, string]] }) else new(proc { |string| [] }) end end end -
Parser examples 2 def string(str) return pure "" if str
== "" c, tail = str[0], str[1..-1] char(c).monadic_eval do |c1| cs <<= self.class.string(tail) pure [c1, *cs].join end end -
Parser examples 3 def one_of(chars) satisfy(->(char) { chars.include?(char) }) end
def many(parser, level = 1) combined = parser | pure(nil) combined.monadic_eval do |result| result2 <<= if result.nil? pure(nil) else self.class.many(parser, level + 1) end pure([result, result2].compact.flatten(level)) end end -
Conclusion Monad is not difficult, It's flat_map The abstraction of
monad is very powerful Syntax is very important I want other representations for nested block By this implementation, I recognized the fun of monadic programming again. -
At last, I never recommend using this gem on production
now!! If you are interested in TracePoint and AST, Examples of the gem's code are helpful for you, maybe. And, let's enjoy darkness programming!!