README

Project 1: An introduction to ML and MIPS

Due September 20, 11:59pm.

The goal of this problem set is to expose you to programming in ML and to learn a few details of the MIPS instruction set architecture.

There are two parts to this assignment. The first part consists of writing a MIPS assembler. In the second part, you will implement an interpreter for a subset of the MIPS instruction set.

Instructions: We have provided skeleton code in this directory. Your job is to fill in the parts of the skeleton code marked TODO.

If you are having trouble getting your code to compile, please post your issue on Piazza, or come see a TF during office hours. If you run out of time, it’s better to comment out the parts that aren’t working than to submit something that won’t compile.

Repo Access and Submitting

(a) Instructions to access the psets repo

Click on the assignment link and sign in using your personal GitHub account.
Create a new group or join an existing group. For the sake of blind grading, please make sure your group name has no personal identifiers! (For example, you can generate a random name here.)
You have now created a new repo under the HarvardCS153–2018-Fall organization; commit and push your assignment here!

(b) Instructions to submit

Make sure you are using OCaml version 4.07.0, or at the least that your submission compiles and runs with OCaml 4.07.0. This is our “supported” version and is what we will be using to grade your problem set!
Please list your HUID(s) in the file huids.txt. This will help us perform blind grading.
Your last commit before the deadline to the master branch of your repo is your final submission. Please note that no late submissions will be accepted. Don’t forget to push!

Part 1: MIPS Assembler

In this part, you will build an assembler for a subset of MIPS assembly. The assembler translates assembly code into machine code, the code that runs on hardware. This exercise will demonstrate how we get from assembly code, something that is still somewhat human-readable, to machine code.

To do this part of the assignment, you will need to understand how MIPS assembly is encoded at the level of bits. To this end, the MIPS documentation is your friend. You can find information about how to encode instructions (and their semantics) in chapter A.10.2 (starting with page A–49) of the SPIM Simulator manual. You may also find the notes on addressing modes (page A–45) helpful.

Your job is to write the assem function in mips_sim.ml:

let rec assem (prog : program) : state = ...

At a high level, you will transform a list of assembly instructions, a program, into an initial starting state. A state consists of a register file, memory and program counter.

Implementation Details

Instructions to implement: add, beq, jr, jal, li, lui, ori, lw, sw.
Please note that the beq instruction has been altered to take an offset directly instead of a label. (These offsets are measured in bytes.) This is done to keep things simple–otherwise you would need to keep track of labels and their corresponding offsets!
For the sake of grading simplicity, please both start the program counter and load your generated machine code into memory at address 0x00000000.
The load immediate (li) instruction is a pseudoinstruction. This means that it is ok to use it in a MIPS assembly program, but MIPS hardware does not actually support this instruction. Instead, the hardware supports a li instruction by encoding it as two instructions, a lui and ori. Thus, your assembler should accept any MIPS assembly program that contains a li instruction, but your interp function should only accept lui and ori instructions to model the MIPS hardware.

Hint: How registers are ordered in the assembly code for an instruction may differ from the order of register fields in the corresponding machine language encoding. In addition to the SPIM simulator chapter, you can refer to (but not alter) parse.mly for the semantics of the instructions you are implementing.

Part 2: MIPS Interpreter

In this part, you will build an interpreter for MIPS code, similar to the SPIM simulator. The goal of this exercise is to become more familiar with the MIPS instruction set architecture and to gain more experience writing ML code.

The interpreter is structured as a function:

let rec interp (init_state : state) : state = ...

Your job is to write the interp function which simulates one step of execution at a time until program termination (for the purposes of this assignment, treat 0x00000000 as the program termination “instruction”). During a step, you should fetch a word’s worth (4 bytes) of values from memory, starting at the address given by the program counter.

You should then decode the instruction and perform the associated operation. For example, if the instruction bytes decode to an "add $1,$2,$3", then you should update register one, with the sum of the values in registers two and three, and update the program counter so that it points to the next instruction.

Look closely at the Int32 module OCaml standard library as it provides most of the functions that you will need for doing bit manipulation.

Implementation Details

For the sake of grading simplicity, please implement your MIPS with little-endian memory rather than big-endian.
You should raise an error if your interp function tries to execute a value from memory that is not a valid machine code instruction. (This does not include 0x00000000, the program termination “instruction”.)