How would I take a simple program to multiply two numbers in MARIE assembly and rewrite it in a language readable for a one address VM

Question

I am tasked with writing code for a VM written in the C language. It can read in a file and perform operations based on the file input. From the example I've been given, it seems the first number of each instruction pertains to a command (1 - load, 2 - add, 3 - store, etc.) with the second number being an adress location.

So far I feel comfortable with MARIE and the programs I've written, for instance, the following code for multiplying 2 numbers. It also checks if the inputted numbers are greater than 0. This is important.

negloop1, clear 
store a 
input 
store a
skipcond 800
jump negloop1 
load a 
output

negloop2, clear 
store b 
input 
store b 
skipcond 800
jump negloop2 
output

load result 
clear 
store result 
load result
add a 
store result 
load b 
subt one 
store b 
skipcond 400
jump 012 
load result 
output 
halt

a,            dec 0
b,            dec 0
one,        dec 1
result,     dec 0

I need to write a program that does the same thing in a language readable by a tiny virutual machine written in the c language. It has the following instructions represented by opcode in digits 1 -11 (load, add, store, sub, in, out, halt, jmp, skipz, skipg, skipl). So instructions would look something like this.

5 5 //in 5
6 7 // out 7
3 0 // store 0
7 0 // halt

I'm not sure how I'd go about translating my program into this type of instructions. I need to implement jump commands but without being able to reference the line to jump to. Also there doesn't seem to be an equivalent command to 'clear'.

Answer 1

First, logically speaking, some of the most useful and complex operations are the binary operators, which are three operand in the sense they use two sources and one destination; they are useful like addition, and complex because of the number of operands necessary.

A one operand machine like MARIE almost certainly has an accumulator.  It can specify one of the sources and then uses the accumulator for the 2nd source operand, and also to for the target to capture the result.  (As @Peter notes, a one operand machine can also be a stack machine.)

MARIE is already such a machine: we look to see how the binary operators are performed, and in case of MARIE, these are add and subt — these instructions specify one (source) memory operand and the other source operand is taken as the accumulator, while the result is captured back into the accumulator.

MARIE also has "unary" operations, the load & store, that provide one memory operand (as source or as target, respectively) and also work with the accumulator.

---

I'm not sure how I'd go about translating my program into this type of instructions.

When we translate C code to assembly, or one assembly to another, there are three logical constructs that you will need to identify to translate:

• variables
• expressions
• statements

---

I'd suggest you focus, for starters, on code sequences like the following:

load result
add a 
store result 

For the above, you will need to make a mapping of a and result to storage, this goes to the translation of variables.  So, for example, you might choose to put a into location 0, (b into location 1), and result into location 2.

(We can't tell you whether these locations are free for you to use, but since you specify Harvard Architecture, we'll assume you can use data locations starting from 0.)

Next, you'll need to translate instructions for doing the complete addition assignment statement, using the variable mapping you've already done.  So, something like:

MARIE	Variables Mapped	Your VM
load result	load 2	1 2
add a	add 0	2 0
store result	store 2	3 2

Finally, as this is a simple assignment statement, you would generally put it in the same place relative to other code as it is in the MARIE assembly.

---

Loops require that you look at the control flow constructs more closely, but MARIE already has relatively primitive control structures that are reflected in your VM.

multiply, load result
add a 
store result 
load b 
subt one 
store b 
skipcond 400
jump multiply 

This loop does the following (in C):

do {
    result += a;
 } while (--b != 0);

The intent is to repeat the addition until b, counted downwards, becomes zero.  Translation to your VM should be straightforward.

Since the MARIE code is using SkipCond 400, which is skip on zero — and what is being skipped is a jump, then semantically it means jump on non-zero.

However, since MARIE is using an assembler with labels that I think you don't have, you'll need to supply a count or value instead of a label for the operand of the jump instruction.  There's two basic architectural choices in what the operand for jump would mean, either an absolute address (this is what MARIE does), or a pc-relative offset (that most other machines will do).  Once you decide what the operand means (how the operand identifies the target), then you need an encoding for that (i.e. if pc-relative, how to encode negative numbers for backward branch).

---

You can think a bit on what you want your in (and out) to do.  MARIE doesn't take operands for this; it uses the accumulator for the target of input and source of output.  Of course, you can make your in & out use operands instead, so in MARIE we might say two instructions: in; store a and you will have just one instruction, i.e. in a, or 5 0.