Creating an Interpreter for Monty Bytecodes Using C Programming Language
PART FOUR
This is a link to the previous part (PART THREE), in case you missed it: https://medium.com/@mr_robertamoah/creating-an-interpreter-for-monty-bytecodes-using-c-programming-language-47c9bab6c4be
In the Part Three article, we implemented the functions for the execution of push, pall and pint. In this part, we will implement the functions for pop, swap, add, etc.
Starting with the pop opcode. This opcode removes the top node of the stack (the last stack node added). The code for this implementation can be seen below.
For the implementation, it will be impossible to pop an empty linked list. When the linked list is empty, we print to the stderr, free up memory and exit from the program. Otherwise, the last node is deleted using the delete_stack_node function. Once we delete a node, we are to update our stack length as well. With the delete_stack_node function, all we do is to set the head to the next node after setting a temporary stack_t pointer to the last node. Then we delete (free up the memory of) the last node, which is now being pointed to by the temporary variable. To test whether this works or not let us examine what the bytecode below is supposed to achieve.
We want to push 1, 2, and 3 in that order. This will make 3 the last to get onto the stack, right? Per our code, the head member of the arguments pointer will be pointing to the node with n of 3. The pall opcode then prints the n values of all the nodes of the linked list starting from 3 to 1. The pop code will then remove the node with n of 3. Another pall should print 2 to 1. Another pop removes node with n of 2. The next pall now prints just 1. The last pop will remove the node with n of 1. Then, the last pall prints nothing. So, we expect to see the output to have the following numbers in the order 3 2 1 2 1 1, with the correct formatting of course.
It works fine. Next on the list is the swap opcode. What does that do? The opcode swap swaps the top two elements of the stack. It is certainly going to fail if there are less than two nodes in the list. A good use case for the stack_length member of our arguments pointer. Let us have a look at the code.
I check if the length of the linked list is less than 2. If that is true, I print error message to stderr, free up all memory allocations and exit program. By now you are familiar with this routine. If there are two or more nodes in the linked list, I try to get the last two nodes with the help of the head member of the arguments pointer. Note that “tmp1->next” is the same as “argument->head->next” and that they give us the last but one node in the stack. How do I swap? This requires some visualization. So, always visualize the nodes as having prev and next members. The next of tmp1 should now point to the node after tmp2. If that isn’t NULL, then that node’s prev should also be the tmp1. After that, I let the next member of tmp2 to be tmp1 whereas the prev member now pointing to NULL. This means tmp2 now becomes to last node. To make the link more complete, I set prev member of tmp1 to tmp2. Now since tmp2 is the last, I make the head member of arguments point to it. The diagram below gives a pictorial view of what just happened.
Considering we have just two nodes. The head will point to the tmp1. tmp1 will have prev which points to NULL and a next which points to tmp2. tmp2 will also have a prev which points to tmp1 and a next which points to NULL in this case, but may as well point to another node, if there are more than two nodes. In diagram two, you realize head now points to tmp2. The prev of tmp2 is set to NULL. It’s next now points to tmp1. Before you actual do that, you need to ensure that tmp1’s next will be set to tmp2’s next. It is NULL here. But if it isn’t, then that nodes prev should also be changed from tmp2 to tmp1. Then tmp1’s prev is made to point to tmp2. It is a bit easier to conceptualize what I did with these diagrams. We will test our code with the bytecode below:
What do you think the bytecodes above supposed to achieve? We already know of the first four lines. The fifth line will swap 3 and 2 nodes. Hence, the last pall opcode is supposed to print 2 3 1. Look at the output below when I run the code. Works fine.
The next opcode to implement in this part is the add opcode. The add opcode adds the top two nodes of the stack, assigns the result to the last but one node, and then removes the last node. Below shows how I implemented the add functionality.
I simply print an error and exit from the program when there are less than two nodes in the linked list. Otherwise, I assign the sum of the n members of the last two nodes to the n member of the last but one node. I then delete the last node using delete_stack_node function. Remember we have seen this function earlier. I then reduce the length of the stack by one because we have removed the last node. Let us examine the bytecodes below, after which we can run our compiled program to verify if our add function works ok.
After the first three lines, we would have a linked list with three nodes, with the last node having its n member being 3. The pall command prints the nodes from 3 to 1. The add opcode then adds the 3 to 2 and assigns it to the n member of the last but one node, which is the stack with n of 2. It will now have 5 instead of 2. The node having 3, the last node, is removed. The last pall command should them print 5 1. Running the program with a file containing these opcodes produces the desired output.
I will end the Part Four of the articles here. Try implementing some opcodes such as sub, div, mul, etc, on your own. They are the next opcodes I deal with in the next Part of this series. Try them. You can then compare your implementation with mine. You can let the implementation of the add opcode guide you. See you.
This is the link to the next part of the series: https://medium.com/@mr_robertamoah/mcreating-an-interpreter-for-monty-bytecodes-using-c-programming-language-916d1837546
