Vcsn  2.4
Be Rational
derived-term.hh
Go to the documentation of this file.
1 #pragma once
2 
5 #include <vcsn/algos/split.hh>
7 #include <vcsn/core/automaton.hh> // all_out
10 #include <vcsn/ctx/fwd.hh>
11 #include <vcsn/dyn/automaton.hh>
12 #include <vcsn/dyn/value.hh>
13 #include <vcsn/misc/getargs.hh>
14 #include <vcsn/misc/raise.hh>
16 
17 namespace vcsn
18 {
19  namespace detail
20  {
23  {
25  enum algo_t
26  {
29  };
30 
31  derived_term_algo(algo_t a, bool b, bool d)
32  : algo(a)
33  , breaking(b)
34  , determinize(d)
35  {}
36 
38  derived_term_algo(std::string algo)
39  {
40  using dta = derived_term_algo;
41  static const auto map = getarg<derived_term_algo>
42  {
43  "derived-term algorithm",
44  {
45  // { algo, breaking, deterministic }.
46  {"auto", dta{expansion, false, false}},
47  {"breaking_derivation", "derivation,breaking"},
48  {"breaking_expansion", "expansion,breaking"},
49  {"derivation", dta{derivation, false, false}},
50  {"derivation,breaking", dta{derivation, true, false}},
51  {"derivation,deterministic",dta{derivation, false, true}},
52  {"derivation_breaking", "derivation,breaking"},
53  {"expansion", dta{expansion, false, false}},
54  {"expansion,breaking", dta{expansion, true, false}},
55  {"expansion,deterministic", dta{expansion, false, true}},
56  {"expansion_breaking", "expansion,breaking"},
57  }
58  };
59  if (boost::starts_with(algo, "lazy,"))
60  algo = algo.substr(5);
61  *this = map[algo];
62  }
63 
67  bool breaking = false;
71  bool determinize = false;
72  };
73 
74  /*--------------------------.
75  | derived_term_automaton. |
76  `--------------------------*/
77 
79  template <typename ExpSet,
82  {
84  : gens{rs.labelset()->generators()}
85  {}
86 
89  using genset_t = decltype(std::declval<ls_t>().generators());
91  };
92 
94  template <typename ExpSet>
95  struct derived_term_automaton_members<ExpSet, false>
96  {
98  };
99 
129  template <typename ExpSet>
131  : public automaton_decorator<expression_automaton<mutable_automaton<context_t_of<ExpSet>>>>
132  {
133  public:
134  using expressionset_t = ExpSet;
136  using expression_t = typename expressionset_t::value_t;
137 
140 
144 
149 
150  static symbol sname()
151  {
152  static auto res = symbol{"derived_term_automaton<"
154  + ">"};
155  return res;
156  }
157 
158  std::ostream& print_set(std::ostream& o, format fmt = {}) const
159  {
160  o << "derived_term_automaton<";
161  return rs_.print_set(o, fmt) << '>';
162  }
163 
165  derived_term_algo algo)
166  : super_t{make_shared_ptr<automaton_t>(rs)}
167  , rs_{rs}
168  , algo_{algo}
169  , members_{rs}
170  {}
171 
174  {
175  try
176  {
178  return via_derivation(exp);
179  else
180  return via_expansion(exp);
181  }
182  catch (const std::runtime_error& e)
183  {
184  raise(e, " while computing derived-term of: ", to_string(rs_, exp));
185  }
186  }
187 
190  {
191  init_(exp);
192  while (!aut_->todo_.empty())
193  {
194  auto p = std::move(aut_->todo_.top());
195  aut_->todo_.pop();
196  complete_via_derivation_(p.first, p.second);
197  }
198  return aut_;
199  }
200 
203  {
204  init_(exp);
205  while (!aut_->todo_.empty())
206  {
207  auto p = std::move(aut_->todo_.top());
208  aut_->todo_.pop();
209  complete_via_expansion_(p.first, p.second);
210  }
211  return aut_;
212  }
213 
214  // private:
216  using super_t::aut_;
217 
219  void init_(const expression_t& exp)
220  {
221  if (algo_.breaking)
222  for (const auto& p: split(rs_, exp))
223  aut_->set_initial(label_of(p), weight_of(p));
224  else
225  aut_->set_initial(exp, ws_.one());
226  }
227 
229  void complete_(state_t s) const
230  {
231  const auto& orig = aut_->origins();
232  auto sn = orig.at(s);
233  const_cast<self_t&>(*this).complete_via_expansion_(s, sn);
234  }
235 
237  auto all_out(state_t s) const
238  -> decltype(vcsn::detail::all_out(aut_, s))
239  {
240  if (this->is_lazy(s))
241  complete_(s);
242  return vcsn::detail::all_out(aut_, s);
243  }
244 
246  template <typename ES = expressionset_t,
249  {
250  aut_->set_lazy(s, false);
251  aut_->set_final(s, constant_term(rs_, src));
252  for (auto l : members_.gens)
253  {
254  auto p = derivation(rs_, src, l, algo_.breaking);
255  if (algo_.determinize)
256  {
257  auto m = ps_.determinize(p);
258  aut_->new_transition(s, label_of(m), l, weight_of(m));
259  }
260  else
261  for (const auto& m: p)
262  aut_->new_transition(s, label_of(m), l, weight_of(m));
263  }
264  }
265 
268  {
269  aut_->set_lazy(s, false);
270  auto expansion = to_expansion_(src);
271  if (algo_.determinize)
273 
274  aut_->set_final(s, expansion.constant);
275  for (const auto& p: expansion.polynomials)
276  if (algo_.breaking)
277  for (const auto& m1: p.second)
278  for (const auto& m2: split(rs_, label_of(m1)))
279  aut_->new_transition(s, label_of(m2), p.first,
280  ws_.mul(weight_of(m1), weight_of(m2)));
281  else if (algo_.determinize)
282  {
283  auto m = ps_.determinize(p.second);
284  aut_->new_transition(s, label_of(m), p.first, weight_of(m));
285  }
286  else
287  for (const auto& m: p.second)
288  aut_->new_transition(s, label_of(m), p.first, weight_of(m));
289  }
290 
294  weightset_t ws_ = *rs_.weightset();
300 
309  };
310  }
311 
313  template <typename ExpSet>
315  = std::shared_ptr<detail::derived_term_automaton_impl<ExpSet>>;
316 
317  template <typename ExpSet>
318  auto
319  make_derived_term_automaton(const ExpSet& rs,
320  const detail::derived_term_algo& algo)
322  {
323  using res_t = derived_term_automaton<ExpSet>;
324  return make_shared_ptr<res_t>(rs, algo);
325  }
326 
332  template <typename ExpSet>
334  expression_automaton<mutable_automaton<typename ExpSet::context_t>>>
335  derived_term(const ExpSet& rs,
336  const typename ExpSet::value_t& r,
337  const std::string& algo = "auto")
338  {
339  auto a = detail::derived_term_algo(algo);
340  auto dt = make_derived_term_automaton(rs, a);
341  return dt->operator()(r);
342  }
343 
349  template <typename ExpSet>
351  expression_automaton<mutable_automaton<typename ExpSet::context_t>>>
352  derived_term(const ExpSet& rs,
353  const typename ExpSet::value_t& r,
354  const std::string& algo = "auto")
355  {
356  auto a = detail::derived_term_algo(algo);
358  "derived_term: cannot use derivation on non-letterized labelsets");
359  // Do not call the operator(), this would trigger the compilation
360  // of via_derivation, which does not compile (on purpose) for non
361  // letterized labelsets.
362  auto dt = make_derived_term_automaton(rs, a);
363  return dt->via_expansion(r);
364  }
365 
366  namespace dyn
367  {
368  namespace detail
369  {
371  template <typename ExpSet, typename String>
372  automaton derived_term(const expression& exp, const std::string& algo)
373  {
374  const auto& e = exp->as<ExpSet>();
375  const auto& rs = e.valueset();
376  const auto& r = e.value();
377  if (boost::starts_with(algo, "lazy,"))
378  {
379  auto a = vcsn::detail::derived_term_algo(algo);
381  "derived_term: laziness works only with expansions");
382  // Do not call the operator(), this would trigger the compilation
383  // of via_derivation, which does not compile (on purpose) for non
384  // letterized labelsets.
385  auto res = make_derived_term_automaton(rs, a);
386  res->init_(r);
387  return res;
388  }
389  else
390  return ::vcsn::derived_term(rs, r, algo);
391  }
392  }
393  }
394 } // vcsn::
value_impl< detail::expansion_tag > expansion
Definition: fwd.hh:24
derived_term_algo algo_
How derived terms are computed.
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
expression_polynomialset_t< ExpSet > make_expression_polynomialset(const ExpSet &rs)
From a ExpSet to its polynomialset.
Definition: split.hh:31
auto all_out(state_t s) const -> decltype(vcsn::detail::all_out(aut_, s))
All the outgoing transitions.
auto rs
Definition: lift.hh:152
return res
Definition: multiply.hh:398
expression_automaton< mutable_automaton< context_t >> automaton_t
The type of the (strict) automaton we build.
std::shared_ptr< detail::derived_term_automaton_impl< ExpSet >> derived_term_automaton
A derived-term automaton as a shared pointer.
typename expressionset_t::value_t expression_t
Our state names: expressions.
automaton_t via_expansion(const expression_t &exp)
Compute the derived-term automaton via expansion.
Compute the derived-term automaton from an expression.
context_t_of< expressionset_t > context_t
Aggregate an automaton, and forward calls to it.
An input/output format for valuesets.
Definition: format.hh:13
automaton_t operator()(const expression_t &exp)
Compute the derived-term automaton.
weightset_mixin< detail::r_impl > r
Definition: fwd.hh:54
void require(Bool b, Args &&...args)
If b is not verified, raise an error with args as message.
Definition: raise.hh:91
auto make_derived_term_automaton(const ExpSet &rs, const detail::derived_term_algo &algo) -> derived_term_automaton< ExpSet >
Provide a variadic mul on top of a binary mul(), and one().
Definition: fwd.hh:46
void complete_via_expansion_(state_t s, const expression_t &src)
Compute the outgoing transitions of src.
expressionset_t rs_
The expression's set.
rat::expression_polynomial_t< ExpSet > split(const ExpSet &rs, const typename ExpSet::value_t &e)
Split an expression.
Definition: split.hh:262
decltype(std::declval< ls_t >().generators()) genset_t
The generators.
Definition: derived-term.hh:89
std::ostream & print_set(std::ostream &o, format fmt={}) const
boost::flyweight< std::string, boost::flyweights::no_tracking, boost::flyweights::intermodule_holder > symbol
An internalized string.
Definition: symbol.hh:23
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
Definition: traits.hh:63
auto is_lazy(Args &&...args) const -> decltype(aut_-> is_lazy(std::forward< Args >(args)...))
Specify a variety of derived-term construction.
Definition: derived-term.hh:22
void init_(const expression_t &exp)
Initialize the computation: build the initial states.
auto weight_of(Args &&...args) const -> decltype(aut_-> weight_of(std::forward< Args >(args)...))
auto label_of(Args &&...args) const -> decltype(aut_-> label_of(std::forward< Args >(args)...))
algo_t algo
Core algorithm.
Definition: derived-term.hh:65
Definition: a-star.hh:8
derived_term_algo(std::string algo)
From algo name to algo.
Definition: derived-term.hh:38
automaton_t via_derivation(const expression_t &exp)
Compute the derived-term automaton via derivation.
auto all_out(const Aut &aut, state_t_of< Aut > s)
Indexes of transitions leaving state s.
Definition: automaton.hh:66
std::shared_ptr< detail::expression_automaton_impl< Aut >> expression_automaton
An expression automaton as a shared pointer.
Definition: fwd.hh:61
std::enable_if_t<!is_letterized_t< labelset_t_of< Aut > >{}, bool > is_letterized(const Aut &aut)
Definition: letterize.hh:161
derived_term_algo(algo_t a, bool b, bool d)
Definition: derived-term.hh:31
derived_term_automaton_members< expressionset_t > members_
Possibly the generators.
derived_term_automaton_impl(const expressionset_t &rs, derived_term_algo algo)
void complete_via_derivation_(state_t s, const expression_t &src)
Compute the outgoing transitions of src.
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
Definition: traits.hh:64
A dyn automaton.
Definition: automaton.hh:17
weight_t_of< ExpSet > constant_term(const ExpSet &rs, const typename ExpSet::value_t &e)
The constant term of e.
std::enable_if_t< labelset_t_of< ExpSet >::is_letterized(), expression_automaton< mutable_automaton< typename ExpSet::context_t > > > derived_term(const ExpSet &rs, const typename ExpSet::value_t &r, const std::string &algo="auto")
The derived-term automaton, for letterized labelsets.
void complete_(state_t s) const
Complete a state: find its outgoing transitions.
auto map(const std::tuple< Ts... > &ts, Fun f) -> decltype(map_tuple_(f, ts, make_index_sequence< sizeof...(Ts)>()))
Map a function on a tuple, return tuple of the results.
Definition: tuple.hh:177
symbol sname()
Definition: name.hh:65
std::string to_string(direction d)
Conversion to string.
Definition: direction.cc:7
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
Definition: traits.hh:67
bool breaking
Whether to break sums.
Definition: derived-term.hh:67
automaton derived_term(const expression &exp, const std::string &algo)
Bridge.
A mapping from strings to Values.
Definition: getargs.hh:33
value_impl< detail::expression_tag > expression
Definition: fwd.hh:25
Additional members when the labelset is letterized.
Definition: derived-term.hh:81
weightset_t_of< context_t > weightset_t
typename detail::context_t_of_impl< base_t< ValueSet >>::type context_t_of
Definition: traits.hh:61
bool determinize
Whether to determinize the expansions and produce a deterministic automaton, at the expense of possib...
Definition: derived-term.hh:71
value_t determinize(const value_t &v) const
Turn the polynomials into (normalized) monomials.