Module: SyMath::Operation::Match

Includes:
SyMath::Operation
Included in:
Value
Defined in:
lib/symath/operation/match.rb

Instance Method Summary collapse

Methods included from SyMath::Operation

#iterate, #recurse

Instance Method Details

#build_assoc_op(args, opclass) ⇒ Object 



6
7
8
9
10
11
12
13
14
15
 
# File 'lib/symath/operation/match.rb', line 6

def build_assoc_op(args, opclass)
  e = args[-1]
  if args.length > 1
    args[0..-2].each do |a|
      e = opclass.new(a, e)
    end
  end

  return e
end

#match(exp, freevars, boundvars = {}) ⇒ Object

Match self with an expression and a set of free variables. A match is found if each of the free variables can be replaced with subexpressions making the expression equal to self. In that case, a hash is returned mapping each of the variables to the corresponding subexpression. If no match is found, nil is returned. An optional boundvars hash contains a map of variables to expressions which are required to match exactly.



104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
 
# File 'lib/symath/operation/match.rb', line 104

def match(exp, freevars, boundvars = {})
  # Mathify free variables
  freevars = freevars.map { |v| v.to_m }

  # Traverse self and exp in parallel. Match subexpressions recursively,
  # and match end nodes one by one. The two value nodes are compared for
  # equality and each argument are matched recursively.
  # Constant or operator: Just match nodes by exact comparison
  if exp.is_a?(SyMath::Definition) and
    !exp.is_a?(SyMath::Definition::Variable)
    # Node is a definition. Exact match is required
    if (self == exp)
      # Return match with no variable bindings
      return [{}]
    else
      return
    end
  end

  # Variable: If it is a free variable, it is a match. We remove it from
  # the freevars set and add it to the boundvars set together with the
  # expression it matches. If it is a bound variable, we require that
  # the expression matches the binding.
  if exp.is_a?(SyMath::Definition::Variable)
    # Node is a variable
    if freevars.include?(exp)
      # Node is a free variable. Return binding.
      return [{ exp => self }]
    elsif boundvars.key?(exp)
      # Node is a bound variable. Check that self matches the binding.
      if boundvars[exp] == self
        return [{}]
      else
        return
      end
    else
      # Node is an unknown variable. Exact match is required
      return (exp == self)? [{}] : nil
    end
  end

  # Operator. Compare class and name. Then compare each argument
  if exp.is_a?(SyMath::Operator)
    # Node is an operator. Check class and name.
    if self.class != exp.class or self.name != exp.name
      return
    end

    # The args_assoc method takes care of associativity by returning the
    # argument list of all directly connected arguments.
    self_args = self.args_assoc
    exp_args = exp.args_assoc
    ret = {}
    m = match_assoc(self_args, exp_args, freevars, boundvars, self.class)
    
    return if m.nil?

    return m.map { |r| boundvars.merge(r) }
  end

  # :nocov:
  # All value types should be covered at this point, but one never knows.
  raise 'Don\'t know how to compare value type ' + exp.class.to_s
  # :nocov:
end

#match_assoc(args1, args2, freevars, boundvars, opclass) ⇒ Object

Match the lists of arguments of two associative operators, binding the free variables in args2 to expressions in args1. Because of the associativity property, multiple matches may be possible. E.g.

x, y, z

[a, b] gives two possible matches: a = (x op y), b = z or

a = x, b = (y op z) A list of hashes is returned, each hash representing a match.



23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
 
# File 'lib/symath/operation/match.rb', line 23

def match_assoc(args1, args2, freevars, boundvars, opclass)
  # If args1 is shorter than args2 we do not have enough arguments for a
  # match
  return if args1.length < args2.length

  # If args2 has only one argument, it must match the whole list of args1
  if args2.length == 1
    return build_assoc_op(args1, opclass).match(
             args2[0], freevars, boundvars)
  end

  ret = []
  all = (0..args1.length - 1).to_a
  fv = freevars
  bv = boundvars

  (1..args1.length - args2.length + 1).each do |n|
    # Match args1[0..m] with args2[0]
    if is_commutative?
      # Select all combinations of n arguments
      sel = all.combination(n)
    else
      # Non-commutative operation. Make one selection of the
      # first n arguments
      sel = [(0..n - 1).to_a]
    end

    # Iterate over all selections and find all possible matches
    sel.each do |s|
      select1 = s.map { |i| args1[i] }
      remain1 = (all - s).map { |i| args1[i] }

      if n == 1
        m0 = select1[0].match(args2[0], freevars, boundvars)
      else
        if args2[0].is_a?(SyMath::Definition::Variable) and
          freevars.include?(args2[0])
          # Register match.
          m0 = [{ args2[0] => build_assoc_op(select1, opclass) }]
        else
          # No match. Skip to the next argument combination
          next
        end
      end

      # Set of matches is empty. Return negative
      next if m0.nil?

      # For each possible first argument match, we build new lists of free
      # and bound variables and try to match the rest of the remaining list
      # of the argument recursively.
      m0.each do |m|
        fv = freevars - m.keys
        bv = boundvars.merge(m)
        mn = match_assoc(remain1, args2[1..-1], fv, bv, opclass)
        if mn.nil?
          # No match. Skip to the next argument combination
          next
        else
          # We have a complete match. Store it in res, and continue
          m0.each do |m0i|
            mn.each do |mni|
              ret << m0i.merge(mni)
            end
          end
        end
      end
    end
  end

  return if ret.empty?
  
  return ret
end

#match_replace(exp, replace, freevars) ⇒ Object 



170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
 
# File 'lib/symath/operation/match.rb', line 170

def match_replace(exp, replace, freevars)
  # Recursively try to match exp to subexpressions of self. If a match
  # is found, replace it and return.

  # First try to match the top expression
  matches = match(exp, freevars)
  if !matches.nil? and matches.length >= 1
    # If there are more than one match, pick the first
    ret = replace.deep_clone
    ret.replace(matches[0])
    return ret
  end

  # No match at top level. Try to match sub expressions.
  if is_a?(SyMath::Operator)
    gotmatch = false

    args2 = @args

    args2.each_with_index do |a, i|
      matched = a.match_replace(exp, replace, freevars)
      if matched != a
        args[i] = matched
        ret = deep_clone
        ret.args[i] = matched
        return ret
      end
    end
  end

  # No match.
  return self
end