solved:CSCI 3155 Project 1 – Compile into Stack Machine Bytecode

$30.00

Category: You will Instantly receive a download link for .zip solution file upon Payment || To Order Original Work Click Custom Order?

Description

5/5 - (1 vote)

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

  1. Ensure everything is saved.
  2. 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.
  3. Run the checkAndZipSubmission sbt task
    • (sbt) Run $ sbt checkAndZipSubmission in a terminal
    • (IntelliJ) Type checkAndZipSubmission on SBT shell.
  4. Ensure whichever option you chose displayed [success] at the end
  5. 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

ExprDoubleIdentifier||||||||||Const(Double)Ident(Identifier)Plus(Expr,Expr)Minus(Expr,Expr)Mult(Expr,Expr)Div(Expr,Expr)Log(Expr)Exp(Expr)Sine(Expr)Cosine(Expr)Let(Identifier,Expr,Expr)all double precision numbers in ScalaStringall scala stringsExpr→Const(Double)|Ident(Identifier)|Plus(Expr,Expr)|Minus(Expr,Expr)|Mult(Expr,Expr)|Div(Expr,Expr)|Log(Expr)|Exp(Expr)|Sine(Expr)|Cosine(Expr)|Let(Identifier,Expr,Expr)Double→all double precision numbers in ScalaIdentifier→Stringall scala strings

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.

Stack Machine Schematic

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 be v. Update the environment by mapping identifier to v.
    • Example: Stack has top element 20.9. The instruction LoadI("x") removes the top element off the stack and updates the environment by adding/replacing the mapping "x" -> 20.9.
  • StoreI(identifier): Take the value that identifier maps to in the environment (if identifier is not present, then throw an exception). Let the value be v. Push v onto the top of the stack.
    • Example: StoreI("zaza") will look up the environment for the value zaza, say 4.3. It will push 4.3 onto the top of stack. Environment is unchanged by this operation.
  • 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 be v1 and second number be v2, subtract them as v2 - 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 be v1 and second number be v2, subtract them as v2 / 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 operations
  • SineI/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 {x2.0,y4.0,z4.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 {x2.0,y4.0,z4.0,result1.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 a stack of type List[Double], an environment of type Map[String, Double] and instruction which is of type Instruction. It returns a List[Double] which represents the stack resulting from executing that instructions and environment Map[String,Double] that is the environment.
  • emulateStackMachine(listOfInstructions) asks you to return the final environment computed by the listOfInstructions. The initial environment is the empty environment and the initial stack is the empty stack (list of doubles). You should call emulateSingleInstruction repeatedly using functors such as foldLeft 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).

compileExpr(Const(f))=[PushI(f)](const-rule)compileExpr(Const(f))=[PushI(f)](const-rule)

Note again that compileExprcompileExpr maps expressions to list of instructions.

Add Rule

compileExpr(e1)=L1, compileExpr(e2)=L2compileExpr(Plus(e1, e2)=ListContatenation(L1,L2,[AddI])(add-rule)compileExpr(e1)=L1, compileExpr(e2)=L2compileExpr(Plus(e1, e2)=ListContatenation(L1,L2,[AddI])(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

compileExpr(e1)=L1, compileExpr(e2)=L2compileExpr(Minus(e1, e2)=ListContatenation(L1,L2,[SubI])(minus-rule)compileExpr(e1)=L1, compileExpr(e2)=L2compileExpr(Minus(e1, e2)=ListContatenation(L1,L2,[SubI])(minus-rule)

The instructions concatenate the lists L1,L2L1,L2 along with the list consisting of a single instruction [ SubI ].

Let Rule

compileExpr(e1)=L1, compileExpr(e2)=L2compileExpr(Let(“x”, e1, e2))=ListConcatenation(L1,[LoadI(x)],L2)(let-rule)compileExpr(e1)=L1, compileExpr(e2)=L2compileExpr(Let(“x”, e1, e2))=ListConcatenation(L1,[LoadI(“x”)],L2)(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.

compileExpr(Ident(str))=[StoreI(str)](ident-rule)compileExpr(Ident(str))=[StoreI(str)](ident-rule)

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 MultDivExpLogSine 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.
  1. Add comparison operators to expressions
    • Geq(Expr, Expr), Leq(Expr, Expr), Eq(Expr, Expr)
    • Add corresponding bytecode instructions.
  2. Add logical operators
    • And(e1, e2), Or (e1,e2), Not(e)
  3. 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.
    1. 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. 😉