Engineering a compiler through examples: building a mathematical expression engine - Part 6
In this final post, we'll explore how our simple lexical analyzers and parsers can be practically applied to solve meaningful and interesting problems.
We will in fact attempt to solve a simple optimization problem: finding the minimum of a basic function (as we know, in certain cases, we can make use of derivatives to efficiently determine the solution).
What are we aiming to achieve ?
What we want to address is finding the minimum of a function of two variables: $f(x,y)=xsin(y)+x^2$.
We won't delve into the mathematical details here, but as we learned in school, a minimum often occurs where the gradient of the function is zero (this isn't always the case, as such a point could also be a saddle point—but we'll keep it simple for now). In essence, our goal is to find a point where the gradient of $f$ vanishes, i.e., where $∇f=0$.
We are therefore led to solving a system of nonlinear equations, and for this, we can turn to the Newton-Raphson method. Once again, we won’t dive into the finer details of the technique—suffice it to say that the minimum $x_{min}$ is approximated iteratively using the following formula.
$$x_{min}^{(new)} = x_{min}^{(old)} + H^{-1}(x_{min}^{(old)}).∇f(x_{min}^{(old)})$$
$H$ denotes the Hessian of the function, which is the matrix of second-order partial derivatives.
Coding the algorithm in our framework
First, we will define a Function class to simplify the manipulation of our mathematical expressions.
1public class Function
2{
3 private ITokenizer _tokenizer;
4 private IParser _parser;
5 private Expression _inner;
6
7 public string Definition => _inner.ToString();
8
9 private Function(Expression inner)
10 {
11 _inner = inner;
12 }
13
14 public Function(string definition)
15 {
16 _tokenizer = new Tokenizer(new StringReader(definition));
17 _parser = new Parser(_tokenizer);
18 _inner = _parser.Parse();
19 }
20}
The constructor takes a string as input, representing the natural way to define the function. Internally, this string is parsed using the tokenizer and syntactic parser, and is then converted into an expression. The private constructor is intended for internal use only and will prove useful later on.
A function can now be easily declared as follows.
1var f = new Function("x*sin(y)+x^2");
To streamline things further, we will also define a DifferentiateWrt method in this class, which will provide an easy way to differentiate a function with respect to a given variable. Similarly, we will implement an Evaluate method to compute the value of a function at a given point.
1public class Function
2{
3 private ITokenizer _tokenizer;
4 private IParser _parser;
5 private Expression _inner;
6
7 public string Definition => _inner.ToString();
8
9 private Function(Expression inner)
10 {
11 _inner = inner;
12 }
13
14 public Function(string definition)
15 {
16 _tokenizer = new Tokenizer(new StringReader(definition));
17 _parser = new Parser(_tokenizer);
18 _inner = _parser.Parse();
19 }
20
21 public Function DifferentiateWrt(string variable)
22 {
23 var differentiator = new DifferentiationExpressionVisitor(variable);
24 var simplificator = new SimplificationExpressionVisitor();
25
26 return new Function(_inner.Accept(differentiator).Accept(simplificator));
27 }
28
29 public double Evaluate(List<(string, double)> parameters)
30 {
31 var evaluator = new EvaluationExpressionVisitor(parameters);
32
33 return (_inner.Accept(evaluator) as ConstantExpression).Value;
34 }
35}
Here, we can see the result of our efforts: differentiating a function becomes an intuitive task, even though behind the scenes, sophisticated data structures and design patterns are at play.
We can now apply all of this machinery to implement the Newton-Raphson method.
1internal class Program
2{
3 static void Main(string[] args)
4 {
5 var n = 300;
6
7 var f = new Function("x*sin(y)+x^2");
8
9 var dfx = f.DifferentiateWrt("x");
10 var dfy = f.DifferentiateWrt("y");
11 var dfxx = dfx.DifferentiateWrt("x"); var dfxy = dfx.DifferentiateWrt("y");
12 var dfyx = dfy.DifferentiateWrt("x"); var dfyy = dfy.DifferentiateWrt("y");
13
14 var v = Vector<double>.Build.Dense(2);
15 v[0] = 1.0; v[1] = 2.0;
16
17 for (var i = 0; i<n; i++)
18 {
19 var grad = Vector<double>.Build.Dense(2);
20 var H = Matrix<double>.Build.Dense(2, 2);
21
22 var parameters = new List<(string, double)> { ("x", v[0]), ("y", v[1]) };
23
24 Console.WriteLine($"value of f: {f.Evaluate(parameters)}, x: {v[0]}, y: {v[1]}");
25
26 grad[0] = dfx.Evaluate(parameters);
27 grad[1] = dfy.Evaluate(parameters);
28
29 H[0, 0] = dfxx.Evaluate(parameters);
30 H[0, 1] = dfxy.Evaluate(parameters);
31 H[1, 0] = dfyx.Evaluate(parameters);
32 H[1, 1] = dfyy.Evaluate(parameters);
33
34 var HInv = H.Inverse();
35
36 v = v - HInv.Multiply(grad);
37 }
38 }
39}
The Newton-Raphson method requires computing the multiplication of a matrix with a vector or inverting a matrix, which is why we rely on a dedicated linear algebra library to handle these operations.
The code is quite straightforward, and thanks to our compiler, we can easily minimize any function. All the complexity is hidden from the user and handled by the computer.
Running the program
The minimum is easily obtained (thanks to the efficiency of the Newton-Raphson method) and we successfully compute the minimum of the function.
Final thoughts
If you wish to delve deeper into this topic, acquire the following books, which encompass all the concepts emphasized in this series and delve into more advanced ones.
- Engineering a Compiler (Cooper, Torczon)
- Compilers: Principles, Techniques, and Tools (Aho, Ullman, Sethi, Lam)
- Design Patterns: Elements of Reusable Object-Oriented Software (Gamma, Helm, Johnson, Vlissides)
Do not hesitate to contact me shoud you require further information.