CS153: Principles of Programming Language Compilation

Computer Science 153
Principles of Programming Language Compilation

Problem Set 1: An introduction to `SML` and MIPS

Due Friday, 18 Sep 2009, 11:00am.

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

Instructions: Create a directory ps1 with files part1.sml and part2.sml. Place your solutions to each part in the associated files and then submit these files through the FAS online submission system (submit). If the programs do not compile, then they will not be accepted. If you are having trouble getting your code to compile, please email me, or come see me. 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.

Submitting your work

Please use the CS153 submission script provided on the ice servers at ~lib153/bin/cs153submit. For each assignment, you should create a new subdirectory to hold all of the supplied files along with any file you create. When you have complete the assignment, submit your work with the following command:

# ~lib153/bin/cs153submit N dir

where N is the assignment number, and dir the the directory containing the files for the assignment. For example, if you are using a directory called ps1 for this assignment, you can submit your work with the command.

# ~lib153/bin/cs153submit 1 ps1

You can submit your work as many times as you like. Only the last submission will be graded. You can view your current submission using the submit command:

submit ls lib153 1: Show the time-stamp and size of your last submission for assignment 1.
submit contents lib153 1: Show the contents of your last submission for assignment 1.

For more information, see man submit on the nice servers. There are two parts to this assignment. The first part consists of three small ML programming problems. In the second part, you will implement an interpreter for a subset of the MIPS instruction set.

Part 0: Course Administravia (Ungraded)

Email the TF with your name and email address to be added to the course mailing list.

Part 1: ML Programming Problems

Hint: Each problem should only require a few lines of code to complete. If you find yourself writing more than a dozen lines of code for any one function, you are probably on the wrong track.

Problem 1.1: Function declarations

Write the following fun declarations:

Write a function that determines whether a string is a palindrome. A palindrome is a word that reads the same forwards as backwards. For instance "racecar" is a palindrome. (Hint: find a library function that can break the string into a list of characters.)
```
fun palindrome(x:string):bool = ???
```
Write a function that takes one integer argument n and returns an increasingly ordered list of all Fibonacci numbers that are less than or equal to n (do not forget to handle all cases). The first two Fibonacci numbers are f₀=0, and f₁=1. For k>1 f_k=f_k-1+f_k-2. If n happens to be less than zero, you should raise an exception.
```
fun fibo(n:int):int list = ???
```

Problem 1.2: Using the Basis Library

The basis library is one of the most helpful resources you have on your quest to learn SML. For this part of the assignment, you should browse The Standard ML Basis Library and then write short functions using the functions in the basis library.

Write a function that takes a string s and changes all the upper case letters to lower case and all the lower case letters to upper case.
```
fun changeCase(s:string):string = ???
```
Write a function that takes a string as an argument and replaces all adjacent repeated occurrences of a character with a single instance of that character. removeDupl("aabbacccdd") should return "abacd".
```
fun removeDupl(s:string):string = ???
```

Problem 1.3: Fold on Binary Search Trees with BST abstract data type

A binary search tree is a binary tree in which any node n has the property that its associated key is strictly greater than all of the keys associated with nodes in its left subtree, and it is strictly smaller than any of the keys associated with nodes in its right subtree. Equivalently, for each node n the node has the property that its key is strictly greater than the keys of its left descendants (if a left child exists), and it is strictly smaller than the key of its right descendants (if a right child exists). (We won't worry about keeping the tree balanced.)

We wish to create an implementation of binary search trees that is parameterized with respect to the notion of order, so that we may use it on values of different types (e.g., strings versus integers) and so that we may choose different orders (e.g., lexicographic versus hash code order.)

Create a structure BinarySearchTree that matches the following signature and follows the intended semantics:

signature BST = sig
  type 'a bst
  
  (* empty(f) creates an empty tree based on the ordering function f *)
  val empty : ('a * 'a -> order) -> 'a bst

  (* insert(t,x) adds the element x to the tree t if not already present, 
   * producing a new tree *)
  val insert : ('a bst * 'a) -> 'a bst

  (* present(t,x) returns true when x is in tree t, and false otherwise *)
  val present : ('a bst * 'a) -> bool

  (* postorder(f,u,t) visits the tree in post-order.  If the tree is
   * empty, returns u.  If the tree is non-empty, then it uses f
   * to combine the key with results from visiting the sub-trees. *)
  val postorder : (('b * 'a * 'b -> 'b) * 'b * 'a bst) -> 'b

  (* map(g,f,t) produces a new tree by applying g to each element in t.
   * The resulting tree should be ordered by f *) 
  val map : (('a -> 'b) * ('b * 'b -> order) * 'a bst) -> 'b bst
  (* size(t) returns the number of elements in the tree t *)
  val size : 'a bst -> int

  (* union(t1,t2) returns a tree that has all of the elements of t1
   * and t2.  Assumes that the ordering functions for the two trees
   * are the same. *)
  val union : 'a bst * 'a bst -> 'a bst

  (* filterout(p,t) returns a tree with all elements x of t such that
   * p(x) evaluates to false. *)
  val filterout : (('a -> bool) * 'a bst) -> 'a bst
end

Try to define as many of the functions in terms of other functions as possible.

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 SML code. The interpreter should be structured as a function:

fun interp (initial_state : state) = interp(step(initial_state))

where we define:

type regfile = Word32.word array  (* 32 elements *)
type memory = Word8.word array    (* pretend as if 2^32 elements *)

type state = {r:regfile, pc:Word32.word, m:memory}

The state of the machine consists of a register file, a program counter (pc), and a memory. The register file has 32 elements in it representing the 32 registers on the MIPS. Memory is represented as an array of bytes.

Your job is to write the step function which simulates one step of execution. 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. (It doesn't matter which Endian-ness you pick, but be consistent.)

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. You can find information about how to decode instructions (and their semantics) in chapter A.10.2 (starting with page A-49) of the SPIM Simulator chapter. Your simulator should include support for the following MIPS instructions:

add, beq, jal, jr, lw

These are a few of the instructions we'll be using throughout the class. You can ignore the other instructions.

The intent is to familiarize yourself with the way instructions are represented and executed on the MIPS. To that end, this is not meant to be a long tedious exercise. Therefore, you do not need to worry about other MIPS instructions, you do not need to worry about overflow or other kinds of exceptions. Finally, you do not need to worry about delay slots. That is, your interpreter should implement the semantics of the MIPS virtual machine. Look closely at the Word32 structure of the library as it provides most of the functions that you will need for doing bit manipulation.

Problem Set 1: An introduction to SML and MIPS