Boolean symbolic expressions

[mkoeppe]

As proposed in ​https://groups.google.com/g/sage-devel/c/U_WGbYG2zOE/m/yq-EDEXDAgAJ

We add symbolic functions and_symbolic, or_symbolic, not_symbolic; the first two are also accessible by repurposing the operators bitwise-and & and bitwise-or |.

By extending the expression parser to also handle & (equivalently, infix and), | (equivalently, infix or), and ~ (equivalently, prefix not), these constructions can also be obtained as a conversion from maxima and giac expression strings.

One application is for the coordinate restrictions of a Chart.

[mkoeppe]

Here's an attempt

---

New commits:

​863c636

sage.functions.boolean.AndSymbolic: New

[charpent]

Replying to mkoeppe:

Here's an attempt

---

New commits:

​863c636

sage.functions.boolean.AndSymbolic: New

I'll test that tomorrow. A couple remarks :

• eval can be farmed out to sympy's And (one of the goals of this addition being the ability to use Sympy's Piecewise expressions of integrals and ODE solutions, often involving logical expressions...). I was originally aiming at wrapping Sympy's logical functions, but got stopped by :

• The showstopper problem I haven't been able to solve yet is translation to Maxima and backtranslation.

This is utterly necessary if you want to keep logical symbolic expressions (or symbolic expressions involving logical parts, as in case calls) simplifyable (other Expression methods are also farmed out to Maxima...).

OTOH, maxima_calculus should be easier, since this interface works "naturally" with the Lisp function tree representing Maxima expressions.

• Translation to Mathematica and Sympy should be trivial (give the names in a conversions argument). I don't know (yet) what is offered by giac and fricas, but maintaining universal translatability seems highly desirable...

HTH,

[egourgoulhon]

Replying to mkoeppe:

One application is for the restrictions of a Chart.

May I ask which application?

[mkoeppe]

Right now, chart restrictions have an ad-hoc representation as nested lists and tuples of symbolic relation expressions; this could be replaced by the corresponding boolean expressions (instances of AndSymbolic, OrSymbolic)

[egourgoulhon]

Replying to mkoeppe:

Right now, chart restrictions have an ad-hoc representation as nested lists and tuples of symbolic relation expressions; this could be replaced by the corresponding boolean expressions (instances of AndSymbolic, OrSymbolic)

Ah yes, this would be nice! Thanks for your answer.

[mkoeppe]

For converting to maxima, some help would be welcome. My last failed attempt looked like this:

src/sage/functions/boolean.py

@@ -31 +31 @@
 
         """
         BuiltinFunction.__init__(self, 'and_symbolic', nargs=0,
-                                 conversions=dict(sympy='And'))
+                                 conversions=dict(sympy='And',
+                                                  maxima='andsymbolic'))
 
     def _eval_(self, *args):
 

src/sage/interfaces/maxima_lib.py

@@ -113 +113 @@
 ecl_eval("(remprop 'mfactorial 'grind)") # don't use ! for factorials (#11539)
 ecl_eval("(setf $errormsg nil)")
 
+ecl_eval("(defmfun $andsymbolic (&rest args) (simplify (cons '(mand) args)))")
+
+
 # the following is a direct adaptation of the definition of "retrieve"
 # in the Maxima file macsys.lisp. This routine is normally responsible
 # for displaying a question and returning the answer. We change it to
@@ -1213 +1216 @@
     sage.symbolic.expression.operator.neg : "MMINUS",
     sage.symbolic.expression.operator.pow : "MEXPT",
     sage.symbolic.expression.operator.or_ : "MOR",
-    sage.symbolic.expression.operator.and_ : "MAND",
+    #sage.symbolic.expression.operator.and_ : "MAND",

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​106cc8f

sage.functions.boolean.AndSymbolic: New

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​859a969

RealSet: Handle symbolic 'and' input

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​0dca442

ConditionSet: flattens symbolic 'and's

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​9427892	Parser.p_atom: Accept parenthesized equations
​a222684	Tokenizer: Tokenize infix '&' or 'and' as '&'
​1741468	fixup atom
​2866ee7	Parser.p_eqn: Accept chains of equations

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​b8f5bf1	Parser.p_eqn: Handle logical and
​fb3f9d0	AndSymbolic._eval_: Weaken simplifications to not trigger equality test

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​9300284	sage.functions.boolean.or_symbolic: New
​e2c4470	src/sage/misc/parser.pyx: Handle '|', 'or'
​6b9adbf	src/sage/interfaces/sympy.py: Fixup _sympysage_and, add _sympysage_or

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​8e10ed3

AndSymbolic, OrSymbolic: Use new function _trivial_bool for simplification

[egourgoulhon]

Thank you for implementing this!

It seems that there is no entry for the new symbolic boolean operators in the reference manual. There should probably be more examples of use. A few naive trials:

sage: var('x y')
(x, y)
sage: s = x>0 & y<0
TypeError: unsupported operand type(s) for &: 'sage.symbolic.expression.Expression'
 and 'sage.symbolic.expression.Expression'

sage: from sage.functions.boolean import and_symbolic
sage: s = and_symbolic(x>0, y<0)
sage: bool(s.subs({x: 1, y: -2}))
TypeError: unable to make sense of Maxima expression 'and_symbolic(1>0,-2<0)'
 in Sage

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​0611026

Expression.__and__, __or__: New

[mkoeppe]

Replying to egourgoulhon:

sage: var('x y')
(x, y)
sage: s = x>0 & y<0
TypeError: unsupported operand type(s) for &: 'sage.symbolic.expression.Expression'
 and 'sage.symbolic.expression.Expression'

The & operator is now implemented -- note that due to Python operator precedence, the operands need to be put in parentheses:

sage: var('x y') 
(x, y) 
sage: (x>0) & (y<0)                                                                                                                                                            
and_symbolic(x > 0, y < 0)

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​a839cdf

AndSymbolic, OrSymbolic: Flatten nested calls

[charpent]

This is work in progress, no ?

• A symbolic_not is necessary. It might implement De Morgan's equalities (or this could be delegated to .expand and .factor, or, alternatively delegated to the ​logical functions).

• These functions currently do nothing :

{{{sage: var("a, b") (a, b) sage: and_symbolic((a>0), (b<0))

---

NameError? Traceback (most recent call last) <ipython-input-2-67fb44f33113> in <module>

---

NameError?: name 'and_symbolic' is not defined sage: (a>0) & (b<0) and_symbolic(a > 0, b < 0) sage: ((a>0) & (b<0)).subs(a==3) and_symbolic(3 > 0, b < 0) }}}

Compare :

sage: ((a>0) & (b<0)).subs(a==3)._sympy_().simplify()._sage_()                  
b < 0
sage: sympy.Not(sympy.And(a._sympy_(), b._sympy_()))                            
~(a & b)
sage: sympy.Not(sympy.And(a._sympy_(), b._sympy_())).simplify()                 
~a | ~b

==> needs_work

---

New commits:

​a839cdf

AndSymbolic, OrSymbolic: Flatten nested calls

[mkoeppe]

Replying to charpent:

This is work in progress, no ?

Yes; setting it to "needs review" allows the patchbot to run

[mkoeppe]

and_symbolic is not a global binding -- you need to import it to use it, or the NameError shows up. See doctests

[mkoeppe]

Replying to charpent:

• A symbolic_not is necessary.

Yes, good point; any help with implementing it is welcome...

[mkoeppe]

Do we want and_symbolic, or_symbolic, not_symbolic as global bindings?

(The names are modeled after the existing min_symbolic, max_symbolic.)

In particular, for not_symbolic, we cannot rely on an operator to make it available: Sage already repurposes the bitwise inversion operator ~ for multiplicative inversion.

[charpent]

Replying to mkoeppe:

and_symbolic is not a global binding -- you need to import it to use it, or the NameError shows up. See doctests

and_symbolic is a tad heavy to be exported. However, global And, Or and Not would be welcome...

BTW, that's how they are known in Sympy...

[mkoeppe]

But capitalized And, Or, Not seem out of line with our naming scheme for symbolic functions - they are all lowercase if I'm not mistaken.

[mkoeppe]

(see src/sage/functions/all.py)

[mkoeppe]

For extending sage.misc.parser, I would follow sage.logic.logicparser (even though I am not sure of its relevance), which uses ~ for logical 'not'. (It also uses -> and <-> for implication/equivalence; and (incompatible with the expression parser) ^ for logical 'xor'.)

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​0a26b5d	Parser.p_eqn: Update doctest output for nested and_symbolic
​5505b38	Tokenizer: Tokenize 'not' and '~' as '~'

[charpent]

Replying to mkoeppe:

For extending sage.misc.parser, I would follow sage.logic.logicparser (even though I am not sure of its relevance), which uses ~ for logical 'not'. (It also uses -> and <-> for implication/equivalence; and (incompatible with the expression parser) ^ for logical 'xor'.)

This would entail conditioning the interpretation of ~ to the type of its arguments, which is fishy : ~(x>0) is indubitably a logical expression, but ~(x>0).subs(x==0) could be understood as ~True}}}, which is ... -2 (!).

Not can be unambiguous, and nine characters lighter than "symbolic_not" ; furthermore, "our naming scheme for symbolic functions" is a scheme, not Gospel...

---

New commits:

​0a26b5d	Parser.p_eqn: Update doctest output for nested and_symbolic
​5505b38	Tokenizer: Tokenize 'not' and '~' as '~'

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​bb06156

src/doc/en/reference/functions/index.rst: Add sage/functions/boolean

[mkoeppe]

Replying to charpent:

Replying to mkoeppe:

For extending sage.misc.parser, I would follow sage.logic.logicparser (even though I am not sure of its relevance), which uses ~ for logical 'not'. [...]

This would entail conditioning the interpretation of ~ [...]

Note, this is just for the expression parser, not for Python semantics.

As I said in comment:29, we cannot use Python operators to make the operation available. We agree here.

[mkoeppe]

Replying to charpent:

Not can be unambiguous, and nine characters lighter than "symbolic_not" ;

It would be not_symbolic, which is discoverable by typing not<TAB> and autocompletes from not_<TAB>, so I don't think the length is a significant burden.

[charpent]

Replying to mkoeppe:

Replying to charpent:

Replying to mkoeppe:

For extending sage.misc.parser, I would follow sage.logic.logicparser (even though I am not sure of its relevance), which uses ~ for logical 'not'. [...]

This would entail conditioning the interpretation of ~ [...]

Note, this is just for the expression parser, not for Python semantics.

As I said in comment:29, we cannot use Python operators to make the operation available. We agree here.

Possible alternatives :

• forget operators, and limit this functionality to logic functions.

• Borrow inspiration from R and create &&, || and possibly ~~ operators (analogous to our representation of bit XOR as ^^).

IMHO, a functional representatin is the most useful...

[mkoeppe]

Replying to charpent:

create &&, || and possibly ~~ operators (analogous to our representation of bit XOR as ^^).

You mean in the preparser? I'll not touch that.

In just Python, creating new operators such as && is not possible.

[charpent]

Something is fishhy in the maxima>Sage conversion :

sage: maxima("(a>0) and (b<0)")                                                 
a>0andb<0
sage: maxima("(a>0) and (b<0)")._sage_()                                        
and_symbolic(a > 0, 0 < 0)

• The second clause is ill-translated

• the operator's translation should be & (or a call to symbolic_and or And).

[mkoeppe]

Yes, see comment:10 -- I have not figured out maxima conversion -- hoping for help from the experts

[mkoeppe]

sage: maxima("(a>0) and (b<0)")                                                 
a>0andb<0

Didn't you fix the whitespace-eating behavior some time recently?

[mkoeppe]

Note

sage: sage.calculus.calculus.symbolic_expression_from_string("a>0andb<0", accept_sequence=True)                          
and_symbolic(a > 0, 0 < 0)
sage: sage.calculus.calculus.symbolic_expression_from_string("a>0and b<0", accept_sequence=True)                         
and_symbolic(a > 0, b < 0)
sage: sage.calculus.calculus.symbolic_expression_from_string("0andb", accept_sequence=True)                              
0

[mkoeppe]

Our expression parser has poor error checking and silently ignores unexpected trailing tokens in some situations:

sage: sage.calculus.calculus.symbolic_expression_from_string("0fffffif", accept_sequence=True)                           
0

[mkoeppe]

Actually, this is just implicit multiplication 0*fffffif, which gets simplified to 0.

[mkoeppe]

Replying to mkoeppe:

sage: maxima("(a>0) and (b<0)")                                                 
a>0andb<0

Didn't you fix the whitespace-eating behavior some time recently?

I see, that's #31796, which appears to be stuck

[charpent]

Replying to mkoeppe:

sage: maxima("(a>0) and (b<0)")                                                 
a>0andb<0

Didn't you fix the whitespace-eating behavior some time recently?

I tried. But this patch entailed other bugs, which I hanven't yet understood == back to the old drawing board...

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​b5e4168	Trac #32315: support iteration and enumerated sets
​e0a8145	Merge #32315
​767e89a	Ticket #31796 : make maxima output parseable.
​d7abbe6	MaximaAbstract._commands: Remove whitespace in apropos output before breaking it apart
​644d831	Merge #31796

[mkoeppe]

Now, with the repaired #31796 merged, the problem is fixed:

sage: maxima("(a>0) and (b<0)")                                                                                    
a > 0 and b < 0
sage: maxima("(a>0) and (b<0)")._sage_()                                                                           
and_symbolic(a > 0, b < 0)

[mkoeppe]

I'm setting this again to needs_review so that the patchbot runs; obviously more work is needed.

[charpent]

Replying to mkoeppe:

Now, with the repaired #31796 merged, the problem is fixed:

sage: maxima("(a>0) and (b<0)")                                                                                    
a > 0 and b < 0
sage: maxima("(a>0) and (b<0)")._sage_()                                                                           
and_symbolic(a > 0, b < 0)

Thanks a lot ; I was searching in that direction, but missed the target you reached masterfully. Kudos !

BTW : "something" translating Maxima's is would be as useful as a translation of Maxima's and, or and not, necessary for the present ticket :

(%i3) is(a>2);
(%o3)                               unknown
(%i4) is(subst([a=3],a>2));
(%o4)                                true

Not coincidentally, it has the same Sage syntax collision problem...

Shouldn't it be added to this ticket ? Alternatively, we could create a new ticket for this and and depend on it.

[mkoeppe]

Could you elaborate on is? What collides with what?

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​f1e2fe0	NotSymbolic, not_symbolic: New
​f492321	src/sage/symbolic/expression_conversions.py: Make a docstring raw
​4aec1e8	Merge #32379

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​175e523	src/sage/functions/boolean.py: Remove unused imports
​218b2d6	and_symbolic, or_symbolic, not_symbolic: Add global bindings

[charpent]

Replying to mkoeppe:

Could you elaborate on is? What collides with what?

is is a Sage operator, roughly equivalent to Lisp's eq :

sage: x.parent() is SR
True

Therefore, the Maxima's is can't be translated by the mechanism used for Maxima's functions :

sage: maxima.is(x>0)
  File "<ipython-input-6-e177b9fc4016>", line 1
    maxima.is(x>Integer(0))
           ^
SyntaxError: invalid syntax

sage: maxima_calculus.is(x>0)
  File "<ipython-input-7-dea1cf49bee0>", line 1
    maxima_calculus.is(x>Integer(0))
                    ^
SyntaxError: invalid syntax

[mkoeppe]

A simple workaround for this is:

sage: getattr(maxima, 'is')(x>0)                                                                                         
unknown

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​4094035

src/sage/interfaces/sympy.py: Handle Not

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​a9302a6

NotSymbolic: Add sympy test

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​d202804

src/sage/functions/boolean.py: Add conversions to giac

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​700e84b

src/sage/functions/boolean.py: Add conversions to maxima

[mkoeppe]

Replying to mkoeppe:

For converting to maxima, some help would be welcome.

I think I figured a solution

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​392926c

Parser.p_eqn: Handle 'not', '~'

[charpent]

Still problematic :

sage: not_symbolic((a>0) & ((b<0) | (x!=0))).simplify()
a <= 0

Worse :

sage: ((a>0) | (x!=0)).simplify()
1

BTW :

sage: ~((a>0) & ((b<0) | (x!=0)))
1/and_symbolic(a > 0, or_symbolic(b < 0, x != 0))

[mkoeppe]

Indeed:

sage: var('a,b')                                                                                                         
(a, b)
sage: ((a>0) | (x!=0)).simplify()                                                                                        
1
sage: ((a>0) | (x!=0))._maxima_()                                                                                        
true
sage: ((a>0) | (x!=0))                                                                                                   
or_symbolic(a > 0, x != 0)
sage: f = ((a>0) | (x!=0))                                                                                               
sage: f._maxima_init_()                                                                                                  
'(_SAGE_VAR_a > 0) or (_SAGE_VAR_x # 0)'
sage: maxima(_)                                                                                                          
true
sage: (x!=0)._maxima_()                                                                                                  
_SAGE_VAR_x # 0
sage: (a>0)._maxima_()                                                                                                   
_SAGE_VAR_a > 0
sage: maxima('(a>0) or (x # 0)')                                                                                         
true

Is this a maxima bug?

[mkoeppe]

Replying to charpent:

BTW :

sage: ~((a>0) & ((b<0) | (x!=0)))
1/and_symbolic(a > 0, or_symbolic(b < 0, x != 0))

Yes, this is as discussed in comment:29, comment:38.

[mkoeppe]

Replying to mkoeppe:

Is this a maxima bug?

Minimal example in plain maxima 5.45.0:

(%i8) (x#0);
(%o8)                                x # 0
(%i9) (x#0) or (x#0);
(%o9)                                true

[mkoeppe]

I think our translation of Python's == and != to = and # on the Maxima side is wrong, and we should use equal and notequal instead - see ​https://maxima.sourceforge.io/docs/manual/maxima_169.html (Special operator: if)

[charpent]

Replying to mkoeppe:

Replying to mkoeppe:

Is this a maxima bug?

Minimal example in plain maxima 5.45.0:

(%i8) (x#0);
(%o8)                                x # 0
(%i9) (x#0) or (x#0);
(%o9)                                true

Did you (or do you plan to) report it in Maxima's bug report system ?

BTW : Sympy's logical functions seem exempt from this bug :

sage: foo = x!=0
sage: sympy.And(*map(lambda u:u._sympy_(), (foo, foo)))._sage_()
x != 0
sage: sympy.Or(*map(lambda u:u._sympy_(), (foo, foo)))._sage_()
x != 0
sage: sympy.Not(foo._sympy_())._sage_()
x == 0

Wrapping Sympy's functions may be a quick way out (that was my initial plan...).

[charpent]

Replying to mkoeppe:

I think our translation of Python's == and != to = and # on the Maxima side is wrong, and we should use equal and notequal instead - see ​https://maxima.sourceforge.io/docs/manual/maxima_169.html (Special operator: if)

Doesn't seem to be a question of precedence :

(%i9) x#0 or x#0;

(%o9) true
(%i10) (x#0) or (x#0);

(%o10) true

[mkoeppe]

No, I no longer think this is a Maxima bug.

I think it is a bug in our interface sage.interfaces.maxima_abstract. There are already two places that work around it (by using equal, notequal): Expression._maxima_init_assume_ and test_relation_maxima.

[mkoeppe]

See the early tickets #1163, #2218

[charpent]

Replying to mkoeppe:

No, I no longer think this is a Maxima bug.

I think it is a bug in our interface sage.interfaces.maxima_abstract. There are already two places that work around it (by using equal, notequal): Expression._maxima_init_assume_ and test_relation_maxima.

Indeed, the documentation is quite clear : = and # : syntactic (in)equality (i. e. isomorphic structures) ; equal and unequal : value (= structural) (in)equality.

This might be a heavy change. Separate ticket, separately tested ?

[mkoeppe]

Yes, I agree. There is a big potential for breakage. I've opened #32383 for it.

[charpent]

A possible plan B (independent of the Maxima snag) is to wrap Sympy's symbolic functions And, Or and Not, possibly leaving the logical operators to a later ticket. This is easy, the only problem being Maxima (1+back)translation, which you have solved.

Wrapping a Python method (imptementation of these functions in Sympy) shouldn't be as heavy as invoking a function in another interpreter : we stay in Python.

This is new functionality, after all : we don't (yet) have to worry about backwards compatibility. Introducing it with limited syntax (possibly extended later) isn't a drawback to anybody.

Thoughts ?

[mkoeppe]

Sympy translation already works, in both directions.

[mkoeppe]

And there is no remaining issue with "syntax".

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​0069e9c

Expression.__and__, __or__: Coerce to common parent or return NotImplemented; fixes @infix_operator doctest

[mkoeppe]

This passes tests but will need more work:

• without #32383, roundtripping through maxima is not safe
• Parser: Use a make_... function instead of importing and_symbolic and hardcoding its use - so that the other uses of Parser are not affected
• Add more documentation and tests
• possibly create a direct conversion from bool to SR so that we get to see False/True, not 0/1
• various places, for example the solve method and global function, should be generalized so that they deal with (at least some) boolean symbolic expressions

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:

​e385497	src/doc/en/reference/functions/index.rst: Add sage/functions/boolean
​8cdd2cb	NotSymbolic, not_symbolic: New
​71341c4	src/sage/functions/boolean.py: Remove unused imports
​1699ec8	and_symbolic, or_symbolic, not_symbolic: Add global bindings
​408bd37	src/sage/interfaces/sympy.py: Handle Not
​b4c6fb6	NotSymbolic: Add sympy test
​bf418fb	src/sage/functions/boolean.py: Add conversions to giac
​833ba8c	src/sage/functions/boolean.py: Add conversions to maxima
​d10ade0	Parser.p_eqn: Handle 'not', '~'
​e9eac61	Expression.__and__, __or__: Coerce to common parent or return NotImplemented; fixes @infix_operator doctest

[mkoeppe]

Rebased.