Assignment 8: Minc Arrays

Due: 5:00pm, Friday, November 2. [Students scheduled to present November 2 or November 5, and any teammates of these students, have an assignment deadline of November 9.] Value: 30 pts.

In class we saw a Haskell implementation of an interpreter for a simple language that I call Minc (Minimal C), supporting while, if, assignment, and print statements and expressions involving comparison and arithmetic operators. The only type of data supported in this language is the integer.

Your assignment is to enhance the interpreter to also support arrays. Arrays may be created by simply enclosing the length of the new array in square brackets, as in [n]. An array of length n has its entries indexed from 0 to n − 1. You can use square brackets to index the array, whether for retrieving a value from the array or modifying a value in the array. The following program for showing the first 20 Fibonacci numbers illustrates.

fibs = [21];
fibs[0] = 0;
fibs[1] = 1;
i = 2;
while (i <= 20) {
    fibs[i] = fibs[i - 1] + fibs[i - 2];
    i = i + 1;
}
i = 1;
while (i <= 20) {
    print fibs[i];
    i = i + 1;
}

Arrays should support non-integer values in an array slot, as illustrated by the following program to display the 20th row of Pascal's triangle.

tri = [20];
i = 0;
while (i < 20) {
    tri[i] = [i + 1];
    tri[i][0] = 1;
    j = 1;
    while (j < i) {
        tri[i][j] = tri[i - 1][j - 1] + tri[i - 1][j];
        j = j + 1;
    }
    tri[i][i] = 1;
    i = i + 1;
}

i = 0;
while (i <= 20) {
    print tri[19][i];
    i = i + 1;
}

To accomplish this, you will want to download the following four Haskell files as your starting point.

I have already performed several modifications to these files to start your way toward supporting array creation and indexing.

Still to complete are the following:

To test your program, save a Minc program into a file such as fibs.mc, then run ghci Test.hs to enter Haskell with Test.hs loaded. Then execute showRun "fibs.mc" (or showTree "fibs.mc" if you just want to see the syntax tree without executing the program). If you decide to modify your Haskell code, you can tell ghci to load the modified code with the command :reload.