Jump directly to Week 1 | Week 2 | Week 3 | Week 4 | Week 5 | Week 6 | Week 7 | Week 8 | Week 9 | Week 10This document was last modified on December 17, 2006.
Week 1: Friday
| nQueens 3 | yields | [] |
| nQueens 4 | might yield | [[0,1,0,0],[0,0,0,1],[1,0,0,0],[0,0,1,0]] (one of several possible solutions) |
lex input that does
lexical analysis for a
subset of the Jay language, and the
yacc input that
parses a subset of the Jay grammar.
Our overall programming project for the rest of this quarter will be to implement a Jay interpreter in Haskell. The interpreter program (which is a function, of course) should return the final state of the Jay program's environment. Assume that the program's input is a parse tree of the form that we talked about in class. The sample syntax I shared with you for interpreter parse trees (aka the syntax for the proposed intermediate representation of Jay programs) is available from the following link:
Haskell/JayFibSampleParseTree.hs
The TestSuiteSupportModule (which I hope you also used for your NQueens project) is available from the following link:
Haskell/TestSuiteSupportModule.hs
Part 1 Due "Tuesday" of 7th
Week:
The first step will be to implement a way of representing state,
which we have simplistically defined for our own purposes as a set
of {Name, Value} pairs (or {Name, Value} bindings), where Name is
a variable name (identifier for a memory location) and Value is
the value bound to the identifier. We have left the actual
locations out of the equation, meaning, if you think about it, that
our language does not support aliases. The data type definitions
and function signatures for representing state,
and the associated test cases, are available from the following link:
Haskell/ValuesAndState.hs
Part 2 Due "Friday" of 7th
Week:
The next step will be to write code to interpret Jay declarations
expressed in our intermediate language. The data types definitions
and function signatures for representing interpreting declarations,
and the associated test cases, are available from the following link:
Haskell/JayDecls.hs
(Note: although it's not required yet, I would strongly encourage
you to look ahead and implement enough of Part 3 to allow you to
create assignment statements assigning a constant value to a
variable. This will allow you to see the code you wrote in Parts 1
and 2 in action.)
Part 3 Due "Friday" of 8th
Week:
You may wish to keep things simple for your next step, implementing
the very simplest of expressions (e.g., constants and
variables) and the simplest of statements (the empty statement and
assignment statement) first so that you can test them together.
Or you may wish to implement and test all
expression types before going on to statements.
The data types definitions
and function signatures for representing expressions,
and the associated test cases, are available from the following link:
Haskell/JayExpressions.hs
Note: for division, you want to use the "div" operator in Haskell rather than the "/" operator, since the former does integer division.
Part 4 Due "Friday" of 9th
Week:
The final step is to implement the semantics for various types of
statements and then implement the function that interprets a Jay
program expressed in our intermediate parse tree format.
The data types definitions
and function signatures for representing statements,
and the associated test cases, are available from the following link:
Haskell/JayStatements.hs
The file for the program as a whole is:
Haskell/JayInterpreter.hs
The file for the sample fibonacci program from p. 43 of Tucker and Noonan (1st Ed.) is:
Haskell/JayFibSampleParseTree.hs
Jump directly to Week 1 | Week 2 | Week 3 | Week 4 | Week 5 | Week 6 | Week 7 | Week 8 | Week 9 | Week 10