Translator – Data Types and Operators

Three data types are currently planned: double precision (the default), integers and strings. Several operators accept all three as operands (plus, equality, relational and assignment). Consider the different possible operand combinations for the plus operator (the default data type is double, % is for integers and $ is for strings):

A + B
A + J%
I% + B
I% + J%
S$ + T$

Any combination between a number and a string is invalid and an error needs to be reported. However, doubles and integers may be mixed in an expression. The expression will remain integer for efficiency as long as there are integer operands. In a double expression, integers will be promoted (converted) to double.

If the plus operator was implemented as a single routine, at run-time it would have to look at the operands and then decide what action to take, whether to add two doubles, whether to convert one operand or the other from integer to double and then add two doubles, whether to add two integers, or whether to concatenate two strings. All this decision making will slow execution.

These decisions will of course be made before run-time by the Translator. The Translator will know which operation will be needed at run-time, so it will add the appropriate code to the RPN list. Since there are five different possible combinations, that would mean five different add operator codes. If this same thing was implemented for every operator, then the number of codes and the number of execution routines would be excessive.

There are really only three operations, adding doubles, adding integers and concatenating strings. For the other two combinations, one or the other operand needs to be converted from integer to double. To accomplish this, there will be special hidden conversion codes (which have already been mentioned in several earlier posts). With these hidden codes, the above expressions would be converted to RPN as:

A B Add
A J% CvtDbl Add
I% CvtDbl B Add
I% J% AddInt
S$ T$ CatStr

The Add handles doubles, AddInt handles integers, and CatStr (concatenate) handles strings. The CvtDbl code converts it's integer operand to double. For now, the focus will be on doubles and integers; strings require more involved handling and will be added later. Next, data types and internal functions...

Translator – Adding Operators

Adding operator tokens will be handled by the separate function add_operator(). Some extra processing must be performed in addition to adding the token to the output list and pushing the output list's element pointer onto the done stack like is performed for simple operands.

Eventually this function will verify that the data types of operand(s) of the operator are the correct data type. Also for the case of operators taking two operands of the double data type, if either of the operands is an integer, then the special hidden CvtDbl operator must be inserted into the output list after the operand. This is the purpose of having the done stack and why it contains pointers to the output list elements. The pointers will be used to insert tokens after an element when necessary.

For now, the operands will simply be popped off of the done stack. For unary operators, only one operand is popped off of the done stack. This function will return the status of adding the operator, which will be an error or Good upon success.

Translator – Unary Operators

Up to now, the subject of operators have referred to binary operators or operators with two operands. Unary operators only have only one operand. Only two unary operators are currently planned, - (negate) and NOT. Unary operators are found in expressions preceding an operand. Examples are -A + B, A + -B, and -(A+B). Two unary operators appearing together will be allowed, for example A + --B, but the translator will make no effort to try and optimize this (it's up to the programmer to make an effort to not do stuff like this).

When the current token contains a unary operator, it will be pushed directly onto the operator stack, since there are no operators currently planned that have the highest precedence. With the highest precedence, they will come off the stack whenever a binary operator is processed.

There will be two negate operators, one for integers (NegInt) and one for doubles (NegDbl), so the unary – operator will not need to insert any conversion operator. However, the NOT operator will only work with integers, so if the operand is a double, a hidden double to integer conversion operator (CvtInt) needs to be added to the RPN list before adding the NOT operator.

Translator – Operand Stack

When processing operators, it is necessary check the data types of it's operands already in the RPN list and it may be necessary to insert hidden conversion operators into the RPN list. The location of the first operand may not be the second to the last item added to the RPN list. Take the example A% * B% + C * D; the + operator will be the last operator to be processed, at which point the RPN list will contain A% B% MulInt C D MulDbl. For the + operator, which needs to be the add double operator also needs a CvtDbl inserted after the * operator, which has been changed to an multiple integer operator.

The Translator needs to save the location of where the previous operands are located, for both checking data types and for inserting conversion operators. This will be accomplished with another stack named the operand stack. When an operand is added to the RPN list, it's the pointer to element containing the operand in the RPN list will also be pushed onto the operand stack. When an operator is processed, it will pop it's operands off of the operand stack and use them to check data types and insert necessary conversion operator. After the operator is added to the RPN list, it's element pointer into the RPN list is pushed onto the operand stack for a future operator.

The operand stack parallels the run-time stack except instead of holding results of operands/operators, it will hold pointers to the items the will create the results during run-time.

Looking back at the example, when the + operator is processed, on the operand stack, there will be a pointer to the MulInt operator and a pointer to the MulDbl operator. It will insert a CvtDbl after the MulInt operator,  add an AddDbl to the RPN list and push it's element pointer onto the operand stack. The resulting RPN list will contain  A% B% AddInt CvtDbl C D MulDbl AddDbl. When this expression is executed during run-time, no time wasting decisions or checks need to be made.

Translator – Operators

As mentioned, operator tokens are pushed onto an operator stack after pulling higher precedence operators off of the operator stack and adding them to the RPN list. However, there is some handling that needs to be performed before an operator can be added to the RPN list.  For each operator, the Translator needs to check the data type of the operator's operand to be sure they are compatible with the operator and/or to add the proper operator dependent on the data types of the operands.

Take the + operator, which can have integer, double or string operands. If both operands are strings, then the concatenation operator needs to be added. For numeric values, it's a bit more involved. If both the operands are integers, then an add integer operator is added. If both the operand are doubles, then an add double operator is added. For an integer and a double, the result will be a double, but the operand that is an integer (which could be the first or the second operand) needs to be converted to a double before performing an add double operator.

The goal is for optimal execution, so having the add double operator check to see if the one of the operands is an integer that needs to be converted first during run time is not ideal. This check should be done before hand. If a conversion is needed, an internal integer to double conversion operator will be inserted into the code.  So, for the expression A% + B, the internal code will be A% CvtDbl B +. During run time, the CvtDbl will operate like a function or unary operator, when A% is pushed onto the run-time stack, the CvtDbl will pop it off the stack, convert it to double and push the double value back on the stack.

The Translator will insert these hidden operators into the RPN list after the appropriate operand as needed by the operator.  (This is why the List class was modified to have append and insert functions – see post List Class – Updated.) When the internal code is output by the Recreator, these hidden operators will not produce any output.