Question 8

Deadline	Friday, November 10, 11:59pm
Name on Marmoset	Q8
To Submit	`practice.wlp4`

Introduction to WLP4

The ultimate goal of the projects in this course is to write a compiler that translates a C-like programming language called WLP4 into MIPS assembly language. You can then translate the MIPS assembly into MIPS machine language with your assembler from Project 2, and run your programs!

The purpose of this question is to get you familiar with the features and limitations of WLP4, to help you better understand the requirements of compilation. There will not be further WLP4 programming questions, but you will have to write your own WLP4 programs to test the components of your compiler!

WLP4 Quick Introduction

WLP4 is similar to a small subset of C, but it uses C++ style memory allocation (new/delete instead of malloc/free). It only supports int and int* variables, basic arithmetic (addition, subtraction, multiplication, division, and modulo), conditional statements (if/else) and while loops with comparison-based tests, a println statement for printing numbers, memory allocation with new and delete, and procedures that return an int value.

The syntax of WLP4 is harshly restricted, which makes it more annoying to write, but easier to compile. For example:

All variable declarations must appear at the start of a procedure. Mid-procedure declarations are not allowed.
All variables must be initialized to a constant. They cannot be initialized to another variable or the result of an expression. They cannot be left uninitialized.
Integer literals cannot be negative. In fact, there is no unary (one-operand) minus operator. To get -1, for example, you must write 0 - 1.
Every if statement must have a matching else, even if it's empty. There is no "else if" syntax.
An if statement can only have one boolean condition (no && or || operators).
You can only have one return statement per procedure and it must be at the very end.
Array access must be done using pointer arithmetic. Instead of writing array[index], you must write *(array+index).

More detailed information about WLP4 is linked below:

How to Compile and Run WLP4 Programs

Informal Introduction to WLP4

Formal WLP4 Specification

WLP4 Practice

Step 1. Write a WLP4 procedure int abs(int n) { ... } that computes the absolute value of an integer. You do not need to properly handle the case of -2³¹ = -2147483648 (this integer has no positive counterpart in 32-bit two's complement).

Step 2. Write a WLP4 procedure int tieBreak(int a, int b) { ... } which should be called with two distinct integers as parameters.

If the integers have different absolute values, return the integer with the smaller absolute value.
If the integers have the same absolute value, then since they are distinct, one is positive and one is negative. Return the negative integer.

Step 3. Write a WLP4 procedure int wain(int *array, int size) { ... } that takes a non-empty array of integers in the range -241 to 241 (inclusive) as input and returns the integer that occurs most frequently. If there is a tie for the most frequent integer, break the tie using the rule from the tieBreak procedure.

The wain procedure is the WLP4 equivalent of main. It must appear as the last procedure in the program, or a parsing error will occur.

For full marks, your program should run in linear time (in the size of the input array). A quadratic time solution using nested loops can get at most 50% of the marks.

Examples

Suppose the input array is [1, 2, 2, 3, 3, 3]. Your program should return 3.

Suppose the input array is [4, 4, 2, 4, 2, -3, 2, -3, -3]. There's a three way tie between 4, 2 and -3. Since 2 has the least absolute value, your program should return 2.

Suppose the input array is [1, -1, 2, -2]. There's a four way tie between 1, -1, 2, and -2. Among these, 1 and -1 tie for the smallest absolute value. To break this tie, you choose the negative number, so you return -1.

Testing

Compile your program with wlp4c. This will produce MIPS machine code, which can be run directly with one of our MIPS emulators. Which emulator you use depends on whether the wain procedure takes two integer parameters, or a pointer (int*) and an integer.

For this question, you should test your program with mips.array. The array address in $1 corresponds to the first parameter of wain and the size in $2 corresponds to the second parameter. The return value will be placed in $3.

wlp4c < practice.wlp4 > practice.mips
mips.array practice.mips
Enter length of array: 4
Enter array element 0: 3
Enter array element 1: 1
Enter array element 2: 2
Enter array element 3: 3
Running MIPS program.
MIPS program completed normally.
$01 = 0x00000fcc   $02 = 0x00000004   $03 = 0x00000003   $04 = 0x00000004
...

Or more concisely:

mips.array <(wlp4c < practice.wlp4) <<< "4 3 1 2 3"
Enter length of array: Enter array element 0: Enter array element 1: ... Running MIPS program.
MIPS program completed normally.
$01 = 0x00000fcc   $02 = 0x00000004   $03 = 0x00000003   $04 = 0x00000004
...

Hints

If you don't know how to find the most frequent element in an array in linear time, it is a good problem to practice your skill at designing algorithms. However, the main purpose of this question is not to practice algorithm design, but rather to get you familiar with the WLP4 language. If you are having trouble with the algorithm design aspect, there are some hints below, though we encourage you to try to solve the question without them.

Hint 1

Your first instinct might be to solve the problem with a hash table, but implementing a hash table in WLP4 would be extremely painful. Instead, implement something similar but simpler.

Hash tables are useful when the keys are not integers, or when the number of keys are very large. In this problem, the keys are integers that lie in a small range.

Hint 2

If the range of integers was 0 to 241, you could solve this problem using an array of size 242, where array[i] stores the number of occurrences of number i. Modify this approach to work with the range -241 to 241.

Hint 3

Using an array that tracks the frequency of each integer, you can solve the problem with two loops:

One loop to zero-initialize the frequency array.
One loop over the input array to fill out the frequency array and find the most frequent number.

Keep track of the current "winner" during the second loop, and call tieBreak whenever you find a new candidate for the "winner".

Hint 4 (Full Algorithm)

Create a variable called mostFrequent to store the most frequent number.

Allocate an array called frequency of size 483, where frequency[i+241] will store the number of occurrences of number i. Initialize all the elements to zero.

Initialize mostFrequent to the first element of the input array.

Loop through the remaining elements of the input array. For each value i in the input array:

Increment frequency[i+241] by 1.
If frequency[i+241] is greater than frequency[mostFrequent+241], set mostFrequent = i.
If frequency[i+241] is equal to frequency[mostFrequent+241], set mostFrequent = tieBreak(mostFrequent, i).

Return mostFrequent.