Vcsn  2.4
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>
227  auto work_(const tuple_t& v)
228  {
229  const auto& ps = visitor_.ps_.template project<I>();
230  const auto& rs = visitor_.rs_.template project<I>();
231  if (rs.labelset()->is_one(std::get<I>(visitor_.variable_)))
232  // ∂ε(E) = ⟨c(E)⟩ . 1.
233  return ps.value(rs.one(),
234  constant_term(rs, std::get<I>(v.sub())));
235  else
236  return vcsn::derivation(rs,
237  std::get<I>(v.sub()),
238  std::get<I>(visitor_.variable_));
239  }
240 
242  template <size_t... I>
244  {
245  return visitor_.ps_.tuple(work_<I>(v)...);
246  }
247 
250  {
252  }
253 
254  const self_t& visitor_;
255  };
256 
257  template <typename Dummy>
258  struct visit_tuple<false, Dummy>
259  {
261  {
263  }
264  const self_t& visitor_;
265  };
266 
267  void visit(const tuple_t& v, std::true_type) override
268  {
269  res_ = visit_tuple<>{*this}(v);
270  }
271 
272  private:
275  weightset_t ws_ = *rs_.weightset();
281  };
282  } // rat::
283 
285  template <typename ExpSet>
287  derivation(const ExpSet& rs,
288  const typename ExpSet::value_t& e,
290  bool breaking)
291  {
293  "derivation: requires letterized labelset");
295  auto res = derivation(e, a);
296  if (breaking)
297  res = split(rs, res);
298  return res;
299  }
300 
301 
303  template <typename ExpSet>
304  rat::expression_polynomial_t<ExpSet>
305  derivation(const ExpSet& rs,
308  bool breaking = false)
309  {
311  using polynomial_t = rat::expression_polynomial_t<ExpSet>;
312  auto res = polynomial_t{};
313  for (const auto& m: p)
314  res = ps.add(res,
315  ps.lweight(weight_of(m),
316  derivation(rs, label_of(m), a, breaking)));
317  return res;
318  }
319 
320 
329  template <typename ExpSet,
330  typename = std::enable_if_t<!std::is_same<word_t_of<ExpSet>,
331  label_t_of<ExpSet>>{}>>
332  rat::expression_polynomial_t<ExpSet>
333  derivation(const ExpSet& rs,
334  const typename ExpSet::value_t& e,
335  const word_t_of<ExpSet>& l,
336  bool breaking = false)
337  {
338  auto word = rs.labelset()->letters_of(l);
339  auto i = std::begin(word);
340  auto end = std::end(word);
341  require(i != end, "derivation: word cannot be empty");
342  auto res = derivation(rs, e, *i, breaking);
343  for (++i; i != end; ++i)
344  res = derivation(rs, res, *i, breaking);
345  return res;
346  }
347 
348 
349  namespace dyn
350  {
351  namespace detail
352  {
354  template <typename ExpSet, typename Label, typename Bool>
355  polynomial
356  derivation(const expression& exp, const label& lbl, bool breaking)
357  {
358  const auto& e = exp->as<ExpSet>();
359  const auto& l = lbl->as<Label>().value();
360  const auto& rs = e.valueset();
362  return {ps, vcsn::derivation(rs, e.value(), l, breaking)};
363  }
364  }
365  }
366 } // vcsn::
typename expressionset_t::value_t expression_t
Definition: derivation.hh:43
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:287
void visit(const tuple_t &v, std::true_type) override
Definition: derivation.hh:267
expression_polynomialset_t< ExpSet > make_expression_polynomialset(const ExpSet &rs)
From a ExpSet to its polynomialset.
Definition: split.hh:31
auto rs
Definition: lift.hh:152
return res
Definition: multiply.hh:398
VCSN_RAT_VISIT(conjunction, e)
Definition: derivation.hh:153
polynomial derivation(const expression &exp, const label &lbl, bool breaking)
Bridge.
Definition: derivation.hh:356
weightset_t ws_
Shorthand to the weightset.
Definition: derivation.hh:275
An inner node implementing a weight.
Definition: expression.hh:255
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
typename polynomialset_t::value_t polynomial_t
Definition: derivation.hh:48
void require(Bool b, Args &&...args)
If b is not verified, raise an error with args as message.
Definition: raise.hh:91
Provide a variadic mul on top of a binary mul(), and one().
Definition: fwd.hh:46
typename detail::label_t_of_impl< base_t< ValueSet >>::type label_t_of
Definition: traits.hh:62
rat::expression_polynomial_t< ExpSet > split(const ExpSet &rs, const typename ExpSet::value_t &e)
Split an expression.
Definition: split.hh:262
typename weightset_t::value_t weight_t
Definition: derivation.hh:45
typename super_t::node_t node_t
Definition: derivation.hh:50
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
Definition: traits.hh:63
expression_t prod_(typename mul_t::iterator begin, typename mul_t::iterator end) const
Build a product for these expressions.
Definition: derivation.hh:140
label_t variable_
The derivation variable.
Definition: derivation.hh:280
auto work_(const tuple_t &v)
Work on tape I.
Definition: derivation.hh:227
Definition: a-star.hh:8
labelset_t_of< context_t > labelset_t
Definition: derivation.hh:41
#define VCSN_RAT_UNSUPPORTED(Type)
Definition: visitor.hh:74
weightset_t_of< expressionset_t > weightset_t
Definition: derivation.hh:44
std::enable_if_t<!is_letterized_t< labelset_t_of< Aut > >{}, bool > is_letterized(const Aut &aut)
Definition: letterize.hh:161
typename labelset_t_of< base_t< ValueSet >>::word_t word_t_of
Definition: traits.hh:90
weight_t_of< ExpSet > constant_term(const ExpSet &rs, const typename ExpSet::value_t &e)
The constant term of e.
polynomial_t res_
The result.
Definition: derivation.hh:278
#define BUILTIN_UNREACHABLE()
Definition: builtins.hh:13
polynomial_t work_(const tuple_t &v, detail::index_sequence< I... >)
Tuple of derivations of all the tapes.
Definition: derivation.hh:243
An inner node with multiple children.
Definition: expression.hh:118
typename super_t::tuple_t tuple_t
Definition: derivation.hh:220
return v
Definition: multiply.hh:361
auto & as()
Extract wrapped typed value.
Definition: value.hh:53
Functor to compute the derivation of an expression.
Definition: derivation.hh:32
polynomial_t operator()(const expression_t &v, label_t var)
Definition: derivation.hh:59
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
Definition: traits.hh:67
context_t_of< expressionset_t > context_t
Definition: derivation.hh:40
A dyn Value/ValueSet.
Definition: fwd.hh:23
static constexpr const char * me()
Definition: derivation.hh:52
polynomial_t operator()(const tuple_t &v)
Entry point.
Definition: derivation.hh:249
value_impl< detail::expression_tag > expression
Definition: fwd.hh:25
label_t_of< context_t > label_t
Definition: derivation.hh:42
typename detail::context_t_of_impl< base_t< ValueSet >>::type context_t_of
Definition: traits.hh:61
derivation_visitor(const expressionset_t &rs)
Definition: derivation.hh:54
auto label_of(const welement< Label, Weight > &m) -> decltype(m.label())
The label of a welement.
Definition: wet.hh:146
value_impl< detail::polynomial_tag > polynomial
Definition: fwd.hh:27
std::string to_string(identities i)
Wrapper around operator<<.
Definition: identities.cc:42
typename expressionset_t::const_visitor super_t
Definition: derivation.hh:37