CS 421 (Spring 2014): mps

CS 421: Programming Languages and Compilers

main :: policy :: lectures :: mps :: exams :: unit project :: resources :: faq

Machine Problems for Spring 2014

	Topic:	Issued:	Due at 11:59pm CT on:
MP1	OCaml: Basic OCaml	Thursday, Jan 23	Sunday, Feb 2
MP2	Pattern Matching and Recursion	Thursday, Jan 30	Sunday, Feb 9
MP3	Recursion Patterns and Higher-Order Functions	Thursday, Feb 6	Sunday, Feb 16
MP4	Continuation-Passing Style	Thursday, Feb 13	Sunday, Feb 23
MP5	Working with ADTs: Implementing CPS	Thursday, Feb 20	Sunday, Mar 2
MP6	A Unification-Based Type Inferencer	Thursday, Feb 27	Sunday, Mar 16
MP7	Unification Algorithm	Thursday, Mar 13	Tuesday, Apr 1
MP8	A Lexer for MicroML	Thursday, Mar 20	Sunday, Apr 6
MP9	A Parser for MicroML	Thursday, Apr 3	Sunday, Apr 13
MP10	An Evaluator for MicroML	Thursday, Apr 10	Sunday, Apr 27
MP11	A Transition Semantics Evaluator for CPS	Thursday, Apr 24	Sunday, May 4

Hand Written Assignments for Spring 2014

	Topic:	Issued:	Due at 11:59pm CT on:
HW1	Evaluation and Evironments	Thursday, Jan 23	Sunday, Feb 2
HW2	Evaluating the application of a function	Thursday, Jan 30	Sunday, Feb 9
HW3	Order of Evaluation	Thursday, Feb 6	Sunday, Feb 16
HW4	CPS Transformation	Thursday, Feb 13	Sunday, Feb 23
HW5	User-Defined Datatypes	Thursday, Feb 20	Sunday, Mar 2
HW6	Polymorphic Type Inference	Thursday, Feb 27	Sunday, Mar 16
HW7	Unification	Thursday, Mar 13	Tuesday, Apr 1
HW8	Regular Expression	Thursday, Mar 20	Sunday, Apr 6
HW9	Parse Trees, Ambiguous Grammars, and LR and Recursive Descent Parsing	Thursday, Apr 3	Sunday, Apr 13
HW10	Operational and Transition Semantics	Thursday, Apr 10	Sunday, Apr 27
HW11	Lambda Calculus and Hoare Logic	Thursday, Apr 17	Sunday, May 4

Instructions for Solving and Submitting Assignments

Assignment problems are distributed through a dedicated subversion repository, and assignment solutions are collected through the same subversion repository.

Each student is given a svn directory that needs to be checked out before it can be used for solving and submitting assignments. You can check out this directory as follows:

mkdir <working_directory>

svn co https://subversion.ews.illinois.edu/svn/sp14-cs421/<your_netid> <working_directory>

After the initial checkout, <working_directory> contains a subdirectory assignments. Once an assignment (mp or hw) is announced, this directory will contain a subdirectory named after the assignment (e.g. hw11, mp1, etc) with the files relevant to the respective assignment. You can retrieve this directory by running in assignments:

svn up

For an hw, the directory will contain the file hwX.pdf, where X is the number of the hw. You need to add to that directory your solution, which needs to be called as specified in the distributed file hwX.pdf. Typically, your submission's name is hwX-solution.pdf, but check the assignment's instructions. You can add the <solution file> to the subversion repository by running in the assignment directory:

svn add <solution file>

For an mp, the directory will contain several files, including mpX.pdf, where X is the number of the mp. You need to add your solution in the file specified in mpX.pdf, tipically mpX.ml (see more details below).

To submit an assignment, once you have completed the necessry files as decribed in the assignment instructions, run in the assignment directory

svn commit -m "<your comment here>"

You may restrict svn commit to a specific collection of files and directories by adding a list to the end of the command.

You may do multiple commits; the version that is in the repository at the time specified by the assignment instructions on the due date is that one that will be collected and graded.

Guide for Doing MPs
A guide for how to attack an MP: Check out the `mp`X directory from the subversion repository (as described above). Go into that directory. Start by executing `make`. This will create the grader executable. Run the executable (`./grader`). Examine the failing test cases for places where errors were produced by your code. At this point, everything should compile, but the score will be 0. Read and understand the problem from the handout that you wish to begin working on (usually, working from top to bottom makes most sense). There is a `tests` file in this directory. This is an important file containing an incomplete set of test cases; you'll want to add more cases to test your code more thoroughly. Reread the problem from the handout, examining any sample output given. Open the `tests` file. Find the test cases given for that problem. Add your own test cases by following the same pattern as of the existing test cases. Try to get a good coverage of your function's behaviour. You should even try to have enough cases to guarantee that you will catch any errors (this is not always possible, but a desirable goal). And yes, test cases should be written even before starting the implementation of your function. This is a good software development practice. If necessary, reread the statement of the problem once more. Place your code for the solution in `mp`X`.ml` (or `mp`X`.mll` or `mp`X`.mly` as specified by the assignment instructions), replacing the stub found there for it. Implement your function. Try to do this in a step-wise fashion. When you think you have a solution (or enough of a part of one to compile and be worth testing), save you work and execute `make` and the `./grader` again. Examine the passing and failing test cases again. Each failure is an instance where your code failed to give the right output for the given input, and you will need to examine your code to figure out why. When you are finished making a round of corrections, run `make`, followed by `./grader` again. Continue until you find no more errors. When your code no longer generates any errors for the problem on which you were working, return to steps 3) and 4) to proceed with the next problem you wish to solve, until there are no more problems to be solved. When you have finished all problems (or given up and left the problem with the version given in the stub file), commit your solution.

Guide for Doing MPs

A guide for how to attack an MP:

Check out the mpX directory from the subversion repository (as described above). Go into that directory.
Start by executing make. This will create the grader executable. Run the executable (./grader). Examine the failing test cases for places where errors were produced by your code. At this point, everything should compile, but the score will be 0.
Read and understand the problem from the handout that you wish to begin working on (usually, working from top to bottom makes most sense). There is a tests file in this directory. This is an important file containing an incomplete set of test cases; you'll want to add more cases to test your code more thoroughly. Reread the problem from the handout, examining any sample output given. Open the tests file. Find the test cases given for that problem. Add your own test cases by following the same pattern as of the existing test cases. Try to get a good coverage of your function's behaviour. You should even try to have enough cases to guarantee that you will catch any errors (this is not always possible, but a desirable goal). And yes, test cases should be written even before starting the implementation of your function. This is a good software development practice.
If necessary, reread the statement of the problem once more. Place your code for the solution in mpX.ml (or mpX.mll or mpX.mly as specified by the assignment instructions), replacing the stub found there for it. Implement your function. Try to do this in a step-wise fashion. When you think you have a solution (or enough of a part of one to compile and be worth testing), save you work and execute make and the ./grader again. Examine the passing and failing test cases again. Each failure is an instance where your code failed to give the right output for the given input, and you will need to examine your code to figure out why. When you are finished making a round of corrections, run make, followed by ./grader again. Continue until you find no more errors.
When your code no longer generates any errors for the problem on which you were working, return to steps 3) and 4) to proceed with the next problem you wish to solve, until there are no more problems to be solved.
When you have finished all problems (or given up and left the problem with the version given in the stub file), commit your solution.

Interactive Debugging
In addition to running "make" and "grader", you probably want to test your code interactively at the top level: Enter the directory with your source file. Type `ocaml` at the command line. Type `#load "mpXcommon.cmo";;` at the OCaml prompt, where X is the number of the assignment (this loads in the common stuff that we give you in compiled form by default). Type `#use "mpX.ml";;` at the OCaml prompt, where X is the number of the assignment. This loads in your code, and adds the functions you have defined to the identifiers recognized at top level. Type in commands followed by '`;;`' at the OCaml prompt to test your code interactively. Anything that you can do in a code file, you can do interactively. For example, you can define identifiers using '`let x =` ...', etc... With each MP, you will be given a solution in compiled form. You may interactively test the solution to a problem, after having loaded `"mpXcommon.cmo"`, by loading the solution file by typing `#load "solution.cmo";;`. After that, if you are supposed to write a function called, say `splat`, and wish to fine out what it does on an input, say `39.2`, you make execute the solution's version of `splat` by typing `Solution.splat 39.2;;`. Notice the capitalization.

Interactive Debugging

In addition to running "make" and "grader", you probably want to test your code interactively at the top level:

Enter the directory with your source file.
Type ocaml at the command line.
Type #load "mpXcommon.cmo";; at the OCaml prompt, where X is the number of the assignment (this loads in the common stuff that we give you in compiled form by default).
Type #use "mpX.ml";; at the OCaml prompt, where X is the number of the assignment. This loads in your code, and adds the functions you have defined to the identifiers recognized at top level.
Type in commands followed by ';;' at the OCaml prompt to test your code interactively. Anything that you can do in a code file, you can do interactively. For example, you can define identifiers using 'let x = ...', etc...
With each MP, you will be given a solution in compiled form. You may interactively test the solution to a problem, after having loaded "mpXcommon.cmo", by loading the solution file by typing #load "solution.cmo";;. After that, if you are supposed to write a function called, say splat, and wish to fine out what it does on an input, say 39.2, you make execute the solution's version of splat by typing Solution.splat 39.2;;. Notice the capitalization.