Artem's blog

Mainly .NET (C#, ASP.NET) and my projects

Archives for Mathos Project

Mathos Parser is now an expression compiler

The requirement of performing several thousands of calculations (for example, during integration) led to the optimization with pre-scanned expressions. But the aim to make Mathos Parser even faster still remained. Now, I would like to introduce you to a new project of Mathos Project – Mathos Expression Compiler, based on the math tokenizer and parser logic of Mathos Parser.

This API allows you to parse an expression and “store” it as CIL code. Then, using ILAsm, you can generate a new assembly that will contain your expression entirely parsed. The only operation that occurs at runtime is the insertion of values into the variables that you declared and the operation on that variable value. To make it even faster, most of the calculations are already done before the runtime, for example, x+3+5 would be stored as x+8.

In this scenario, the time consideration can be important. Even if it is faster to execute CIL instructions, the compilation process can take some time. This has not been tested yet. The process is illustrated below:

a1

This is a very simplified way of looking at it but the point is to always test Mathos Parser together with Mathos Expression Compiler and make an estimate of how much time would be saved in different scenarios. It all depends on the context. But note, that

A performance hit is incurred only the first time the method is called. All subsequent calls to the method execute at the full speed of the native code because verification and compilation to native code don’t need to be performed again. //p. 12. Jeffrey Richter. CLR via C# 3rd Edition

So, if you plan to execute the function trillion times, it might be a good a idea to keep in mind the Expression Compiler as a better alternative, because at that point, the compilation time will be negligible.

Now, back to the features. It was mentioned in the beginning that it is based on the Mathos Parser. Note, in terms of features, Mathos Expression Compiler has at this point only a subset of those of Mathos Parser. At this point, you cannot have functions as sincos, and your own custom functions, but this will be changed in the nearest future.

There are also some changes to the way operators work. To declare an operator properly, you should use the variables OperatorListOperatorAction, and OperatorActionIL. Below, a simple example of addition operator:

Comparison operators are a bit more tricky. An example of greater than operator is shown below:

For those who understand IL, the @ sign might seem a bit strange. It is simply a way to tell the stack count to the if statement (in the compilation process).

When you actually generate an expression, this is how your IL code for that expression might look:

Will return (only IL for the expression):

When you have the IL code, you should name the output executable(or dll) as MathosILParser, otherwise, you might get an error. In future, an option will be added to customize the name of the output file, but at this point, please use RegEx (or replace option) to change the MathosILParser.exe to something else (in the IL code).

Your function can later by called as shown below. Note, I am not using reflection at all.

I hope this short guide was helpful, even if it might be a bit messy. If you have performed any testing related to speed or if you want to show some examples, please feel free to comment or contact me.

The advantages of pre-scanned expressions

RubyInt project, or Iron Ruby Based Mathos Core Library Interpreter was one of the projects to be tested with the new parser feature, that is, pre-scanned expressions.

In the Integral approximation module, it is quite good to use pre-scanned expressions, since the expression stays the same through the entire process. The execution time improved in this case.

The integral approximation website in Mathos Laboratory (see it here) has also shown good results thanks to this optimization. In Mathos Laboratory in particular, it is important that methods are quick and use as small amount of resources as possible, because it is hosted in the Cloud.

I have performed some quick tests using an i3 processor (the methods are in changeset 37964), although I would not recommend them to draw specific conclusions (there is a random error involved so more repetitions of each test are needed). Also, the difficulty level of an expression can affect the tokenization time. The graphs are located below:

mp2

mp_separatly

One conclusion that can be drawn from this is that the optimization only gets useful when the same expression is evaluated more than 100-500 times.

Faster evaluation using a pre-scanned expression

[This article was updated to included changes in v. 1.0.7.2. Originally written for v. 1.0.7.1]

Today, I published a newer version of Mathos Parser on both CodePlex and NuGet. The release notes:

from v.1.0.7.2:

  • Force user to use ReadOnlyCollection when using a token list as a parameter.

from v. 1.0.7.1

  • Added method GetTokens
  • Changed the structure a bit. Now, the Scanner returns tokens instead of continuing with MathParserLogic. This is good if the same kind of expression is to be used many times.

But what does this really mean? Well, previous versions of the parser worked more locally, that is, once one function was executed, it triggered another function, and so on. Now, however, the Scanner (private method) returns a list of tokens instead of launching MathParserLogic directly. If you simply want to get tokens, you would have to execute the GetTokens function, as shown below:

You can then send the tokens list into either Parse or ProgrammaticallyParse and it will parse it in the same way as if you would enter a string expression, that is:

Both statements above will return 32, but there is one main difference; the execution time will be so much smaller for the second statement, where a “pre-compiled” list is being used. If it would take 100 milliseconds (ms) to find the value of the first statement, it would take approximately 9-10 ms for the second one. The ratio is 10:1.

This is great if you want to perform an operation where the same function is involved several thousands times, for example when approximating an integral.

I am currently thinking about converting math expressions into IL code, but this will happen sometime in future!

Creating a programming language with Mathos Parser (2)

In this article, I would like to find out whether it is possible to construct a programming language with Mathos Parser. In general, the question is if a simple expression parser has the necessary things to easily convert it into a language.

The answer is yes, but the language will be very limited if additional features are not added. The reason for this is because what most languages have in common is some sort of  user/machine interaction, while an expression parser only allows you to parse mathematical things and is not really designed to interpret how to write to a file or allocate memory.

For example, imagine you want to create something similar to if statements  and you decide to treat an if as a function. You would use following code:

So, if whatever we pass into the first parameter is true, the value in the second parameter will be returned. This is quite cool, but it does not allow us to return a series of statements. Instead, we could design a new kind of if statement that would, depending on the result from this if function, execute the right method. Here is how I solved it:

As you can see, the if statement is still there, but there is now a feature that will interpret the result and make something happen. You can also use \n to separate between different statements and also name a collection of statements, as shown below:

Note that both examples use a function get(). It can also be implemented as a function:

You might have noticed the use of statements (see notTrue statement). Their role is to simulate a method. Everything you enter into a statement will not be executed until you call it, so you can insert undefined variables into a statement when you define it and later assign them with a value. I have also added commands like write, title, pause, clear and end. These are extensions to the language and are interpreted in the method below:

Some programmers will certainly argue that the code above is not that optimized and is quite primitive. Well, it serves its purpose and makes Mathos Parser look more like a language.

In the next article I want to implement a while feature into this awesome programming language.

Conclusion: Just because something can parse expressions does not mean it can parse a series of statement. In order to fix this we can either choose to add some features externally, or, go into the parser itself and make it more adjusted to this particular task. This language does not alter Mathos Parser in any way.

Downloads:

Factorial notation in Mathos Parser (1)

In this article series, I would like to look at how Mathos Parser (a very simple expression parser) can be used to perform things that were not originally intended. Today, I am going to show what has to be done to make Mathos Parser able to interpret factorial notation, such as “4!

Already in the parser, we can solve this in at least two different ways:

  • creating a localFunction fact() that will take one parameter and return the factorial of that number
  • using FactorialPower(falling power) instead, that is 4!4 would be 24 and 4!1=4.

Both methods do not require you to change anything in the input string, but they might not be as close to the mathematical notation as we want it to be. Therefore, as a part of this article, I am going to illustrate the changes in the input string that have to be made, to make it understand 4!.

  1. Include Reg Ex name space as following:
  2. Add these two methods somewhere in the class:
  3. Define the Mathos Parser and add a definition of the factorial operator including the way it should be executed. Note, at this stage, for this to work, the factorial number has to be in the form of 4!0 or 4!1 ((both result in 24).
  4. Before the input string can be parsed, perform the following action (assuming you have defined a variable input with a value):
  5. Parser the string and store the result:

This is how we can make Mathos Parser able to understand mathematical notation of factorial. In the next article of this series, we are going to look at how Mathos Parser can be used to construct a new programming language.

Evaluate string expressions

Learn more about how to change a lambda expression on runtime: http://mathosproject.com/updates/convert-a-string-expression-into-a-lambda-expression/

Integral approximation

Constructed an integral approximation application: http://mathosproject.com/updates/integral-approximation-tool/

Mathos Project website updating

Mathos Project websites, http://mathosproject.com/ and http://mathosproject.info/ are for the moment under a big update, and hence not available for the moment. This will be fixed 31/1, but it might take longer time depending on several factors.

Please check back soon! 🙂