Student Proposal: Computer Algebra System (CAS) Implementation

[joshuanianji]

Hey everyone, I'm a student and this is my proposal for this year's GSoC. It's a bit more on the academic side, but if you are interested I'd love to work on it.

Title: Computer Algebra System (CAS) Implementation in Elm

Name: Joshua Ji
Name in Elm Slack: OshuaJay

Summary:
The goal of this project is to implement a Computer Algebra System (CAS) in Elm, particularly the ASAE data type mentioned in Chapter 3 of Joel S. Cohen’s Computer Algebra and Symbolic Computation. Such a data type represents mathematical expressions in a way that can be manipulated and simplified in a nontrivial manner, unlike the more conventional binary expression tree that has many limitations.

How the project will be done:
Following the book should be sufficient. Although long, most of it is dedicated to prerequisites, and the section focusing on the implementation is of reasonable length. It explains the data structure and provides pseudocode to implement some of the functionality that can be added to such a library (such as polynomial factorization and derivatives). The scheme implementation can be used as a supplementary resource.

What will the project focus on:
This project will focus on providing a clean API to create symbolic mathematical expressions, and basic functionality for manipulating them. Further extensions may be possible if there is enough time.

Benefits:
A subset of the elm community has been moving toward more computationally expensive projects, such as simulations using elm-physics and elm-3d-scene. Further developments in this field may require a greater demand for a more complicated mathematical library, especially as many problems in physics and math use systems of equations and other nontrivial equations. In fact, similar libraries in other languages, like SymPy in Python, are a basis for a huge variety of projects in geometry, statistics, physics and more. A project like this will serve both as a proof of concept and a gateway for more powerful applications built with Elm.

Goals:

• Define the AST for the Algebraic Expressions, as well as an API to create it.
• Create a parser to generate the AST from a LaTeX-formatted equation, and a function to generate LaTeX-formatted code from the AST.
• Create an evaluation function, given a dictionary of the variables to values.
• (optional) Create a function to factorize a polynomial, or approximate the roots.
• (optional) Create a function to take the derivative of an AST.

What’s Needed: Elm, parsing, math
Difficulty: Medium

[mpizenberg]

From the book:

Computer algebra is the field of mathematics and computer science that is concerned with the development, implementation, and application of algorithms that manipulate and analyze mathematical expressions.

Something that I found quite fuzzy while reading the introduction is that "computer algebra" is described in very generic terms for any kind of mathematical expression. Yet while reading the table of contents, it seems the book only deals with polynomial expressions. Is this because that's some kind of a base requirement for the field and the book specifically introduces those base concepts? Because another that is quite important I'd have though is handling differential equations for integrals and derivations. I would think that it would be needed for automatic differentiation of neural networks for example.

In any case, that sounds like a lot of fun! There must not be a lot of mentors for this very specific topic, I hope you find one!

[joshuanianji]

Thanks @mpizenberg! This project seems fun, though I think finding mentors will be tricky.

Yet while reading the table of contents, it seems the book only deals with polynomial expressions. Is this because that's some kind of a base requirement for the field and the book specifically introduces those base concepts?

I would assume this is the case, but I am also speculating. Looking at the preface, they emphasize how they wanted this to be an "introductory text" that wouldn't "include all refinements of a particular topic of algorithm." Handling differential equations would be super cool to implement in a library, but I guess this book wanted to focus on more elementary applications, with some mathematical rigor. But who knows, maybe that program can be implemented if this project is successful!

[ianmackenzie]

What's involved in being a mentor/what's the expected time commitment? I do think it would be great to explore symbolic computation in Elm (could indeed be very useful for elm-geometry related stuff) and I'd be interested in supporting that.

My initial reaction to the specific proposal is that I'd be more inclined to focus on implementing some interesting operations (simplification, differentiation, integration) instead of spending a lot of time on parsing or pretty-printing; seems to me that a project for a computer algebra system should focus mostly on the algebra =) I don't think there are any real unknowns for parsing and pretty printing, so I'd be tempted to implement them at a later stage if the core functionality works out and it seems like the project will be useful.

[razzeee]

I think https://youtu.be/3J_eBuYxcyg might be helpful, but those times, time frames are old as Google cut down the project scopes for this year. So times should be smaller.

[joshuanianji]

Hey @ianmackenzie, I'm glad you're interested in this proposal.

I think you bring up a good point in that this project would benefit more if it focused on the algebra, and less of the technicalities. I'm open to tweak the goals of the project and discuss it further on the #gsoc slack channel!