Description
The objective of this project is to explore (A) compiling arithmetic expressions with let-bindings into a stack machine bytecode and (B) writing an emulator to execute this bytecode. This is all to be done in standalone scala using IntelliJ or some IDE that supports sbt
(Scala Build Tools).
Instructions for Testing.
IntelliJ
Instructions are provided in a separate pdf/pptx presentation in the same directory as this notebook.
Command line: sbt
You can run Main from the command prompt with the current directory as the very top directory of the project, by running the following commands:
$ sbt compile
$ sbt test
Running ScalaTest tests
Also, we will use a powerful unit testing package called scalatest. The tests themselves are in two files in the directory src/test/scala/edu/colorado/csci3155/project1/
IntelliJ
Type test
in the SBT shell window. It will provide all tests that passed and tests that failed.
sbt
To run this go to the terminal and from the very top directory run:
$ sbt test
It will say success if all tests run or give you a failure messages.
Instructions for submission
- Ensure everything is saved.
- Run the tests one last time to ensure everything works as expected. You will not be able to submit if your code does not at least compile.
- Run the
checkAndZipSubmission
sbt task- (sbt) Run
$ sbt checkAndZipSubmission
in a terminal - (IntelliJ) Type
checkAndZipSubmission
on SBT shell.
- (sbt) Run
- Ensure whichever option you chose displayed
[success]
at the end - Upload the generated “submission.zip” file located at the project root folder (at the same level as “src”, “build.sbt”, etc.).
The Language
We have encountered arithmetic expressions and let bindings given by the grammar
The objective of this project is to explore compiling this into a stack machine bytecode and writing an emulator to execute this bytecode.
Part 1: Stack Machine Bytecode
A stack machine runs instructions that work on a stack of numbers and an environment. The environment binds variable names to numbers. The stack machine has a set of instructions shown below. Keep the picture below in mind as you think of how a stack machine works.
As an instruction runs, it is going to change the environment and stack. The following is the specification for stack machine instruction set you will have to implement. Pay special attention to the SubI
and DivI
instructions since the order matters.
Stack Machine Instruction Set
LoadI(identifier)
: Pop off the top element of the stack. Let the number popped off bev
. Update the environment by mappingidentifier
tov
.- Example: Stack has top element
20.9
. The instructionLoadI("x")
removes the top element off the stack and updates the environment by adding/replacing the mapping"x" -> 20.9
.
- Example: Stack has top element
StoreI(identifier)
: Take the value thatidentifier
maps to in the environment (ifidentifier
is not present, then throw an exception). Let the value bev
. Pushv
onto the top of the stack.- Example:
StoreI("zaza")
will look up the environment for the valuezaza
, say4.3
. It will push4.3
onto the top of stack. Environment is unchanged by this operation.
- Example:
PushI(d)
: push the number d onto the stack.PopI
: pop off the top element of the stack – throw an exception if the stack is empty.AddI
: pop two numbers from the stack, add them and push the result back to the stack. Throw an exception if the stack is empty during any of the pop operations.SubI
: pop two numbers from the stack: let the first number popped bev1
and second number bev2
, subtract them asv2 - v1
(this order is very important) and push the result back to the stack. Throw an exception if the stack is empty during any of the pop operations.MultI
: pop two numbers from the stack, multiply them and push the result back to the stack. Throw an exception if the stack is empty during any of the pop operations.DivI
: pop two numbers from the stack, let the first number popped bev1
and second number bev2
, subtract them asv2 / v1
(this order is very important) and push the result back to the stack. Throw an exception if the stack is emptyduring any of the pop operations. Throw exception if division by zero.LogI
: pop one number from the stack, compute its log if positive and push the result back onto the stack. If non-positive throw an exception. Throw an exception if the stack is empty during any of the pop operations.ExpI
: pop one number from the stack, compute its exponential exex and push the result back onto the stack. Throw an exception if the stack is empty during any of the pop operationsSineI/CosineI
: pop one number from the stack, compute its sin/cos respectively, and push the result back onto the stack. Throw an exception if the stack is empty during any of the pop operations.
Example
Given:
- List of instructions
[ StoreI("x"), PushI(3.0), AddI, PushI("y"), SubI, LoadI("result") ]
and - Environment that maps {x↦2.0,y↦4.0,z↦4.0}{x↦2.0,y↦4.0,z↦4.0}.
- Empty Stack represented by the empty list.
we execute each instruction in turn starting from the empty stack. We will implement the stack as a list with the head of the list as the top of the stack.
- Initially the stack is empty.
- When we execute
PushI("x")
, the stack is[ 2.0 ]
and environment is the same. - When we execute
PushI(3.0)
, the stack is[ 3.0, 2.0 ]
and environment is the same. - When we execute
AddI
, the stack becomes[ 5.0 ]
and environment is the same. - When we execute
PushI(4.0)
, the stack becomes[ 4.0, 5.0 ]
and environment is the same. - When we execute
SubI
, the stack becomes[ 1.0 ]
and environment is the same. - When we execute
LoadI("result")
the stack is now[]
(empty) and environment is {x↦2.0,y↦4.0,z↦4.0,result↦1.0}{x↦2.0,y↦4.0,z↦4.0,result↦1.0}.
Instructions for Part 1
Implement the methods emulateSingleInstruction
and emulateStackMachine
in the file StackMachineEmulator.scala
. For your convenience, the stack machine instructions have been defined as a very simple inductive definition giving case classes for all the instructions. We will use an immutable List data structure to simulate the stack.
emulateSingleInstruction(stack, env, instruction)
takes in astack
of typeList[Double]
, an environment of typeMap[String, Double]
and instruction which is of typeInstruction
. It returns aList[Double]
which represents the stack resulting from executing that instructions and environmentMap[String,Double]
that is the environment.emulateStackMachine(listOfInstructions)
asks you to return the final environment computed by thelistOfInstructions
. The initial environment is the empty environment and the initial stack is the empty stack (list of doubles). You should callemulateSingleInstruction
repeatedly using functors such asfoldLeft
rather than using iteration.
Coding Style Requirements
- The use of while, for loops and mutables var is prohibited.
- Any recursive functions used for the emulator (part 1 of assignment) must be made
tail recursive
and the annotation@tailrec
must be used. This however does not apply to part 2 of this assignment below.
Part 2: Compiling Expressions to a List of ByteCode Instructions
We will now describe the compilation
of expressions into bytecode instructions.
For instance the expression let x = 1.0 in x + (2.0 - 3.0) * 5.0
is represented as an AST
Let("x",
Const(1.0),
Plus(Ident("x"), Mult(Minus(Const(2.0), Const(3.0)), Const(5.0))
)
The overall goal of this part is to compile this down into a list of bytecode instructions that serves to evaluate this through the emulator you have built in part 1.
For example, the expression above produces the instructions
PushI(1.0)
LoadI("x")
StoreI("x")
PushI(2.0)
PushI(3.0)
MinusI
PushI(5.0)
MultI
AddI
You should check that evaluating this sequence gives the result -4.0
on top of the stack. Please pay particular attention to the order of the operands for MinusI
according to the specification provided in Part 1.
The idea is to implement a function compileExpr(e) that given an expression e yields a list of instructions according to the following operational semantics definition.
Constant Rule
The rule for constants is simple. An expression Const(f)
compiles to the instruction PushI(f)
.
Note again that compileExprcompileExpr maps expressions to list of instructions.
Add Rule
The instructions concatenate the lists L1,L2L1,L2 along with the list consisting of a single instruction [ AddI ]
. Note that the ++
operator in scala implements the list concatenation.
Subtract Rule
The instructions concatenate the lists L1,L2L1,L2 along with the list consisting of a single instruction [ SubI ]
.
Let Rule
Notice that the compilation introduces a LoadI
instruction after executing the instructions L1L1 corresponding to e1
. This instruction ensures that the result of the computation is loaded onto the identifier “x” in the environment.
Ident Rule
Ident("x")
is simply implemented by the StoreI
operation.
The rule simply asks you to generate a list with a single instruction for an identifier expression.
If you have followed the logic clearly, why is this rule not raising any kind of error? Where is the check whether str
is in the environment beign done??
Rules for Other expressions
We hope that you will be able to fill in rules for other cases Mult
, Div
, Exp
, Log
, Sine
and Cosine
.
Instructions for Part 2
The definition of Expression AST is given in the file Expr.scala
Your goal is to implement the compilation routine compileToStackMachineCode(e: Expr): List[StackMachineInstruction]
in the file StackMachineCompilation.scala
. The function takes in an expression e
and outputs a list of stack machine instructions.
Extra Credit
Important
- Extra credit is only for students who are done with the regular graded part of the assignment.
- You must submit your regular assignment separately before you begin the extra credit.
- If you do not receive full credit on your regular project assignment above, you will not receive any extra credit.
- Priority/help will only be given to students attempting this part if other students doing the regular part are done and instructors have time.
- Also, instructions are kept vague so that the student can try to figure things out by themselves.
- Finally, this is not easy — it may be challenging and you are well advised to skip it.
- Add comparison operators to expressions
Geq(Expr, Expr), Leq(Expr, Expr), Eq(Expr, Expr)
- Add corresponding bytecode instructions.
- Add logical operators
And(e1, e2), Or (e1,e2), Not(e)
- To support short circuiting translate the And/Or into IfThenElse.
And(e1, e2)
=if (e1) then (if (e2) then TRUE else FALSE) else FALSE
- Similarly translate Or into If then else.
- Add if then else / conditional expressions.
IfThenElse (e1, e2, e3)
To support if then else add a conditional skip
and unconditional skip
instructions to the bytecode.
The unconditional skip instruction SkipI(k)
simply skips over the next k
instructions.
The conditional skip operator SkipIfFalse(k)
will check the top of the stack and if it is false, then skip the next k
instructions.
The trick to properly implementing IfThenElse
is to generate the proper semantic rules and proper set of instructions that include conditional/unconditional skips.
Update the instruction emulator to emulate the stack machine and the compilation of expression.
Deliverables for EC Please deliver the extra credit portions separately to us. Write a 1-2 page report in the same style of jupyter notebook that I have used to describe all the changes you did. Write test cases to document your code and show how it works. Ask for an appointment with course staff. You will be interview graded for the extra credit.
Extra Credit will give you a “bypass” on a spot exam. You can skip any spot exam for full credit. Alternatively, you can take a bypass on any assignment for full credit. These are on top of existing “drop the lowest score” we are providing students.
Extra Extra Credit.
The compilation system we developed here is technically “incorrect”. I.e, it does not implement the “same” operational semantics we had originally given for the interpreter in our class notebook. This incorrectness has to do with how we handled scoping. Explain why it is incorrect and develop a fix for this issue 🙂
Extra Extra Credit will not get you anything more than the fact that the force will be stronger in you as a result. 😉