jw76 ============ Assignment 6 ============ This assignment starts from the step 1 of Assignment 5. The eagerEval() (valueValue() in Assignment 4) is renamed as eval(), while all other evaluation methods are removed. lexer.java, Parser.java and other relevant interpreter classes: Added "letrec" for recursive-let support (limited to maps). The orginal "let" is now defined as non-recursive let. Also added "letcc" constructs for extra credit. Unshadow.java: Performs the unshadowing transformation. The visitor traverses the AST and returns a new unshadowed AST structure. It also transforms "&" and "|" into if-then-else constructs. Note: At this time, the transformation of "&" and "|" is not done in the parser. So a program "map M,N to M & N" will be parsed as "map M,N to M & N" by the Parser class, but it will be converted to "map M:1,N:2 to map M:1,N:1 to if M:1 then N:1 else false" by the unshadowing transformation. Cps.java: Performs the CPS transformation. The transformation will start from a binary function mapping program Cps[map x to x, M0], where M0 is the unshadowed form of the given program. The two private methods, convertCps(AST, AST) and convertRsh(AST), will respectively convert Cps[k, M] and Rsh[S] to AST constructs recursively. The code is basically the step-by-step interpretation of the definitions of Cps and Rsh in Java. Sd.java: Performs the static-distance transformation. The visitor traverses the AST and returns a new AST in static-distance format. Also added new AST classes (SdLet, SdLetRec, SdLetcc, SdMap, SdVariable) to support static-distance format. Assign6Test.java: More test cases are added. They are supposed to cover most of the cases in this assignment. ============ Assignment 5 ============ This assignment is based on my previous assignments to support a typed Jam dialect. Most of the changes are made in the lexer and ther parser, as well as two new files TypeCheck.java and Type.java, while the other parts are mostly unchanged. Type.java: Defined types: UnitType, IntType, BoolType, ListType, RefType, and ClosureType. TypeCheck.java: The TypeVisitor will recursively traverse the ASTs, perform type-checking for each AST, and returns the returning type of each AST. There are also three auxiliary class (PrimFunTypeVisitor, UnOpTypeVisitor, and BinOpTypeVisitor), which help type-check the primitive function apps, unary-operator apps and binary-operator apps respectively. Interpreter.java: Used eagerEval() and lazyEval() to replace the previous nine interpeter. Also added type check after context-sensitive check. lexer.java and Parser.java: Modified to conform to the new typed syntax. Variable and NullConstant now have a Type attribute. Assign5Test.java: More test cases are added. They are supposed to cover most of the cases in this assignment. Note that the test cases of previous assignments are removed due to compatibility issues. ============ Assignment 4 ============ This assignment extends my solution of the previous assignment to support references and blocks. Most of the changes are made in the lexer and the parser to support the new operators and grammars. For the interpreter's part, new evaluation mechanisms are added, but they are quite simple and straightforward. lexer.java: New tokens, "!", "ref", and "<-", are added. There are also two new types of JamVal: JamRef and JamUnit, where JamRef is simply the reference (or box) and JamUnit is the special value "unit". Parser.java: Added a new private method parseBlock to parse blocks. Also refactored "parseExp" by splitting up different production rules into different methods. UnOpInterpreter.java: Added evaluation mechanism for "!" and "ref". PrimFunInterpreter.java: Added evaluation mechanism for "<-". Context.java: Added context-sensitive checking for blocks. ASTInterpreter.java Added evaluation mechanism for blocks. Assign4Test.java: More test cases are added. They are supposed to cover most of the cases in this assignment. ============ Assignment 3 ============ This assignment basically extends my solution of assignment 2, with more complete functionality. There are a bunch of new interfaces added to the program, but the basic structure is preserved. Context-sensitive checking: Two new classes, "Context" and "ContextVisitor", are added. ContextVisitor will traverse the AST nodes recursively and raise an syntax exception if there is any free or duplicate variable. Safety: Safety was taken into account in my assignment 2 solution. In this assignment, I just made a few improvements, such as the divide-by-zero situations. Lazy cons: A new abstract class "LazyCons" that inherits from JamCons is the base class of all lazy cons with different evaluation strategies, including LazyConsByValue, LazyConsByName, and LazyConsByNeed. They are basically initialized with null values, and the values will be evaluated at different time according to the evaluation strategy used. Recursive let: Added a new static method "generate" in ValueBinding, which generate a list of bindings from an array of variables to an array of the corresponding expressions. This new method is used to replace the previous one in "let" to support "recursive let". Nine interpreters: Created a new class EvaluationPolicy that encapsulate the calling convention and cons convention. The evaluation policy will be passed into the interpreters in assignment 2. The three interpreters in assignment 2 are preserved, using the default cons-by-value strategies. Test: More test cases are added. They are supposed to cover most of the cases in this assignment. ============ Assignment 2 ============ The Interpreter class contains three public methods to interpret a Jam expression according to different evaluation strategies, which are JamVal callByValue(), JamVal callByName(), and JamVal callByName(). The class InterpreterBase is the base class of all interpreters, including ASTInterpreter: generic interpreter that interprets an AST to a JamVal BinOpInterpreter: interprets binary operator App to a JamVal JamFunInterpreter: interprets Jam functions (Map and primitive functions) to a JamVal PrimFunInterpreter: interprets Jam primitive functions to a JamVal UnOpInterpreter: interprets binary operator App to a JamVal EnvironmentInterpreter: assigns a value to a given variable All of them but EnvironmentInterpreter extend from this base class as well as implements a specific visitor interface. When a target, e.g. an AST node, calls "accept", it requests the interpreter to convert it to a JamVal. Then, the corresponding method in the corresponding interpreter will be called. This is basically how the interpreters are implemented. ============ Assignment 1 ============ The Parser class uses public method AST parse() to parse Jam expression. Inside the class, there are totally six private parsing methods implemented，including AST parseExp(Token), AST parseTerm(Token), Def parseDef(Token), AST parseFactor(Token), Variable[] parseIdList(), and AST[] parseExpList(). Each of these private methods will be responsible of parsing a specific type of expressions. In addition, each of them is referenced by a single or multiple methods, parsing the expressions recursively. The detailed process can be found here https://www.cs.rice.edu/~javaplt/411/16-spring/Assignments/1/OriginalSyntaxDiagrams.pdf where each section in this diagram is correspondent to a private method above. The public method AST parse() simply calls AST parseExp(Token) at the beginning, and returns an Abstract Syntax Tree if there is no syntax error. Any parsing method is able to throw a ParseException if there is a syntax error, which will finally be thrown out by AST parse(). Unit tests are also implemented along with the parser, and they can prove the correctness of this program. Given sample test files, including those in "simple", "medium", and "hard" folders, are also used to verify the correctness of this program.