286 lines
14 KiB
Markdown
286 lines
14 KiB
Markdown
# Luxferre's Truly Tiny BASIC (LTTB) implementation notes
|
|
|
|
This document serves as the definite reference for everyone intending to create a new and fully compatible LTTB language interpreter implementation. It describes all the algorithms and data structures necessary to recreate a fully functional LTTB interpreter from scratch.
|
|
|
|
## Data structures required for LTTB implementations
|
|
|
|
* Integer numbers (signed)
|
|
* Strings
|
|
* Lists (arrays that can store numbers and strings)
|
|
* Associative arrays (key-value objects)
|
|
* Stacks (or any other linear structure that can emulate them, including lists)
|
|
|
|
## Globals
|
|
|
|
An LTTB interpreter requires the following globals:
|
|
|
|
* Program working memory `PROGMEM` (associative array)
|
|
* Variable storage area `VARS` (associative array)
|
|
* Subroutine call stack `CALLSTACK`
|
|
* Instruction pointer `IP` (integer)
|
|
|
|
Initial values:
|
|
|
|
* `PROGMEM` = empty
|
|
* `VARS["A"]..VARS["Z"] = 0`
|
|
* `CALLSTACK` = empty
|
|
* `IP = 0`
|
|
|
|
## Overall interpreter session flow
|
|
|
|
1. Print the welcome banner.
|
|
2. If the implementation is CLI-based and there is a file name passed into the command-line argument, run the `LOAD` routine on this file.
|
|
3. Output the prompt `> ` and expect user input on the same line.
|
|
4. Read the user input, trim leading/trailing whitespace and uppercase it. Save it as `CMD`.
|
|
5. If `CMD` equals exactly to `BYE`, print the "Bye!" message and exit the interpreter.
|
|
6. If `CMD` is exactly one of these `RUN LIST NEW CLEAR LOAD SAVE`, execute the corresponding interactive routine and go to step 3. For `NEW` and `CLEAR`, the interactive routine must be the same.
|
|
7. Execute program line input routine `PROGINPUT` with `CMD` as a parameter and then go to step 3.
|
|
|
|
## Program line input routine (`PROGINPUT`)
|
|
|
|
Accepts the statement string `STMT` as the input line argument.
|
|
|
|
1. Trim leading/trailing whitespace from `STMT`.
|
|
2. Return from the routine if the `STMT` is an empty string.
|
|
3. Initialize line number variable `LNO` as 0.
|
|
4. Iterate through characters of `STMT`. If the current character `C` is a digit, set `LNO = LNO * 10 + C`. Repeat this step as long as `C` is a digit or a whitespace character.
|
|
5. Starting from the first non-digit and non-whitespace character, save the rest of the `STMT` string as the statement body `BODY`.
|
|
6. If `LNO > 0`, set `PROGMEM[LNO] = BODY`. Otherwise, run statement execution routine `PROGEXEC` with `BODY` as a parameter.
|
|
|
|
## Program statement execution routine (`PROGEXEC`)
|
|
|
|
Accepts the statement string `STMT` as the input line argument.
|
|
|
|
1. Read the keyword identifier `KW` from the first two non-whitespace characters in `STMT`.
|
|
2. If the second character in `KW` is equal to `=`, go to step 3, otherwise go to step 5.
|
|
3. Set `KW` to the value `LE`.
|
|
4. Prepend the value `LE ` (two characters `LE` and then a whitespace) to the beginning of `STMT`.
|
|
5. If `KW` is exactly one of these `EN GO IF IN LE PR RE`, go to the next step, otherwise return.
|
|
6. Find the position of the first whitespace in `STMT`, then copy everything from this position to the end of `STMT` into `BODY`.
|
|
7. Trim leading/trailing whitespace from `BODY`.
|
|
8. If `KW` is equal to `GO` and the **third** non-whitespace character of `STMT` is equal to `S`, execute core language routine named `GOS` with `BODY` as a parameter and return.
|
|
9. Execute core language routine with the name equal to the value of `KW` with `BODY` as a parameter and return.
|
|
## Number normalization function (`NORM`)
|
|
|
|
Accepts any number-like value `V` as the argument.
|
|
|
|
1. If `V` is an empty string, return 0 immediately.
|
|
2. Convert `V` into an integer (by truncating the decimal part if necessary).
|
|
3. If `V` is inside the allowed range (-32768 to 32767), return `V`.
|
|
4. Set `V = V % 65536`.
|
|
5. If `V` exceeds 32767, set `V = V - 65536`.
|
|
6. Return `V`.
|
|
|
|
## Evaluation helper function (`EVALHELPER`)
|
|
|
|
Simple two-value evaluator. Accepts two stacks, value stack `VALSTACK` and operator stack `OPSTACK`.
|
|
|
|
1. Pop operation `OP` from `OPSTACK`.
|
|
2. Pop operand `V2` from `VALSTACK`.
|
|
3. Pop operand `V1` from `VALSTACK`.
|
|
4. If `OP` is equal to `$`, set `RES` to a random value between 0 and `(V2 + 32768) % 32768`.
|
|
5. If `OP` is equal to `+`, set `RES = V1 + V2`.
|
|
6. If `OP` is equal to `-`, set `RES = V1 - V2`.
|
|
7. If `OP` is equal to `*`, set `RES = V1 * V2`.
|
|
8. If `OP` is equal to `/` and `V2` is not 0, set `RES = V1 / V2`.
|
|
9. Push the value of `NORM(RES)` to `VALSTACK`.
|
|
10. Return `VALSTACK` and `OPSTACK`.
|
|
|
|
## Expression evaluation function (`EXPREVAL`)
|
|
|
|
Mathematical expression and intrinsic function application engine. Accepts a single `EXPR` string as a parameter.
|
|
|
|
Requires a precedence map `PRECMAP` to be pre-defined as follows: `"(" => 0, "+" => 1, "-" => 1, "*" => 2, "/" => 2, "$" => 3`.
|
|
|
|
1. Trim leading/trailing whitespace from `EXPR`.
|
|
2. If `EXPR` is empty, return 0.
|
|
3. Initialize `VALSTACK` and `OPSTACK` as empty stacks.
|
|
4. Initialize `VALBUF` and `PREVC` as empty strings.
|
|
5. Set index `I = 0`.
|
|
6. [Main Loop] Fetch character `C = EXPR[I]`. If out of bounds, go to step 16.
|
|
7. If `C` is whitespace, increment `I` and go to step 6.
|
|
8. If `C` is a digit:
|
|
- Append `C` to `VALBUF`.
|
|
- Set `PREVC = C`, increment `I`, go to step 6.
|
|
9. If `VALBUF` is not empty, push `NORM(VALBUF)` to `VALSTACK` and clear `VALBUF`.
|
|
10. If EXPR[I onwards] starts with `RND`:
|
|
- Push 0 to `VALSTACK`.
|
|
- Set `C` to `$`.
|
|
- Advance `I` by 3, go to step 14 (process `$` as operator).
|
|
11. If `C` is a variable `A`-`Z`:
|
|
- Push `NORM(VARS[C])` to `VALSTACK`.
|
|
- Set `PREVC = C`, increment `I`, go to step 6.
|
|
12. If `C` is `(`:
|
|
- Push `(` to `OPSTACK`.
|
|
- Set `PREVC = C`, increment `I`, go to step 6.
|
|
13. If `C` is `)`:
|
|
- While `OPSTACK` top is not `(`: Execute `EVALHELPER(VALSTACK, OPSTACK)`.
|
|
- Pop `(` from `OPSTACK`.
|
|
- Set `PREVC = C`, increment `I`, go to step 6.
|
|
14. If `C` is an operator (`+ - * / $`):
|
|
- If C is `+` or `-` AND (`PREVC` is empty OR belongs to `( + - * / $`):
|
|
- Push 0 to `VALSTACK`.
|
|
- While `OPSTACK` is not empty AND `PRECMAP[OPSTACK top] >= PRECMAP[C]`:
|
|
- Execute `EVALHELPER(VALSTACK, OPSTACK)`.
|
|
- Push `C` to `OPSTACK`.
|
|
- Set `PREVC = C`, increment `I`, go to step 6.
|
|
16. [Finalization] If `VALBUF` is not empty, push `NORM(VALBUF)` to `VALSTACK`.
|
|
17. While `OPSTACK` is not empty: Execute `EVALHELPER(VALSTACK, OPSTACK)`.
|
|
18. Return pop from `VALSTACK`.
|
|
|
|
## Core language routines
|
|
|
|
### `EN`
|
|
|
|
Program end routine.
|
|
|
|
1. Set `IP = -1`.
|
|
2. Clear `CALLSTACK`.
|
|
|
|
### `GO`
|
|
|
|
Direct jump routine. Accepts `EXPR` string as a parameter.
|
|
|
|
Set `IP = EXPREVAL(EXPR) - 1`.
|
|
|
|
### `GOS`
|
|
|
|
Subroutine caller. Accepts `EXPR` string as a parameter.
|
|
|
|
1. Push `IP` to `CALLSTACK`.
|
|
2. Set `IP = EXPREVAL(EXPR) - 1`.
|
|
|
|
### `RE`
|
|
|
|
Return from a subroutine.
|
|
|
|
Pop the value from `CALLSTACK` and set `IP` to it.
|
|
|
|
### `LE`
|
|
|
|
Assign a value to the variable. Accepts `STMT` string as a parameter.
|
|
|
|
1. Treat the first Latin letter in `STMT` as the variable name `VARNAME`.
|
|
2. Treat everything after the first `=` character in `STMT` as the expression `EXPR`.
|
|
3. Set `VARS[VARNAME] = EXPREVAL(EXPR)`.
|
|
|
|
### `IF`
|
|
|
|
Conditionally execute the statement that follows the expressions with the relative operator. Accepts `STMT` string as a parameter.
|
|
|
|
1. Find the first position of either of these characters `> = <` inside `STMT`. Record the position into two integer variables, `ROPOS` and `ROEND`, and the first found character itself into the string variable `RELOP`.
|
|
2. If the character at `ROPOS + 1` position inside `STMT` also is either of `> = <`, then append this character to `RELOP` and increment `ROEND` by 1.
|
|
3. Set the string `EXPR1` to everything from the start of `STMT` to the character at position `ROPOS - 1` inclusively.
|
|
4. Set the string `REST` to everything from the position `ROEND + 1` to the end of `STMT` inclusively.
|
|
5. Initialize the integer position variable `THENPOS` to -1.
|
|
6. Pick the next keyword `KW` from this list in this particular order: `THEN IF LET = RETURN GOSUB INPUT PRINT GOTO END`. Go to step 11 when the list is exhausted.
|
|
7. Set `THENPOS` to the first position of the currently iterated keyword `KW` inside `REST`. If not found, go to step 6.
|
|
8. If `KW` is equal exactly to `=`, decrement `THENPOS` by 1.
|
|
9. Copy the value of `THENPOS` to another integer variable, `RESTPOS`.
|
|
10. If `KW` is equal exactly to `THEN`, increment `RESTPOS` by 4.
|
|
11. Set the string `EXPR2` to everything from the start of `REST` to `THENPOS - 1` inclusively.
|
|
12. Set `REST` to everything from the position `RESTPOS` to the end of the `REST` string inclusively.
|
|
13. Perform comparison operation denoted by `RELOP` on `EXPREVAL(EXPR1)` and `EXPREVAL(EXPR2)`. If the result of comparison is true, execute `PROGINPUT(REST)`.
|
|
|
|
### `IN`
|
|
|
|
Value input routine. Accepts `STMT` string as a parameter.
|
|
|
|
1. Remove all whitespace inside `STMT`.
|
|
2. Split the value of `STMT` by a comma `,` into a list `VARLIST`.
|
|
3. Output the prompt `? ` and expect user input on the same line.
|
|
4. Read the user input into a buffer string, remove all whitespace inside it and uppercase it. Save it as `INPUTBUF`.
|
|
5. Split the value of `INPUTBUF` by a comma `,` into a list `INPUTLIST`.
|
|
6. Iterate over `VARLIST`. For each 1-character variable `VAR` inside `VARLIST`, take the corresponding expression `VAREXPR` from `INPUTLIST` (under the same index) and set `VARS[VAR] = EXPREVAL(VAREXPR)`.
|
|
|
|
### `PR`
|
|
|
|
Value and string printing routine. Accepts `STMT` string as a parameter.
|
|
|
|
1. Initialize an empty list `PRINTLIST` and an empty string buffer `ITEM`.
|
|
2. Set the `QUOTING` flag to 0.
|
|
3. Fetch the next character `C` from `STMT`. Go to step 10 if there are no more characters.
|
|
4. If `C` is a double quote `"`, then flip the `QUOTING` flag (set `QUOTING = 1 - QUOTING`), append the value of `C` to `ITEM` and go to step 3. Otherwise, go to step 5.
|
|
5. If the `QUOTING` flag is set, append the value of `C` to `ITEM` and go to step 3.
|
|
6. If `C` is either a comma (`,`) or a semicolon (`;`), go to step 7, otherwise go to step 9.
|
|
7. If the current `ITEM` value is not empty, append it to the `PRINTLIST` and clear the `ITEM` variable.
|
|
8. Append the value of `C` to `PRINTLIST` and go to step 3.
|
|
9. If `C` is not a whitespace, append its value to `ITEM` and go to step 3.
|
|
10. If the current `ITEM` value is not empty, append it to the `PRINTLIST` and clear the `ITEM` variable.
|
|
11. Fetch the next item string `ITEM` from `PRINTLIST`. Go to step 15 if there are no more items.
|
|
12. If `ITEM` begins with a double quote `"`, trim all double quotes from the beginning and end and output its value verbatim (without a newline). Go to step 11.
|
|
13. If `ITEM` is equal exactly to a comma `,`, then output a TAB character (`\t`, ASCII 9) and go to step 11.
|
|
14. If `ITEM` is not equal to a semicolon `;`, then output the value of `EXPREVAL(ITEM)` verbatim, without a newline. Go to step 11.
|
|
15. If the last `ITEM` value is not a comma `,` or a semicolon `;`, output a newline.
|
|
|
|
## Interactive routines
|
|
|
|
### `RUN`
|
|
|
|
Run the program currently loaded into the working memory.
|
|
|
|
1. Set `IP = 1`.
|
|
2. If `PROGMEM[IP]` exists, is not empty and does not start with the string `REM`, execute `PROGEXEC(PROGMEM[IP])`.
|
|
3. Increment `IP` by 1.
|
|
4. If `IP > 0` and `IP < 32768`, go to step 2.
|
|
|
|
### `LIST`
|
|
|
|
Output program listing.
|
|
|
|
Two algorithms are provided: for the platforms that can extract associative array keys and for those that cannot.
|
|
|
|
Algorithm 1:
|
|
|
|
1. Extract key list `LNOS` from `PROGMEM` associative array. Sort the list in the integer numeric order.
|
|
2. Fetch the next key `LNO` from `LNOS`. Upon exhaustion, return from the routine.
|
|
3. If `PROGMEM[LNO]` is not empty, output the value of `LNO`, TAB character (ASCII 9) and `PROGMEM[LNO]` with a newline at the end. Go to step 2.
|
|
|
|
Algorithm 2:
|
|
|
|
1. Set `I = 1`.
|
|
2. If `PROGMEM[I]` exists and is not empty, output the value of `I`, TAB character (ASCII 9) and `PROGMEM[I]` with a newline at the end.
|
|
3. Increment `I` by 1.
|
|
4. If `I > 0` and `I < 32768`, go to step 2.
|
|
|
|
### `NEW` / `CLEAR`
|
|
|
|
Memory clear routine.
|
|
|
|
Restore all globals to their initial values:
|
|
|
|
* `PROGMEM` = empty
|
|
* `VARS["A"]..VARS["Z"] = 0`
|
|
* `CALLSTACK` = empty
|
|
* `IP` = 0
|
|
|
|
### `LOAD`
|
|
|
|
Program loading routine from external storage media. The provided algorithm works with disk file I/O as the most popular form of interaction.
|
|
|
|
1. Prompt the user for a file name/path `FNAME`.
|
|
2. If the file does not exist, notify the user about this error and return.
|
|
3. Execute the `CLEAR` interactive routine.
|
|
4. Open a file handle `FH` for reading from the file under the path `FNAME`.
|
|
5. Read the next program line `PROGLINE` from the file handle `FH`. Go to step 9 upon end-of-file condition.
|
|
6. Trim the leading and trailing whitespace from `PROGLINE`.
|
|
7. If `PROGLINE` is not empty, execute `PROGINPUT(PROGLINE)`.
|
|
8. Go to step 5.
|
|
9. Close the handle `FH` and notify the user about successful program loading.
|
|
|
|
### `SAVE`
|
|
|
|
Program saving routine into external storage media. The provided algorithm works with disk file I/O as the most popular form of interaction.
|
|
|
|
1. Prompt the user for a file name/path `FNAME`.
|
|
2. If the file name/path isn't writable, notify the user about this error and return.
|
|
3. Open a file handle `FH` for writing into the file under the path `FNAME`.
|
|
4. Perform the algorithm described for the `LIST` routine, but using the specified file handle instead of standard output and space character (ASCII 32) instead of TAB character (ASCII 9).
|
|
5. Close the handle `FH` and notify the user about successful program saving.
|
|
|
|
## Closing notes
|
|
|
|
The set of algorithms in this document should be enough to create a complete and functional LTTB interpreter in any modern programming language. If you have any corrections or optimizations regarding the algorithms, feel free to create an issue in this repository.
|
|
|
|
In order to verify implementation correctness, you can use the code inside [test.bas](test.bas) shipped in this repository.
|