Course:CPSC312-2016-Project1-ProCAS

Prolog Computer Algebra System (ProCAS)

Authors: Gabriel Henderson, Dominic Kuang

What is the problem?

We wish to implement a symbolic Computer Algebra System (CAS) for integration and differentiation. A quick google search for "prolog cas" does not return many relevant results, although a small symbolic computation package was found that was relatively limited and had not been updated since 1987. In the comments of this Piazza post, Dr. Poole stated that "the language we have now with definite clauses and function symbols is rich enough to express all of math". Therefore, we feel that the implementation of a Computer Algebra System in Prolog is feasible.

What is the something extra?

The differentiation function implemented in Assignment 3 is severely limited in that it can only differentiate the product or sum of linear terms. We would like to extend this function to work for nonlinear expressions such as $f(x)=x^{5}y^{2}+2xy^{3}+4$ and expressions containing logarithmic, exponential, and trigonometric functions such as $g(x)=e^{x}\ln(\sin x)$. We would also like to improve the simplification algorithm to be more useful and to simplify expressions into a normal or canonical form. Lastly, and most interestingly, we would like to see if integration functionality could be implemented solely based on differentiation rules. Indeed, to compute $\int f(x)\,dx$, Prolog could simply search for a function $F(x)$ such that $F'(x)=f(x)$.

What did we learn from doing this?

We found Prolog to be a suitable language to implement most of the features that would be expected of a CAS. We were able to successful implement the following: differentiation, evaluation, substitution, expansion, simplification, Newton's method, and the Taylor expansion. Initially, we hoped to define integration purely in terms of differentiation. However, it soon became clear to us that this was not a tractable approach due to limited stack space and a large search domain. With the code we have now, integration will almost certainly result in a stack overflow except in the case of an "obvious" anti-derivative. A problem we faced when implementing differentiation was that Prolog had no way to generalize operations on functions. Thus, it is not possible to implement the chain rule without painstakingly specifying the outcome of the operation for each individual function (The Art of Prolog: Advanced Programming Techniques, page 81-82). This could perhaps have been overcome by using a 2-tuple function representation such as ⟨function name, arguments⟩ but we felt that it was unintuitive and difficult to read and work with. On the contrary, we found Prolog was excellent for implementing many of the other features such as expansion and simplification due to the rule- and logic-based nature of mathematics. In conclusion, the logic programming paradigm is indeed suitable for the implementation of CAS, although we were not able to get integration for "free" as we hoped.