Vcsn  2.2
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/label.hh>
8 #include <vcsn/dyn/polynomial.hh>
9 #include <vcsn/dyn/expression.hh>
10 #include <vcsn/misc/raise.hh>
12 
13 namespace vcsn
14 {
15 
16  /*--------------------------.
17  | derivation(expression). |
18  `--------------------------*/
19 
20  template <typename ExpSet>
21  rat::expression_polynomial_t<ExpSet>
22  derivation(const ExpSet& rs,
23  const typename ExpSet::value_t& e,
24  label_t_of<ExpSet> a,
25  bool breaking = false);
26 
27  namespace rat
28  {
32  template <typename ExpSet>
34  : public ExpSet::const_visitor
35  {
36  public:
37  using expressionset_t = ExpSet;
38  using super_t = typename expressionset_t::const_visitor;
40 
44  using expression_t = typename expressionset_t::value_t;
46  using weight_t = typename weightset_t::value_t;
47 
50 
51  using node_t = typename super_t::node_t;
52 
53  constexpr static const char* me() { return "derivation"; }
54 
56  : rs_(rs)
57  {}
58 
61  {
62  variable_ = var;
63  v->accept(*this);
64  return std::move(res_);
65  }
66 
67  private:
71 
73  {
74  res_ = ps_.zero();
75  }
76 
78  {
79  res_ = ps_.zero();
80  }
81 
83  {
84  if (e.value() == variable_)
85  res_ = ps_.one();
86  else
87  res_ = ps_.zero();
88  }
89 
91  {
92  polynomial_t res = ps_.zero();
93  for (const auto& v: e)
94  {
95  v->accept(*this);
96  ps_.add_here(res, res_);
97  }
98  res_ = std::move(res);
99  }
100 
102  {
103  // We generate a sum.
104  auto res = ps_.zero();
105  // Accumulate the product of the constant terms of the
106  // previous factors.
107  weight_t constant = ws_.one();
108  for (unsigned i = 0, n = e.size(); i < n; ++i)
109  {
110  const auto& v = e[i];
111  v->accept(*this);
112  // See to-expansion.hh, case of prod, for an explanation
113  // of the following line.
114  res_
115  = ps_.rmul_label(res_,
116  prod_(std::next(e.begin(), i+1), std::end(e)));
117  ps_.add_here(res, ps_.lmul(constant, res_));
118  constant = ws_.mul(constant, constant_term(rs_, v));
119  if (ws_.is_zero(constant))
120  break;
121  }
122  res_ = std::move(res);
123  }
124 
130  prod_(typename prod_t::iterator begin,
131  typename prod_t::iterator end) const
132  {
133  using expressions_t = typename prod_t::values_t;
134  if (begin == end)
135  return rs_.one();
136  else if (std::next(begin, 1) == end)
137  return *begin;
138  else
139  return std::make_shared<prod_t>(expressions_t{begin, end});
140  }
141 
142 
144  {
145  // The first polynomial.
146  e.head()->accept(*this);
147  auto res = res_;
148  for (unsigned i = 1, n = e.size(); i < n; ++i)
149  {
150  const auto& v = e[i];
151  v->accept(*this);
152  res = ps_.conjunction(res, res_);
153  }
154  res_ = std::move(res);
155  }
156 
158  {
159  polynomial_t res = ps_.zero();
160  for (unsigned i = 0; i < e.size(); ++i)
161  {
162  e[i]->accept(*this);
163  for (const auto& m: res_)
164  {
165  typename node_t::values_t expressions;
166  for (unsigned j = 0; j < e.size(); ++j)
167  if (i == j)
168  expressions.emplace_back(label_of(m));
169  else
170  expressions.emplace_back(e[j]);
171  // FIXME: we need better n-ary constructors.
172  ps_.add_here(res,
173  std::make_shared<shuffle_t>(expressions),
174  weight_of(m));
175  }
176  }
177  res_ = std::move(res);
178  }
179 
181  {
182  e.sub()->accept(*this);
183  res_ = ps_.complement(res_);
184  }
185 
187  {
188  e.sub()->accept(*this);
189  // We need a copy of e, but without its weights.
190  res_ = ps_.lmul(ws_.star(constant_term(rs_, e.sub())),
191  ps_.rmul_label(res_, e.shared_from_this()));
192  }
193 
195  {
196  e.sub()->accept(*this);
197  res_ = ps_.lmul(e.weight(), res_);
198  }
199 
201  {
202  e.sub()->accept(*this);
203  res_ = ps_.rmul(res_, e.weight());
204  }
205 
206  /*---------.
207  | tuple. |
208  `---------*/
209 
210  using tuple_t = typename super_t::tuple_t;
211  template <bool = context_t::is_lat,
212  typename Dummy = void>
213  struct visit_tuple
214  {
216  template <size_t... I>
218  {
219  return
220  visitor_
221  .ps_
222  .tuple(vcsn::derivation(detail::project<I>(visitor_.rs_),
223  std::get<I>(v.sub()),
224  std::get<I>(visitor_.variable_))...);
225  }
226 
229  {
231  }
232 
233  const self_t& visitor_;
234  };
235 
236  template <typename Dummy>
237  struct visit_tuple<false, Dummy>
238  {
240  {
242  }
243  const self_t& visitor_;
244  };
245 
246  void visit(const tuple_t& v, std::true_type) override
247  {
248  res_ = visit_tuple<>{*this}(v);
249  }
250 
251  private:
254  weightset_t ws_ = *rs_.weightset();
260  };
261 
262  } // rat::
263 
265  template <typename ExpSet>
267  derivation(const ExpSet& rs,
268  const typename ExpSet::value_t& e,
270  bool breaking)
271  {
272  static_assert(ExpSet::context_t::labelset_t::is_free(),
273  "derivation: requires free labelset");
275  auto res = derivation(e, a);
276  if (breaking)
277  res = split(rs, res);
278  return res;
279  }
280 
281 
283  template <typename ExpSet>
284  rat::expression_polynomial_t<ExpSet>
285  derivation(const ExpSet& rs,
288  bool breaking = false)
289  {
291  using polynomial_t = rat::expression_polynomial_t<ExpSet>;
292  auto res = polynomial_t{};
293  for (const auto& m: p)
294  res = ps.add(res,
295  ps.lmul(weight_of(m),
296  derivation(rs, label_of(m), a, breaking)));
297  return res;
298  }
299 
300 
309  template <typename ExpSet,
310  typename = std::enable_if_t<!std::is_same<word_t_of<ExpSet>,
311  label_t_of<ExpSet>>
312  ::value>>
313  rat::expression_polynomial_t<ExpSet>
314  derivation(const ExpSet& rs,
315  const typename ExpSet::value_t& e,
316  const word_t_of<ExpSet>& l,
317  bool breaking = false)
318  {
319  auto word = rs.labelset()->letters_of(l);
320  auto i = std::begin(word);
321  auto end = std::end(word);
322  require(i != end, "derivation: word cannot be empty");
323  auto res = derivation(rs, e, *i, breaking);
324  for (++i; i != end; ++i)
325  res = derivation(rs, res, *i, breaking);
326  return res;
327  }
328 
329 
330  namespace dyn
331  {
332  namespace detail
333  {
335  template <typename ExpSet, typename Label, typename Bool>
336  polynomial
337  derivation(const expression& exp, const label& lbl, bool breaking)
338  {
339  const auto& e = exp->as<ExpSet>();
340  const auto& l = lbl->as<Label>().label();
341  const auto& rs = e.expressionset();
343  return make_polynomial(ps,
344  vcsn::derivation(rs, e.expression(),
345  l, breaking));
346  }
347  }
348  }
349 } // vcsn::
polynomial_t res_
The result.
Definition: derivation.hh:257
typename expression_polynomialset_t< ExpSet >::value_t expression_polynomial_t
Type of polynomials of expressions from the ExpSet type.
Definition: split.hh:27
#define VCSN_RAT_UNSUPPORTED(Type)
Definition: visitor.hh:68
std::shared_ptr< const detail::polynomial_base > polynomial
Definition: fwd.hh:70
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
Definition: traits.hh:59
polynomial_t operator()(const expression_t &v, label_t var)
Definition: derivation.hh:60
polynomial make_polynomial(const PolynomialSet &ps, const typename PolynomialSet::value_t &p)
Definition: polynomial.hh:103
typename expressionset_t::const_visitor super_t
Definition: derivation.hh:38
Definition: a-star.hh:8
void require(Bool b, Args &&...args)
If b is not verified, raise an error with args as message.
Definition: raise.hh:78
polynomial_t operator()(const tuple_t &v)
Entry point.
Definition: derivation.hh:228
Functor to compute the derivation of an expression.
Definition: derivation.hh:33
VCSN_RAT_VISIT(conjunction, e)
Definition: derivation.hh:143
void visit(const tuple_t &v, std::true_type) override
Definition: derivation.hh:246
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
Definition: traits.hh:55
Provide a variadic mul on top of a binary mul(), and one().
Definition: fwd.hh:46
An inner node with multiple children.
Definition: expression.hh:118
weight_t_of< ExpSet > constant_term(const ExpSet &rs, const typename ExpSet::value_t &e)
The constant term of e.
auto weight_of(const welement< Label, Weight > &m) -> decltype(m.weight())
The weight of a welement.
Definition: wet.hh:154
weightset_t_of< expressionset_t > weightset_t
Definition: derivation.hh:45
static constexpr const char * me()
Definition: derivation.hh:53
#define BUILTIN_UNREACHABLE()
Definition: builtins.hh:13
std::shared_ptr< const detail::label_base > label
Definition: fwd.hh:61
derivation_visitor(const expressionset_t &rs)
Definition: derivation.hh:55
polynomial derivation(const expression &exp, const label &lbl, bool breaking)
Bridge.
Definition: derivation.hh:337
weightset_t ws_
Shorthand to the weightset.
Definition: derivation.hh:254
typename super_t::tuple_t tuple_t
Definition: derivation.hh:210
auto rs
Definition: lift.hh:151
expression_t prod_(typename prod_t::iterator begin, typename prod_t::iterator end) const
Build a product for these expressions.
Definition: derivation.hh:130
typename detail::context_t_of_impl< base_t< ValueSet >>::type context_t_of
Definition: traits.hh:53
auto label_of(const welement< Label, Weight > &m) -> decltype(m.label())
The label of a welement.
Definition: wet.hh:146
labelset_t_of< context_t > labelset_t
Definition: derivation.hh:42
typename detail::label_t_of_impl< base_t< ValueSet >>::type label_t_of
Definition: traits.hh:54
An inner node implementing a weight.
Definition: expression.hh:264
label_t variable_
The derivation variable.
Definition: derivation.hh:259
std::shared_ptr< detail::expression_base > expression
Definition: expression.hh:92
polynomial_t work_(const tuple_t &v, detail::index_sequence< I... >)
Tuple of derivations of all the tapes.
Definition: derivation.hh:217
context_t_of< expressionset_t > context_t
Definition: derivation.hh:41
label_t_of< context_t > label_t
Definition: derivation.hh:43
typename labelset_t_of< base_t< ValueSet >>::word_t word_t_of
Definition: traits.hh:82
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:267
expression_polynomialset_t< ExpSet > make_expression_polynomialset(const ExpSet &rs)
From a ExpSet to its polynomialset.
Definition: split.hh:33
typename polynomialset_t::value_t polynomial_t
Definition: derivation.hh:49
typename weightset_t::value_t weight_t
Definition: derivation.hh:46
typename super_t::node_t node_t
Definition: derivation.hh:51
typename expressionset_t::value_t expression_t
Definition: derivation.hh:44
rat::expression_polynomial_t< ExpSet > split(const ExpSet &rs, const typename ExpSet::value_t &e)
Split an expression.
Definition: split.hh:264