Vcsn  2.3
Be Rational
derivation.hh
Go to the documentation of this file.
1 #pragma once
2 
4 #include <vcsn/algos/split.hh>
6 #include <vcsn/ctx/fwd.hh>
7 #include <vcsn/dyn/value.hh>
8 #include <vcsn/dyn/value.hh>
9 #include <vcsn/misc/raise.hh>
11 
12 namespace vcsn
13 {
14 
15  /*--------------------------.
16  | derivation(expression). |
17  `--------------------------*/
18 
19  template <typename ExpSet>
20  rat::expression_polynomial_t<ExpSet>
21  derivation(const ExpSet& rs,
22  const typename ExpSet::value_t& e,
23  label_t_of<ExpSet> a,
24  bool breaking = false);
25 
26  namespace rat
27  {
31  template <typename ExpSet>
33  : public ExpSet::const_visitor
34  {
35  public:
36  using expressionset_t = ExpSet;
37  using super_t = typename expressionset_t::const_visitor;
39 
43  using expression_t = typename expressionset_t::value_t;
45  using weight_t = typename weightset_t::value_t;
46 
49 
50  using node_t = typename super_t::node_t;
51 
52  constexpr static const char* me() { return "derivation"; }
53 
55  : rs_(rs)
56  {}
57 
60  {
61  try
62  {
63  variable_ = var;
64  v->accept(*this);
65  return std::move(res_);
66  }
67  catch (const std::runtime_error& e)
68  {
69  raise(e,
70  " while computing derivative of: ", to_string(rs_, v), "\n"
71  " with respect to: ",
72  to_string(*rs_.labelset(), var));
73  }
74  }
75 
76  private:
81 
83  {
84  res_ = ps_.zero();
85  }
86 
88  {
89  res_ = ps_.zero();
90  }
91 
93  {
94  if (e.value() == variable_)
95  res_ = ps_.one();
96  else
97  res_ = ps_.zero();
98  }
99 
101  {
102  polynomial_t res = ps_.zero();
103  for (const auto& v: e)
104  {
105  v->accept(*this);
106  ps_.add_here(res, res_);
107  }
108  res_ = std::move(res);
109  }
110 
112  {
113  // We generate a sum.
114  auto res = ps_.zero();
115  // Accumulate the product of the constant terms of the
116  // previous factors.
117  weight_t constant = ws_.one();
118  for (unsigned i = 0, n = e.size(); i < n; ++i)
119  {
120  const auto& v = e[i];
121  v->accept(*this);
122  // See to-expansion.hh, case of mul, for an explanation
123  // of the following line.
124  res_
125  = ps_.rmul_label(res_,
126  prod_(std::next(e.begin(), i+1), std::end(e)));
127  ps_.add_here(res, ps_.lweight(constant, res_));
128  constant = ws_.mul(constant, constant_term(rs_, v));
129  if (ws_.is_zero(constant))
130  break;
131  }
132  res_ = std::move(res);
133  }
134 
140  prod_(typename mul_t::iterator begin,
141  typename mul_t::iterator end) const
142  {
143  using expressions_t = typename mul_t::values_t;
144  if (begin == end)
145  return rs_.one();
146  else if (std::next(begin, 1) == end)
147  return *begin;
148  else
149  return std::make_shared<mul_t>(expressions_t{begin, end});
150  }
151 
152 
154  {
155  // The first polynomial.
156  e.head()->accept(*this);
157  auto res = res_;
158  for (unsigned i = 1, n = e.size(); i < n; ++i)
159  {
160  const auto& v = e[i];
161  v->accept(*this);
162  res = ps_.conjunction(res, res_);
163  }
164  res_ = std::move(res);
165  }
166 
168  {
169  polynomial_t res = ps_.zero();
170  for (unsigned i = 0; i < e.size(); ++i)
171  {
172  e[i]->accept(*this);
173  for (const auto& m: res_)
174  {
175  typename node_t::values_t expressions;
176  for (unsigned j = 0; j < e.size(); ++j)
177  if (i == j)
178  expressions.emplace_back(label_of(m));
179  else
180  expressions.emplace_back(e[j]);
181  // FIXME: we need better n-ary constructors.
182  ps_.add_here(res,
183  std::make_shared<shuffle_t>(expressions),
184  weight_of(m));
185  }
186  }
187  res_ = std::move(res);
188  }
189 
191  {
192  e.sub()->accept(*this);
193  res_ = ps_.complement(res_);
194  }
195 
197  {
198  e.sub()->accept(*this);
199  // We need a copy of e, but without its weights.
200  res_ = ps_.lweight(ws_.star(constant_term(rs_, e.sub())),
201  ps_.rmul_label(res_, e.shared_from_this()));
202  }
203 
205  {
206  e.sub()->accept(*this);
207  res_ = ps_.lweight(e.weight(), res_);
208  }
209 
211  {
212  e.sub()->accept(*this);
213  res_ = ps_.rweight(res_, e.weight());
214  }
215 
216  /*---------.
217  | tuple. |
218  `---------*/
219 
220  using tuple_t = typename super_t::tuple_t;
221  template <bool = context_t::is_lat,
222  typename Dummy = void>
223  struct visit_tuple
224  {
226  template <size_t... I>
228  {
229  return
230  visitor_
231  .ps_
232  .tuple(vcsn::derivation(detail::project<I>(visitor_.rs_),
233  std::get<I>(v.sub()),
234  std::get<I>(visitor_.variable_))...);
235  }
236 
239  {
241  }
242 
243  const self_t& visitor_;
244  };
245 
246  template <typename Dummy>
247  struct visit_tuple<false, Dummy>
248  {
250  {
252  }
253  const self_t& visitor_;
254  };
255 
256  void visit(const tuple_t& v, std::true_type) override
257  {
258  res_ = visit_tuple<>{*this}(v);
259  }
260 
261  private:
264  weightset_t ws_ = *rs_.weightset();
270  };
271 
272  } // rat::
273 
275  template <typename ExpSet>
277  derivation(const ExpSet& rs,
278  const typename ExpSet::value_t& e,
280  bool breaking)
281  {
282  static_assert(ExpSet::context_t::labelset_t::is_free(),
283  "derivation: requires free labelset");
285  auto res = derivation(e, a);
286  if (breaking)
287  res = split(rs, res);
288  return res;
289  }
290 
291 
293  template <typename ExpSet>
294  rat::expression_polynomial_t<ExpSet>
295  derivation(const ExpSet& rs,
298  bool breaking = false)
299  {
301  using polynomial_t = rat::expression_polynomial_t<ExpSet>;
302  auto res = polynomial_t{};
303  for (const auto& m: p)
304  res = ps.add(res,
305  ps.lweight(weight_of(m),
306  derivation(rs, label_of(m), a, breaking)));
307  return res;
308  }
309 
310 
319  template <typename ExpSet,
320  typename = std::enable_if_t<!std::is_same<word_t_of<ExpSet>,
321  label_t_of<ExpSet>>{}>>
322  rat::expression_polynomial_t<ExpSet>
323  derivation(const ExpSet& rs,
324  const typename ExpSet::value_t& e,
325  const word_t_of<ExpSet>& l,
326  bool breaking = false)
327  {
328  auto word = rs.labelset()->letters_of(l);
329  auto i = std::begin(word);
330  auto end = std::end(word);
331  require(i != end, "derivation: word cannot be empty");
332  auto res = derivation(rs, e, *i, breaking);
333  for (++i; i != end; ++i)
334  res = derivation(rs, res, *i, breaking);
335  return res;
336  }
337 
338 
339  namespace dyn
340  {
341  namespace detail
342  {
344  template <typename ExpSet, typename Label, typename Bool>
345  polynomial
346  derivation(const expression& exp, const label& lbl, bool breaking)
347  {
348  const auto& e = exp->as<ExpSet>();
349  const auto& l = lbl->as<Label>().value();
350  const auto& rs = e.valueset();
352  return {ps, vcsn::derivation(rs, e.value(), l, breaking)};
353  }
354  }
355  }
356 } // vcsn::
polynomial_t res_
The result.
Definition: derivation.hh:267
return v
Definition: multiply.hh:361
typename labelset_t_of< base_t< ValueSet >>::word_t word_t_of
Definition: traits.hh:90
weightset_t_of< expressionset_t > weightset_t
Definition: derivation.hh:44
context_t_of< expressionset_t > context_t
Definition: derivation.hh:40
#define BUILTIN_UNREACHABLE()
Definition: builtins.hh:13
typename polynomialset_t::value_t polynomial_t
Definition: derivation.hh:48
derivation_visitor(const expressionset_t &rs)
Definition: derivation.hh:54
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
Definition: traits.hh:63
typename detail::context_t_of_impl< base_t< ValueSet >>::type context_t_of
Definition: traits.hh:61
auto label_of(const welement< Label, Weight > &m) -> decltype(m.label())
The label of a welement.
Definition: wet.hh:146
void visit(const tuple_t &v, std::true_type) override
Definition: derivation.hh:256
An inner node implementing a weight.
Definition: expression.hh:264
void require(Bool b, Args &&...args)
If b is not verified, raise an error with args as message.
Definition: raise.hh:91
A dyn Value/ValueSet.
Definition: fwd.hh:23
return res
Definition: multiply.hh:398
typename super_t::tuple_t tuple_t
Definition: derivation.hh:220
typename expressionset_t::const_visitor super_t
Definition: derivation.hh:37
label_t variable_
The derivation variable.
Definition: derivation.hh:269
rat::expression_polynomial_t< ExpSet > derivation(const ExpSet &rs, const typename ExpSet::value_t &e, label_t_of< ExpSet > a, bool breaking=false)
Derive an expression wrt to a letter.
Definition: derivation.hh:277
auto rs
Definition: lift.hh:152
weightset_t ws_
Shorthand to the weightset.
Definition: derivation.hh:264
expression_t prod_(typename mul_t::iterator begin, typename mul_t::iterator end) const
Build a product for these expressions.
Definition: derivation.hh:140
Definition: a-star.hh:8
typename detail::label_t_of_impl< base_t< ValueSet >>::type label_t_of
Definition: traits.hh:62
value_impl< detail::polynomial_tag > polynomial
Definition: fwd.hh:27
typename weightset_t::value_t weight_t
Definition: derivation.hh:45
polynomial derivation(const expression &exp, const label &lbl, bool breaking)
Bridge.
Definition: derivation.hh:346
polynomial_t work_(const tuple_t &v, detail::index_sequence< I... >)
Tuple of derivations of all the tapes.
Definition: derivation.hh:227
labelset_t_of< context_t > labelset_t
Definition: derivation.hh:41
rat::expression_polynomial_t< ExpSet > split(const ExpSet &rs, const typename ExpSet::value_t &e)
Split an expression.
Definition: split.hh:262
label_t_of< context_t > label_t
Definition: derivation.hh:42
std::string to_string(identities i)
Wrapper around operator<<.
Definition: identities.cc:41
polynomial_t operator()(const expression_t &v, label_t var)
Definition: derivation.hh:59
static constexpr const char * me()
Definition: derivation.hh:52
typename expression_polynomialset_t< ExpSet >::value_t expression_polynomial_t
Type of polynomials of expressions from the ExpSet type.
Definition: split.hh:26
auto weight_of(const welement< Label, Weight > &m) -> decltype(m.weight())
The weight of a welement.
Definition: wet.hh:154
auto & as()
Extract wrapped typed value.
Definition: value.hh:53
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
Definition: traits.hh:67
expression_polynomialset_t< ExpSet > make_expression_polynomialset(const ExpSet &rs)
From a ExpSet to its polynomialset.
Definition: split.hh:31
typename expressionset_t::value_t expression_t
Definition: derivation.hh:43
An inner node with multiple children.
Definition: expression.hh:118
#define VCSN_RAT_UNSUPPORTED(Type)
Definition: visitor.hh:75
VCSN_RAT_VISIT(conjunction, e)
Definition: derivation.hh:153
Provide a variadic mul on top of a binary mul(), and one().
Definition: fwd.hh:46
polynomial_t operator()(const tuple_t &v)
Entry point.
Definition: derivation.hh:238
weight_t_of< ExpSet > constant_term(const ExpSet &rs, const typename ExpSet::value_t &e)
The constant term of e.
value_impl< detail::expression_tag > expression
Definition: fwd.hh:25
typename super_t::node_t node_t
Definition: derivation.hh:50
Functor to compute the derivation of an expression.
Definition: derivation.hh:32