Reference Vs. Temporary Strings

During run-time as expressions are executed, the result from each operator or function is pushed back onto the evaluation stack. This result is considered a temporary value, which will be used by the next operation (operator, function or command). The evaluation stack holds these temporary values. However, the actual character arrays for strings, including temporary string values, will not be contained in the stack elements, only a pointer (and length) of the character array. Consider this string expression and it's translation:

A$+B$+C$  A$ B$ +$ C$ +$

As this expression is executed, the value of A$ is pushed onto the stack. For double and integer variables, values are simply copied to the stack. However, for strings, only it's character array pointer and length will be copied to the top item on the stack. This prevents having to allocate a new array and to copy the actual string value of A$ to the array. This item on the stack is a reference string. Similarly, the value B$ is pushed onto of the stack.

At the first +$ operator, a string needs to be created to hold the concatenation of A$ and B$. First the A$ and B$ operands are popped from the stack. The size of the result character array is allocated for the total length of A$ and B$. The contents of A$ and B$ are copied to this character array. The resulting string's length and character array pointer are then pushed on to the stack. This item on the stack is a temporary string.

The value of C$ is pushed on to the stack. At the second +$ operator, another temporary string needs to be created to hold the concatenation of A$+B$ (now a temporary string on the stack) and C$ (a reference string). Both operands are popped off of the stack and a temporary string is created as before. However, for this operator, after the result has been pushed on to the stack, the character array of the temporary string holding A$+B$ needs to be deleted. Next, what implications this has on the Translator...

String Data Type

It now time in the Translator development that consideration needs to be given to how the program will be executed at run-time, which will determine what the Translator needs to do - and this applies to strings. Keeping in mind that the goal is to do as much work and decision making during translation so that it does not have to be done at run-time, which will aid in fast execution.

During execution, operands are pushed onto the evaluation stack, popped off by operators and functions, evaluated and the result pushed back onto the stack. Each evaluation stack element can hold a double or an integer. Strings are a little more involved. Strings are variable length and can be quite large, therefore a stack element cannot hold a string (or the stack would be very large).

C++, the underlying language, does not have a string type. Strings are handled as character arrays. These arrays need to be allocated for the appropriate size as needed and deallocated when no longer needed. A stack element will be a union of the different types that can be pushed onto the stack (double, integer, reference, etc.). For a string, the item in the union will be the previously implemented String class, which contains the length and pointer to the string's character array. Next, the difference between a reference strings and temporary strings...

Translator – Data Types and Assignments (Release)

Testing started by using the previous six translator test input sets. First discovered that a check was needed for a NULL expression information structure pointer in the data type and unary code access functions, specifically for the Null and EOL codes. Also discovered that any unary operators needed their own expression information structures since all that standard ones set the unary code to the Null code. Many other minor bugs discovered with these test inputs were corrected.

There were no differences with the first four test input sets, since these contain only expressions with no assignment operators. The fifth and sixth test input sets had differences because either the correct data type assignment operator is now being added or a hidden conversion operator is now being inserted. Even though care was taken to make sure all the assignments in the test inputs were valid, one statement was trying to assign an integer to a string, so this expression was corrected.

A seventh test input set was added. One of the errors tested pointed to a token that may not be appropriate. The statement “A=B$+5” produces a data type error as expected, but the error is “expected string” pointing to the 5. This is not wrong, the plus is processed first and with the first operand a string, the Translator expects a string for the second operand, hence the error. But this may be confusing to the user, the error should probably be “expected double” pointing to the B$. This will be left as is for now to be revisited later, since there is no easy fix for this.

The code now handles data types for assignment operators and ibcp_0.1.10-src.zip has been uploaded at Sourceforge IBCP Project along with the binary for the program. Next the string handling needs to be expanded...

Translator – Data Types and Assignments (Implementation)

The only issue that occurred as support for data types were being added to assignment operators was developing code to return the proper error and the proper token for assignment lists. The issue was that the error should point to the first token in the line that has in error, which is complicated by the fact the the items in the list are processed in reverse order as that is how the tokens are pulled from the done stack.

This section proved to be difficult to implement, so the gory details won't be included here. An added complication was that a not a reference error should be reported on a token that is both not a reference and is not the correct data type. Basically the code needs to keep track of the last operand processed. A reference error is reported on the current operand being processed, but a data type error is reported on the last operand processed, but only if it is a reference (otherwise a reference error has already been set for the token).

Now that these changes have been implemented and compile successfully, debugging and testing can begin...

Translator – Expression Information (Revisited)

Sometimes programing is an evolutionary process. The final solution is not arrived at initially, so an intermediate solution is made. Once made, another better solution is made. And so on until  arriving at a final solution. And this seems to be the case with the expression information, which has taken a while to arrive at a good solution. The changes described in the last post were completed, but they didn't look very good (very cluttered) – maybe there was better way, perhaps using new operator as originally planned.

It was also observed that a lot of the operators had the same operands, for example one double, two doubles, two integers, etc. There was no reason to have an operand array with two double data types for every operator that requires this – in other words, the same array could be used for all the operators (or internal functions) that take two double operands. There only needs to be one data type operand array for each unique operand set – so there will be one DblDbl_OperandArray that will be used for all operators or internal functions that take two double operands, an so on for the other possible operand sets.

All the possible unique operand arrays will be defined using the convention Dbl, Int, and Str for each operand data type (e.g. StrInt for two operands, a string and an integer operand). All the associated codes arrays will defined next, where each code has it's own array. There will be two macros (defines) that will produce the arguments for the expression information constructor in the table entries, which will look like this:

new ExprInfo(Double_DataType, Null_Code, Operands(DblDbl), AssocCodes(Add))

In this example, the Operands macro will produce two arguments, a 2 for the size of the operand array and a pointer to DblDbl_OperandArray. The size of the array will be calculated within the macro. The AssocCodes macro will be similarly defined. The constructor will have default argument values so if there are no associated codes, the AssocCodes() argument would not be included and the number of associate codes would be set to zero and the array pointer set to a NULL. Similarly if there are no operands.

As the table entries were being updated, it was observed that many of the entries had identical expression information constructor calls – for example, the math functions generally return a double, have no unary code, have one double operand and no associated codes. Again there is no reason to have a separate expression information structure for each one. So there will be comman expression information structures defined for these in the form of Dbl_Dbl_ExprInfo (returns double and has one double operand) and Int_IntInt_ExprInfo (returns double and has two integer operands), an so on. The address of these will be put into the table entries.

The table entries for the main codes are unique because each has it's own associated codes array, so the new ExprInfo syntax listed above will be used for these. This may still not be the best solution, but it's good enough for now, and I need to stop fiddling with this and get data type handling for assignments implemented...

Translator – Table Entry Expression Information

There will be an expression information structure for holding the expression related data for operators and internal functions (data type, unary code, number of operands, operand data types, number of associated codes and associated codes). The plan was to use the new operator along with the constructor of the expression information structure within the table entries like this:

{value, value, new ExprInfo(value, value, …), value, …},

The constructor would have a variable number of argument depending on the requirements of the operator or internal function. However, in practice this did not work. While variable arguments can be used in constructors, the actual arguments in the “...” can not be enumerations. So instead, the expression information structure along with the operand data type and associated code arrays will be defined outside of the table entries like this:

DataType Op_OperandDataType[2] = {Double_DataType, Double_DataType};
Code Op_AssocCode[1] = {OpInt_Code};
ExprInfo Op_ExprInfo(Double_DataType, Null_Code, 2, Op_OperandDataType,
  1, Op_AssocCode);

If there are no operands (no argument internal functions only) or associated codes, then there will be no need to define these arrays. The constructor will be defined with default arguments that will set the pointers to the arrays to NULL. For the expression information above, the table entry will look like this:

{value, value, &Op_ExprInfo, value, …},

The table access functions will be modified to get the data using the expression information structure pointer of the table entry instead of direct members of the table entry. Because of the nature of C++, none of the code that uses the access functions need to be modified, with one caveat. The match code function assumed there were two associated codes and stopped its loop when a Null code was found. This function will be changed to get the number of associated codes (a new access function) and use that value for the loop. Fortunately this is a very minor change.

Now there is a lot of editing to modify the table entries for the new expression information structures and then on to implementing data handling for the assignment operators...

Translator – Table Entry Restructuring

In looking ahead in the design of the assignment operators, I realized the size of the associated code array will need to increase from 2 to 5. This is due (spoiler alert) because there will be three types of strings internally – more on this when the design of strings begins shortly. Having an associated code array size of 5 for only two operators is a waste. There's needs to be a little more efficient storage system that doesn't penalize all the table entries for only two entries. Similarly for the operand data type array (now set at a size of 3).

In thinking about this further, only the operators and internal functions require the data type, unary code, number of operands, operand data types, associated codes and perhaps even the precedence. Currently the precedence for commands is obtained from the table entry, but no actual values have been entered yet. The design and implementation of commands is further done the line, so for now, precedence will remain implemented as is.

Anyway, for operators and internal functions, the information mentioned can be put into an expression information structure, for which a pointer to this structure will be put into the table entry. The expression information structure (class) will have a constructor to initialize the members from the constructors arguments and the new operator will be used to allocate the structure. Likewise for the operand data type and associated code arrays – the arrays will be allocated for only the size needed.

Translator – Data Types On Assignments

The assignment operators need a little bit different handling that regular operators because they require reference tokens for the operands being assigned. The reference tokens will have a specific data type and can not be converted between types. Only the value being assigned can be converted to the type of the reference operands. An added complication with the assignment list operators is that they have no set number of reference operands so the number of operands and the operand data types in the table entries will not work, which the match code routine relies on.

To support the assignment operator, the match code routine needs to be modified so that when it sees a reference operand, to only check if the data type matches exactly to the data type in the table entry. The main assignment operator (Assign, which will handle the double data type) will have two associated codes, AssignInt and AssignStr. The second operand for Assign and AssignInt can be converted.

For the assignment list operators, it has already been decided that all of the variables being assigned must be the same data type, in other words, no mixing of doubles and integers – mainly for efficiency during run-time. The match code routine was not designed to handle a variable number of operands for a code. However, the match code routine can be used, at least to check the two operands on top of the done stack, which would be the value being assigned and the last reference operand in the list being assigned.

In the add operator routine, upon returning from the match code routine successfully, it can then check if the operator is an assignment list operator. This can be accomplish with a new assignment list operator flag in the table entry. If this flag is set, then the add routine would proceed to check the rest of the operands on the done stack for the reference flag (which it does now) and check to see if the data type is the same as the assignment list operator returned from the match code routine.

Translator – Data Types (Release)

The remaining minor bugs were found by simply tracing through using the debugger. There are minor differences in the previous test input sets due to the addition of the internal CvtDbl and CvtInt codes. Many test inputs were added for the sixth set of the test inputs for the data type handling including several error tests.

Now that the source tree is under CVS, the full source tree is being released with all the test sub-directory files. All the test output files have also been located in the test sub-directory. In the future, the full source tree will only be release for major releases (which means for the interim releases, only the main project files, current test output files and any new test program source files will be included).

The code now handles data types in expression (but not the assignment operators) and ibcp_0.1.9‑src.zip has been uploaded at Sourceforge IBCP Project along with the binary for the program (which now will run from the Windows command line and without MinGW being installed). Next the data type handling for the assignment operators...

Translator – Data Types (Implementation)

The final implementation of the data type handling was completed except for assignment operators – these will take a little extra processing because of the references (which are not convertible), plus the assignment list operator does not have a fixed number of operands. The assignment operators will be handled later.

The new find_code() function returns a Status enumeration value, either Good upon success or one of the three new error codes for the “excepted <data type>” errors. A reference to the token is passed so that it can be changed to point to the error. I realized that the comma and close parentheses tokens were not being deleted in all cases. There needs to be some sort of memory leak checking added to the program. The new and delete operators can probably be overloaded, so some checking can be added. This is a side-project for another day, but it is needed.

Testing began with the existing Translator test inputs (1 through 5) – some differences were expected (new conversion codes). What follows are some of the changes that were needed as the debugging progressed:

When the operands are being popped off of the done stack (the operand array needs to be filled in reverse order), the reference flags needed to be cleared (no need to check if it is set first), just like was previously being done for operators and internal functions.

When checking the associated codes and a convertible match is found, it is only recorded if no convertible match has been found so far (in other words, find only the first convertible match).

When changing the token to a new associated code, in addition to changing the index in the token, the data type also needed to be set to new code's data type, which might be different than the main code (for example Abs returns Double, but AbsInt returns Integer).

Quite a few of the expressions in the existing test inputs are not working correctly, or worse, causing the program to crash. One test input VAL(STR$("1.23")) was written incorrectly in the first place, which should have been VAL(STR$(1.23)) or STR$(VAL("1.23")), but at least the code properly detected this error.  Debugging continues...

Project Executable Issue Resolved

The cause of the problem why the executable would not run in the Windows (XP) command window was finally identified. During the transition to CVS, it was discovered that the older executables had no problem running in the command window. The problem started with release 0.1.2 (release 0.1.1 worked). Some time was finally spent investigating what changed between 0.1.1 and 0.1.2 to cause this problem.

During the investigation, it was also discovered that the executables require libgcc_s_dw2‑1.dll to run. This library comes with MinGW. The GCC GNU GPL (General Public License) prevents this library from being distributed with executables without also distributing the source code for it – something not desirable. However, there is the linker option “‑static‑libgcc” that will statically link this library into the executable, which is permitted under the GCC GPL, so future executables will be linked this way. VIDE complains about this option upon loading the project indicating libraries should be entered in the project library tab – but it does correctly use this option on linking. This will be left as is for the moment. Unfortunately, this library issue was not the cause of the command window problem.

After further investigation, the problem was determined to be caused by  the transition from the test_parser program to the ibcp program (the test_parser.cpp source file to the ibcp.cpp and test_ibcp.cpp source files). One of the changes made was in the GPL header print function to print the actual name of the executable, not a fixed string. This simply involved printing the first command line argument. Under MSYS, Insight (GDB) and apparently when run from Windows Explorer, this first argument (argv[0]) contains the full path of the program, which was not desired. A string function was used to find the last back-slash in this full path and only print the string that comes after this character.

The problem was that from the command window, only the program name entered is passed as the first argument (the path or the “.exe” is not included unless entered on the command line). In any case, the strrchr() library function used to get a pointer to the last back-slash returned a NULL because a back-slash was not found, and using this NULL caused the crash. The code was corrected to allow for a lack of a path – problem solved.

Translator – Data Type Matching

When determining which code (main or associated) to use from the operand's data types, there can be an exact match, no match or a convertible match. A convertible match can be made to be an exact match when conversion code(s) are added after the operand that doesn't match exactly. An exact match is preferred.

There will be a match routine that will determine the type of match there is between the current operand's data type(s) and a code's required data type(s). In additional to returning the type of match found (exact, none, or convertible), the conversion codes needed for each operand or Null if a particular operand does not need conversion will also be returned.

This match routine will use an table holding the conversion codes for each possible operand (have) data type and required (need) data type pairs. For the pairs where the two data types are the same, the conversion code will be set to the Null code. For the pairs with an Integer or Double vs. a String, the conversion code will be set to an Invalid code. The only pairs with actual conversion codes are the have Integer need Double pair (CvtDbl) and the have Double need Integer pair (CvtInt).

The routine for finding the code for the data types of the operand(s) will be called from both the add operator routine and the internal function routine (after the number of arguments is checked). The operands will be pulled off of the done stack to get their data types. Using the match routine, the operands will be checked against the main code for a data type match. If an exact match is found, then no further action is needed. If a convertible match was found, the main code is saved in case no further exact match is found.

When the main code is not an exact match, each of the associated codes (if any) of the main code table entry are checked for a match. For each, if an exact match is found, then no further action is needed. If a convertible match was found, the associated code is saved in case no further exact match is found.

If a convertible match was found, then the token's code is changed and the conversion codes are inserted into the output list after the operands. If no match was found, then one of three “expected <data type>” errors (one for each data type) will be reported against the first operand with an Invalid code in the conversion codes returned from the match routine.

Translator – Data Type (Table Updates)

Before working on the design of the routines that will handle the matching of the data types and finding the correct code, I decided to make the changes to the table entries for the new operand data type (operand_datatype) array and associated code (assoc_code) array and make sure these compile. The number of arguments member (nargs) was also renamed to the number of operands (noperands). New access functions for these members were added to the Table class.

All the table entries for the operators and internal functions were updated with the new values. The number of operands (previously nargs) for all of the operators were previously set to zero, so these were changed to 1 for the unary or 2 for the binary operators. The data type for many operators were also incorrectly set to None, so these was changed to the appropriate data type.

New entries for all the associated codes were added to the table and their codes were added to the Code enumeration. An entry for the CDBL functions was missing and was added. An entry for a new function FRAC was also added (this function will return the fractional part of a floating point values).

The integer division operator (“\” or IntDiv) is intended to be used with double operands, which will be rounded and converted to integers internally before the division. The operand data types could have been set to the integer data type, but then the CvtInt would always be inserted for both operands.  This operator only has one code and should not be used with integer operands as the regular division should be used, but this will be allowed (CvtDbl will be inserted, but only to be converted back to integers internally).

The Power operator will have three forms, the standard double/double (Power) and integer/integer (PowerInt), but there will also be a double/integer code (PowerMul). The PowerInt will use integer multiplication internally. The idea for the PowerMul code is for it to also use multiplication internally instead of calling the standard C pow() function for speed. However, the pow() function may already have these optimizations, so this may be unnecessary. Some experiments will be needed to determine which is more efficient. The goal is to allow the programmer to use an expression like A^2 instead of A*A and not be penalized by slow execution.

Translator – Associated Codes

Operators and some internal functions allow different operand data types, each will have it's own code (e.g. Add, AddInt, and CatStr), but only one name in the source (e.g. “+”). The Parser will only find the first one in the table since the Parser is only responsible for breaking the source into tokens, not looking at data types and determining appropriate codes. It is the Translator's responsibility to examine and validate the operands of operators and internal functions and to set the token to the appropriate code.

To accomplish this, the first entry in the table (that the Parser finds, the default entry), which for many will be the code that handles the double data type, will contain the other codes associated to the main code. These codes will be put into an associated code array in the table entry.

After obtaining the data types of the operands from the done stack, the Translator will check to see if there is a match to the code by checking the required operand data types in the code's table entry. If there is no match, then each of the associated code table entries will be checked for a match.

In addition to an exact match, there will also be a convertible match. With this type of match, hidden conversion codes can be inserted to obtain the desired data types. The exact match will be preferred so that the correct code is used. For example, if the first exact match or convertible match is used, then for Integer + Integer, the Translator would use the default Add code (for doubles) and add two CvtInt instead of using the preferred AddInt code. Next, how a convertible match will be detected...

Translator – Operand Data Types

Now it has been established that operators and internal functions can be handled the same way, except that the number of arguments (operands) is checked first for internal functions. For internal functions, the number of arguments check also determines which code to use (MID2 vs. MID3, INSTR2 vs. INSTR3, or ASC vs. ASC2).

Each code (operator or internal function) has a return data type, a fixed number of operands and a expected data type for each operand. The word operand will be used instead of argument from now on, which  is more appropriate when applied to operators. Taking the plus operator as an example, which will have three codes (one main and two associated codes):

Add  Double  (2)  Double  Double
AddInt  Integer  (2)  Integer  Integer
CatStr  String  (2)  String  String

The code is listed first along with the return data type. The number of operands is in parentheses followed by the data type of each operand. If there is an add with a double and an integer operand, the Add code will be used with a CvtInt inserted after the integer operand.

The table entries already contain the code and data type values and the number of arguments will be renamed to the number of operands. A new operand data type array needs to be added to the table entries. The size of this array will be set to three since there are currently no planned functions containing more than three arguments. Next, how associated codes will be handled...

Translator – Operators and Internal Functions

Unary operators have one operand. When the translation to RPN of unary operators is compared to the translation of functions with one argument, it can be seen that the translations are the same (one operand followed by the code):

-A  →  A Neg
ABS(A)  →  A Abs

Binary operators have two operands. When the translation to RPN of binary operators is compared to the translation of functions with two arguments, it can be seen that the translations are the same (two operands followed by the code):

A$+B$  →  A$ B$ CatStr
LEFT$(A$,2)  →  A$ 2 Left

There are no tertiary or more operators, but functions with three of more arguments have a similar format except there would be more operands before the code. So, once the source code for operators and internal functions are translated to RPN, there is no difference between them - operand(s) followed by a code. Therefore, for data type handling, both operators and functions can be handled the same way. Next, how data types will be handled...