SI413 Lab 14: Compiling

Not all programming languages are interpreted, and not all interpreters interpret the abstract syntax tree directly, as we have done. What are the alternatives? Well code for non-interpreted languages is compiled to run on a physical machine, and a lot of code for interpreted languages is actually compiled to run on a virtual machine, which means that it is compiled to some simple assembly-like language that is interpreted directly by the virtual machine. In this lab we'll start the process of compiling SPL code to run on the "Simple Virtual Machine" (SVM), which is ... a simple virtual machine. It's been written specifically to mesh easily with SPL.

Part 0: Virtual Machines

The virtual machine you're probably most familiar with is the Java Virtual Machine (JVM). Java code is compiled into "byte code", which is the assembly-like language understood by the JVM. The JVM is a stack-based machine rather than register-based like a typical physical machine. This means that instructions pop their arguments from a stack of values (the "vstack") and, which they produce results, push them back. This will take some getting used to.

Part 1: Interactive vm

The vm we'll be using for this lab is vm1, which is at ~wcbrown/bin/vm1. You enter assembly instructions, hit ctrl-d and it evaluates them. Alternatively, you can enter instructions followed by "done", and it will evaluate what you've typed and wait for more. Yet another alternative is to enter instructions and then ";", which will act like "done" except that after the instructions have been executed, the vstack gets printed out.

> ~wcbrown/bin/vm1
const 5      
const 3
mul
const 2
add
write
done
17
const 5      
const 3
;
|| 5 3
mul
;
|| 15
const 2
;
|| 15 2
add
;
|| 17

Write code to perform the following calculations (save in a text file sol.txt):

1. write 4 + (18 - 6) / (3 + 3);
2. write 3*5 + 1 < 40/5 + 7;
3. new x := 21; write x*x*x*x - 3*x + 1;

TIP: Run "./vm1 -h" to get a list of commands the VM recognizes. The VM *does* support variables -- see the help file and/or example in part 3 below. You should use variables to solve the third problem above.

Part 2:

Download lab14.tar into your course directory and unpack (tar xf lab14.tar). Start adding to eval so that it emits SVM assembly for SPL programs using arithmetic, boolean, comparisons, "new" variables, and variable assignment. In particular, you should generate valid code for the three examples above, e.g.:

bash> ./go > tmp.txt
write 4 + (18 - 6) / (3 + 3);
bash> ~wcbrown/bin/vm1 tmp.txt
6
bash> ./go > tmp.txt
write 3*5 + 1 < 40/5 + 7;
bash> ~wcbrown/bin/vm1 tmp.txt
false
bash> ./go > tmp.txt
new x := 21; write x*x*x*x - 3*x + 1;
bash> ~wcbrown/bin/vm1 tmp.txt
194419

Part 3: get short-circuit eval to work right!

To do this, you'll need branches and gotos. This example shows how they work. Fundamentally they use labels. a word followed by a : is a label, and a word followed by a # is a label rerference, i.e. it gets literally replaced with the address of the instruction immediately after the corresponding label. BTW: if the first char on a line is %, it's a comment.

% This defines x and y and computes y + abs(x)
% define x and y
const x
const 5
newid
const y
const 7
newid
% if x < 0 push -x else push x, i.e. push abs(x) 
const x
idval
const 0
lt
lab1#
swap
branch
const x
idval
lab2#
goto
lab1:
const 0
const x
idval
dif
lab2:
% compute y + abs(x)
const y
idval
add
write

Of course to test this you need to try code like this:

{
  new a := 8;
  new b := 0;
  write b != 0 and a/b > 3;
}

Submission

You don't need a separate submission for this lab. I will grade your Lab 15 submission (which extends this lab) and give you credit for this lab. However: that means sol.txt (from Part 1) must appear in your Lab15 submission.