Lattice Land Core Library
Loading...
Searching...
No Matches
ast.hpp
Go to the documentation of this file.
1// Copyright 2021 Pierre Talbot
2
3#ifndef LALA_CORE_AST_HPP
4#define LALA_CORE_AST_HPP
5
6#include "battery/utility.hpp"
7#include "battery/vector.hpp"
8#include "battery/string.hpp"
9#include "battery/tuple.hpp"
10#include "battery/variant.hpp"
11#include "battery/shared_ptr.hpp"
12#include "battery/unique_ptr.hpp"
13#include "sort.hpp"
14#include <optional>
15
16#ifdef _WINDOWS
17# undef DIFFERENCE // Avoid clash with #define in WinUser.h
18# undef IN // Avoid clash with #define in ntdef.h
19#endif
20
21namespace lala {
22
23/** A "logical variable" is just the name of the variable. */
24template<class Allocator>
25using LVar = battery::string<Allocator>;
26
27/** The kind of interpretation operations. */
28enum class IKind {
29 ASK,
30 TELL
31};
32
33/** We call an "abstract variable" the representation of a logical variable in an abstract domain.
34It is a pair of integers `(aty, vid)` where `aty` is the UID of the abstract element and `vid` is an internal identifier of the variable inside the abstract element.
35The mapping between logical variables and abstract variables is maintained in an environment (see `env.hpp`).
36An abstract variable always has a single name (or no name if it is not explicitly represented in the initial formula).
37But a logical variable can be represented by several abstract variables when the variable occurs in different abstract elements. */
38class AVar {
39 int value;
40public:
41 CUDA constexpr AVar(): value(-1) {}
42 constexpr AVar(const AVar&) = default;
43 constexpr AVar(AVar&&) = default;
44 constexpr AVar& operator=(const AVar&) = default;
45 constexpr AVar& operator=(AVar&&) = default;
46 CUDA constexpr bool operator==(const AVar& other) const {
47 return value == other.value;
48 }
49 CUDA constexpr bool operator!=(const AVar& other) const {
50 return value != other.value;
51 }
52
53 CUDA constexpr AVar(AType atype, int var_id): value((var_id << 8) | atype) {
54 assert(atype >= 0);
55 assert(var_id >= 0);
56 assert(atype < (1 << 8));
57 assert(var_id < (1 << 23));
58 }
59 CUDA constexpr AVar(AType atype, size_t var_id): AVar(atype, static_cast<int>(var_id)) {}
60
61 CUDA constexpr bool is_untyped() const {
62 return value == -1;
63 }
64
65 CUDA constexpr int aty() const {
66 return is_untyped() ? -1 : (value & ((1 << 8) - 1));
67 }
68
69 CUDA constexpr int vid() const {
70 return is_untyped() ? -1 : value >> 8;
71 }
72
73 CUDA constexpr void type_as(AType aty) {
74 value = (vid() << 8) | aty;
75 }
76};
77
78/** A first-order signature is a triple \f$ (X, F, P) \f$ where \f$ X \f$ is the set of variables, \f$ F \f$ the set of function symbols and \f$ P \f$ the set of predicates.
79 We represent \f$ X \f$ by strings (see `LVar`), while \f$ F \f$ and \f$ P \f$ are described in the following enumeration `Sig`.
80 For programming conveniency, we suppose that logical connectors are included in the set of predicates and thus are in the signature as well.
81 Finally, function symbols and predicates are at the "same level".
82 Hence a predicate can occur as the argument of a function, which is convenient when modelling, consider for example a cardinality constraint: \f$ ((x > 4) + (y < 4) + (z = 3)) \neq 2 \f$.
83
84 Symbols are sometimes overloaded across different universe of discourse.
85 For instance, `ADD` can be used over integers, reals and even set of integers (pairwise addition).
86
87 Division and modulus are defined as usual over continuous domains such as rational and real numbers.
88 However, it gets more tricky when defined over discrete domains such as integers and floating-point numbers, since there is not a single definition of division and modulus.
89 The various kinds of discrete divisions are explained in (Leijend D. (2003). Division and Modulus for Computer Scientists), and we add four of those definitions to the logical signature.
90 There are several use-cases of modulus and division:
91 * If you write a constraint model, you probably want to use euclidean division and modulus (EDIV, EMOD) as this is the most "mathematical" definition.
92 * If you intend to model the semantics of a programming language, you should use the same kind of division as the one present in your programming language (most likely truncated division).
93 */
94enum Sig {
95 ///@{
96 NEG, ABS, ///< Unary arithmetic function symbols.
97 ADD, SUB, MUL, POW, MIN, MAX, ///< Binary arithmetic function symbols.
98 SQRT, EXP, LN, ///< Square root, natural exponential and natural logarithm function symbols.
99 NROOT, LOG, ///< nth root and logarithm to base (both binary function symbols).
100 SIN, COS, TAN, ASIN, ACOS, ATAN, SINH, COSH, TANH, ASINH, ACOSH, ATANH, ///< Trigonometric unary function symbols.
101 DIV, MOD, ///< Division and modulus over continuous domains (e.g., floating-point numbers and rational).
102 TDIV, TMOD, ///< Truncated division, present in most programming languages, is defined as \f$ a\,\mathbf{tdiv}\,b = \mathit{trunc}(a/b) \f$, i.e., it rounds towards zero. Modulus is defined as \f$ a\,\mathbf{tmod}\,b = a - b * (a\,\mathbf{tdiv}\,b) \f$.
103 FDIV, FMOD, ///< Floor division (Knuth D. (1972). The Art of Computer Programming, Vol 1, Fundamental Algorithms), is defined as \f$ a\,\mathbf{fdiv}\,b = \lfloor a/b \rfloor \f$, i.e., it rounds towards negative infinity. Modulus is defined as \f$ a\,\mathbf{fmod}\,b = a - b * (a\,\mathbf{fdiv}\,b) \f$.
104 CDIV, CMOD, ///< Ceil division is defined as \f$ a\,\mathbf{cdiv}\,b = \lceil a/b \rceil \f$. Modulus is defined as \f$ a\,\mathbf{cmod}\,b = a - b * (a\,\mathbf{cdiv}\,b) \f$.
105 EDIV, EMOD, ///< Euclidean division (Boute T. R. (1992). The Euclidean definition of the functions div and mod). The properties satisfy by this division are: (1) \f$ a\,\mathbf{ediv}\,b \in \mathbb{Z} \f$, (2) \f$ a = b * (a\,\mathbf{ediv}\,b) + (a\,\mathbf{emod}\,b) \f$ and (3) \f$ 0 \leq a\,\mathbf{emod}\,b < |b|\f$. Further, note that Euclidean division satisfies \f$ a\,\mathbf{ediv}\,(-b) = -(a\,\mathbf{ediv}\,b) \f$ and \f$ a\,\mathbf{emod}\,(-b) = a\,\mathbf{emod}\,b \f$.
107 SUBSET, SUBSETEQ, SUPSET, SUPSETEQ, ///< Set inclusion predicates.
108 IN, ///< Set membership predicate.
109 CARD, ///< Cardinality function from set to integer.
110 HULL, ///< Unary function performing the convex hull of a set, e.g., \f$ \mathit{hull}(s) = \{x \;|\; \mathit{min}(s) \leq x \leq \mathit{max}(s) \} \f$.
111 CONVEX, ///< Unary predicate, requiring \f$ s = \mathit{hull}(s) \f$.
112 EQ, NEQ, ///< Equality relations.
113 LEQ, GEQ, LT, GT, ///< Arithmetic comparison predicates. When applied to set, it corresponds to the lexicographic ordering of the sorted set according the underlying natural ordering of the elements in the set.
114 AND, OR, IMPLY, EQUIV, NOT, XOR, ///< Logical connector.
115 ITE, ///< If-then-else
116 MAXIMIZE, ///< Unary "meta-predicate" indicating that its argument must be maximized, according to the increasing ordering of the underlying universe of discourse. This is not a predicate because it is defined on the solutions space of the whole formulas.
117 MINIMIZE ///< Same as MAXIMIZE, but for minimization.
118 ///@}
120
121CUDA NI inline const char* string_of_sig(Sig sig) {
122 switch(sig) {
123 case NEG: return "-";
124 case ABS: return "abs";
125 case ADD: return "+";
126 case SUB: return "-";
127 case MUL: return "*";
128 case DIV: return "/";
129 case TDIV: return "tdiv";
130 case FDIV: return "fdiv";
131 case CDIV: return "cdiv";
132 case EDIV: return "ediv";
133 case MOD: return "%%";
134 case TMOD: return "tmod";
135 case FMOD: return "fmod";
136 case CMOD: return "cmod";
137 case EMOD: return "emod";
138 case POW: return "^";
139 case SQRT: return "sqrt";
140 case EXP: return "exp";
141 case LN: return "ln";
142 case NROOT: return "nroot";
143 case LOG: return "log";
144 case SIN: return "sin";
145 case COS: return "cos";
146 case TAN: return "tan";
147 case ASIN: return "asin";
148 case ACOS: return "acos";
149 case ATAN: return "atan";
150 case SINH: return "sinh";
151 case COSH: return "cosh";
152 case TANH: return "tanh";
153 case ASINH: return "asinh";
154 case ACOSH: return "acosh";
155 case ATANH: return "atanh";
156 case MIN: return "min";
157 case MAX: return "max";
158 case UNION: return "\u222A";
159 case INTERSECTION: return "\u2229";
160 case DIFFERENCE: return "\\";
161 case SYMMETRIC_DIFFERENCE: return "\u2296";
162 case COMPLEMENT: return "complement";
163 case IN: return "\u2208";
164 case SUBSET: return "\u2282";
165 case SUBSETEQ: return "\u2286";
166 case SUPSET: return "\u2283";
167 case SUPSETEQ: return "\u2287";
168 case CARD: return "card";
169 case HULL: return "hull";
170 case CONVEX: return "convex";
171 case EQ: return "=";
172 case NEQ: return "\u2260";
173 case LEQ: return "\u2264";
174 case GEQ: return "\u2265";
175 case LT: return "<";
176 case GT: return ">";
177 case AND: return "\u2227";
178 case OR: return "\u2228";
179 case IMPLY: return "\u21D2";
180 case EQUIV: return "\u21D4";
181 case NOT: return "\u00AC";
182 case XOR: return "\u2295";
183 case ITE: return "ite";
184 case MAXIMIZE: return "maximize";
185 case MINIMIZE: return "minimize";
186 default:
187 assert(false);
188 return "<bug! unknown sig>";
189 }
190 }
191
192 CUDA NI inline const char* string_of_sig_txt(Sig sig) {
193 switch(sig) {
194 case NEG: return "neg";
195 case ADD: return "add";
196 case SUB: return "sub";
197 case MUL: return "mul";
198 case DIV: return "div";
199 case MOD: return "mod";
200 case POW: return "pow";
201 case UNION: return "union";
202 case INTERSECTION: return "intersection";
203 case DIFFERENCE: return "difference";
204 case SYMMETRIC_DIFFERENCE: return "symmetric_difference";
205 case IN: return "in";
206 case SUBSET: return "subset";
207 case SUBSETEQ: return "subseteq";
208 case SUPSET: return "supset";
209 case SUPSETEQ: return "supseteq";
210 case EQ: return "eq";
211 case NEQ: return "neq";
212 case LEQ: return "leq";
213 case GEQ: return "geq";
214 case LT: return "lt";
215 case GT: return "gt";
216 case AND: return "and";
217 case OR: return "or";
218 case IMPLY: return "imply";
219 case EQUIV: return "equiv";
220 case NOT: return "not";
221 case XOR: return "xor";
222 default: return string_of_sig(sig);
223 }
224 }
225
226 CUDA NI inline constexpr bool is_prefix(Sig sig) {
227 return sig == ABS || sig == SQRT || sig == EXP || sig == LN || sig == NROOT || sig == LOG || sig == SIN || sig == COS || sig == TAN || sig == ASIN || sig == ACOS || sig == ATAN || sig == SINH || sig == COSH || sig == TANH || sig == ASINH || sig == ACOSH || sig == ATANH || sig == MIN || sig == MAX || sig == COMPLEMENT || sig == CARD || sig == HULL || sig == CONVEX || sig == ITE || sig == MAXIMIZE || sig == MINIMIZE;
228 }
229
230 CUDA NI inline constexpr bool is_division(Sig sig) {
231 return sig == DIV || sig == TDIV || sig == EDIV || sig == FDIV || sig == CDIV;
232 }
233
234 CUDA NI inline constexpr bool is_modulo(Sig sig) {
235 return sig == MOD || sig == TMOD || sig == EMOD || sig == FMOD || sig == CMOD;
236 }
237
238 CUDA NI inline constexpr bool is_associative(Sig sig) {
239 return sig == ADD || sig == MUL || sig == AND || sig == OR || sig == EQUIV || sig == XOR
240 || sig == UNION || sig == INTERSECTION || sig == MAX || sig == MIN;
241 }
242
243 CUDA NI inline constexpr bool is_commutative(Sig sig) {
244 // All operators defined in `is_associative` are also commutative for now.
245 return is_associative(sig) || sig == EQ;
246 }
247
248 CUDA NI inline constexpr bool is_arithmetic_comparison(Sig sig) {
249 return sig == LEQ || sig == GEQ || sig == EQ || sig == NEQ || sig == GT || sig == LT;
250 }
251
252 CUDA NI inline constexpr bool is_logical(Sig sig) {
253 return sig == AND || sig == OR || sig == IMPLY || sig == EQUIV || sig == NOT || sig == XOR;
254 }
255
256 CUDA NI inline constexpr bool is_predicate(Sig sig) {
257 return sig == IN || sig == SUBSET || sig == SUBSETEQ || sig == SUPSET || sig == SUPSETEQ ||
258 sig == EQ || sig == NEQ || sig == LEQ || sig == GEQ || sig == LT || sig == GT;
259 }
260}
261
262namespace battery {
263 template<>
264 CUDA NI inline void print(const lala::Sig& sig) {
265 printf("%s", lala::string_of_sig(sig));
266 }
267}
268
269namespace lala {
270
271/** `TFormula` represents the AST of a typed first-order logical formula.
272In our context, the type of a formula is an integer representing the UID of an abstract domain in which the formula should to be interpreted.
273It defaults to the value `UNTYPED` if the formula is not (yet) typed.
274By default, the types of integer and real number are supported.
275The supported symbols can be extended with the template parameter `ExtendedSig`.
276This extended signature can also be used for representing exactly constant such as real numbers using a string.
277The AST of a formula is represented by a variant, where each alternative is described below.
278We represent everything at the same level (term, formula, predicate, variable, constant).
279This is generally convenient when modelling to avoid creating intermediate boolean variables when reifying.
280We can have `x + (x > y \/ y > x + 4) >= 1`.
281
282Differently from first-order logic, the existential quantifier does not have a subformula, i.e., we write \f$ \exists{x:Int} \land \exists{y:Int} \land x < y\f$.
283This semantics comes from "dynamic predicate logic" where a formula is interpreted in a context (here the abstract element).
284(The exact connection of our framework to dynamic predicate logic is not yet perfectly clear.) */
285template<class Allocator, class ExtendedSig = battery::string<Allocator>>
286class TFormula {
287public:
288 using allocator_type = Allocator;
290 using Sequence = battery::vector<this_type, Allocator>;
291 using Existential = battery::tuple<LVar<Allocator>, Sort<Allocator>>;
293 using Formula = battery::variant<
294 logic_bool, ///< Representation of Booleans.
295 logic_int, ///< Representation of integers.
296 logic_real, ///< Approximation of real numbers.
297 LogicSet, ///< Set of Booleans, integers, reals or sets.
298 AVar, ///< Abstract variable
299 LVar<Allocator>, ///< Logical variable
300 Existential, ///< Existential quantifier
301 battery::tuple<Sig, Sequence>, ///< ADD, SUB, ..., EQ, ..., AND, .., NOT
302 battery::tuple<ExtendedSig, Sequence> ///< see above
303 >;
304
305 /** Index of Booleans in the variant type `Formula` (called kind below). */
306 static constexpr size_t B = 0;
307
308 /** Index of integers in the variant type `Formula` (called kind below). */
309 static constexpr size_t Z = B + 1;
310
311 /** Index of real numbers in the variant type `Formula` (called kind below). */
312 static constexpr size_t R = Z + 1;
313
314 /** Index of sets in the variant type `Formula` (called kind below). */
315 static constexpr size_t S = R + 1;
316
317 /** Index of abstract variables in the variant type `Formula` (called kind below). */
318 static constexpr size_t V = S + 1;
319
320 /** Index of logical variables in the variant type `Formula` (called kind below). */
321 static constexpr size_t LV = V + 1;
322
323 /** Index of existential quantifier in the variant type `Formula` (called kind below). */
324 static constexpr size_t E = LV + 1;
325
326 /** Index of n-ary operators in the variant type `Formula` (called kind below). */
327 static constexpr size_t Seq = E + 1;
328
329 /** Index of n-ary operators where the operator is an extended signature in the variant type `Formula` (called kind below). */
330 static constexpr size_t ESeq = Seq + 1;
331
332private:
333 AType type_;
334 Formula formula;
335
336public:
337 /** By default, we initialize the formula to `true`. */
338 CUDA TFormula(): type_(UNTYPED), formula(Formula::template create<B>(true)) {}
339 CUDA TFormula(Formula&& formula): type_(UNTYPED), formula(std::move(formula)) {}
340 CUDA TFormula(AType uid, Formula&& formula): type_(uid), formula(std::move(formula)) {}
341
342 CUDA TFormula(const this_type& other): type_(other.type_), formula(other.formula) {}
343 CUDA TFormula(this_type&& other): type_(other.type_), formula(std::move(other.formula)) {}
344
345 template <class Alloc2, class ExtendedSig2>
346 friend class TFormula;
347
348 template <class Alloc2, class ExtendedSig2>
349 CUDA NI TFormula(const TFormula<Alloc2, ExtendedSig2>& other, const Allocator& allocator = Allocator())
350 : type_(other.type_), formula(Formula::template create<B>(true))
351 {
352 switch(other.formula.index()) {
353 case B: formula = Formula::template create<B>(other.b()); break;
354 case Z: formula = Formula::template create<Z>(other.z()); break;
355 case R: formula = Formula::template create<R>(other.r()); break;
356 case S: formula = Formula::template create<S>(LogicSet(other.s(), allocator));
357 break;
358 case V: formula = Formula::template create<V>(other.v()); break;
359 case LV: formula = Formula::template create<LV>(LVar<Allocator>(other.lv(), allocator)); break;
360 case E: formula = Formula::template create<E>(
361 battery::make_tuple(
362 LVar<Allocator>(battery::get<0>(other.exists()), allocator),
363 battery::get<1>(other.exists())));
364 break;
365 case Seq:
366 formula = Formula::template create<Seq>(
367 battery::make_tuple(
368 other.sig(),
369 Sequence(other.seq(), allocator)));
370 break;
371 case ESeq:
372 formula = Formula::template create<ESeq>(
373 battery::make_tuple(
374 ExtendedSig(other.esig(), allocator),
375 Sequence(other.eseq(), allocator)));
376 break;
377 default: printf("print: formula not handled.\n"); assert(false); break;
378 }
379 }
380
381 CUDA void swap(this_type& other) {
382 ::battery::swap(type_, other.type_);
383 ::battery::swap(formula, other.formula);
384 }
385
386 CUDA this_type& operator=(const this_type& rhs) {
387 this_type(rhs).swap(*this);
388 return *this;
389 }
390
392 this_type(std::move(rhs)).swap(*this);
393 return *this;
394 }
395
396 CUDA Formula& data() { return formula; }
397 CUDA const Formula& data() const { return formula; }
398 CUDA AType type() const { return type_; }
399 CUDA void type_as(AType ty) {
400 type_ = ty;
401 if(is(V)) {
402 v().type_as(ty);
403 }
404 }
405
406 CUDA constexpr bool is_untyped() const {
407 return type() == UNTYPED;
408 }
409
410 CUDA NI std::optional<Sort<allocator_type>> sort() const {
411 using sort_t = Sort<allocator_type>;
412 switch(formula.index()) {
413 case B: return sort_t(sort_t::Bool);
414 case Z: return sort_t(sort_t::Int);
415 case R: return sort_t(sort_t::Real);
416 case S: {
417 if(s().empty()) {
418 return {}; // Impossible to get the sort of the empty set.
419 }
420 for(int i = 0; i < s().size(); ++i) {
421 auto subsort = battery::get<0>(s()[i]).sort();
422 if(!subsort.has_value()) {
423 subsort = battery::get<1>(s()[i]).sort();
424 }
425 if(subsort.has_value()) {
426 return sort_t(sort_t::Set, std::move(*subsort) , s().get_allocator());
427 }
428 }
429 break;
430 }
431 case E: return battery::get<1>(exists());
432 }
433 return {};
434 }
435
436 CUDA static this_type make_true() { return TFormula(); }
437 CUDA static this_type make_false() { return TFormula(Formula::template create<B>(false)); }
438
439 CUDA static this_type make_bool(logic_bool b, AType atype = UNTYPED) {
440 return this_type(atype, Formula::template create<B>(b));
441 }
442
443 CUDA static this_type make_z(logic_int i, AType atype = UNTYPED) {
444 return this_type(atype, Formula::template create<Z>(i));
445 }
446
447 /** Create a term representing a real number which is approximated by interval [lb..ub].
448 By default the real number is supposedly over-approximated. */
449 CUDA static this_type make_real(double lb, double ub, AType atype = UNTYPED) {
450 return this_type(atype, Formula::template create<R>(battery::make_tuple(lb, ub)));
451 }
452
453 CUDA static this_type make_real(logic_real r, AType atype = UNTYPED) {
454 return this_type(atype, Formula::template create<R>(r));
455 }
456
457 CUDA static this_type make_set(LogicSet set, AType atype = UNTYPED) {
458 return this_type(atype, Formula::template create<S>(std::move(set)));
459 }
460
461 /** The type of the formula is embedded in `v`. */
462 CUDA static this_type make_avar(AVar v) {
463 return this_type(v.aty(), Formula::template create<V>(v));
464 }
465
466 CUDA static this_type make_avar(AType ty, int vid) {
467 return make_avar(AVar(ty, vid));
468 }
469
470 CUDA static this_type make_lvar(AType ty, LVar<Allocator> lvar) {
471 return this_type(ty, Formula::template create<LV>(std::move(lvar)));
472 }
473
475 return this_type(ty, Formula::template create<E>(battery::make_tuple(std::move(lvar), std::move(ctype))));
476 }
477
478 /** If `flatten` is `true` it will try to merge the children together to avoid nested formula. */
479 CUDA NI static this_type make_nary(Sig sig, Sequence children, AType atype = UNTYPED, bool flatten=true)
480 {
481 if(is_associative(sig) && flatten) {
482 Sequence seq{children.get_allocator()};
483 for(size_t i = 0; i < children.size(); ++i) {
484 if(children[i].is(Seq) && children[i].sig() == sig && children[i].type() == atype) {
485 for(size_t j = 0; j < children[i].seq().size(); ++j) {
486 seq.push_back(std::move(children[i].seq(j)));
487 }
488 }
489 else {
490 seq.push_back(std::move(children[i]));
491 }
492 }
493 return this_type(atype, Formula::template create<Seq>(battery::make_tuple(sig, std::move(seq))));
494 }
495 else {
496 return this_type(atype, Formula::template create<Seq>(battery::make_tuple(sig, std::move(children))));
497 }
498 /** The following code leads to bugs (accap_a4 segfaults, wordpress7_500 gives wrong answers).
499 * I don't know why, but it seems that the simplification is not always correct, perhaps in reified context?
500 * Or perhaps it is a question of atype? */
501 // if(seq.size() == 0) {
502 // if(sig == AND) return make_true();
503 // if(sig == OR) return make_false();
504 // }
505 // if(seq.size() == 1 && (sig == AND || sig == OR)) {
506 // return std::move(seq[0]);
507 // }
508 }
509
510 CUDA static this_type make_unary(Sig sig, TFormula child, AType atype = UNTYPED, const Allocator& allocator = Allocator()) {
511 return make_nary(sig, Sequence({std::move(child)}, allocator), atype);
512 }
513
514 CUDA static this_type make_binary(TFormula lhs, Sig sig, TFormula rhs, AType atype = UNTYPED, const Allocator& allocator = Allocator(), bool flatten=true) {
515 return make_nary(sig, Sequence({std::move(lhs), std::move(rhs)}, allocator), atype, flatten);
516 }
517
518 CUDA static this_type make_nary(ExtendedSig esig, Sequence children, AType atype = UNTYPED) {
519 return this_type(atype, Formula::template create<ESeq>(battery::make_tuple(std::move(esig), std::move(children))));
520 }
521
522 CUDA size_t index() const {
523 return formula.index();
524 }
525
526 CUDA bool is(size_t kind) const {
527 return formula.index() == kind;
528 }
529
530 CUDA bool is_true() const {
531 return (is(B) && b()) || (is(Z) && z() != 0);
532 }
533
534 CUDA bool is_false() const {
535 return (is(B) && !b()) || (is(Z) && z() == 0);
536 }
537
538 CUDA logic_int to_z() const {
539 assert(is(B) || is(Z));
540 return (is(B) ? (b() ? 1 : 0) : z());
541 }
542
543 CUDA bool is_constant() const {
544 return is(B) || is(Z) || is(R) || is(S);
545 }
546
547 CUDA bool is_variable() const {
548 return is(LV) || is(V);
549 }
550
551 CUDA bool is_unary() const {
552 return is(Seq) && seq().size() == 1;
553 }
554
555 CUDA bool is_binary() const {
556 return is(Seq) && seq().size() == 2;
557 }
558
559 CUDA logic_bool b() const {
560 return battery::get<B>(formula);
561 }
562
563 CUDA logic_int z() const {
564 return battery::get<Z>(formula);
565 }
566
567 CUDA const logic_real& r() const {
568 return battery::get<R>(formula);
569 }
570
571 CUDA const LogicSet& s() const {
572 return battery::get<S>(formula);
573 }
574
575 CUDA AVar v() const {
576 return battery::get<V>(formula);
577 }
578
579 CUDA const LVar<Allocator>& lv() const {
580 return battery::get<LV>(formula);
581 }
582
583 CUDA const Existential& exists() const {
584 return battery::get<E>(formula);
585 }
586
587 CUDA Sig sig() const {
588 return battery::get<0>(battery::get<Seq>(formula));
589 }
590
591 CUDA NI bool is_logical() const {
592 if(is(Seq)) {
593 return ::lala::is_logical(sig());
594 }
595 return false;
596 }
597
598 CUDA NI bool is_predicate() const {
599 if(is(Seq)) {
600 return ::lala::is_predicate(sig());
601 }
602 return false;
603 }
604
605 CUDA NI bool is_comparison() const {
606 if(is(Seq)) {
607 Sig s = sig();
609 }
610 return false;
611 }
612
613 CUDA const ExtendedSig& esig() const {
614 return battery::get<0>(battery::get<ESeq>(formula));
615 }
616
617 CUDA const Sequence& seq() const {
618 return battery::get<1>(battery::get<Seq>(formula));
619 }
620
621 CUDA const this_type& seq(size_t i) const {
622 return seq()[i];
623 }
624
625 CUDA const Sequence& eseq() const {
626 return battery::get<1>(battery::get<ESeq>(formula));
627 }
628
629 CUDA const this_type& eseq(size_t i) const {
630 return eseq()[i];
631 }
632
633 CUDA logic_bool& b() {
634 return battery::get<B>(formula);
635 }
636
637 CUDA logic_int& z() {
638 return battery::get<Z>(formula);
639 }
640
641 CUDA logic_real& r() {
642 return battery::get<R>(formula);
643 }
644
645 CUDA LogicSet& s() {
646 return battery::get<S>(formula);
647 }
648
649 CUDA AVar& v() {
650 return battery::get<V>(formula);
651 }
652
653 CUDA Sig& sig() {
654 return battery::get<0>(battery::get<Seq>(formula));
655 }
656
657 CUDA ExtendedSig& esig() {
658 return battery::get<0>(battery::get<ESeq>(formula));
659 }
660
661 CUDA Sequence& seq() {
662 return battery::get<1>(battery::get<Seq>(formula));
663 }
664
665 CUDA this_type& seq(size_t i) {
666 return seq()[i];
667 }
668
669 CUDA Sequence& eseq() {
670 return battery::get<1>(battery::get<ESeq>(formula));
671 }
672
673 CUDA this_type& eseq(size_t i) {
674 return eseq()[i];
675 }
676
677 CUDA NI this_type map_sig(Sig sig) const {
678 assert(is(Seq));
679 this_type f = *this;
680 f.sig() = sig;
681 return std::move(f);
682 }
683
684 CUDA NI this_type map_atype(AType aty) const {
685 this_type f = *this;
686 f.type_as(aty);
687 return std::move(f);
688 }
689
690private:
691 template <class Fun>
692 CUDA NI void inplace_map_(Fun fun, const this_type& parent) {
693 switch(formula.index()) {
694 case Seq: {
695 for(int i = 0; i < seq().size(); ++i) {
696 seq(i).inplace_map_(fun, *this);
697 }
698 break;
699 }
700 case ESeq: {
701 for(int i = 0; i < eseq().size(); ++i) {
702 eseq(i).inplace_map_(fun, *this);
703 }
704 break;
705 }
706 default: {
707 fun(*this, parent);
708 break;
709 }
710 }
711 }
712
713public:
714
715 /** In-place map of each leaf of the formula to a new leaf according to `fun`. */
716 template <class Fun>
717 CUDA NI void inplace_map(Fun fun) {
718 return inplace_map_(fun, *this);
719 }
720
721 /** Map of each leaf of the formula to a new leaf according to `fun`. */
722 template <class Fun>
723 CUDA NI this_type map(Fun fun) {
724 this_type copy(*this);
725 copy.inplace_map([&](this_type& f, const this_type& parent){ f = fun(f, parent); });
726 return std::move(copy);
727 }
728
729private:
730 template<size_t n>
731 CUDA NI void print_sequence(bool print_atype, bool top_level = false) const {
732 const auto& op = battery::get<0>(battery::get<n>(formula));
733 const auto& children = battery::get<1>(battery::get<n>(formula));
734 if(children.size() == 0) {
736 return;
737 }
738 if constexpr(n == Seq) {
739 if(children.size() == 1) {
740 if(op == ABS) printf("|");
741 else if(op == CARD) printf("#(");
742 else printf("%s(", string_of_sig(op));
743 children[0].print_impl(print_atype);
744 if(op == ABS) printf("|");
745 else if(op == CARD) printf(")");
746 else printf(")");
747 return;
748 }
749 }
750 bool isprefix = true;
751 if constexpr(n == Seq) {
752 isprefix = is_prefix(op);
753 }
754 if(isprefix) {
756 }
757 printf("(");
758 for(int i = 0; i < children.size(); ++i) {
759 children[i].print_impl(print_atype);
760 if(i < children.size() - 1) {
761 if(!isprefix) {
762 printf(" ");
764 printf(" ");
765 }
766 else {
767 printf(", ");
768 }
769 }
770 if constexpr(n == Seq) {
771 if(op == AND && top_level) {
772 printf("\n");
773 }
774 }
775 }
776 printf(")");
777 }
778
779 CUDA NI void print_impl(bool print_atype = true, bool top_level = false) const {
780 switch(formula.index()) {
781 case B:
782 printf("%s", b() ? "true" : "false");
783 break;
784 case Z:
785 printf("%lld", z());
786 break;
787 case R: {
788 const auto& r_lb = battery::get<0>(r());
789 const auto& r_ub = battery::get<1>(r());
790 if(r_lb == r_ub) {
791 printf("%.50lf", r_lb);
792 }
793 else {
794 printf("[%.50lf..%.50lf]", r_lb, r_ub);
795 }
796 break;
797 }
798 case S:
799 printf("{");
800 for(int i = 0; i < s().size(); ++i) {
801 const auto& lb = battery::get<0>(s()[i]);
802 const auto& ub = battery::get<1>(s()[i]);
803 if(lb == ub) {
804 lb.print(print_atype);
805 }
806 else {
807 printf("[");
808 lb.print(print_atype);
809 printf("..");
810 ub.print(print_atype);
811 printf("]");
812 }
813 if(i < s().size() - 1) {
814 printf(", ");
815 }
816 }
817 printf("}");
818 break;
819 case V:
820 printf("var(%d, %d)", v().vid(), v().aty());
821 break;
822 case LV:
823 lv().print();
824 break;
825 case E: {
826 if(print_atype) { printf("("); }
827 const auto& e = exists();
828 printf("var ");
829 battery::get<0>(e).print();
830 printf(":");
831 battery::get<1>(e).print();
832 if(print_atype) { printf(")"); }
833 break;
834 }
835 case Seq: print_sequence<Seq>(print_atype, top_level); break;
836 case ESeq: print_sequence<ESeq>(print_atype, top_level); break;
837 default: printf("print: formula not handled.\n"); assert(false); break;
838 }
839 if(print_atype) {
840 printf(":%d", type_);
841 }
842 }
843
844public:
845 CUDA void print(bool print_atype = false) const {
846 print_impl(print_atype, true);
847 }
848};
849
850template<typename Allocator, typename ExtendedSig>
852 return lhs.type() == rhs.type() && lhs.data() == rhs.data();
853}
854
855template<typename Allocator, typename ExtendedSig>
856CUDA bool operator!=(const TFormula<Allocator, ExtendedSig>& lhs, const TFormula<Allocator, ExtendedSig>& rhs) {
857 return !(lhs == rhs);
858}
859
860} // namespace lala
861#endif
Definition ast.hpp:38
CUDA constexpr int vid() const
Definition ast.hpp:69
CUDA constexpr int aty() const
Definition ast.hpp:65
CUDA constexpr AVar(AType atype, size_t var_id)
Definition ast.hpp:59
CUDA constexpr void type_as(AType aty)
Definition ast.hpp:73
constexpr AVar(const AVar &)=default
CUDA constexpr bool operator==(const AVar &other) const
Definition ast.hpp:46
constexpr AVar & operator=(const AVar &)=default
CUDA constexpr AVar(AType atype, int var_id)
Definition ast.hpp:53
constexpr AVar & operator=(AVar &&)=default
CUDA constexpr AVar()
Definition ast.hpp:41
CUDA constexpr bool is_untyped() const
Definition ast.hpp:61
constexpr AVar(AVar &&)=default
Definition b.hpp:10
Definition ast.hpp:286
static constexpr size_t Seq
Definition ast.hpp:327
CUDA const Sequence & eseq() const
Definition ast.hpp:625
CUDA logic_int to_z() const
Definition ast.hpp:538
CUDA logic_bool & b()
Definition ast.hpp:633
battery::vector< this_type, Allocator > Sequence
Definition ast.hpp:290
CUDA Sig sig() const
Definition ast.hpp:587
CUDA TFormula(this_type &&other)
Definition ast.hpp:343
friend class TFormula
Definition ast.hpp:346
CUDA TFormula(Formula &&formula)
Definition ast.hpp:339
static CUDA this_type make_exists(AType ty, LVar< Allocator > lvar, Sort< Allocator > ctype)
Definition ast.hpp:474
CUDA const logic_real & r() const
Definition ast.hpp:567
CUDA NI this_type map_sig(Sig sig) const
Definition ast.hpp:677
CUDA bool is_binary() const
Definition ast.hpp:555
CUDA NI void inplace_map(Fun fun)
Definition ast.hpp:717
CUDA NI TFormula(const TFormula< Alloc2, ExtendedSig2 > &other, const Allocator &allocator=Allocator())
Definition ast.hpp:349
CUDA this_type & operator=(this_type &&rhs)
Definition ast.hpp:391
CUDA LogicSet & s()
Definition ast.hpp:645
static CUDA this_type make_set(LogicSet set, AType atype=UNTYPED)
Definition ast.hpp:457
static constexpr size_t R
Definition ast.hpp:312
CUDA AVar & v()
Definition ast.hpp:649
static CUDA this_type make_false()
Definition ast.hpp:437
static CUDA this_type make_true()
Definition ast.hpp:436
TFormula< Allocator, ExtendedSig > this_type
Definition ast.hpp:289
CUDA bool is_true() const
Definition ast.hpp:530
CUDA Formula & data()
Definition ast.hpp:396
static CUDA this_type make_z(logic_int i, AType atype=UNTYPED)
Definition ast.hpp:443
CUDA this_type & eseq(size_t i)
Definition ast.hpp:673
CUDA logic_real & r()
Definition ast.hpp:641
CUDA const Sequence & seq() const
Definition ast.hpp:617
CUDA NI std::optional< Sort< allocator_type > > sort() const
Definition ast.hpp:410
CUDA bool is_false() const
Definition ast.hpp:534
static CUDA this_type make_real(double lb, double ub, AType atype=UNTYPED)
Definition ast.hpp:449
battery::tuple< LVar< Allocator >, Sort< Allocator > > Existential
Definition ast.hpp:291
static constexpr size_t S
Definition ast.hpp:315
static CUDA this_type make_unary(Sig sig, TFormula child, AType atype=UNTYPED, const Allocator &allocator=Allocator())
Definition ast.hpp:510
CUDA NI bool is_logical() const
Definition ast.hpp:591
CUDA logic_bool b() const
Definition ast.hpp:559
CUDA bool is_variable() const
Definition ast.hpp:547
CUDA bool is_unary() const
Definition ast.hpp:551
CUDA bool is(size_t kind) const
Definition ast.hpp:526
CUDA const this_type & eseq(size_t i) const
Definition ast.hpp:629
static CUDA this_type make_nary(ExtendedSig esig, Sequence children, AType atype=UNTYPED)
Definition ast.hpp:518
CUDA ExtendedSig & esig()
Definition ast.hpp:657
CUDA this_type & seq(size_t i)
Definition ast.hpp:665
static constexpr size_t V
Definition ast.hpp:318
static CUDA this_type make_bool(logic_bool b, AType atype=UNTYPED)
Definition ast.hpp:439
CUDA bool is_constant() const
Definition ast.hpp:543
CUDA void type_as(AType ty)
Definition ast.hpp:399
CUDA const LVar< Allocator > & lv() const
Definition ast.hpp:579
CUDA Sig & sig()
Definition ast.hpp:653
static CUDA this_type make_binary(TFormula lhs, Sig sig, TFormula rhs, AType atype=UNTYPED, const Allocator &allocator=Allocator(), bool flatten=true)
Definition ast.hpp:514
CUDA AType type() const
Definition ast.hpp:398
static constexpr size_t B
Definition ast.hpp:306
CUDA TFormula(const this_type &other)
Definition ast.hpp:342
Allocator allocator_type
Definition ast.hpp:288
CUDA const LogicSet & s() const
Definition ast.hpp:571
CUDA Sequence & eseq()
Definition ast.hpp:669
CUDA constexpr bool is_untyped() const
Definition ast.hpp:406
static CUDA this_type make_real(logic_real r, AType atype=UNTYPED)
Definition ast.hpp:453
CUDA this_type & operator=(const this_type &rhs)
Definition ast.hpp:386
static constexpr size_t ESeq
Definition ast.hpp:330
logic_set< this_type > LogicSet
Definition ast.hpp:292
static CUDA this_type make_lvar(AType ty, LVar< Allocator > lvar)
Definition ast.hpp:470
CUDA Sequence & seq()
Definition ast.hpp:661
CUDA AVar v() const
Definition ast.hpp:575
CUDA NI this_type map_atype(AType aty) const
Definition ast.hpp:684
CUDA NI bool is_comparison() const
Definition ast.hpp:605
CUDA TFormula(AType uid, Formula &&formula)
Definition ast.hpp:340
CUDA TFormula()
Definition ast.hpp:338
CUDA NI bool is_predicate() const
Definition ast.hpp:598
static CUDA this_type make_avar(AType ty, int vid)
Definition ast.hpp:466
CUDA const this_type & seq(size_t i) const
Definition ast.hpp:621
CUDA void print(bool print_atype=false) const
Definition ast.hpp:845
CUDA void swap(this_type &other)
Definition ast.hpp:381
CUDA logic_int z() const
Definition ast.hpp:563
CUDA const ExtendedSig & esig() const
Definition ast.hpp:613
battery::variant< logic_bool, logic_int, logic_real, LogicSet, AVar, LVar< Allocator >, Existential, battery::tuple< Sig, Sequence >, battery::tuple< ExtendedSig, Sequence > > Formula
Definition ast.hpp:303
CUDA NI this_type map(Fun fun)
Definition ast.hpp:723
CUDA const Formula & data() const
Definition ast.hpp:397
CUDA size_t index() const
Definition ast.hpp:522
CUDA const Existential & exists() const
Definition ast.hpp:583
static constexpr size_t E
Definition ast.hpp:324
static constexpr size_t LV
Definition ast.hpp:321
static CUDA this_type make_avar(AVar v)
Definition ast.hpp:462
CUDA static NI this_type make_nary(Sig sig, Sequence children, AType atype=UNTYPED, bool flatten=true)
Definition ast.hpp:479
CUDA logic_int & z()
Definition ast.hpp:637
static constexpr size_t Z
Definition ast.hpp:309
Definition ast.hpp:262
CUDA NI void print(const lala::Sig &sig)
Definition ast.hpp:264
Definition abstract_deps.hpp:14
CUDA NI constexpr bool is_commutative(Sig sig)
Definition ast.hpp:243
battery::tuple< double, double > logic_real
Definition sort.hpp:119
CUDA NI const char * string_of_sig_txt(Sig sig)
Definition ast.hpp:192
bool logic_bool
Definition sort.hpp:109
long long int logic_int
Definition sort.hpp:114
CUDA constexpr bool operator==(const CartesianProduct< As... > &a, const CartesianProduct< Bs... > &b)
Definition cartesian_product.hpp:504
CUDA NI bool is_arithmetic_comparison(const F &f)
Definition algorithm.hpp:360
CUDA NI constexpr bool is_associative(Sig sig)
Definition ast.hpp:238
Sig
Definition ast.hpp:94
@ HULL
Unary function performing the convex hull of a set, e.g., .
Definition ast.hpp:110
@ XOR
Logical connector.
Definition ast.hpp:114
@ SIN
Unary arithmetic function symbols.
Definition ast.hpp:100
@ ITE
If-then-else.
Definition ast.hpp:115
@ NEQ
Equality relations.
Definition ast.hpp:112
@ SYMMETRIC_DIFFERENCE
Unary arithmetic function symbols.
Definition ast.hpp:106
@ LEQ
Unary arithmetic function symbols.
Definition ast.hpp:113
@ NOT
Unary arithmetic function symbols.
Definition ast.hpp:114
@ ACOS
Unary arithmetic function symbols.
Definition ast.hpp:100
@ IMPLY
Unary arithmetic function symbols.
Definition ast.hpp:114
@ TANH
Unary arithmetic function symbols.
Definition ast.hpp:100
@ TMOD
Truncated division, present in most programming languages, is defined as , i.e., it rounds towards ze...
Definition ast.hpp:102
@ ATAN
Unary arithmetic function symbols.
Definition ast.hpp:100
@ ASIN
Unary arithmetic function symbols.
Definition ast.hpp:100
@ CARD
Cardinality function from set to integer.
Definition ast.hpp:109
@ SUPSETEQ
Set inclusion predicates.
Definition ast.hpp:107
@ MOD
Division and modulus over continuous domains (e.g., floating-point numbers and rational).
Definition ast.hpp:101
@ DIFFERENCE
Unary arithmetic function symbols.
Definition ast.hpp:106
@ ATANH
Trigonometric unary function symbols.
Definition ast.hpp:100
@ CONVEX
Unary predicate, requiring .
Definition ast.hpp:111
@ UNION
Unary arithmetic function symbols.
Definition ast.hpp:106
@ OR
Unary arithmetic function symbols.
Definition ast.hpp:114
@ EQ
Unary arithmetic function symbols.
Definition ast.hpp:112
@ ACOSH
Unary arithmetic function symbols.
Definition ast.hpp:100
@ NROOT
Unary arithmetic function symbols.
Definition ast.hpp:99
@ GEQ
Unary arithmetic function symbols.
Definition ast.hpp:113
@ ADD
Unary arithmetic function symbols.
Definition ast.hpp:97
@ IN
Set membership predicate.
Definition ast.hpp:108
@ COS
Unary arithmetic function symbols.
Definition ast.hpp:100
@ POW
Unary arithmetic function symbols.
Definition ast.hpp:97
@ MIN
Unary arithmetic function symbols.
Definition ast.hpp:97
@ INTERSECTION
Unary arithmetic function symbols.
Definition ast.hpp:106
@ LN
Square root, natural exponential and natural logarithm function symbols.
Definition ast.hpp:98
@ SINH
Unary arithmetic function symbols.
Definition ast.hpp:100
@ EDIV
Unary arithmetic function symbols.
Definition ast.hpp:105
@ DIV
Unary arithmetic function symbols.
Definition ast.hpp:101
@ GT
Arithmetic comparison predicates. When applied to set, it corresponds to the lexicographic ordering o...
Definition ast.hpp:113
@ FMOD
Floor division (Knuth D. (1972). The Art of Computer Programming, Vol 1, Fundamental Algorithms),...
Definition ast.hpp:103
@ MAX
Binary arithmetic function symbols.
Definition ast.hpp:97
@ SQRT
Unary arithmetic function symbols.
Definition ast.hpp:98
@ LT
Unary arithmetic function symbols.
Definition ast.hpp:113
@ TDIV
Unary arithmetic function symbols.
Definition ast.hpp:102
@ FDIV
Unary arithmetic function symbols.
Definition ast.hpp:103
@ EXP
Unary arithmetic function symbols.
Definition ast.hpp:98
@ COMPLEMENT
Set functions.
Definition ast.hpp:106
@ TAN
Unary arithmetic function symbols.
Definition ast.hpp:100
@ SUBSETEQ
Unary arithmetic function symbols.
Definition ast.hpp:107
@ AND
Unary arithmetic function symbols.
Definition ast.hpp:114
@ MAXIMIZE
Unary "meta-predicate" indicating that its argument must be maximized, according to the increasing or...
Definition ast.hpp:116
@ SUBSET
Unary arithmetic function symbols.
Definition ast.hpp:107
@ MINIMIZE
Same as MAXIMIZE, but for minimization.
Definition ast.hpp:117
@ EQUIV
Unary arithmetic function symbols.
Definition ast.hpp:114
@ ABS
Unary arithmetic function symbols.
Definition ast.hpp:96
@ ASINH
Unary arithmetic function symbols.
Definition ast.hpp:100
@ SUB
Unary arithmetic function symbols.
Definition ast.hpp:97
@ SUPSET
Unary arithmetic function symbols.
Definition ast.hpp:107
@ COSH
Unary arithmetic function symbols.
Definition ast.hpp:100
@ MUL
Unary arithmetic function symbols.
Definition ast.hpp:97
@ CMOD
Ceil division is defined as . Modulus is defined as .
Definition ast.hpp:104
@ LOG
nth root and logarithm to base (both binary function symbols).
Definition ast.hpp:99
@ CDIV
Unary arithmetic function symbols.
Definition ast.hpp:104
@ NEG
Unary arithmetic function symbols.
Definition ast.hpp:96
@ EMOD
Euclidean division (Boute T. R. (1992). The Euclidean definition of the functions div and mod)....
Definition ast.hpp:105
battery::vector< battery::tuple< F, F >, typename F::allocator_type > logic_set
Definition sort.hpp:127
int AType
Definition sort.hpp:18
CUDA NI constexpr bool is_prefix(Sig sig)
Definition ast.hpp:226
CUDA NI constexpr bool is_predicate(Sig sig)
Definition ast.hpp:256
CUDA NI const char * string_of_sig(Sig sig)
Definition ast.hpp:121
CUDA NI constexpr bool is_division(Sig sig)
Definition ast.hpp:230
IKind
Definition ast.hpp:28
battery::string< Allocator > LVar
Definition ast.hpp:25
CUDA NI constexpr bool is_logical(Sig sig)
Definition ast.hpp:252
CUDA NI constexpr bool is_modulo(Sig sig)
Definition ast.hpp:234
#define UNTYPED
Definition sort.hpp:21
Definition sort.hpp:26