Yes, it would be silly to have not read anything we could about any CAS created before. Symbolics.jl derives a lot of its structure from the recent SymEngine. I’ve been working with the MetaTheory.jl author on their egraphs-based approach, we’ve been digging through other rule-based systems, etc. You can read through our issues and chat channels to see the few hundred other articles referenced over the first few years of building this out. Of course there’s always more to read though, but at this point it’s less high level and more in the weeds.
We started a long time ago, and have never stated that and never would. Implementation language isn’t the issue in these kinds of algorithms, it’s rather the algorithms that create it. But, there is a lens to take it from. A lot of what we’ve been doing is parsing through to ask two questions:
What are the things that have shown to perform well after all of these years?
How do the algorithms change when considering Tapir-like task-based parallelism?
The second part is very key: pervasive higher-level parallelism changes what kinds of algorithms scale, and so perusing the literature with this in mind has really been enlightening as to what the next challenges to address are in this area.
I have not found references to the literature on CAS, except to sympy or wrappers around sympy, or to SymEngine, or Sage. Some of it seems to prominently feature ideas like reference counting, type management, tree traversals and such. This is truly down in the weeds – the CAS written in Lisp have taken memory management for granted for decades, although work in this area has continued, e.g. for parallel garbage collection, compaction, and other improvements. Of course Lisp has routinely dealt with programs as objects, compiled them, possibly automatically or on demand. Some, perhaps most, Lisps have incorporated multiprocessing features, and provided foreign function calling mechanisms to access libraries in C-family languages, CUDA, etc. There are obvious ties between Julia and the language concepts in Lisp for Julia implementation, so it’s not clear to me how these meta language issues are CAS-particular notions. The idea that “ADD” and “MUL” and “POW” can be types is not going to advance the state of the art in (say) writing an effective symbolic expression simplification program. So let’s look further…
By looking at sympy as the source for CAS algorithms and re-wrapping in Julia, all kinds of algorithms can be accessed, and that’s fine as far it goes. It may be just what the Julia community needs to implement applications of interest to practitioners of scientific (I guess mostly numerical) computing. I expect there will be further progress in sympy, available free, as time goes on. So that’s a plus.
On the other hand, solving already solved problems (e.g. compute GCDs of polynomials, factor polynomials over various algebraic domains, looking up integrals by pattern matching, expansion in series, generation optimized C code, plotting 2d, 3d, typesetting TeX …) is not addressing the issues identified at the edges of CAS – math representation and manipulation – which have arisen over the decades, say in Axiom, Reduce, Maxima, Maple, Mathematica… These are issues that inhibit further progress in making a widely-applicable interactive symbolic-math scientific assistant that doesn’t stub its toes on computations that (to users) seem to be in reach, if ony the CAS knew xxxxx. . When these issues are recognized, e.g. by looking at the newgroup mailing lists, they have prompted introspection into the design process – what would have been done differently at the start of the project, had the issues been identified earlier. The reality is that generations of CAS projects have started at ground zero, re-implemented the standard algorithms, made a few nominal changes like choice of language, instituting a different type/inheritance/category/message-passing/API/functional… paradigm, using new hardware and software substrates, etc. Unfortunately unexamined – the barriers that should have been examined earlier. Assumptions, functions of (one or more) complex variables-- branch cuts, singularities, multiple values, infinite or indefiinite size sets, discontinuous functions, infinities, undefined or indefinite values, IEEE NaN floats, are ones that come to mind.
Now it may be that Symbolics.jl is really aimed at the simpler tasks – what we essentially have in sympy already – and that’s OK. (Your category 1.)
And maybe it is time once again to look at multiprocessing (see work from the 1980s – wikipedia search for multilisp). So that’s OK too, though the opportunities for parallel algorithms in symbolic realms seems considerably less promising than in numerical linear algebra.
Symbolic data tends to be irregular/unpredictable, sparse. PhD theses have been written on parallelism in these algorithms. It is not likely that being parallel will address the issues mentioned above. (So using Tapir etc may make some things faster, but if the task is O(2^n), you kind of get stuck.
If there is a “new” CAS design to extend beyond (say) sympy, it would be nice to know the designers would recognize/address the uncomfortable areas in existing CAS systems, not just the comfortable ones. So this would be a third question to add to the previous two.
Most of the literature must’ve been dropped into the Julia Slack then, which has a slackhole due to too much activity, so we may have lost a lot of it. This is why we moved to Zulip, where even yesterday there was a pretty lively chat on rewriting algorithms. But there are many people in the organization who’s main focus is SAT solvers, e-graph formulations (working with MetaTheory.jl), category theory (Catlab.jl), and things along those lines.
Maybe it’s best to describe the organization at a more personal level. We have started to get close to feature parity with SymPy because we needed it as a backend for acausal modeling in ModelingToolkit.jl. SymPy, Reduce, and Mathematica (through MathLink) were far too slow for this to work out, and so Symbolics.jl was born out of solving that performance issue. It has been pulled out of SciML and MTK to become its own project to allow the wider symbolic-interested Julia community to grab hold of it and start to use it.
With that, there’s two directions that we have taken in the organization. One is to have a “backend independent” CAS, Symbolics.jl, which allows for users to do high level like “integration” and start to use these high level pieces as stable building blocks in other software (like ModelingToolkit.jl). In that sense, getting feature parity with SymPy with orders of magnitude improved performance is the goal I have set because it’s what I (some of the active contributors to the project) need.
However, I said there are two directions because that’s somewhat changing. My focus is still on numerical methods for scientific machine learning and differential equations, but what has happened from this work on ModelingToolkit is that we have a PhD student @shashi and some talented devs like @YingboMa who have been getting deeply into the symbolic computing literature, and they have been the ones driving “the more” in this area. This is where SymbolicUtils.jl comes from, and then collaborations with MetaTheory.jl, and this whole exploration of alternative formulations of rewriting systems. With the success of ModelingToolkit and its symbolic-numeric approaches, this has been pushing the Julia Lab towards more of these symbolic computing questions, getting undergraduate and master’s researchers interested in the intersection of numerical computing, compilers, and symbolic algebra. I would still say this is still a smaller offshoot of my research and the activities of the Julia Lab (where because we maintain so many libraries and organization already, we have the infrastructure to tag this along as it is a dependency to our main projects), but with where we have gotten with JuliaSymbolics and Symbolics.jl, that may not be the only focus for all of the contributors anymore.
So coalescing the Julia developer community around a core CAS infrastructure to get feature parity with SymPy (with massive performance improvements) is what the target was, but it’s not out of the question that I shoot you an email 3 years from now because some new PhD student is interested in driving the lower level details forward. I think that is mostly going to depend on the students and the community that we find.
This reminds me of a discussion in the old julia-dev mailing list, on the possibility of translating Axiom to Julia: https://groups.google.com/g/julia-dev/c/NTfS9fJuIcE/m/CHQWJcMc1JsJ . Some thought the similarities in the languages made it plausible, but the discussion ended with people talking of ways to interface with existing software.
I think this one is most similar to Sagemath, using a nicer language to provide a homogenous interface to the best software in various subfields, and building additional types and algorithms on top of that.
In any case I’m looking forward to a new CAS written in Julia from the ground up!
I agree with you in general.
But, Mathematica is most definitely not just a bag of tricks. Anyone implementing a CAS should have a thorough understanding of its semantics (such as they are) and know how, in the design space, their choices agree or differ.
Additionally, I think the modern thing to think about is the difference between interfaces and implementation. The CAS itself, to the user, is a grab bag of high level functions. The underlying representations can continually change, and so the whole difference between E-Graphs and rewriters can continue to be investigated.
Isn’t this exactly what @rfateman is trying to warn against? As I understand
there are limitations that cannot be thought out later? Seeming to be detailed technical points far from the high level functionality turn out to be breaking progress in exactly that high level interface?
Mathematica has many tricks, but it also has deeply rooted design errors, even at the level of arithmetic of numbers (when a number has lost all precision).
If you think it is obvious that sqrt(9) is 3, what does that mean for solving(y^2=9), which has two solutions? or solving y^3=1+I, which has 3, none of them “positive”. or a^b generally, including 0^-1 and 0^0.
These are examples that are easy to state. But if they have already fallen into the cracks, what else might there be?
Scratchpad/Axiom etc while more rigorous, seems to have a tendency to be off-putting to users less comfortable with abstract algebra, types etc. Contrast users with system programmers.
The key to success may be in finding a community of users, or possibly a clear presentation of an application library, that has already figured out ‘most’ of what needs to be done to complete the computation you need – and all you need to do is supply something phrased naturally in the language of the problem domain.
It is a huge barrier to learn large parts of a CAS, knowing in advance that 90% of it is irrelevant. But not knowing which 90%.
In the meantime, people building systems should make it possible to construct such tools, libraries, etc.
Apologies for being wordy; covid stay-at-home keeps me near the computer.
RJF
One can look at the list of major computer algebra systems on Wikipedia and quickly get in despair how difficult designing a universal computer algebra system is. As a PhD candidate in physics, I find that constructing and manipulating symbolic expressions, for instance constructing matrix determinants and taking symbolic derivatives or calculating residues, work well in Mathematica as long as things are commutative.
However, most QM stuff, condensed matter physics, general relativity and particle physics, tend to be non-commutative in a particularly unordinary way which takes the most time for the students to do. Having peeked in CAS literature on noncommutative algebra [1], I suspect these problems will not be addressed with a rule-based rewriting and internal tree representations. In that light, I would encourage developers to be mindful of the limitations and scope of what the new CAS tries to accomplish and, in future, provide a gallery of examples so potential users would not get burned
[1] I found research literature on how Cadabra: Papers using Cadabra system explaining best the issues of axiomatic rule-based systems in a plain language. I highly encourage you to read the papers as they IMO gives a different mindset to think about the rewriting systems and I guess Julia type system could be quite a good fit (also to be inspired on a Julia port ).
Think about this comment a little bit deeper. We’ve read the literature (of course), and now it’s saying don’t try anything until you know you have a plan that won’t fail at anything? Isn’t that a little crazy?
Instead, we are building something based off of the current literature that already is solving problems in cases where the previous tools we hooked up with failed (we have set ModelingToolkit.jl up with SymPy, SymEngine, and REDUCE already before starting a CAS, all of those had failed to do what we needed before this had succeeded). Will we have gotten everything right the first time? No, in fact we’re already onto our 3rd underlying representation, now hitting benchmark speeds on par with SymEngine (which itself benchmarks really well), with an extensible rule-based system that supports non-commutative algebras. We may have to tweak it again, and making a higher level that is robust to such changes is just good smart coding. Remember, we’re only in year 2 of what is a 30 year journey.
This is a FOSS project in a high level language .The key to success is not just in finding a community of users, but also fostering a community of developers. With the SciML ecosystem we’ve already shown how building a strong foundation can quickly start to bring in 20+ developers to the ecosystem, even more than what you get in languages like in Python mostly because there is no language barrier to the library development (the Julia library is written in Julia so users easily become developers!).
I like to think long term. This is simply the second year of what is at least a 30 year long project. The first things to do are to give a well-maintained library so that developers interested in this area can have one solid place they know they can contribute and others will help keep it going. Julia has been missing this for a long time, which has led to small projects starting and stopping. This is now already baked into the work of many larger organizations with multiple developers, so with this higher bus factor we can start to help guide community contributions towards a full-blown CAS.
Our first community of users is related to those doing numeric computing in SciML, as the CAS was first made to solve problems in ModelingToolkit.jl, but this announcement is really about expanding that vision and now allowing the larger community to join in on the project and pull it towards being the CAS they need for the other disciplines. Hopefully our non-commutative algebra rule systems, which we’re using for array symbolics, will be useful in other areas as well. I assume that will lead others to expand the CAS to support things like QM in nice ways.
As I have seen in our previously successful ventures, fostering a community and maintaining a constant stream of improvements towards a clear and common goal does wonders. We’re early into this project, it’s going to be a long one, but we have identified a need and want to help the language’s community get a full solution. What we have released with it a big step in that direction, but there is a journey ahead of us.
That’s not at all what it says. I thought of it this way: Of course you developed a nice tool (ModelingToolkit.jl) that does the job that you were trying to do, where other systems have failed. Then the decision was made afterwards to extract this very specific tool to make a generic CAS, calling it Symbolics.jl and opening a new organization on github. This is where qualified people came in and argued that there are many things to do wrong at the beginning of a generic CAS and one should be careful. This does not imply that no progress should be made. I hope as much as anyone else that this project succeeds in its goals and becomes another cornerstone of the Julia ecosystem, taking CAS seriously as you might say.
Things did go wrong. Here’s a bit of the history so far. We started in DifferentialEquations.jl with a small macro, ParameterizedFunctions.jl. What if we could symbolically improve people’s model code?
This was first based in SymPy, which was too slow for the prototype to work out well. At the same time, the SymEngine release announcement popped up on the Julia Google Groups (before Discourse, or 2BD). SymEngine was just what we needed for a small bit of symbolics, and October 2016 that is where we were:
We were happy with that for awhile, but along came @Gaussia with improvement after improvement to DiffEqBio (now known as Catalyst.jl). It was close (but not exactly) copying similar code for symbolic improvements like Jacobians over to the @reaction_networks DSL:
and similarly Pumas.jl was released shortly after, built on ParameterizedFunctions.jl.
However, we started noticing everyone in the community was similarly duplicating work inside of DSLs: there was no symbolic target for DifferentialEquations.jl, so every package made their own. What if there was one fully-featured symbolic interface for “if you symbolically declared an ODE like this, then we all share the same transformations”. That became ModelingToolkit.jl. But as we expanded beyond “build Jacobian and simplify”, SymEngine wasn’t enough. It was missing too many features. But SymPy was too slow.
So we gave a try to Reduce:
That was okay, but still not hitting the SymEngine speeds. Soon after that was replaced by what you’d probably call version 1 of the pure Julia part of the CAS, now not just added higher level features but the full representation itself in Julia. @HarrisonGrodin was really instrumental in that.
It was at this time (2018!), that we first started realizing that (a) this is the right feature set for what we need but (b) we should probably be refactoring it around a core rewrite system. See some of:
and
This is where paper after paper on rule rewriting systems and CAS’s, the pros and cons of different approaches, etc. all started flying through the Slack. While Terms.jl never truly came into fruition as we had hoped, we still had a meager CAS inside of ModelingToolkit.jl which did what we needed so we were happy for a bit. ParameterizedFunctions.jl, DiffEqBio (now Catalyst.jl), Pumas, etc. were now parsers of DSLs generating MTK forms, coalescing onto one code base with one definition of Jacobian. Great!
Until we needed to scale a bit more, needed equation solvers, etc. We got @shashi as a PhD student in the Julia Lab and funding from the ARPA-E to develop this into a full Modelica-like system. For a small bit of details, see for example the Dymola compilation process:
@shashi, @YingboMa, and @Mason poured through the papers (and @shashi took Sussman’s courses on the topic, becoming a fan of the Structure and Interpretation of Classical Mechanics book ), leading to a fully-featured rewrite system in SymbolicUtils.jl
@shashi’s release of SymbolicUtils.jl references tools like sicmutils as a big influence in its approaches.
At this point, ModelingToolkit was starting to have part of itself be a CAS, while the other big chunk was an equation-based modeling system. SymbolicUtils.jl was enough of CAS features that people wanted it to be a CAS (just look at how many Discourse articles there were on it), but of course all of the high level features like differentiation, build_function (the analogue to lambdify) were part of ModelingToolkit. So MTK’s docs started accommodating to two audiences: those who just want a CAS, and those who wanted equation-based modeling. But as it grew into a full Modelica competitor (which you will soon see has many new additions to go beyond Modelica , papers and tutorials coming), there was “no room” in the documentation.
So we set a vision, a plan for how to get there, already had a developer team and funding, starting seeking out additional funding sources, and finally split the CAS off placing it into an organization with SymbolicUtils.jl, forming JuliaSymbolics.
So we definitely had some bumps along the road and false starts, mostly because 5 years ago we didn’t know we were on the road to building a CAS. But over this time and after connecting with many libraries (some of which never got public code working well), and after digging through the literature, trying multiple rewrite systems, we are at something that works pretty well and that’s Symbolics.jl. It is fast, internally parallelized, and hits a lot of core features that people seem to want. It needs some more documentation and tutorials, and that’s mostly because it was confined to just being the first tutorial of ModelingToolkit for the last few years, and now it’s free to expand its tutorials in every topic a CAS covers.
And the improvements haven’t stopped there. In order to do staged programming and on-the-fly JIT properly, RuntimeGeneratedFunctions.jl was created as a solution:
And recently I’ve been talking with @0x0f0f0f a lot about MetaTheory.jl, which is an alternative rewriting system based on recent innovations called egraphs:
When I say recent, I mean POPL Distinguished Paper 2021. So how does this relate to more traditional rewrite approaches? You won’t find any papers on what happens if old rewrite system X is replaced by egg! In my mind there needs to be an organization building out a full CAS to research that question in full realistic scenarios. It needs to be in one of the high level languages where the researchers are working, and be fully-extendable with having its theory and rule system editable on the fly from the host language. And that’s where we are at with Symbolics.jl.
Given this journey it would be foolish of me to think we have found “our final form”, especially as we are evaluating other candidate rewrite systems to have under the hood! And I believe that a combination strategy will likely be the solution, using egraphs in some places while rewriters in others. But yes, we learned from mistakes overtime and now it’s pretty battle-hardened. At each step of the road we required it to solve all of the problems of the past, and do more. I think we are well past high level “read a paper” and by now deep into the weeds.
2nd mover advantage: see where other CASs failed & try to avoid as many of those mistakes in the beginning when it counts the most
The best ways to address (2) would be:
Proprietary CAS developers like Steve Wolfram to publicly list all the things he would do differently if he could start over (unlikely)
Open source CAS developers to publicly list all the things they’d do differently if they could start over
Study the relevant literature (looks like Symbolics.jl ppl did a good job here)
It looks like there is an impressive amount of talent working on Symbolics.jl.
AFAICT, none of them have much experience designing CASs. @rfateman, it looks like you’re possibly the most experienced CAS person in this thread, have you considered contributing to Symbolics.jl?
I personally don’t know anything about designing a CAS.
I have spent an enormous amount of time working w/ Mathematica (& their tech support engineers). As a user I know a large number of problems that can be solved w/ paper & pencil, but not by Mathematica. I’m happy to contribute those problems.
I’d say doing it right away is way better than never. I think Symbolics.jl did a great thing and it is a great attemp to develop a useful CAS system. No software is perfect at the very beginning. If there is one, it will never be started, lol.
Oscar is indeed an umbrella library/project, and has been developed for the past 5-6 years, funded by DFG (German NSF), and they don’t reimplement everything in pure Julia, but they don’t just provide interfaces, they really implement algorithms in Julia too, at least for some parts. Thanks to NemoCAS, a part of Oscar, Julia got several features that were missing, to be able to do computer algebra, and they already have such essential things like multivariate polynomials. And they use rather permissive licenses.
That is to say, I think it’s wise to join efforts with them, for the numerical parts like integration, etc.
Yes, we’re already looking at how to leverage Oscar and AbstractAlgebra.jl (the tool underneath some of NemoCAS). In fact, AbstractAlgebra.jl is already a dependency of SymbolicUtils.jl and used in some algorithms. So that’s not an empty promise: we’re using and extending their efforts today.
For e.g. algberaic numbers one can look at http://nemocas.org/ (a part of Oscar) - which is written in Julia, so it fits perfectly into your goal already. (And written by experts in computational number theory, too)
This form of a “CAS” is very different from what we’re looking at. It’s the “mathematician’s CAS”, not the “scientist’s CAS”. Think, SymPy or Mathematica, not GAP. Indeed some tools from Oscar.jl or AbstractAlgebra.jl will be helpful in doing this (particularly we’re looking at the polynomial support), but they do not achieve our stated goals. For example, if you look at Oscar.jl, the very first page of the documentation is “Ring Interface”, where as SymPy does not require presuppose knowledge of what ring theory is to get going. So while those tools will be useful for things like Groebner basis algorithms (maybe, because both libraries have a non-permissive open source license so we may not be able to use them), they are very far from being something that acts like:
@variables x y
gcd(x^2 y^2 + x y^2 + 1, y^2 + 2x + 3)
Nor do they support lambdification (build_function) to parallel functions, differentiation, etc. so they are a piece of the puzzle, but not quite close to the goal we’re looking at.
Do you mean to say that mathematics is not science, and that non-mathematicians do not encounter group representations (maybe you need to talk to physicists) or algebraic numbers and finite fields (maybe you need to talk to cryptographers).
And you surely will meet a huge chunk of Galois theory in symbolic integration, so if you want a non-baby symbolic integration then you’d need permutation groups…
As to your example - why is it a problem to set suitable defaults, so that gcd would be defined in the way you want.
I also don’t see why dependence of external libraries differently licensed is a problem. E.g. you have gmp.jl in Julia base, and nobody is worried that GMP is under GPL, right? Then, if GMP is OK, then why MPFR etc is not?
).
we were happy for a bit. ParameterizedFunctions.jl, DiffEqBio (now Catalyst.jl), Pumas, etc. were now parsers of DSLs generating MTK forms, coalescing onto one code base with one definition of Jacobian. Great!
), leading to a fully-featured rewrite system in SymbolicUtils.jl
]
so we may not be able to use them), they are very far from being something that acts like: