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.
- 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 theseshowXXX
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:
- 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.
- 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
andExprNode
types.- For
StmtNode
, theStmtAssn
constructor takes anExprNode
rather than aString
to indicate the assignment's left side. - For
ExprNode
, there are two new constructors,ExprSub
andExprNewArray
.
- For
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 theValue
type.New functions
arrayCreate
,arraySet
, andarrayGet
have been added to help you with manipulating an array.The
evalStmt
case for an assignment statement now usesevalLValue
to determine how to modify a variable.The
evalLValue
function has been added. Given a variable mapping and anExprNode
, 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 theExprNode
associated with the new value.In Test.hs, the
showTree
function has been modified to handle the modified definition ofStmtNode
and the newExprSub
andExprNewArray
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 usingExprSub
andExprNewArray
.In Eval.hs, you will need to modify
evalLValue
to deal with writing to an array index, and you will need to modifyevalExpr
to deal with creating an array and with retrieving from an array index. You should find the included functionsarrayCreate
,arraySet
, andarrayGet
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.