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.

Depends on #32383

CC: @EmmanuelCharpentier @nbruin @egourgoulhon @fchapoton @spaghettisalat @kcrisman

Component: symbolics

Work Issues: Parser: Use a make_... function instead of importing and_symbolic...

Author: Matthias Koeppe

Branch/Commit: u/mkoeppe/boolean_symbolic_expressions @ e9eac61

Issue created by migration from https://trac.sagemath.org/ticket/31911

[mkoeppe]

Branch: u/mkoeppe/boolean_symbolic_expressions

[mkoeppe]

comment:2

Here's an attempt

---

New commits:

863c636

sage.functions.boolean.AndSymbolic: New

[mkoeppe]

Commit: 863c636

[mkoeppe]

Description changed:

--- 
+++ 
@@ -1,3 +1,4 @@
 As proposed in https://groups.google.com/g/sage-devel/c/U_WGbYG2zOE/m/yq-EDEXDAgAJ

+One application is for the restrictions of a `Chart`.

[7822f248-ba56-45f1-ab3d-4de7482bdf9f]

comment:4

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]

comment:6

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]

comment:7

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]

comment:10

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

diff --git a/src/sage/functions/boolean.py b/src/sage/functions/boolean.py
index 58089dce81..d32acca761 100644
--- a/src/sage/functions/boolean.py
+++ b/src/sage/functions/boolean.py
@@ -31,7 +31,8 @@ class AndSymbolic(BuiltinFunction):

         """
         BuiltinFunction.__init__(self, 'and_symbolic', nargs=0,
-                                 conversions=dict(sympy='And'))
+                                 conversions=dict(sympy='And',
+                                                  maxima='andsymbolic'))

     def _eval_(self, *args):

diff --git a/src/sage/interfaces/maxima_lib.py b/src/sage/interfaces/maxima_lib.py
index 40367c5242..2f6ab545f8 100644
--- a/src/sage/interfaces/maxima_lib.py
+++ b/src/sage/interfaces/maxima_lib.py
@@ -113,6 +113,9 @@ ecl_eval('(defun principal nil (cond ($noprincipal (diverg)) ((not pcprntd) (mer
 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,7 +1216,8 @@ sage_op_dict = {
     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",

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

106cc8f

sage.functions.boolean.AndSymbolic: New

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 863c636 to 106cc8f

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

859a969

RealSet: Handle symbolic 'and' input

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 106cc8f to 859a969

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

0dca442

ConditionSet: flattens symbolic 'and's

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 859a969 to 0dca442

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 0dca442 to 2866ee7

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 2866ee7 to fb3f9d0

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

[mkoeppe]

Author: Matthias Koeppe

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from fb3f9d0 to 6b9adbf

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 6b9adbf to 8e10ed3

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

8e10ed3

AndSymbolic, OrSymbolic: Use new function _trivial_bool for simplification

[egourgoulhon]

comment:20

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

[mkoeppe]

Dependencies: #32315

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 8e10ed3 to 0611026

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

0611026

Expression.__and__, __or__: New

[mkoeppe]

comment:23

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)

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

a839cdf

AndSymbolic, OrSymbolic: Flatten nested calls

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 0611026 to a839cdf

[7822f248-ba56-45f1-ab3d-4de7482bdf9f]

comment:25

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)

in --- 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]

comment:26

Replying to @EmmanuelCharpentier:

This is work in progress, no ?

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

[mkoeppe]

comment:27

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

[mkoeppe]

comment:28

Replying to @EmmanuelCharpentier:

• A symbolic_not is necessary.

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

[mkoeppe]

comment:29

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.

[7822f248-ba56-45f1-ab3d-4de7482bdf9f]

comment:31

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]

comment:32

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]

comment:33

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

[mkoeppe]

comment:34

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'.)

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from a839cdf to 5505b38

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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 '~'

[7822f248-ba56-45f1-ab3d-4de7482bdf9f]

comment:36

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 '~'

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

bb06156

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

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 5505b38 to bb06156

[mkoeppe]

comment:38

Replying to @EmmanuelCharpentier:

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]

comment:39

Replying to @EmmanuelCharpentier:

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.

[7822f248-ba56-45f1-ab3d-4de7482bdf9f]

comment:40

Replying to @mkoeppe:

Replying to @EmmanuelCharpentier:

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]

comment:41

Replying to @EmmanuelCharpentier:

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.

[mkoeppe]

Work Issues: Parser: Use a make_... function instead of importing and_symbolic...