Vcsn  2.4
Be Rational
inductive.hh
Go to the documentation of this file.
1 #pragma once
2 
5 #include <vcsn/dyn/automaton.hh>
6 #include <vcsn/dyn/value.hh>
7 
8 namespace vcsn
9 {
10 
11  /*-------------------------.
12  | inductive(expression). |
13  `-------------------------*/
14 
20  template <Automaton Aut, typename ExpSet, typename Tag>
21  Aut
22  inductive(const ExpSet& rs, const typename ExpSet::value_t& r,
23  Tag = {});
24 
25  namespace rat
26  {
32  template <Automaton Aut, typename ExpSet, typename Tag>
34  : public ExpSet::const_visitor
35  {
36  public:
37  using automaton_t = Aut;
38  using expressionset_t = ExpSet;
39  using tag_t = Tag;
41 
44  using expression_t = typename expressionset_t::value_t;
49 
50  using super_t = typename expressionset_t::const_visitor;
51 
53  constexpr static const char* me() { return "inductive"; }
54 
56  : rs_{rs}
57  , as_{rs_.context()}
58  {}
59 
61  {
62  try
63  {
64  v->accept(*this);
65  return std::move(res_);
66  }
67  catch (const std::runtime_error& e)
68  {
69  raise(e, " while computing inductive of: ", to_string(rs_, v));
70  }
71  }
72 
73  private:
75  {
76  v->accept(*this);
77  return std::move(res_);
78  }
79 
80  using tuple_t = typename super_t::tuple_t;
81  template <bool = context_t::is_lat,
82  typename Dummy = void>
83  struct visit_tuple
84  {
86  template <size_t I>
87  auto tape_(const tuple_t& v)
88  {
89  const auto& rs = project<I>(visitor_.rs_);
90  using automaton_t =
92  return ::vcsn::inductive<automaton_t>(rs,
93  std::get<I>(v.sub()),
94  tag_t{});
95  }
96 
98  template <size_t... I>
100  {
101  return visitor_.as_.tuple(tape_<I>(v)...);
102  }
103 
105  auto operator()(const tuple_t& v)
106  {
107  visitor_.res_ = tape_(v, labelset_t::indices);
108  }
110  };
111 
112  template <typename Dummy>
113  struct visit_tuple<false, Dummy>
114  {
115  void operator()(const tuple_t&)
116  {
118  }
120  };
121 
122  void visit(const tuple_t& v, std::true_type) override
123  {
124  visit_tuple<>{*this}(v);
125  }
126 
128  {
129  res_ = as_.zero();
130  }
131 
133  {
134  res_ = as_.one();
135  }
136 
138  {
139  res_ = as_.atom(e.value());
140  }
141 
143  template <Automaton AutSet>
144  using compose_mem_fn_t =
145  decltype(std::declval<AutSet>()
146  .compose(std::declval<typename AutSet::value_t>(),
147  std::declval<typename AutSet::value_t>()));
148 
150  template <typename AutSet>
152 
153 
155  {
156  detail::static_if<has_compose_mem_fn<automatonset_t>{}>
157  ([this](const auto& e)
158  {
159  auto res = recurse(e.head());
160  for (const auto& c: e.tail())
161  res = as_.compose(res, recurse(c));
162  res_ = std::move(res);
163  },
164  [](const auto&)
165  {
166  raise("compose: context is not composable");
167  })
168  (e);
169  }
170 
172  {
173  detail::static_if<labelset_t::is_letterized()>
174  ([this](const auto& e)
175  {
176  auto res = recurse(e.head());
177  for (const auto& c: e.tail())
178  res = as_.conjunction(res, recurse(c));
179  res_ = std::move(res);
180  },
181  [this](const auto&)
182  {
183  raise("conjunction: labelset must be letterized: ",
184  *rs_.labelset());
185  })
186  (e);
187  }
188 
190  {
191  detail::static_if<labelset_t::is_letterized()>
192  ([this](const auto& e)
193  {
194  auto res = recurse(e.head());
195  for (const auto& c: e.tail())
196  res = as_.infiltrate(res, recurse(c));
197  res_ = std::move(res);
198  },
199  [this](const auto&)
200  {
201  raise("infiltrate: labelset must be letterized: ",
202  *rs_.labelset());
203  })
204  (e);
205  }
206 
208  {
209  detail::static_if<labelset_t::is_letterized()>
210  ([this](const auto& e)
211  {
212  auto res = recurse(e.head());
213  for (const auto& c: e.tail())
214  res = as_.ldivide(res, recurse(c));
215  res_ = std::move(res);
216  },
217  [this](const auto&)
218  {
219  raise("ldivide: labelset must be letterized: ",
220  *rs_.labelset());
221  })
222  (e);
223  }
224 
226  {
227  detail::static_if<labelset_t::is_letterized()>
228  ([this](const auto& e)
229  {
230  auto res = recurse(e.head());
231  for (const auto& c: e.tail())
232  res = as_.shuffle(res, recurse(c));
233  res_ = std::move(res);
234  },
235  [this](const auto&)
236  {
237  raise("shuffle: labelset must be letterized: ",
238  *rs_.labelset());
239  })
240  (e);
241  }
242 
244  {
245  auto res = recurse(e.head());
246  for (const auto& c: e.tail())
247  res = as_.add(res, recurse(c));
248  res_ = std::move(res);
249  }
250 
252  {
253  auto res = recurse(e.head());
254  for (const auto& c: e.tail())
255  res = as_.mul(res, recurse(c));
256  res_ = std::move(res);
257  }
258 
260  {
261  res_ = as_.star(recurse(e.sub()));
262  }
263 
265  {
266  detail::static_if<labelset_t::is_free()>
267  ([this](const auto& e)
268  {
269  res_ = as_.complement(recurse(e.sub()));
270  },
271  [this](const auto&)
272  {
273  raise("complement: labelset must be free: ",
274  *rs_.labelset());
275  })
276  (e);
277  }
278 
280  {
281  res_ = as_.transposition(recurse(e.sub()));
282  }
283 
285  {
286  res_ = as_.lweight(e.weight(), recurse(e.sub()));
287  }
288 
290  {
291  res_ = as_.rweight(recurse(e.sub()), e.weight());
292  }
293 
294  private:
297  automaton_t res_ = nullptr;
298  };
299  } // rat::
300 
301 
302  template <Automaton Aut, typename ExpSet, typename Tag>
303  Aut
304  inductive(const ExpSet& rs, const typename ExpSet::value_t& r, Tag)
305  {
307  return ind(r);
308  }
309 
310  namespace dyn
311  {
312  namespace detail
313  {
315  template <typename ExpSet, typename Tag>
316  automaton inductive_tag_(const ExpSet& rs,
317  const typename ExpSet::value_t& r)
318  {
320  return ::vcsn::inductive<automaton_t>(rs, r, Tag{});
321  }
322 
324  template <typename ExpSet, typename String>
325  automaton
326  inductive(const expression& exp, const std::string& algo)
327  {
328  // FIXME: So far, there is a single implementation of expressions,
329  // but we should actually be parameterized by its type too.
330  using expressionset_t = ExpSet;
331  using expression_t = typename expressionset_t::value_t;
332  const auto& e = exp->as<expressionset_t>();
333 
334  using fn_t
335  = auto(const expressionset_t&, const expression_t&) -> automaton;
336  static const auto map = getarg<std::function<fn_t>>
337  {
338  "inductive algorithm",
339  {
340  {"auto", "standard"},
341  // {"general", inductive_tag_<ExpSet, general_tag>},
342  {"standard", inductive_tag_<ExpSet, standard_tag>},
343  }
344  };
345  return map[algo](e.valueset(), e.value());
346  }
347  }
348  }
349 }
context_t_of< expressionset_t > context_t
Definition: inductive.hh:42
automaton inductive(const expression &exp, const std::string &algo)
Bridge.
Definition: inductive.hh:326
automaton_t operator()(const expression_t &v)
Definition: inductive.hh:60
VCSN_RAT_VISIT(transposition, e)
Definition: inductive.hh:279
auto rs
Definition: lift.hh:152
return res
Definition: multiply.hh:398
An inner node implementing a weight.
Definition: expression.hh:255
Aut inductive(const ExpSet &rs, const typename ExpSet::value_t &r, Tag={})
Build a inductive automaton from an expression.
Definition: inductive.hh:304
std::shared_ptr< detail::mutable_automaton_impl< Context >> mutable_automaton
Definition: fwd.hh:25
typename expressionset_t::value_t expression_t
Definition: inductive.hh:44
auto complement(const value_t &e, std::true_type) const -> value_t
Add a complement operator: e{c}.
weightset_mixin< detail::r_impl > r
Definition: fwd.hh:54
VCSN_RAT_VISIT(complement, e)
Definition: inductive.hh:264
auto rweight(const value_t &e, const weight_t &w) const -> value_t
Right-multiplication by a weight.
auto conjunction(const value_t &l, const value_t &r) const -> value_t
Build an conjunction product: l & r.
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
Definition: traits.hh:63
auto tuple(Value &&...v) const -> value_t
Build a tuple: e | f | ....
VCSN_RAT_VISIT(infiltrate, e)
Definition: inductive.hh:189
static auto mul(const value_t &l, const value_t &r) -> value_t
inductive_visitor(const expressionset_t &rs)
Definition: inductive.hh:55
Build an automaton by induction from an expression.
Definition: inductive.hh:33
typename expressionset_t::const_visitor super_t
Definition: inductive.hh:50
Definition: a-star.hh:8
auto zero() const -> value_t
Definition: automatonset.hh:78
weight_t_of< context_t > weight_t
Definition: inductive.hh:47
auto operator()(const tuple_t &v)
Entry point.
Definition: inductive.hh:105
auto atom(const label_t &l) const -> value_t
Definition: automatonset.hh:95
auto shuffle(const value_t &l, const value_t &r) const -> value_t
Build a shuffle product: l : r.
auto tape_(const tuple_t &v)
One tape.
Definition: inductive.hh:87
auto star(const value_t &e) const -> value_t
Add a star operator: e*.
static constexpr const char * me()
Name of this algorithm, for error messages.
Definition: inductive.hh:53
labelset_t_of< context_t > labelset_t
Definition: inductive.hh:45
typename detail::weight_t_of_impl< base_t< ValueSet >>::type weight_t_of
Definition: traits.hh:66
auto compose(const value_t &l, const value_t &r) const -> std::enable_if_t< are_composable< Ctx, Ctx >
Build a composition: l @ r.
auto one() const -> value_t
Definition: automatonset.hh:86
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
Definition: traits.hh:64
A dyn automaton.
Definition: automaton.hh:17
#define BUILTIN_UNREACHABLE()
Definition: builtins.hh:13
void visit(const tuple_t &v, std::true_type) override
Definition: inductive.hh:122
state_t_of< automaton_t > state_t
Definition: inductive.hh:48
auto transposition(const value_t &e) const -> value_t
Add a transposition operator.
automaton_t recurse(const expression_t &v)
Definition: inductive.hh:74
An inner node with multiple children.
Definition: expression.hh:118
return v
Definition: multiply.hh:361
weightset_t_of< context_t > weightset_t
Definition: inductive.hh:46
static auto add(const value_t &l, const value_t &r) -> value_t
auto infiltrate(const value_t &l, const value_t &r) const -> value_t
Build an infiltration product: l &: r.
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
Definition: traits.hh:67
A mapping from strings to Values.
Definition: getargs.hh:33
value_impl< detail::expression_tag > expression
Definition: fwd.hh:25
automaton inductive_tag_(const ExpSet &rs, const typename ExpSet::value_t &r)
Helper function to facilitate dispatch below.
Definition: inductive.hh:316
auto & as()
Extract wrapped typed automaton.
Definition: automaton.hh:37
decltype(std::declval< AutSet >().compose(std::declval< typename AutSet::value_t >(), std::declval< typename AutSet::value_t >())) compose_mem_fn_t
The type of the AutSet::compose() member function.
Definition: inductive.hh:147
typename detail::context_t_of_impl< base_t< ValueSet >>::type context_t_of
Definition: traits.hh:61
VCSN_RAT_VISIT(conjunction, e)
Definition: inductive.hh:171
auto lweight(const weight_t &w, const value_t &e) const -> value_t
Left-multiplication by a weight.
auto tape_(const tuple_t &v, detail::index_sequence< I... >)
Sum of sizes for all tapes.
Definition: inductive.hh:99
std::string to_string(identities i)
Wrapper around operator<<.
Definition: identities.cc:42
auto ldivide(const value_t &l, const value_t &r) const -> value_t
r`.
typename super_t::tuple_t tuple_t
Definition: inductive.hh:80