INTERPRETER

[hiperiondev]

Here we will only discuss issues related to the internal functioning of the interpreter/VM (opcodes, data types, address types, memory management, etc).

[hiperiondev]

I have opened this section so as not to mix such specific topics in other discussions

[hiperiondev]

I have created a spreadsheet to be able to describe and discuss opcodes and how they work.

https://docs.google.com/spreadsheets/d/1HnU5Mh2sUnhWXuy_SXFKASFkREhg8sih/edit?usp=sharing&ouid=100473230682014903193&rtpof=true&sd=truehttps://docs.google.com/spreadsheets/d/1HnU5Mh2sUnhWXuy_SXFKASFkREhg8sih/edit?usp=sharing&ouid=100473230682014903193&rtpof=true&sd=true

[hiperiondev]

I have added a stupid print OP in compiler. I don't know some functionalities then print value and possible opcode

https://pastebin.com/MrtZL8Xn

[hiperiondev]

Starting the disassembler. There are still things that I don't quite understand.

https://github.com/hiperiondev/Toy-disassembler

[Ratstail91]

@hiperiondev TOY_OP_DOT is identifical to TOY_OP_FN_CALL, EXCEPT the first parameter and the function name positions have been switched. (It was a crappy stopgap solution that made the compiler a PITA to code in).

TOY_OP_FN_CALL 's parameters on the stack are: the function identifier, followed by each argument, followed by an integer signaling the number of arguments that are on the stack.

Finally, function bytecode is recursive - that is to say, a function has it's own literal cache, function section and runnable code section. In addition, I think the first two bytes of the runnable code section are ACTUALLY specifying the literal within the function's cache containing the parameter list, and the next two bytes specify the literal in the cache which is the returns array. (sticking those indexes within the runnable section was another ugly hack - sorry!)

I should note that the final parameter might actually signal a rest parameter with TOY_LITERAL_FUNCTION_ARG_REST.

[hiperiondev]

@hiperiondev TOY_OP_DOT is identifical to TOY_OP_FN_CALL, EXCEPT the first parameter and the function name positions have been switched. (It was a crappy stopgap solution that made the compiler a PITA to code in).

TOY_OP_FN_CALL 's parameters on the stack are: the function identifier, followed by each argument, followed by an integer signaling the number of arguments that are on the stack.

Good. In any case, a disassembler only takes into account the bytecode, not the execution time. In the case of FN_CALL there is no argument in the code, therefore it is an opcode without arguments.

Finally, function bytecode is recursive - that is to say, a function has it's own literal cache, function section and runnable code section. In addition, I think the first two bytes of the runnable code section are ACTUALLY specifying the literal within the function's cache containing the parameter list, and the next two bytes specify the literal in the cache which is the returns array. (sticking those indexes within the runnable section was another ugly hack - sorry!)

Could you give me a concrete example of how that would be interpreted? I guess that's why the first test (fib-memo) works but the second fails (function-within-function-bugfix), clearly I can't apply toy_read_interpreter_sections directly to the function body.

If it is exactly the same as the rest of the code, the two bytes that you say are consumed here:
int functionCount = readWord((*prg)->program, pc);
int functionSize = readWord((*prg)->program, pc);

Is there a recursion limit for functions?

I should note that the final parameter might actually signal a rest parameter with TOY_LITERAL_FUNCTION_ARG_REST.

[hiperiondev]

I have solved the recursion problem in the function code and now it seems to work correctly.
Could you check if the result is correct?
On the other hand I have noticed that the code of the functions begins with:
EOF
EOF
PASS
EOF

And every FN_RETURN continue with:
PASS
EOF

That's right?

[hiperiondev]

There's no hurry!

On the other hand, nested functions ends in :
FN_RETURN
PASS
EOF
SCOPE_END
SECTION_END
EOF

therefore:
PASS
EOF
SCOPE_END
They should never be interpreted.

It's right?

[hiperiondev]

Since the function has information about its length, the last 2 bytes should not be necessary either:
SECTION_END
EOF

On the other hand, I don't think there is a function that does not end in FN_RETURN, so that opcode would not be necessary either.

[Ratstail91]

that seems odd...

[hiperiondev]

A disassembler is an excellent tool for optimizing a language. Once we agree that it works correctly it could be added to the REPL

[Ratstail91]

I'd love to see the fruits of your work pay off like that!

[Ratstail91]

Just making a note here: while the args & rets literal indexes are technically stored within the program section, they are extracted BEFORE the function proceeds to execInterpreter. For all intents and purposes, they almost make up their own section within the function definition...

(I fixed how these are read in the disassembler, btw - check the pull requests)

[hiperiondev]

Good!!!
In the example you add (generator) , function:
| | | ( fun 0 [ start: 1841, end: 2755 ] )
| | | ( Reading 43 literals )
| | | | ( identifier rng )
It does not end with FN_RETURN. what happens in that case? it's right?

[Ratstail91]

It exits without a return value.

[hiperiondev]

After:
FN_RETURN
there is:
PASS
EOF
SCOPE_END

Is that a bug or does it have some functionality?

[Ratstail91]

@hiperiondev Oops, we're reading it wrong - FN_RETURN actually has a two-byte argument, representing the number of values being returned via the stack.

[Ratstail91]

Opened hiperiondev/Toy-disassembler#2 to fix it

[Ratstail91]

FYI: This is basically a stub of code, to enable the possible future addition of multiple return values. It's the same reason the returns are specified in an array as well.

[Ratstail91]

There do seem to be superfluous opcodes - like the scope begin and end surrounding the functions - there's already an automatic scope push/pop in the interpreter's calling code...

[hiperiondev]

You beat me to the punch!
I was about to comment exactly that case

[Ratstail91]

| | | | | ( fun 0 [ start: 8039, end: 8095 ] )
| | | | | ( Reading 6 literals )
| | | | | | [0] ( identifier key )
| | | | | | [1] ( type INTEGER: 0)
| | | | | | [2] ( identifier value )
| | | | | | [3] ( array 0 1 2 1 )
| | | | | | [4] ( array )
| | | | | | [5] ( integer 0 )
| | | | |
| | | | | ------ CODE ------
| | | | | [args literal 3, rets literal 4]
| | | | | [ 08085 ](004) LITERAL b(2)
| | | | | [ 08087 ](004) LITERAL b(5)
| | | | | [ 08089 ](038) COMPARE_NOT_EQUAL
| | | | | [ 08090 ](049) FN_RETURN w(1)
| | | | | [ 08093 ](255) SECTION_END
| | | | | [ 08094 ](000) EOF
| | | | | ---- END CODE ----

That looks much nicer without the extra SCOPE operations.

[Ratstail91]

That's actually something I'm leaving until version 2.0 - actually, we don't have to worry about deprecated opcodes until we start running out of opcode room.

[hiperiondev]

The disassembler I consider complete at this stage.
It would be necessary to present the functions separately, but that implies reformulating several things,
If you want to add it as a tool, I could avoid making new modifications until your new version.

[Ratstail91]

Give me a couple hours, I'll let you know when my tweaks are done.

[hiperiondev]

I've changed my code to yours to continue development on that branch.

[Ratstail91]

sorry the change was a bit more drastic than expected.

[hiperiondev]

I was thinking that maybe FN_RETURN is not the proper name for the OPCODE, since it doesn't really perform a RETURN but rather a data manipulation for the return.

Perhaps FN_DATA_RETURN would be more appropriate.

[Ratstail91]

It's associated with the return keyword, and terminates the function early anyway - if nothing is returned, the interpreter receives a null literal.

[hiperiondev]

I'm going to start separating the code from the functions.
I have a question with nested functions (example: function-within-function-bugfix.toy)
What would be the appropriate way to identify the index of the functions?

[hiperiondev]

I don't understand exactly what you mean by that.

[Ratstail91]

Don't worry about it too much, I'll sort it eventually, and it's not a major problem.

[hiperiondev]

In https://github.com/hiperiondev/Toy-disassembler/ I've added hierarchical notation for functions.
You can test this with function-within-function-bugfix.tb

[hiperiondev]

Also the code of each function is "isolated". the Program Counter should start from zero on each of them.
I have added this to project.
If you are agree I'll add to Toy code

[Ratstail91]

Sounds good, actually. Thanks!

[hiperiondev]

In generator.toy, function 0 (generateTilemapData)
the code indicate:
| | | ------ ( code ) ------
| | | ( args 2, rets 3 )

I understand that this would indicate the number of values returned, but currently it cannot be more than 1.
Why does the function have those values?
Same unknown values in the others functions.

[Ratstail91]

No, those represent a literal in the cache - the specified literal represents the argument array (it's set up before the function begins), and the returns array.

[hiperiondev]

At the beginning of the file are the calls to import:
| | [0] ( standard identifier )
| | [1] ( null )
| | [2] ( identifier random )

Why is there a NULL in the middle?

[Ratstail91]

Because null is also a literal, its value needs to be defined. In this case, null is the value of the alias.

I think.

I used to have null, true and false defined as the first three literals by default, but stopped doing that at some point.

[hiperiondev]

In generator.tb
| | [00074] ( identifier generateTilemapData )
| | [00075] ( function index: 0 )
...
code:
| | | 00044 SCOPE_BEGIN
| | | 00045 SCOPE_BEGIN
| | | 00046 LITERAL b(7)
| | | 00048 LITERAL b(14)
| | | 00050 LITERAL b(15)
| | | 00052 LITERAL b(16)
| | | 00054 DOT
| | | 00055 LITERAL b(7)
| | | 00057 LITERAL b(14)
| | | 00059 LITERAL b(15)
| | | 00061 LITERAL b(16)
| | | 00063 DOT
| | | 00064 LITERAL b(7)
| | | 00066 LITERAL b(14)
| | | 00068 LITERAL b(5)
| | | 00070 LITERAL b(16)
| | | 00072 DOT
| | | 00073 SCOPE_END
| | | 00074 SCOPE_END

Why does it nest two SCOPEs?
It is not the only one in code.

[Ratstail91]

These might be from for loops - they end up looking like this:

{
    pre clause
    conditional
    if false jump to end
    {
        body
    }
    post clause
    jump to conditional
    end
}
pop stack

If the body has a pair of braces in the source, then the scopes around the "body" will be redundant...

It might be possible to remove the extra scope around the body. I'll test it with #107 soon.

[Ratstail91]

Alternatively, you might be running this on pre-1.3 bytecode...

[Ratstail91]

here's a thought - arrays generally don't shrink their capacities...

but the interpreter's stack could do that to free up memory, perhaps?

[Ratstail91]

That's not a stack, that's a linked list?

[hiperiondev]

A stack can be constructed in many forms. A linked list is one, an array is other.
Is defined by functionality, not by construction.
Usually a dynamic growing is a linked list and a fixed sized an array.

[Ratstail91]

a linked list results in memory fragmentation, cache misses, and slows it down compared to an array.

[hiperiondev]

Yes. But a dynamic array too. The alternative is a fixed size stack.

[hiperiondev]

A fixed size stack is the better alternative for constrained devices.
May be a tool for precompiled programs can calculate the maximum stack size.
I'll think about this.

[Ratstail91]

Concerning #107 - I've made a few tweaks (will push and close in a moment) to remove an excess scope creation when using for loops with a block around the body.

a.toy

for (var i: int = 0; i < 10; i++) {
    print i;
}

a.tb

File: test.tb
Size: 91
[Header Version: 1.3.0 (Aug 22 2023 01:04:44)]

| ---- ( literals ) ----
| ( Reading 5 literals )
| | [00000] ( integer 0 )
| | [00001] ( identifier i )
| | [00002] ( type INTEGER: 0)
| | [00003] ( integer 10 )
| | [00004] ( integer 1 )
| ( end literals )
| -- ( end literals) --
|
| ---- ( main code ) ----
| [ 00000 ](015) SCOPE_BEGIN
| [ 00001 ](004) LITERAL b(0)
| [ 00003 ](019) VAR_DECL b(1) b(2)
| [ 00006 ](004) LITERAL b(1)
| [ 00008 ](004) LITERAL b(3)
| [ 00010 ](039) COMPARE_LESS
| [ 00011 ](047) IF_FALSE_JUMP w(34)
| [ 00014 ](015) SCOPE_BEGIN
| [ 00015 ](004) LITERAL b(1)
| [ 00017 ](003) PRINT
| [ 00018 ](016) SCOPE_END
| [ 00019 ](004) LITERAL b(1)
| [ 00021 ](006) LITERAL_RAW
| [ 00022 ](004) LITERAL b(1)
| [ 00024 ](004) LITERAL b(1)
| [ 00026 ](004) LITERAL b(4)
| [ 00028 ](008) ADDITION
| [ 00029 ](023) VAR_ASSIGN
| [ 00030 ](050) POP_STACK
| [ 00031 ](046) JUMP w(6)
| [ 00034 ](016) SCOPE_END
| [ 00035 ](255) SECTION_END
| [ 00036 ](000) EOF
| -- ( end main code ) --

b.toy

for (var i: int = 0; i < 10; i++) print i;

b.tb

File: test.tb
Size: 91
[Header Version: 1.3.0 (Aug 22 2023 01:04:44)]

| ---- ( literals ) ----
| ( Reading 5 literals )
| | [00000] ( integer 0 )
| | [00001] ( identifier i )
| | [00002] ( type INTEGER: 0)
| | [00003] ( integer 10 )
| | [00004] ( integer 1 )
| ( end literals )
| -- ( end literals) --
|
| ---- ( main code ) ----
| [ 00000 ](015) SCOPE_BEGIN
| [ 00001 ](004) LITERAL b(0)
| [ 00003 ](019) VAR_DECL b(1) b(2)
| [ 00006 ](004) LITERAL b(1)
| [ 00008 ](004) LITERAL b(3)
| [ 00010 ](039) COMPARE_LESS
| [ 00011 ](047) IF_FALSE_JUMP w(34)
| [ 00014 ](015) SCOPE_BEGIN
| [ 00015 ](004) LITERAL b(1)
| [ 00017 ](003) PRINT
| [ 00018 ](016) SCOPE_END
| [ 00019 ](004) LITERAL b(1)
| [ 00021 ](006) LITERAL_RAW
| [ 00022 ](004) LITERAL b(1)
| [ 00024 ](004) LITERAL b(1)
| [ 00026 ](004) LITERAL b(4)
| [ 00028 ](008) ADDITION
| [ 00029 ](023) VAR_ASSIGN
| [ 00030 ](050) POP_STACK
| [ 00031 ](046) JUMP w(6)
| [ 00034 ](016) SCOPE_END
| [ 00035 ](255) SECTION_END
| [ 00036 ](000) EOF
| -- ( end main code ) --

[hiperiondev]

This week I think I'm going to be a bit loaded with work. As soon as I get free I will return to the project

[Ratstail91]

No worries @hiperiondev - I've been struggling with depression over the last week or two, so I've gotten very little done; I'm even running out of time for the game jam I mentioned.

[hiperiondev]

No problem. As I already told you: health comes first. Next month I'm also going to be a bit complicated, I'm getting divorced and I'm going to move. to another house. We all have a troubled life.

[Ratstail91]

Yikes! All the best to you, my man.

[hiperiondev]

Everything is alright! It is by mutual agreement and without conflicts, all very friendly. But life change is disruptive.

[hiperiondev]

I just pushed a change to the disassembler. Now you can choose a linear presentation according to a conventional assembler.
I am going to add the calculation of jumps to labels to eliminate the line numbers

[hiperiondev]

Question about JUMPs:

• The argument is a readShort (unsigned short). How do you do a backflip? From what I see, it adds the literal that is always positive (interpreter->count = target + interpreter->codeStart)

• What address is interpreter->codeStart?

[Ratstail91]

codeStart should be the first line of actually executable code; it gets captured at the beginning of execInterpreter().

[hiperiondev]

I understand, it would be the beginning of the function code.
So the jump is always positive because it starts from the beginning of the current block of code. This would be that if I consider 0 the PC of the current function then the jump is always absolute. Is this correct?

[Ratstail91]

That sounds about right, I think? I think the jump opcodes that were in the disassembly output were correct, at least.

[hiperiondev]

In LITERAL_ARRAY and LITERAL_DICTIONARY what is SUBTYPE?

[Ratstail91]

The subtypes are what they contain - for an array, there's only one type as it's subtype, but literal dictionary has two - one for key and one for value.

[hiperiondev]

Now, with the last commit, disassembler show all the program relative to labels.
This is usefull for rethink some things :-)

[Ratstail91]

Sorry - this doesn't seem to have worked correctly, so I've reverted it, until further testing can be done.

[hiperiondev]

Here it works correctly. What is exactly the problem?
I follow the development of the disassembler in a different project until it has been well tested:
https://github.com/hiperiondev/Toy-disassembler

[Ratstail91]

See #112

[hiperiondev]

I'm back! Although, for now a little slow because I am moving to a new house, when I am completely settled I will resume the project with more vigor.

I've been working on a new interpreter, based on the JVM handles frames for local variables.

You can see the first implementation is: https://github.com/hiperiondev/stack_vm

[Ratstail91]

Hey! Sorry I've been quiet - I've been on a break, been some medical emergencies in the family. I hope you're doing ok!

I'll have a look at this in just a moment.