# 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 = ; fibs = 0; fibs = 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 = ; i = 0; while (i < 20) {     tri[i] = [i + 1];     tri[i] = 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[i];     i = i + 1; } ```

• Lex.hs handles breaking an input stream into tokens and creating the `TokenStream` monad. You should not have a reason to modify this file.
• Parse.hs creates a `TokenStream` that generates a corresponding syntax tree.
• Eval.hs executes a program represented by a list of syntax trees representing individual statements.
• Test.hs defines functions for loading information from a file and displaying a list of all tokens (`showTokens`), the resulting syntax tree (`showTree`), or executing the program (`showRun`). Each of these `showXXX` functions take a string as a parameter, which should be the name of a file containing your Minc code. Like Lex.hs, you should not have a reason to modify this file.

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

• In Lex.hs, I have modified it so that when it encounters a square bracket, it generates a token of type `Punct` whose text is the square bracket.

• In Parse.hs, the comments at top summarize the grammar that the file is created to implement. The grammar has seen two changes:

1. The Stmt → Symbol ‘=’ Expr ‘;’ rule has been modified to Stmt → Factor ‘=’ Expr ‘;’ to account for the fact that an assignment statement may have a subscripted array on the left side.
2. To account for the possibility of array subscripting in a factor, the Factor → Symbol | Number | ‘(’ Expr ‘)’ rule has been replace by Factor → Base { ‘[’ Expr ']' } with the new rule Base → Symbol | Number | ‘(’ Expr ‘)’ | ‘[’ Expr ‘]’. (The new option at the end of the Base rule reflects array creation.)
• These modifications have been reflected in the definition of the `StmtNode` and `ExprNode` types.

1. For `StmtNode`, the `StmtAssn` constructor takes an `ExprNode` rather than a `String` to indicate the assignment's left side.
2. For `ExprNode`, there are two new constructors, `ExprSub` and `ExprNewArray`.
• The code to parse an assignment statement now calls `parseFactor` to read the left-hand side of an assignment.

• In Eval.hs, a `ValArray` constructor has been added to the options for the `Value` type.

• New functions `arrayCreate`, `arraySet`, and `arrayGet` have been added to help you with manipulating an array.

• The `evalStmt` case for an assignment statement now uses `evalLValue` to determine how to modify a variable.

• The `evalLValue` function has been added. Given a variable mapping and an `ExprNode`, it generates a pair of values. The first item in the pair is the value of the expression, while the second is a function that given some new value returns a modified variable mapping with the destination represented by the `ExprNode` associated with the new value.

• In Test.hs, the `showTree` function has been modified to handle the modified definition of `StmtNode` and the new `ExprSub` and `ExprNewArray` constructors.

Still to complete are the following:

• In Parse.hs, you will need to modify `parseFactor` to account for the modification of its definition in the EBNF grammar. It will create new nodes using `ExprSub` and `ExprNewArray`.

• In Eval.hs, you will need to modify `evalLValue` to deal with writing to an array index, and you will need to modify `evalExpr` to deal with creating an array and with retrieving from an array index. You should find the included functions `arrayCreate`, `arraySet`, and `arrayGet` useful for these purposes.

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.