Vcsn  2.4
Be Rational
random-expression.hh
Go to the documentation of this file.
1 #include <ostream>
2 #include <regex>
3 #include <string>
4 
5 #include <boost/algorithm/string/erase.hpp>
6 #include <boost/tokenizer.hpp>
7 
8 #include <vcsn/core/rat/expressionset.hh> // make_expressionset
9 #include <vcsn/core/rat/less.hh>
10 #include <vcsn/dyn/algos.hh>
11 #include <vcsn/misc/algorithm.hh>
12 #include <vcsn/misc/cast.hh>
13 #include <vcsn/misc/raise.hh>
14 #include <vcsn/misc/random.hh>
16 
17 namespace vcsn
18 {
19  namespace detail
20  {
21 
27  template <typename ExpressionSet,
28  typename RandomGenerator = std::default_random_engine>
30  {
31  public:
32  using expressionset_t = ExpressionSet;
33  using expression_t = typename expressionset_t::value_t;
34  using weight_t = typename expressionset_t::weight_t;
35  using weightset_t = typename expressionset_t::weightset_t;
36 
38  const std::string& param,
39  RandomGenerator& gen)
40  : rs_{rs}
41  , gen_{gen}
42  {
43  parse_param_(param);
44  }
45 
48  std::ostream& print_random_expression(std::ostream& out) const
49  {
50  return print_random_expression_(out, length_);
51  }
52 
55  std::string random_expression_string() const
56  {
57  std::ostringstream out;
59  return out.str();
60  }
61 
65  {
67  }
68 
69  private:
72  void parse_param_(const std::string& param)
73  {
74  // Set default value.
75  length_ = 6;
76  using tokenizer = boost::tokenizer<boost::escaped_list_separator<char>>;
77  auto sep = boost::escaped_list_separator<char>("#####", ",", "\"");
78  auto tok = tokenizer(param, sep);
79  for (auto it = tok.begin(); it != tok.end(); ++it)
80  {
81  auto tok_arg = std::string{*it};
82  auto eq = tok_arg.find_first_of('=');
83  auto op = tok_arg.substr(0, eq);
84  boost::algorithm::erase_all(op, " ");
85  if (op == "w")
86  random_weight_.parse_param(tok_arg.substr(eq + 1));
87  else
88  {
89  float value = 1;
90  if (eq != std::string::npos)
91  value = lexical_cast<float>(tok_arg.substr(eq + 1));
92  if (has(arities_, op))
93  operators_[op] = value;
94  else if (op == "length")
95  length_ = value;
96  else
97  raise("random_expression: invalid operator: ", op);
98  }
99  }
101  [](const auto& v){ return v.second; });
102  }
103 
105  void print_weight_(std::ostream& out) const
106  {
107  out << "<";
108  rs_.weightset()->print(random_weight_.generate_random_weight(), out);
109  out << ">";
110  }
111 
113  void print_label_(std::ostream& out) const
114  {
115  rs_.labelset()->print(random_label(*rs_.labelset(), gen_), out);
116  }
117 
119  void print_unary_exp_(std::ostream& out, unsigned length,
120  const std::string& op) const
121  {
122  // Prefix.
123  if (op == "!" || op == "w.")
124  {
125  out << '(';
126  if (op == "w.")
127  print_weight_(out);
128  else
129  out << op;
130  print_random_expression_(out, length - 1);
131  out << ')';
132  }
133  // Postfix.
134  else
135  {
136  out << '(';
137  print_random_expression_(out, length - 1);
138  if (op == ".w")
139  print_weight_(out);
140  else
141  out << op;
142  out << ")";
143  }
144  }
145 
149  void print_binary_exp_(std::ostream& out, unsigned length,
150  const std::string& op) const
151  {
152  if (length < 3)
153  print_label_(out);
154  else
155  {
156  auto dis = std::uniform_int_distribution<>(1, length - 2);
157  auto num_lhs = dis(gen_);
158  out << "(";
159  print_random_expression_(out, num_lhs);
160  out << op;
161  print_random_expression_(out, length - 1 - num_lhs);
162  out << ")";
163  }
164  }
165 
166  std::ostream&
167  print_random_expression_(std::ostream& out, unsigned length) const
168  {
169  // If there is no operators at all, that's impossible to
170  // construct an expression, so just return a label.
171  if (operators_.empty())
172  print_label_(out);
173 
174  // One symbol left: print a label.
175  else if (length == 1)
176  print_label_(out);
177 
178  // All operators are possible, choose one randomly (with
179  // associated weight probability) and print the associated
180  // expression.
181  else
182  {
183  // Choose an operator.
184  auto op = chooser_it_(proba_op_, operators_)->first;
185  switch (arities_.at(op))
186  {
187  case 0:
188  out << op;
189  break;
190  case 1:
191  print_unary_exp_(out, length, op);
192  break;
193  case 2:
194  print_binary_exp_(out, length, op);
195  break;
196  default:
197  assert(!"invalid arity");
198  }
199  }
200  return out;
201  }
202 
205  unsigned length_;
207  std::map<std::string, float> operators_;
209  std::unordered_map<std::string, int> arities_
210  {
211  // Nullary.
212  {"\\e", 0},
213  {"\\z", 0},
214  // Unary.
215  {"!", 1},
216  {"{c}", 1},
217  {"*", 1},
218  {"{T}", 1},
219  {"w.", 1},
220  {".w", 1},
221  // Binary.
222  {"&", 2},
223  {"&:", 2},
224  {":", 2},
225  {".", 2},
226  {"<+", 2},
227  {"%", 2},
228  {"+", 2},
229  {"{/}", 2},
230  {"{\\}",2},
231  };
232 
235  std::vector<float> proba_op_;
237  RandomGenerator& gen_;
241  };
242 
244  template <typename ExpressionSet, typename RandomGenerator = std::mt19937>
245  random_expression_impl<ExpressionSet, RandomGenerator>
246  make_random_expression_impl(const ExpressionSet& rs,
247  const std::string& param,
248  RandomGenerator& gen = make_random_engine())
249  {
250  return {rs, param, gen};
251  }
252 
253  } // end namespace vcsn::detail
254 
255 
262  template <typename ExpressionSet>
263  std::string
264  random_expression_string(const ExpressionSet& rs, const std::string& param)
265  {
266  auto random_exp = detail::make_random_expression_impl(rs, param);
267  return random_exp.random_expression_string();
268  }
269 
270 
272  template <typename ExpressionSet>
273  typename ExpressionSet::value_t
274  random_expression(const ExpressionSet& rs, const std::string& param)
275  {
276  auto random_exp = detail::make_random_expression_impl(rs, param);
277  return random_exp.random_expression();
278  }
279 
280  namespace dyn
281  {
282  namespace detail
283  {
285  template <typename Context, typename String, typename Identities>
286  expression
287  random_expression(const context& ctx, const std::string& param,
288  identities ids)
289  {
290  const auto& c = ctx->as<Context>();
291  auto rs = make_expressionset(c, ids);
292  return {rs, random_expression(rs, param)};
293  }
294  }
295  }
296 } // end namespace vcsn
std::ostream & print_random_expression_(std::ostream &out, unsigned length) const
expression random_expression(const context &ctx, const std::string &param, identities ids)
Bridge.
std::ostream & print_random_expression(std::ostream &out) const
Print a random expression string (not parsed, so there might be some syntactic sugar such as <+)...
T lexical_cast(const std::string &str)
String to templated type T conversion.
Definition: cast.hh:79
typename expressionset_t::weightset_t weightset_t
auto rs
Definition: lift.hh:152
static identities ids(const driver &d)
Get the identities of the driver.
Definition: parse.cc:89
auto make_expressionset(const context< LabelSet, WeightSet > &ctx, rat::identities ids={}) -> expressionset< context< LabelSet, WeightSet >>
Shorthand to expressionset constructor.
void print_label_(std::ostream &out) const
Print label.
ExpressionSet::value_t random_expression(const ExpressionSet &rs, const std::string &param)
Generate a random expression.
void print_binary_exp_(std::ostream &out, unsigned length, const std::string &op) const
Print binary expression with binary operator.
void parse_param_(const std::string &param)
FIXME: maybe use something similar to Boost.ProgramOptions or getargs.
std::mt19937 & make_random_engine()
Generate a unique random device.
Definition: random.cc:6
std::unordered_map< std::string, int > arities_
Number of arguments of each operator.
auto & as()
Downcast to the exact type.
Definition: context.hh:36
Definition: a-star.hh:8
std::vector< float > proba_op_
Vector of weights associated with the operators, i.e., the probabilities to pick each operator...
auto out(const Aut &aut, state_t_of< Aut > s)
Indexes of visible transitions leaving state s.
Definition: automaton.hh:85
auto transform(const Container &c, Fun &&fun)
Map a unary function on a container of values, and return the vector the results. ...
Definition: algorithm.hh:157
random_expression_impl< ExpressionSet, RandomGenerator > make_random_expression_impl(const ExpressionSet &rs, const std::string &param, RandomGenerator &gen=make_random_engine())
Convenience constructor.
std::string random_expression_string() const
A random expression string (not parsed, so there might be some syntactic sugar such as <+)...
Template-less root for contexts.
Definition: context.hh:16
random_expression_impl(const expressionset_t &rs, const std::string &param, RandomGenerator &gen)
typename expressionset_t::value_t expression_t
void print_unary_exp_(std::ostream &out, unsigned length, const std::string &op) const
Print expression with unary operator.
void print_weight_(std::ostream &out) const
Print random weight.
Class random expression generator.
random_weight< weightset_t, RandomGenerator > random_weight_
Random weights generator.
std::map< std::string, float > operators_
For each operator, its probability.
discrete_chooser< RandomGenerator > chooser_it_
auto conv(const ValueSet &vs, const std::string &str, Args &&...args) -> decltype(vs.conv(std::declval< std::istream & >(), std::forward< Args >(args)...))
Parse str via vs.conv.
Definition: stream.hh:29
value_impl< detail::expression_tag > expression
Definition: fwd.hh:25
ATTRIBUTE_PURE bool has(const boost::container::flat_set< Key, Compare, Allocator > &s, const Key &e)
Whether e is member of s.
Definition: setalpha.hh:25
expressionset< Context >::value_t random_label(const expressionset< Context > &rs, RandomGenerator &gen=RandomGenerator())
Random label from expressionset: limited to a single label.
RandomGenerator & gen_
Random generator.
std::string random_expression_string(const ExpressionSet &rs, const std::string &param)
Generate a random expression string.
typename expressionset_t::weight_t weight_t
Random selector on container, using discrete distribution.
Definition: random.hh:27
expression_t random_expression() const
A random expression (parsed, so there cannot be syntactic sugar such as <+).