Expressions

Representation

A mathematical expression in Symbolica can consist of rational numbers, variables, functions, and the operations addition, multiplication, and exponentiation. An example Symbolica expression is:

\[ f(x,y)^2 + x \cdot y + 1\]

Division and negation are represented through a power of -1 and a multiplication by -1 respectively:

\[ \frac{1}{x} \rightarrow x^{-1},\qquad -x = -1*x \]

The addition and multiplication operator are viewed as n-ary operators, instead of binary operators. What that means is all factors or summands are treated at the same level. In a tree representation it looks like:

flowchart TD
    Mul --> Mulb{Mul}
    Mul --> a
    Mulb --> b
    Mulb --> c
Figure 1: Binary operator
flowchart TD
    Mul --> a
    Mul --> b
    Mul --> c
Figure 2: N-ary operator

We can represent any Symbolica expression as a tree, where we refer to each node as an atom. For example, the expression

\[\frac{4}{3} (x+1) f(x,y^z,3)\] can be viewed as:

flowchart TD
    Mul --> Num{Num 4/3}
    Mul --> Add
    Add --> Varx{Var x}
    Add --> Num2{Num 1}
    Mul --> Fn{Fn f}
    Fn --> Varxx{Var x}
    Fn --> Pow{Pow}
    Pow --> Vary{Var y}
    Pow --> Varz{Var z}
    Fn --> Num3{Num 3}

Note that although we can represent the expression by a tree, this is not the way Symbolica represents, them as this would take too much memory. Symbolica uses a custom linear, compressed expression that is approximately 8 times smaller than Mathematica’s and 3 times smaller than Form’s. This way, many terms can fit in memory at the same time. See Memory Representation for more details.

Emulation using functions

Even though Symbolica does not (yet) natively support vectors or other mathematical constructs you may want to use, functions are flexible enough to capture these construct. For example, a vector with an index could be represented as vec(p,mu), representing \(p^\mu\), a dot product \(p_1 \cdot p_2\) could be represented as dot(p1,p2), etc.

Creating Symbolica expressions

In the following example we create a Symbolica expression f(x)*(1+y) via string parsing:

from symbolica import Expression
e = Expression.parse('f(x)*(1+y)')
print(e)
use symbolica::{
    representations::Atom,
    state::{State, Workspace},
};

fn main() {
    let mut state = State::new();
    let workspace: Workspace = Workspace::new();

    let input = Atom::parse("f(x)*(1+y)", &mut state, &workspace).unwrap();

    println!("{}", input.printer(&state));
}

Or can be constructed from combinations of variables, functions and numbers:

from symbolica import Expression
x, y = Expression.vars('x', 'y')
f = Expression.fun('f')
e = f(x)*(1+y)
print(e)

To define a single variable, use Expression.var and for a single function Expression.fun. To define multiple variables / functions at the same time, use Expression.vars / Expression.funs.

Wrap the atoms in a builder that takes the state and workspace, to be able to use overloaded operators.

use symbolica::{
    representations::{AsAtomView, Atom},
    state::{State, Workspace},
};

fn main() {
    let mut state = State::new();
    let ws: Workspace = Workspace::new();

    let x = Atom::parse("x", &mut state, &ws).unwrap();
    let y = Atom::parse("y", &mut state, &ws).unwrap();

    let mut xb = x.builder(&state, &ws);
    xb = (-(xb + &y + &x) * &y * &ws.new_num(6)).pow(&ws.new_num(5)) / &y;

    println!("{}", xb.as_atom_view().printer(&state));
}

Symmetric functions

Functions can be defined to be symmetric in their arguments. This has the effect that the function arguments will be sorted according to the canonical form. For example, f(3,2,1) where f is symmetric:

from symbolica import Expression
f = Expression.fun('f', symmetric=True)
e = f(3,2,1)
print(e)
use symbolica::{
    representations::{AsAtomView, FunctionBuilder},
    state::{FunctionAttribute, State, Workspace},
};

fn main() {
    let mut state = State::new();
    let ws: Workspace = Workspace::new();

    let f_id = state.get_or_insert_fn("f", Some(vec![FunctionAttribute::Symmetric]));
    let f = FunctionBuilder::new(f_id, &state, &ws)
        .add_arg(&ws.new_num(3))
        .add_arg(&ws.new_num(2))
        .add_arg(&ws.new_num(1))
        .finish();

    println!("{}", f.as_atom_view().printer(&state));
}

yields f(1,2,3).

Output formatting

from symbolica import Expression
a = Expression.parse('128378127123 z^(2/3)*w^2/x/y + y^4 + z^34 + x^(x+2)+3/5+f(x,x^2)')
print(a.pretty_str(multiplication_operator=' ', num_exp_as_superscript=True, number_thousands_separator='_'))
print(a.pretty_str(latex=True))
let main () {
    let n = Atom::parse(
        "128378127123 z^(2/3)*w^2/x/y + y^4 + z^34 + x^(x+2)+3/5+f(x,x^2)",
        &mut state,
        &ws,
    )
    .unwrap();

    let mut p = n.printer(&state);
    p.print_opts.number_thousands_separator = Some('_');
    p.print_opts.multiplication_operator = ' ';
    p.print_opts.num_exp_as_superscript = true;
    println!("{}", p);

    let mut p = e.printer(&state);
    p.print_opts.latex = true;
    println!("{}", p);
}

which yields:

z³⁴+x^(x+2)+y⁴+f(x,x²)+128_378_127_123 z^(2/3) w² x⁻¹ y⁻¹+3/5
$$z^{34}+x^{x+2}+y^{4}+f(x,x^{2})+128378127123 z^{\frac{2}{3}} w^{2} \frac{1}{x} \frac{1}{y}+\frac{3}{5}$$

Canonical form

An expression has a normal form or canonical form, which is one preferred way in which it is written. For example, the normal form of 1+1 is 2, and the normal form of x*x is x^2. The procedure of normalizing an expression is performed after every operation, so that you should never see a non-canonical expression. Each computer algebra system has its own rules to decide which form is the normal form (or may not even write expression in a unique form!).

The (recursive) rules for normalization for Symbolica are defined per atom. For a

  • Variable
    • Always normalized
  • Number
    • Remove the common divisor between the numerator and denominator
  • Sum
    • Normalize and sort all summands
    • Remove summands that are 0
    • Add summands that are equal apart from their coefficient (\(x+ 2x \rightarrow 3x\))
  • Product
    • Normalize and sort all factors
    • If any factor is 0, return the number 0
    • Remove factor of 1
    • Convert equal factors apart from their power into a power (\(x x^a \rightarrow x^{a+1}\))
  • Power
    • Normalize the base and exponent
    • Normalize \(\text{num}^\text{num}\), \(0^a \rightarrow 1\), and \(1^a \rightarrow 1\)
  • Function
    • Normalize all arguments
    • Sort all arguments when the function is symmetric

The comparison of two atoms, which is used for sorting, is well-defined, however the convention could change between Symbolica versions.

Note that normalization is supposed to be quick, since it happens often. This means that expensive operations, such as expansion and factorization are not considered. For example, \((x+1)^2\) is a Symbolica normal form and \(1+2x+x^2\) is as well, even though they are mathematically equivalent.

Term streaming

In many scenarios an expression contains many terms, where each term is relatively small. Also often, symbolic operations can be performed term by term. The list of common operations that cannot be done term per term is short:

  • Factorization
  • GCD computation
  • Horner scheme construction
  • Pattern match \(a+b\)
  • …

The following operations can be done term per term:

  • Most pattern matches, such as \(y f(x)\)
  • Expansion
  • Differentiation
  • Integration
  • …

When using some global memory, operations such as finding the maximum term, or counting the number of terms that satisfy a certain condition can also be done term-by-term.

With this in mind, we realize that for many operations the expression does not need to be in memory as a whole at the same time: only one term needs to be in memory. Once it is processed, it can be written to disk. We call this term streaming and it allows for huge expressions to be processed.

Symbolica can convert an expression into a stream and it provides an easy way to perform operations on terms in parallel by using a map. The input of the map is one term and the output should be an expression. In the example below a derivative is applied to each term, in parallel.

from symbolica import Expression
x, y = Expression.vars('x', 'y')
e = x +x**2 + x*y + y**2 + x*y**4
e = e.map(Transformer().derivative(x))
print(e)

The Transformer() can be viewed as a Python lambda function

lambda x: x.derivative()

and is explained more here.

use symbolica::{
    representations::Atom,
    state::{ResettableBuffer, State, Workspace},
    streaming::TermStreamer,
};

fn main() {
    let mut state = State::new();
    let workspace: Workspace = Workspace::default();

    let x = state.get_or_insert_var("x");
    let input = Atom::parse("x + x^2 + x^y + y^2 + x*y^4", &mut state, &workspace).unwrap();

    let mut stream = TermStreamer::new_from(input);

    stream = stream.map(|workspace, term| {
        let mut out = Atom::new();
        term.as_view().derivative(x, workspace, &state, &mut out);
        out
    });

    let res = stream.to_expression(&workspace, &state);
    println!("\t+ {}", res.printer(&state));
}

By default, map uses all system cores.

Global information

Information that involves comparison between terms can be collected using appropriate synchronized structures, like atomics or mutexes. Currently, this is only possible in Rust. Note that due to Rust’s borrow checker, there can be no memory problems such as race conditions.

In the example below, the maximum numerical argument of the function f over all terms is determined (in parallel).

Not available yet.

Obtain the maximal function argument using an atomic integer.

use std::sync::atomic::{AtomicI64, Ordering};

use ahash::HashMap;
use symbolica::{
    id::{Match, Pattern},
    representations::{number::BorrowedNumber, Atom, AtomView, Num},
    state::{State, Workspace},
    streaming::TermStreamer,
};

fn main() {
    let mut state = State::new();
    let workspace: Workspace = Workspace::default();

    let x_ = state.get_or_insert_var("x_");
    let input = Atom::parse("f(1)+f(2)+f(3)+f(4)", &mut state, &workspace).unwrap();
    let pattern = Pattern::parse("f(x_)", &mut state, &workspace).unwrap();

    let stream = TermStreamer::new_from(input);

    let max_argument = AtomicI64::new(0);

    // map every term in the expression
    stream.map(|_, term| {
        if let Some((_, _, _, m)) = pattern
            .pattern_match(term.as_view(), &state, &HashMap::default())
            .next()
        {
            if let Some(Match::Single(n)) = m.get(x_) {
                if let AtomView::Num(nn) = n {
                    if let BorrowedNumber::Natural(a, 1) = nn.get_number_view() {
                        max_argument.fetch_max(a, Ordering::SeqCst);
                    }
                }
            }
        }

        term
    });

    println!("Max argument: {}", max_argument.load(Ordering::SeqCst));
}