1 /* 2 Expression writer 3 4 Copyright (C) 2014 AMPL Optimization Inc 5 6 Permission to use, copy, modify, and distribute this software and its 7 documentation for any purpose and without fee is hereby granted, 8 provided that the above copyright notice appear in all copies and that 9 both that the copyright notice and this permission notice and warranty 10 disclaimer appear in supporting documentation. 11 12 The author and AMPL Optimization Inc disclaim all warranties with 13 regard to this software, including all implied warranties of 14 merchantability and fitness. In no event shall the author be liable 15 for any special, indirect or consequential damages or any damages 16 whatsoever resulting from loss of use, data or profits, whether in an 17 action of contract, negligence or other tortious action, arising out 18 of or in connection with the use or performance of this software. 19 20 Author: Victor Zverovich 21 */ 22 23 #ifndef MP_EXPR_WRITER_H_ 24 #define MP_EXPR_WRITER_H_ 25 26 #include "mp/basic-expr-visitor.h" 27 28 namespace mp { 29 30 namespace prec { 31 enum Precedence { 32 UNKNOWN, 33 CONDITIONAL, // if-then-else 34 IFF, // <==> 35 IMPLICATION, // ==> else 36 LOGICAL_OR, // or || 37 LOGICAL_AND, // and && 38 NOT, // not ! 39 RELATIONAL, // < <= = == >= > != <> 40 ADDITIVE, // + - less 41 ITERATIVE, // sum prod min max 42 MULTIPLICATIVE, // * / div mod 43 EXPONENTIATION, // ^ 44 UNARY, // + - (unary) 45 CALL, // a function call including functional forms of 46 // min and max 47 PRIMARY // variable, string or constant 48 }; 49 } 50 51 namespace expr { 52 // Returns operator precedence for the specified expression kind assuming the 53 // notation used by ExprWriter. 54 prec::Precedence precedence(expr::Kind kind); 55 56 class PrecInfo { 57 private: 58 static const prec::Precedence INFO[LAST_EXPR + 1]; 59 friend prec::Precedence precedence(Kind kind) { 60 MP_ASSERT(internal::IsValid(kind), "invalid expression kind"); 61 return INFO[kind]; 62 } 63 }; 64 } 65 66 template <typename ExprTypes, typename NumericExpr> 67 inline bool IsZero(NumericExpr expr) { 68 typedef typename ExprTypes::NumericConstant NumericConstant; 69 NumericConstant n = ExprTypes::template Cast<NumericConstant>(expr); 70 return n && n.value() == 0; 71 } 72 73 // An expression visitor that writes AMPL expressions in a textual form 74 // to fmt::Writer. It takes into account precedence and associativity 75 // of operators avoiding unnecessary parentheses except for potentially 76 // confusing cases such as "!x = y" which is written as "!(x = y) instead. 77 template <typename ExprTypes> 78 class ExprWriter : 79 public BasicExprVisitor<ExprWriter<ExprTypes>, void, ExprTypes> { 80 private: 81 fmt::Writer &writer_; 82 int precedence_; 83 84 MP_DEFINE_EXPR_TYPES(ExprTypes); 85 86 typedef BasicExprVisitor<ExprWriter<ExprTypes>, void, ExprTypes> Base; 87 88 static int precedence(Expr e) { return expr::precedence(e.kind()); } 89 90 // Writes an argument list surrounded by parentheses. 91 template <typename Iter> 92 void WriteArgs(Iter begin, Iter end, const char *sep = ", ", 93 int precedence = prec::UNKNOWN); 94 95 template <typename Expr> 96 void WriteArgs(Expr e, const char *sep = ", ", 97 int precedence = prec::UNKNOWN) { 98 WriteArgs(e.begin(), e.end(), sep, precedence); 99 } 100 101 // Writes a function or an expression that has a function syntax. 102 template <typename Expr> 103 void WriteFunc(Expr e) { 104 writer_ << str(e.kind()); 105 WriteArgs(e); 106 } 107 108 template <typename ExprType> 109 void WriteBinary(ExprType e); 110 111 void WriteCallArg(Expr arg); 112 113 class Parenthesizer { 114 private: 115 ExprWriter &writer_; 116 int saved_precedence_; 117 bool write_paren_; 118 119 public: 120 Parenthesizer(ExprWriter &w, Expr e, int precedence); 121 ~Parenthesizer(); 122 }; 123 124 public: 125 explicit ExprWriter(fmt::Writer &w) 126 : writer_(w), precedence_(prec::UNKNOWN) {} 127 128 void Visit(NumericExpr e, int precedence = -1) { 129 Parenthesizer p(*this, e, precedence); 130 Base::Visit(e); 131 } 132 133 void Visit(LogicalExpr e, int precedence = -1) { 134 Parenthesizer p(*this, e, precedence); 135 Base::Visit(e); 136 } 137 138 void VisitNumericConstant(NumericConstant c) { writer_ << c.value(); } 139 140 void VisitUnary(UnaryExpr e) { 141 writer_ << str(e.kind()) << '('; 142 Visit(e.arg(), prec::UNKNOWN); 143 writer_ << ')'; 144 } 145 146 void VisitMinus(UnaryExpr e) { 147 writer_ << '-'; 148 Visit(e.arg()); 149 } 150 151 void VisitPow2(UnaryExpr e) { 152 Visit(e.arg(), prec::EXPONENTIATION + 1); 153 writer_ << " ^ 2"; 154 } 155 156 void VisitBinary(BinaryExpr e) { WriteBinary(e); } 157 void VisitBinaryFunc(BinaryExpr e); 158 void VisitIf(IfExpr e); 159 void VisitVarArg(VarArgExpr e) { WriteFunc(e); } 160 void VisitSum(SumExpr e); 161 void VisitCount(CountExpr e) { WriteFunc(e); } 162 void VisitNumberOf(NumberOfExpr e); 163 void VisitPLTerm(PLTerm e); 164 void VisitCall(CallExpr e); 165 void VisitVariable(Variable v) { writer_ << 'x' << (v.index() + 1); } 166 167 void VisitNot(NotExpr e) { 168 writer_ << '!'; 169 // Use a precedence higher then relational to print expressions 170 // as "!(x = y)" instead of "!x = y". 171 LogicalExpr arg = e.arg(); 172 Visit(arg, 173 precedence(arg) == prec::RELATIONAL ? prec::RELATIONAL + 1 : -1); 174 } 175 176 void VisitBinaryLogical(BinaryLogicalExpr e) { WriteBinary(e); } 177 void VisitRelational(RelationalExpr e) { WriteBinary(e); } 178 void VisitLogicalCount(LogicalCountExpr e); 179 void VisitIteratedLogical(IteratedLogicalExpr e); 180 void VisitImplication(ImplicationExpr e); 181 void VisitAllDiff(PairwiseExpr e) { WriteFunc(e); } 182 void VisitLogicalConstant(LogicalConstant c) { writer_ << c.value(); } 183 }; 184 185 template <typename ExprTypes> 186 ExprWriter<ExprTypes>::Parenthesizer::Parenthesizer( 187 ExprWriter<ExprTypes> &w, Expr e, int prec) 188 : writer_(w), write_paren_(false) { 189 saved_precedence_ = w.precedence_; 190 if (prec == -1) 191 prec = w.precedence_; 192 write_paren_ = precedence(e) < prec; 193 if (write_paren_) 194 w.writer_ << '('; 195 w.precedence_ = precedence(e); 196 } 197 198 template <typename ExprTypes> 199 ExprWriter<ExprTypes>::Parenthesizer::~Parenthesizer() { 200 writer_.precedence_ = saved_precedence_; 201 if (write_paren_) 202 writer_.writer_ << ')'; 203 } 204 205 template <typename ExprTypes> 206 template <typename Iter> 207 void ExprWriter<ExprTypes>::WriteArgs( 208 Iter begin, Iter end, const char *sep, int precedence) { 209 writer_ << '('; 210 if (begin != end) { 211 Visit(*begin, precedence); 212 for (++begin; begin != end; ++begin) { 213 writer_ << sep; 214 Visit(*begin, precedence); 215 } 216 } 217 writer_ << ')'; 218 } 219 220 template <typename ExprTypes> 221 template <typename ExprType> 222 void ExprWriter<ExprTypes>::WriteBinary(ExprType e) { 223 int prec = precedence(e); 224 bool right_associative = prec == prec::EXPONENTIATION; 225 Visit(e.lhs(), prec + (right_associative ? 1 : 0)); 226 writer_ << ' ' << str(e.kind()) << ' '; 227 Visit(e.rhs(), prec + (right_associative ? 0 : 1)); 228 } 229 230 template <typename ExprTypes> 231 void ExprWriter<ExprTypes>::WriteCallArg(Expr arg) { 232 if (NumericExpr e = ExprTypes::template Cast<NumericExpr>(arg)) { 233 Visit(e, prec::UNKNOWN); 234 return; 235 } 236 assert(arg.kind() == expr::STRING); 237 writer_ << "'"; 238 const char *s = ExprTypes::template Cast<StringLiteral>(arg).value(); 239 for ( ; *s; ++s) { 240 char c = *s; 241 switch (c) { 242 case '\n': 243 writer_ << '\\' << c; 244 break; 245 case '\'': 246 // Escape quote by doubling. 247 writer_ << c; 248 // Fall through. 249 default: 250 writer_ << c; 251 } 252 } 253 writer_ << "'"; 254 } 255 256 template <typename ExprTypes> 257 void ExprWriter<ExprTypes>::VisitBinaryFunc(BinaryExpr e) { 258 writer_ << str(e.kind()) << '('; 259 Visit(e.lhs(), prec::UNKNOWN); 260 writer_ << ", "; 261 Visit(e.rhs(), prec::UNKNOWN); 262 writer_ << ')'; 263 } 264 265 template <typename ExprTypes> 266 void ExprWriter<ExprTypes>::VisitIf(IfExpr e) { 267 writer_ << "if "; 268 Visit(e.condition(), prec::UNKNOWN); 269 writer_ << " then "; 270 NumericExpr else_expr = e.else_expr(); 271 bool has_else = !IsZero<ExprTypes>(else_expr); 272 Visit(e.then_expr(), prec::CONDITIONAL + (has_else ? 1 : 0)); 273 if (has_else) { 274 writer_ << " else "; 275 Visit(else_expr); 276 } 277 } 278 279 template <typename ExprTypes> 280 void ExprWriter<ExprTypes>::VisitSum(SumExpr e) { 281 writer_ << "/* sum */ ("; 282 typename SumExpr::iterator i = e.begin(), end = e.end(); 283 if (i != end) { 284 Visit(*i); 285 for (++i; i != end; ++i) { 286 writer_ << " + "; 287 Visit(*i); 288 } 289 } 290 writer_ << ')'; 291 } 292 293 template <typename ExprTypes> 294 void ExprWriter<ExprTypes>::VisitNumberOf(NumberOfExpr e) { 295 writer_ << "numberof "; 296 typename NumberOfExpr::iterator i = e.begin(); 297 Visit(*i++, prec::UNKNOWN); 298 writer_ << " in "; 299 WriteArgs(i, e.end()); 300 } 301 302 template <typename ExprTypes> 303 void ExprWriter<ExprTypes>::VisitPLTerm(PLTerm e) { 304 writer_ << "<<" << e.breakpoint(0); 305 for (int i = 1, n = e.num_breakpoints(); i < n; ++i) 306 writer_ << ", " << e.breakpoint(i); 307 writer_ << "; " << e.slope(0); 308 for (int i = 1, n = e.num_slopes(); i < n; ++i) 309 writer_ << ", " << e.slope(i); 310 writer_ << ">> "; 311 NumericExpr arg = e.arg(); 312 if (Variable var = ExprTypes::template Cast<Variable>(arg)) 313 writer_ << "x" << (var.index() + 1); 314 else 315 writer_ << "e" << ((ExprTypes::template Cast<CommonExpr>(arg)).index() + 1); 316 } 317 318 template <typename ExprTypes> 319 void ExprWriter<ExprTypes>::VisitCall(CallExpr e) { 320 writer_ << e.function().name() << '('; 321 typename CallExpr::iterator i = e.begin(), end = e.end(); 322 if (i != end) { 323 WriteCallArg(*i++); 324 for (; i != end; ++i) { 325 writer_ << ", "; 326 WriteCallArg(*i); 327 } 328 } 329 writer_ << ')'; 330 } 331 332 template <typename ExprTypes> 333 void ExprWriter<ExprTypes>::VisitLogicalCount(LogicalCountExpr e) { 334 writer_ << str(e.kind()) << ' '; 335 Visit(e.lhs()); 336 writer_ << ' '; 337 WriteArgs(e.rhs()); 338 } 339 340 template <typename ExprTypes> 341 void ExprWriter<ExprTypes>::VisitIteratedLogical(IteratedLogicalExpr e) { 342 // There is no way to produce an AMPL forall/exists expression because 343 // its indexing is not available any more. So we write a count expression 344 // instead with a comment about the original expression. 345 writer_ << "/* " << str(e.kind()) << " */ "; 346 int prec = prec::LOGICAL_AND + 1; 347 const char *op = " && "; 348 if (e.kind() == expr::EXISTS) { 349 prec = prec::LOGICAL_OR + 1; 350 op = " || "; 351 } 352 WriteArgs(e, op, prec); 353 } 354 355 template <typename ExprTypes> 356 void ExprWriter<ExprTypes>::VisitImplication(ImplicationExpr e) { 357 Visit(e.condition()); 358 writer_ << " ==> "; 359 Visit(e.then_expr(), prec::IMPLICATION + 1); 360 LogicalExpr else_expr = e.else_expr(); 361 LogicalConstant c = ExprTypes::template Cast<LogicalConstant>(else_expr); 362 if (!c || c.value() != 0) { 363 writer_ << " else "; 364 Visit(else_expr); 365 } 366 } 367 368 template <typename ExprTypes, typename LinearExpr, typename NumericExpr> 369 void WriteExpr(fmt::Writer &w, const LinearExpr &linear, 370 NumericExpr nonlinear) { 371 bool have_terms = false; 372 typedef typename LinearExpr::iterator Iterator; 373 for (Iterator i = linear.begin(), e = linear.end(); i != e; ++i) { 374 double coef = i->coef(); 375 if (coef != 0) { 376 if (have_terms) 377 w << " + "; 378 else 379 have_terms = true; 380 if (coef != 1) 381 w << coef << " * "; 382 w << "x" << (i->var_index() + 1); 383 } 384 } 385 if (!nonlinear || IsZero<ExprTypes>(nonlinear)) { 386 if (!have_terms) 387 w << "0"; 388 return; 389 } 390 if (have_terms) 391 w << " + "; 392 ExprWriter<ExprTypes>(w).Visit(nonlinear); 393 } 394 395 // Writes a problem in AMPL format. 396 template <typename Problem> 397 void Write(fmt::Writer &w, const Problem &p) { 398 // Write variables. 399 double inf = std::numeric_limits<double>::infinity(); 400 int num_vars = p.num_vars(); 401 for (int i = 0; i < num_vars; ++i) { 402 w << "var x" << (i + 1); 403 typename Problem::Variable var = p.var(i); 404 double lb = var.lb(), ub = var.ub(); 405 if (lb == ub) { 406 w << " = " << lb; 407 } else { 408 if (lb != -inf) 409 w << " >= " << lb; 410 if (ub != inf) 411 w << " <= " << ub; 412 } 413 w << ";\n"; 414 } 415 416 // Write objectives. 417 for (int i = 0, n = p.num_objs(); i < n; ++i) { 418 typename Problem::Objective obj = p.obj(i); 419 w << (obj.type() == mp::obj::MIN ? "minimize" : "maximize") << " o: "; 420 WriteExpr<typename Problem::ExprTypes>( 421 w, obj.linear_expr(), obj.nonlinear_expr()); 422 w << ";\n"; 423 } 424 425 // Write algebraic constraints. 426 for (int i = 0, n = p.num_algebraic_cons(); i < n; ++i) { 427 w << "s.t. c" << (i + 1) << ": "; 428 typename Problem::AlgebraicCon con = p.algebraic_con(i); 429 double lb = con.lb(), ub = con.ub(); 430 if (lb != ub && lb != -inf && ub != inf) 431 w << lb << " <= "; 432 WriteExpr<typename Problem::ExprTypes>( 433 w, con.linear_expr(), con.nonlinear_expr()); 434 if (lb == ub) 435 w << " = " << lb; 436 else if (ub != inf) 437 w << " <= " << ub; 438 else if (lb != -inf) 439 w << " >= " << lb; 440 w << ";\n"; 441 } 442 } 443 } // namespace mp 444 445 #endif // MP_EXPR_WRITER_H_ 446