Computer Algebra System in Rust

help
1

I'm looking for a working CAS library in Rust. I did the usual shallow research in github, forums, dimforge (old nalgebra), etc. I wonder if it already exists.

In python, I usually need the following.

from sympy import *

def elementaryIntegrals(n):
    x, y, l = symbols('x y lambda')

    f1 = Matrix([
        [1],
        [x],
        [0],
    ])

    f2 = Matrix([
        [1],
        [1-l],
        [l],
    ])

    f3 = Matrix([
        [1],
        [0],
        [y],
    ])

    if n == 0:
        return integrate(f1 * f1.transpose(), (x, 0, 1))
    if n == 1:
        return integrate(f2 * f2.transpose() * sqrt(2), (l, 0, 1))
    if n == 2:
        return integrate(f3 * f3.transpose(), (y, 1, 0))

Questions:

  1. Is there any existing working library in Rust?
  2. Would you have sample working codes in Rust?
  3. Ideas to having a safe C or C++ port to Rust
  4. Anyone else willing or needing to build it?
  5. Let's unite forces?

Why CAS in Rust?

  1. Porting to wasm
  2. Native CAS in Rust accelerates numerical computing development in Rust
2 Likes
2

I wrote a very much prototype a while ago: https://github.com/s3bk/bullet

But it lacks matrix (and higher) support and only implements very few functions right now.

3

Seems interesting.

Would explain me how Jit and avx interferes in the build?

4

Basically whatever is feed to it is translated into a expression graph.
That is then processed by the poorly named "compiler" part that calls methods on the various backends. This builds up the output

  • x86_64 (jit, can be executed directly)
  • ptx (can be run on the gpu directly)
  • glsl (to be compiled by the gpu driver)
  • rust (proc_macro)
5

It seems nalgebra supports generic elements. But requires primitive operations to be implemented. I'm not expert in nalgebra source though. In discord, guys were talking about defining a Matrix of Matrices to reach more further dimensions.

6

nagebra is definitely an option. But it is not a CAS.

7

Second time I was told that.

lol

8

I would like to type things like this.

#[test]
fn second_order_derivative() {
    let x: Symbol = Symbol::new("x");
    let one: Symbol = Symbol::new("1");
    let two: Symbol = Symbol::new("2");

    let square_polynomium = x * x + one;

    let slope = Diff::upon(square_polynomium)
        .expect("No derivative was found.");
    assert_eq!(slope, x * two);
}

Bullet has the functionality already.

9

I fixed up bullet added your test:
https://github.com/s3bk/bullet/blob/master/tests/diff.rs

Normally you'd just use

let square_polynomium = b.parse("x^2 + 1")?;
10

One more good place to do quick searches if you don't already know about it:

1 Like
11

Don't misunderstand me. I'm not arguing, I trust your code. In fact I've got no production in the matter. So, thanks for showing the functionality is implemented indeed.

I downloaded the repository and tried to compile it. It stopped due to cuda dependency, it is configured through a relative path in Cargo.toml. How can I fix that?

Also, is it possible to add the following?

#[test]
fn derivative_chain_rule_sample_1() {
    let x: Symbol = Symbol::new("x");
    let two: Symbol = Symbol::new("2");

    let square_sin = x.sin() * x.sin(); // sin(x)^2

    let slope = Diff::upon(square_sin, x)
        .expect("No derivative was found.");

    assert_eq!(slope, two * x.sin() * x.cos());
}

#[test]
fn derivative_chain_rule_sample_2() {
    let x: Symbol = Symbol::new("x");
    let two: Symbol = Symbol::new("2");

    let sin_square = (x.pow(2)).sin(); //sin(x^2)

    let slope = Diff::upon(sin_square, x)
        .expect("No derivative was found.");

    assert_eq!(slope, two * x * (x.pow(2)).cos());
}

I believe I've done the maths right.

12

updated the repo to fix that.

use bullet::{builder::Builder, func::{Func, Transient}};

let b = Builder::new();
let x: NodeRc = …;
let s = b.func(Func::Transient(Transient::Sin), x)?;

to create cos of the node x.

Also: bullet is not tested.

DO NOT USE IN PRODUCTION

1 Like
13

I'm thinking about something like this.

A generic form for an expression. Which could be a single variable, an association between expressions, operations or even associative operations over expressions.

Implementations of Symbols, Associations and Operations would compose the expressions. They could assume addition, subtraction, division, power, trigonometric operations, differential operations, and else after the implementation.

Well known expression manipulation like substitution, expansion, simplification should be implemented in the form of traits, so that it could analyze the expression tree through recursion.

I wonder how the existing std::collections could take place. I'd keep the expression structure separated from anything else, in order to keep it clean. A pre-processing step of the whole structure could generate related collections of auxiliary data, as long as it is necessary for manipulation algorithms.

use std::cell::RefCell;

pub trait Association/* : Evaluable + Replaceable + Expandable + Simplifiable + Sortable */ {
    fn rhs(&self) -> &RefCell<Expression>;
    fn lhs(&self) -> &RefCell<Expression>;
}

pub trait Operation/* : Evaluable + Replaceable + Expandable + Simplifiable + Sortable */ {
    fn argument(&self) -> &RefCell<Expression>;
}

pub trait AssociativeOperation/* : Evaluable + Replaceable + Expandable + Simplifiable + Sortable */ {
    fn argument(&self) -> &RefCell<Expression>;
    fn modifier(&self) -> &RefCell<Expression>;
}

pub enum Expression {
    AssociativeOperation(Box<dyn AssociativeOperation>),
    Operation(Box<dyn Operation>),
    Association(Box<dyn Association>),
    Symbol(Symbol),
}


pub trait Replaceable {
    fn substitute(&self, old: &Symbol, new: &Symbol) -> Result<Rc<Expression>, Rc<Expression>>;
}

pub trait Evaluable {
    fn evaluate(&self) -> Result<Rc<Expression>, Rc<Expression>>;
}

pub trait Simplifiable {
    fn simplify(&self) -> Result<Rc<Expression>, Rc<Expression>>;
}

pub trait Expandable {
    fn expand(&self) -> Result<Rc<Expression>, Rc<Expression>>;
}

pub trait Sortable {
    fn sort(&self) -> Result<Rc<Expression>, Rc<Expression>>;
}

pub struct Addition {
    rhs: RefCell<Expression>,
    lhs: RefCell<Expression>,
}

impl Association for Addition {
    fn rhs(&self) -> &RefCell<Expression> {
        &self.rhs
    }
    fn lhs(&self) -> &RefCell<Expression> {
        &self.lhs
    }
}

impl std::ops::Add for Expression {
    type Output = Expression;
    fn add(self, other: Expression) -> Expression {
        Expression::Association(Box::new(Addition {
            rhs: RefCell::new(self),
            lhs: RefCell::new(other),
        }))
    }
}


pub struct Symbol {
    pub label: String,
    pub value: Option<f64>,
}

impl Symbol {
    pub fn variable(label: String) -> Expression {
        Expression::Symbol(Self {
            label: label,
            value: None,
        })
    }
    pub fn constant(label: String, value: f64) -> Expression {
        Expression::Symbol(Self {
            label: label,
            value: Some(value),
        })
    }
}

impl Eq for Symbol {}
impl PartialEq for Symbol {
    fn eq(&self, other: &Self) -> bool {
        self.label.eq(&other.label) && self.value == other.value
    }
}

Question:

  • Would it be a good design?
  • How to improve it?
14

You could try to port the Yacas kernel on top of Rust, probably with the help of c2rust (you will have to convert C++ code to C first). Some of the code pieces can be switched directly to the nalgebra and any LISP implementation in Rust (or just S-expressions parser like lexpr). It would be a good project. See the sources at https://github.com/grzegorzmazur/yacas.

1 Like
15

Another important thing to check - maths_traits. It provides the following mathematical objects:

  • Group-Like algebraic structures: monoids, groups, abelian groups, etc
  • Ring-Like algebraic structures: rings, fields, GCD domains, Euclidean domains, etc
  • Module-Like structures: vector spaces, algebras, bilinear-forms, etc
  • Integer and Natural numbers
  • Ordered algebraic structures: ordered/archimedian rings, fields, etc
  • Real and Complex numbers
  • Metric properties of sets: metric spaces, inner-product, norm, etc

See also abandoned algebra for inspiration.

You could check also surreal trait that implements more complex numerical abstractions - J. H. Conway's surreal numbers as an example.

3 Likes
16

I considered that. It just ends in sadness.
And it takes forever to compile. My approach is much faster (and smaller), as it does not ship a rustc and llvm. It also isn't limited to what rustc consideres valid.
EDIT I totally misinterpreted what you wrote.

17

You are talking about Enum of Traits againts Enum of Enum? I read expr.rs and node.rs.

Also, I'm trying to compile the repository, I told you. Cuda is a relative dependency in the last commit. I don't have cuda. How can I solve it?

If I could compile it, I could insert tests myself and send a pull request instead of asking you.

18

Sorry, I misinterpreted what you said.

If you update the repo, cuda should be a git dependency.

20

It's not a CAS but you might be able to use the algebraics crate that I wrote for Libre-SOC, it implements real algebraic numbers based on using intervals of dyadic fractions and factored integer polynomials. Add, sub, mul, div, remainder, comparison, conversion to/from integer, floor, ceil, rounding, floor/ceil of log base 2, and raising to rational powers are implemented. It also has bindings to Python if you need that. It also has a bunch of code for factoring integer and modular integer polynomials.

2 Likes
21

I was able to compile with no problems.

How did you implement equality between NodeRcs?