Rubi: Solving Integrals, One Rule at a Time

Hi everyone, my name is Patrick. I work in the neurophysics department of the Max Planck Institute for Human Cognitive and Brain Sciences in Germany. I'm also the developer of the Wolfram language plugin for all the JetBrains ides like Pycharm, Idea or Cline. I did a lot of work on the Stack Exchange side for Mathematica and had some other projects around the Wolfram language and Mathematica. Today, however, I'd like to talk about something entirely different where I'm not an expert in but still, it's worth presenting. The title of my talk is Ruby Solving Integrals One Rule at a time. But what exactly does it mean? And why do we need another integration framework? I mean, Mathematica can solve integrals pretty well, right? There are good reasons in this talk I tried to highlight some of them. So Ruby is the work of Albert Rich and he started working on it in 2008. So it's a dedicated effort for around 15 years. Ruby is a rule based system for finding optimal antiderivatives for large classes of mathematical expressions. There are around 7,000 integration rules right now. They are organized as a decision tree to find the antiderivative. There's a test suite that contains over 72,000 integration problems to test. Basically the system and all this is open source and available on GitHub. Why don't we start with a simple example? So for the installation you can call Paklet Install and give the online resource, or you could go to GitHub and download the packlet from there, or you could even clone the repository and use the latest development version. I will give the link in the end of the presentation. After that you simply load the package as usual, like this, okay? And then Ruby just provides one function which is called int for integrate. And essentially it works very similar to what Mathematica has with its integrate function. So we can call it and we get the antiderivative of the expression that you see here. So, and we could even compare it with the one that Mathematica gives. Or we could give the bounds for the integration, right? And you see it kind of works similar. So that raises even more the question why do we need another integration if we already have all this in Mathematica? We come to that for the next slide. Please bear with me because I'm way out of my comfort zone here. But what I do know is that integration is much harder than derivation, even if you do it on paper. And algorithmically it's kind of similar. So you need very complex methods to to integrate expressions that go beyond the simple things we probably see in school. One of these algorithms is for instance, the RISH algorithm, which was a milestone in computer algebra, as far as I know. And the thing is that these other algorithms usually give you an answer if they can calculate it, but they can't show you how you get to that point. So there's no way to follow the steps of, on paper how you got the antiderivative of an expression. That's one thing. The other thing is that antiderivatives are not unique, so you can have many of them for a single expression. So we know that, we know that from school with the constant C that usually everyone forgot at least once in their, in their lifetime. And the thing is that different antiderivatives can can be drastically different in quality, both in size, but also in the quality of the functions that are used in the antiderivative. Ruby tries to solve specifically these points. So first Ruby tries to give optimal antiderivatives in quality, but also in size of the antiderivative. We'll see an example in a moment. But the other thing is the nature of following a rule based approach. Applying rule after rule to get to the antiderivative gives you a way to see how it was calculated, what transformations were used and how you could repeat it on paper. Let me try to demonstrate what I mean by size of the antiderivative. We will use the very first example we've seen, but we will change the exponent to a 2023, which is more appropriate, I think. So when we integrate this with Ruby we get a pretty short result and to now look how big basically this is. We could use something like the tree form and then we could count the leaves in there. And it's not entirely correct what leaf count gives because it's regards. I think the rational expressions a bit differently. But leaf count gives a good impression of basically how complex or big an expression is. So if we integrate that with Mathematica, we get a vastly different result. And it's so different that basically this leaf count here is orders of magnitudes bigger. I think it's safe to assume that working with a very compact representation that Ruby gives is better than looking on a sum with over 3,000 terms. But actually it's still a valid antiderivative and it's correct. And you can simply show that by doing the opposite operation. So you take the antiderivative and you derive it again and see if you come back to the original form, we could do that and say something like okay, quality here on resmma by X. And then let's just simplify it to give Mathematica a chance to put it back together. And you see we come back to something very similar. I leave it up to you to bring it in the exact same form that we had as an input. But what you can always do is just subtract it from another and then see if you get zero. Let me give another example regarding the quality of the antiderivatives. What we use is a simple expression that contains a cosine in the denominator. Here we will first integrate it with Ruby and then with Mathematica. What we will see is that the result looks pretty similar. So let's try to integrate that here and then that here. You see, the forms are not that different. If we simplify it back, we also see that we get to the original form. And the next step I want to do is I want to just plot basically the antiderivatives of the result of Ruby and the result of Mathematica. So for the result of Ruby we see the that the original function is continuous in the in the region I plotted here, -2p2pi to 2pi and the antiderivative is also continuous, which is a good thing. If we look however, on Mathematica's solution, we see that there are discontinuities in the solution. Generally speaking, it's always nice if you have a continuous function. So for instance, in the one with the discontinuities, we couldn't just simply plug in values to calculate the area under the curve. I have to say that Mathematica does a great job taking care of these discontinuities if you actually calculate the area in a region that goes over such a jump. So if you call integrate on that, you will get the correct answer. It's roughly 1.4 here. So with Ruby, however, we could just take the antiderivative and plug in the values like we learned in school. So left side, right side, and then subtract them from another and what we get is the same result. And if I scroll down, we could not do the same with the enter derivative that Mathematica provided because it contains these jumps. The last thing I wanted to show you is how you can actually look on the steps that Ruby took to calculate an antiderivative. We have a helper function for that. It's called steps. You just wrap it around and Ruby will take care of collecting all the information from all the rules it applied if we call it on this very simple expression X to the power of N, then we will get a view of what rules are applied. So what you see here is in slight red, basically the rule that was applied, and in blue, then the intermediate expression that was used to continue if there would be more steps. So in that case, here it's pretty simple. There's a rule for X to the power of m and it looks like that we can also expand that. What we see here is that Ruby used the Rule 30. So I have to say I'm working on a branch here of Ruby where I try to inject basically a button here so that you can click on it. And if you click it, you go to the original notebook of Albert where he implemented the rule, but also left helpful comments like how it was derived or from which book it was taken. So if we click that here and I drag over the notebook of it and increase the size a bit, then we see here, okay, that's the, that's the rule that was used. And you can find it in these references which are books explained on the website. So the one here, for instance, is the very famous Abramowicz Stegun, which probably everyone has in, in their bookshelf, right? And then you see how the rule works, but also you see the exact code, how it was implemented. However, what makes this approach so powerful is that in longer calculations you can basically follow each step that was taken by Ruby. Right? Let me give you another example. So here we have a bit more complex expression, and if we integrate that and using the steps function we see we get a much larger output. So obviously the first rule is just that the integral of sum of terms is basically integrating each term separately. And then we have these sub expressions, and for each sub expression other rules were called so that finally the output is given at the bottom. I don't want to drag this out for too long, but what I'm saying is that it gives you a deep understanding of how to integrate something. You can look on the rule, you can look on the conditions of the rule, which is basically the requirements that need to be met so that the rule is applicable in a certain step. You can look on Albert's notes, and finally you can just look on the code that implements the rule and see for yourself how it works. Now we have a pretty good impression of how Ruby looks from the user's perspective, but I'd also like to give you the the other direction from the developer's point of view. So how does Ruby actually work and how Is the package laid out and how is the code structured? Let's start by heading over to Mathematica and implement our own very simplistic Ruby. It will do nothing more than find the antiderivative of polynomial expressions like you see on the screen. So we will call our integrator just int. And the rule for integrating the terms here is simply that, okay, if we see an expression like x raised to the power M and we want to integrate it with respect to x, then we get something like 1 over m plus 1 times x to the power of m plus 1. So that's the rule. We can test it already and say, okay, find us the antiderivative of x squared and we get a result. So one thing you should see is that this goes goes south pretty fast. If we don't have a two here, but instead a minus one, because then the solution is something different, right? But we can add this rule. We can say, okay, if we have indeed one over X and we want to integrate it with respect to X, then the result is log of X. So let's see, good so far. Another thing that you might see is that we want to integrate just simple X because it's just raised to the power of one. But in our current approach this stays unevaluated. The reason is that Mathematica doesn't know that this is basically default to the power of one. But we can add this by simply adding a point which adds the default argument. And then Mathematica knows that DX is raised to the power of one and we get the result. Okay, that looks pretty decent. However, there is not a flaw in our approach. What if our power is not free of X? Then the rule doesn't work. This is exactly the case where we need conditions on the rule. So if we have something like X +1 here, our approach is wrong. So what we need to do is we need to put a condition on the rule. And here we can simply say something like free Q MX which says okay, M needs to be free of any access, so now it stays unevaluated. And of course we need to think of another rule that we should add. The last point is that what if we have our example plus x stays unevaluated because how should our integrator know how to integrate a sum of terms? So that's where we need another rule. And we can say something. If we want to integrate something that contains a plus and has arguments and we want to integrate it with respect to X, then probably what we want to do is just integrate all the single parts. So we can say, yeah, just use our integrator and map it over all the arguments. So this will give a list. And what we finally want is make it a sum again. Okay? And there's another floor here. So we need to prevent that this is evaluated when we define it. So we need to put a whole pattern around it. And what happens now is basically that our integrator sees first that it is a sum. So it uses this rule, right, to integrate the parts, and then each part is integrated separately. You might wonder why I'm talking about rules all the time. One way to think about that is that Mathematica also stores all the definitions you give in rules. They're called down values, or there are certain other types of values as well. But for our specific integrator, we can look at the rules. So what we can do is, is simply called down values for our int. And then we see the rules that Mathematica uses. So they have a left side that usually contains a very specific pattern that needs to match, right? And if it matches, then it's replaced with the right side. So another thing it has usually are these conditions on rules that we use extensively in Ruby. So even if a pattern matches, there are certain additional conditions that need to be met so that the rule can be applied. Having our simple example in mind, we can look at how this works in Ruby because essentially it's the same thing. So what we have are the integration rule notebooks, and they look like this. They have rules for very specific situations. So in that case, if the integrand is of the form A plus BX to the power of M. So, and what you see here that Albert took care to very detailed layout, what kind of form is integrated in a specific rule. You got the references that I mentioned earlier and the program code, and you can scroll down and you essentially find the things that we did with our simple integrator. The difference is that Ruby contains many of these notebooks and has, as I said, almost 7,000 rules for integration. Now let us jump to the Ruby source code and look at the folder structure and the files it contains. In the Ruby source code, you find all these notebooks right in the root directory. So you have here the integration rule notebooks directory, and it's deeply nested. And for all kinds of forms, there are notebooks that contain the integration rules. The first step when we build the Ruby package is that we strip out everything from the notebooks and only keep the important rules. These things you find in the Ruby directory under integration rules. And if we compare the notebook we just saw to how it converted, then you see it looks like this. Everything is gone except of the rules. And if we just skim through this subdirectory, we get an impression of the size of the Ruby rules. You see there are many, many of them. Another thing you might have noticed is that the conditions on the rules not only contain functions that you know, like Free Q, but also many of utility functions that were specifically implemented for Ruby. If we jump to to the definition here, we see that they are located in the file integration utility functions. And if we just look on the structure of this file, you see that there are many, many utility functions that are used in Ruby to either do transformations or put conditions on rules. When loading Ruby, all the rule definitions are loaded in a very specific order. This happens in the file Ruby M. So let's jump there. Besides this, the Ruby source code contains functions that we use for showing the steps in a nice way. And you find it here in the show step formatting. We also have Ruby package tools that are used to to build the package, to strip the notebooks and so on and so forth. And that's essentially it. So if you now want to have a look yourself, you can simply clone the repository from GitHub and have a look yourself. You should be all prepared to navigate the source code confidently. So let me give a quick summary. Ruby is a system for rule based integration. All information you need you will find on the website rule based integration.org Albert Rich is the brain behind everything and he dedicated many years to getting things right and ensuring that the solutions that Ruby gives are correct. Nasser Abazi runs the Ruby tests and he does an awesome job of comparing basically the test suite between different computer algebra systems. And lots of other people helped tremendously, one of which will probably sit in the audience, which is Daniel from Wolfram, who as I've heard, helped a lot with infinite recursions. In the bar chart below you see how Ruby performs in comparison to Mathematica 11.3 and Maple running the 72,000 test problems we have. I joined Ruby in 2018 and I worked on putting it on GitHub and making a real pack out of it that can be installed easily. I also took care of decreasing the loading time of the package. I worked on some of the rule displays that are shown to the user so that they are look that they look nice. And we also published a paper so that Ruby can be referenced correctly by all the scientific groups that use Ruby. Still, there's the Question. Why am I here today talking about Ruby when there's someone much more capable who spent basically 15 years of his life working on the project? The sad truth is Albert died just a few weeks ago, completely out of the blue. With Ruby. He left us a very precious gift, accessible to anyone who wants to look at it or work on it. But I'm afraid it will take very capable hands if we want to continue his legacy. I'm sorry for ending my presentation on such a sad note, but I believe that Albert Rich earned it and I thank you very much for your attention. And if you have any questions, I should be live online and I am live online, so thanks everyone who watched. I see one question from Sylvia which is not naive at all. So Silvia asked the question. This looks like one rule works as a patch of another rule, and so on and so forth, and that you need a very specific ordering of the rules to make it work. And you're entirely correct. So Ruby really relies on the ordering of rules and you might wonder, do we need to sort them automatically? So if we will have basically a decision tree or a list of rules that we just try, then yes. But the big but is that we probably know that Mathematica does clever things when you define functions, so it puts rules with very specific patterns first. Right. And then the, the patterns that are more general come, come last. That's usually, I mean, usually when you implement the function and you need a fallback, fallback rule where you say, okay, something went south here, then you just match everything and then you know it will be the last rule to match. So this is how Ruby basically works. We don't need to take care of the ordering of rules in general, but we can rely on the pattern matcher. And I'm pretty sure I know, Silvia, when you check Stack Exchange, I think we had a very famous and very big Q and A about this specificity of patterns and how you can decide if a pattern is more specific than another one. So if the rule should come first or second. And I think that was a very complex topic and I'm pretty sure Daniel could say a lot about that. Yeah. So, and the final point I want to make is that if you look on the Ruby source code, you will see that the rules are not loaded in order. Right. So Albert needed to take care of some things and reversed some loading orders so that the rules worked indeed correctly. So do we have other questions? So Daniel wrote, I believe one of Albert's goals was to have a revised version using a decision tree and that's correct. So what Albert tried is to basically turn this pattern matching based selection of rules into a real decision tree where I say okay, I have an expression, it looks like that. Okay, I can integrate it by that and then you can make the checks down the tree where all the sub expressions are and you can basically have the ordering implicit in the decision tree. That's correct. Thanks idaj. I pre recorded it just to keep time because I've seen that keeping time is a struggle. Yeah, so I also say, see that Oleg wants to ask something about email. I mean you find me on LinkedIn, just search for my name and just hit me up there and we can talk. So if there are no more questions, I would say we successfully kept the time of half an hour and you can enjoy coffee and go to your next webinar. Oh no, there are more. No, I just scrolled down. Okay, let me read at least the chat. So Daniel said, actually I haven't managed to do anything with Ruby as yet. I do have familiar with the infinite recursion though and hope to use that knowledge at some point. Yeah, Jay Jesus said, in my experience Mathematica struggles when calculating integral transforms such as Laplace transform. Would Ruby tackle better such take better care of that. You have to try it out because the last time I used Laplace Transform was when I was at university. I provided the notebook I used as a handout I think and you can just install Ruby there and try it. So Ruby will also have problems with complicated integrals, especially if there are special functions in there that are hard to integrate, but you can really try it out. All right, so then thanks everyone and enjoy the rest of your evening. Morning, Afternoon.