<< Click to Display Table of Contents >> Navigation:  Details > Walking the AST tree

The Gekko parsers produce so-called AST trees. As mentioned before, this is more complicated for commands and command files (.gcm) files than for models (.frm files). Se here regarding the parsers, or see here regarding an example of how to walk an AST tree while emitting dynamic C# code for subsequent execution.

 

Gekko commands AST tree

Walking this tree is a bit complicated. In principle, while walking the tree, it should be possible to just use the C# contained in the sub-nodes (which have already been evaluated), but some things are just more complicated than that. In those cases, while emitting C# code, it may be necessary to search the AST tree upwards, to see more context of where the particular code is situated. An example could be an expression like sum(#i, x[#i]). This function is not just a normal function, but has special functionality: namely that it will loop over the elements of #i (expected to be a list of strings), and sum up the array-series x[...] corresponding to these strings. But there is another kind of sum() function that also works, namelig sum(a, b), where the series a and b are summed like a + b. Therefore, when encountering x[#i] as the second argument of the sum() function, Gekko will look for the context. Is this x[#i] inside a sum() function, being its second argument? If so, does the first argument contain the list name #i? Such questions are answered by looking upwards in the AST-tree (and looking downwards inside another branch). In short, the AST tree is queried to obtain context. For instance, /Parser/Gek/ParserGekWalkASTAndEmit.cs contains the method SearchUpwardsInTree2() which looks for the precence of a sum() function. There are other methods for looking around in the AST tree, in fact SearchUpwardsInTree2()-SearchUpwardsInTree9() all do that.

Looking around in the AST tree typically has to do with more complicated structures of Gekko programs, like conditionals, loops, user-defined functions/procedures and such things. In essence, the AST tree walker functions as a kind of compiler, and compilers are known to do a lot of such looking around (using so-called symbol tables).

The main method for walking the command AST tree is WalkASTAndEmit(). This is a large and recursive method that calls itself, in the manner explained in the example here. But before WalkASTAndEmit(), another walker is called, namely WalkASTAndEmitUnfold().

The "unfolding" walker locates instances of the syntax x[#i], where #i is possibly a list of strings. If such an #i is encountered in the unfolding walker, Gekko will try to see if the #i is 'controlled'. Controlling is a GAMS concept, because GAMS uses syntax like sum(i, x(i)) to loop through dimensions of x, and Gekko uses sum(#i, x[#i]) to do the same. So when encountering #i in x[#i], Gekko tries to find out if this #i is defined (controlled) in for instance a sum() function. Another way to 'control' #i is in a statement like y[#i] = 2 * x[#i];, which will be looped over the #i elements (in GAMS, it would look like y(i) = 2 * x(i);). If a #i inside []-brackets is not 'controlled', it is considered 'uncontrolled'. This is legal to do in PRT/PLOT/SHEET statements, for instance prt x[#i];. This means printing the array-series x, where each column in the print corresponds to one element of #i (for instance x[a], x[b], x[c], if #i contains these three strings).

To do this, Gekko actually transforms/manipulates the AST tree itself corresponding to prt x[#i]; into an equivalent AST tree corresponding to prt unfold(#i, x[#i]);, introducing a Gekko-specific function called unfold(). Later on, in the normal AST tree walker, it is easy to handle unfold(#i, x[#i]),  because it can be treated just like sum(#i, x[#i]), where the 'controlled' #i variable is given explicitly and is easy to see.

But to return to the normal AST tree walker in WalkASTAndEmit(): this method consists of almost 5000 lines, so it is a large method. It deals with all the AST token names possible from the ANTLR parser and handles them. The walker operates with an absolute and relative depth. The absolute depth is augmented by 1 for each sub-node, whereas the relative depth is reset each time a command is encountered. Therefore, whenever relativeDepth == 1, we are at a node representing a Gekko command (because of conditionals, loops, etc., commands need not be at absoluteDepth == 1).

Near the top of WalkASTAndEmit(), there is this code:

 

This is where the sub-nodes are called, recursively. Almost all of WalkASTAndEmit() takes place after this, meaning that when a node is encountered after this, in the switch (node.Text), all the sub-nodes have their .Code contents already filled. For instance, we have this:

 

Note in general that the CA() method clears any code in the node and puts the argument into .Code, whereas A() adds the argument to existing .Code.

It says that if node.Text == "+", we are encountering an addition (it could be simple like a + b, or complicated like a1*a2 + a3[%a4]), and we are going to use the .Code contents of the two children nodes, in this case node[0].Code and node[1].Code. This is inserted into the pattern/schema O.Add(smpl, ... , ... ), because Globals.smpl contains the string "smpl" (which just represents the global sample period). So whatever the sub-nodes contain, this will be inserted into the O.Add() function. The resulting string is put into the .Code field of the present AST node. When the program is run, C# will encounter the expression O.Add(smpl, ... , ... ) and execute the O.Add() method. This method accepts a sample period (the first argument), and in addition two IVariables. So whatever type of variables is fed into O.Add(), the method will figure out how to add them (or issue an error if they cannot be added, for instance if it is two date variables).

Much of the code in WalkASTAndEmit() is of this kind: not too difficult to understand. Another example could be this (slightly abbreviated):

 

This code handles the CLEAR command. First, a line like O.Clear o25 = new O.Clear(); is emitted. The relatively arbitrary 25 here is returned from Num(node), which just fetches the node number, to avoid name collisions in C#. The next line issues a line like o25.names = ... ; where the ... is fetched from the second child node (remember that C# indexing is 0-based). In a Gekko command like CLEAR Work;, the full line would become o25.names = O.FlattenIVariablesSeq(false, new List(new List<IVariable> {new ScalarString("Work")}));. This may seem a bit convoluted, but it is because CLEAR supports a list of names as argument. So a new ScalarString variable is constructed, containing "Work". This is put into a List<IVariable>, which will have only 1 element, and will be fed to a Gekko List. Next, this list is flattened with O.FlattenIVariablesSeq(), because the argument could in principle be a nested list (which it is not here). This is assigned to o25.names, which is a Gekko list variable. In the next line in the box, the GetCodeFromAllChildren() method gets all code from node[0], that is, the first child of the ASTCLEAR node. This sub-node may or may not contain options, for instance if a Gekko command like clear<ref>; is used. Finally, the last line issues something like o25.Exe();, calling the Exe() method of the O.Clear class. This method will handle what needs to be done regarding the CLEAR command.

All in all, a Gekko CLEAR like clear Work; will emit code corresponding to this:

 

So in this sense, the AST tree walker acts like a translator, translating from Gekko commands into corresponding C# code.

The most complicated of walker code is probably the following parts, which are explained in more details:

 

---

 

ASTASSIGNMENT

An assignment is a statement like y = 2 * x;, where the right-hand side (rhs) is assigned to the left-hand side (lhs). The complication here is that assignments may also contain indexers. So we may have for instance y[2020] = 2 * %x;, which is a different kind of assignment. Another example could be an assignment like #m1.#m2.%x = 100;. The assignment says: take the map #m1, find the map #m2 inside #m1, and assign the value %x = 2 inside the map #m2. So this assignment is in reality two normal lookups (#m1 and #m2), with an assignment at the end (%x = 2). The length of the ASTASSIGNMENT code has to do with this.

 

ASTASSIGNMENT may also loop, like in for instance y[#i] = 2 * x[#i];, looping over the string elements of #i.

 

For timeseries assignments, Gekko will perform a check of whether the statement is dynamic, like x = x[-1] + 1;. If so, it may be run dynamically if an option is set. Running it dynamically basically means running it period for period, instead of in one go.

 

Assignments in maps is also handled, for instance #m = (%x1 = 1, %x2 = 2);. This is in reality three assignments.

 

---

 

ASTBANKVARNAME

 

This code handles a "variable", where the variable can contain bankname, symbol/sigil, variable name, and frequency. For instance b1:x!q for a quarterly variable x from the b1 databank, or b2:%y for a scalar %y from the b2 databank.

 

The code works differently depending upon whether the variable is on the left-hand or right-hand side. And as mentioned regarding ASTASSIGNMENT, an assignment like #m1.#m2.%x = 100; really is only an assignment of %x, not of #m1 or #m2.

 

In general, a bankvarname may be composed, using {}-curlies. For instance, the name {'b1'}:{'x'}!{'q'} is the same as b1:x!q, and any string expression can be used inside the {}-curlies. If the bankvarname is simple, like b1:x!q, Gekko can produce code that looks up the variable fast, without boxing the strings inside Gekko strings. Some of the code deals with this fast lookup.

 

Also, the code handles if the variable is "controlled", like for instance the #i inside the []-brackets in the following expression: sum(#i, x[#i]). In this expression, #i is "controlled" by the sum() function. Another example of controlling is if a variable x is a function definition argument. If so, the function argument value is assigned to x.

 

---

 

ASTDOTORINDEXER

This code deals with dots like #m1.#m2.%x, or the equivalent indexes like #m1['#m2']['%x'], which is the same thing. It also deals with more normal indexes, like x[2020] etc.

 

The code first checks whether the dot/index is on the left-hand side (by searching up in the AST tree). If so, it is treated differently.

 

Next, for [] kind of indexes, it is checked whether the inside of [] is a sum or difference (with + or -), like for instance [#i+1]. If so, and if #i is a "controlled" variable like in sum(#i, x[#i+1]), the O.AddSpecial() method is used instead of the normal O.Add() method. This method allows to add/deduct something to for instance an age variable like pop[#a], where pop is an array-series defined over ages #a, and where the ages are strings like '1', '2', '3', etc. Normally you cannot add '3' and 1 (adding a string and a value), but O.AddSpecial() allows it via converting '3' into 3, adding 3 and 1, and converting 4 into '4'. Therefore, you can use lags/leads with ages.

 

Take note: indexers like x[a] with a simple a ident are in general understood as x['a'].

 

The code also checks if the inside of a []-index starts with + or -. If so, the index is always considered a lead or lag, and special code is used to evaluate it. Therefore, at lead or lag must always start with + or -, no exceptions, which makes it  less error-prone to use leads/lags. For something like x[%i], just stipulating that if %i is > 0, it is a lead, and if %i < 0, it is a lag is not good. What if, for instance, x is an undated series, where x[1] is the first observation? Then x[1] could both be the first observation or leading the whole series, which is confusing.

 

A special form of dot is the function dot, like x.avgt() or similar functions. Such a dot function is understood as avgt(x), and this translation is done here, too.

 

Left-hand side assignments are also handled here, via calls to the O.IndexerSetData() method. This happens for instance in a statement like x[2000] = 3;, where first x is looked up, and then the value 3 is assigned to the [2000] element of x.

 

---

 

ASTFUNCTIONDEF2, ASTPROCEDUREDEF

Functions and procedure definitions are handled in much the same way: a procedure can be thought of as a stand-alone function that does not return anything.

What should be noted about function and procedure definitions is that they allow the use of time periods inside <>-tags. For instance, when calling a function, like y = f(<2000 2010>, x1, xy);, where 2000-2010 will be used as local period. The parameters of such a field are stated like for instance this: function series f(<date %t1, date %t2>, series ser1, series ser2); ... ; end;., so that %t1 and %t2 can be used inside the function. But such a field is optional, and if it is omitted, like the call f(x1, x2);, the dates %t1 and %t2 will attain values corresponding to the local or global Gekko time settings.

 

All this means that when counting the parameters of a function/procedure in node.functionDef (which is a List<ArgHelper>), the optional time periods attain parameter numbers 0 and 1 in the list, and the first "real" parameter gets parameter number 2.

 

Another thing to take note of it the so-called name type for functions/procedures. This makes it possible to call a function as for instance f(abc), where the argument is name type. In that case, because it is name type, Gekko will not try to first find a timeseries abc. Instead it treats abc as the string 'abc', just as if the argument type had been string, and the call had been f('abc'). This can be practical, avoiding to type superfluous single quotes.

 

Finally, there is the question of optional parameters. You may define a function like function val f(val %x1, val %x2 'parameter 2' = 1); ... ; end;, where the first argument is mandatory, and the second can be omitted. So you may use f(3, 4), but if you use f(3), %x2 will be set to 1. Also, you may activate prompting by calling f?(3), in which case Gekko will ask you for the value of the last parameter (in a dialog box). When a function/procedure with optional parameters is defined, Gekko actually constructs all the overloaded variants. For instance, with function val f(val %x1, val %x2 'parameter 2' = 1, val %x3 'parameter 3' = 1); ... ; end;, Gekko will construct three "physical" functions. One with just %x1, one with %x1 and %x2, and one with %x1, %x2, and %x3. This is what is done in the last part of the code.

 

---

 

ASTFUNCTION, ASTPROCEDURE

Function and procedure calls. Also covers ASTFUNCTIONNAKED, ASTOBJECTFUNCTION, ASTOBJECTFUNCTIONNAKED, ASTFUNCTION_Q, ASTFUNCTIONNAKED_Q, ASTOBJECTFUNCTION_Q, ASTOBJECTFUNCTIONNAKED_Q, ASTPROCEDURE_Q.

 

Functions and procedure calls are handled in much the same way: the procedure can be thought of as a stand-alone function that does not return anything.

In general, the function calls can be normal (like y = f(x);), naked (like f(x);), object function (like y = x.f();), and with question symbol (like y = f?(x);). Therefore these combinations. Procedures, though, have only 1 variant.

In the code, a function call like sum(#i, x[#i]) is treated differently. In essence, this will loop over the elements of the list of strings #i, and use these elements in x[#i]. It may also be an unfold(#i, x[#i]), which is a special function created by Gekko to handle printing of columns of data (when issuing for instance prt x[#i];). If it is such a function, Gekko will emit a Func<> that handles this looping. Also, $-conditions in sum() functions are handled.

If not a sum() or unfold() function, it is first tested whether it is a Gekko inbuilt function. If it is, the function may contain meta-information about lags. For instance, the in-built function movavg() has the following line: [MyCustom(Lag = "lag=[4]-1")]. The movavg() function is called like y = movavg(x, 3);, being the same as y = (x + x[-1] + x[-2])/3;. The problem here is that the inside of movavg() may be an expression, for instance y = movavg(x + y, 3);. Since timeseries in Gekko 3.0 are treated in a vector-like fashion, when doing the addition x + y, Gekko has to perform this over the period t1-3 to t2, where t1 and t2 are the start and end period. If this is not done, there will be missing values in the y = movavg(x, 3); statement (in the first three observations of y). Therefore, the meta-information [4]-1 tells Gekko to look for a particular function argument (in this case argument number 2, corresponding to the value 3), and use this to augment the sample period. Read more about this issue here.

Otherwise, the code also handles user-defined function and procedure calls. User-defined functions/procedures do not support the above-mentioned meta-information regarding lags. Maybe it should...