CS 421: Programming Languages and Compilers
Machine Problems for Fall 2014
Topic: Issued: Due at 23:59pm CT on: Automatic extension
(with 20% penalty)
until 23:59pm CT on:
MP1 OCaml: Basic OCaml Tuesday, Aug 28 Tuesday, Sep 2 Thursday, Sep 4
MP2 Pattern Matching and Recursion Tuesday, Sep 2 Tuesday, Sep 9 Thursday, Sep 11
MP3 Recursion Patterns and Higher-Order Functions Tuesday, Sep 9 Tuesday, Sep 16 Thursday, Sep 18
MP4 Higer-Order Functions and Continuation-Passing Style Tuesesday, Sep 16 Tuesday, Sep 23 Thursday, Sep 25
MP5 Working with ADTs: Implementing CPS Tuesday, Sep 23 Tuesday, Sep 30 Thursday, Oct 2
MP6 A Unification-Based Type Inferencer Tuesday, Sep 30 Tuesday, Oct 14 Thursday, Oct 16
MP7 Unification Algorithm Tuesday, Oct 14 Tuesday, Oct 21 Thursday, Oct 23
MP8 A Lexer for PicoML Tuesday, Oct 21 Tuesday, Oct 28 Thursday, Oct 30
MP9 A Parser for PicoML Wednesday, Oct 29 Thursday, Nov 13 Saturday, Nov 15
MP10 An Evaluator for PicoML Friday, Nov 14 Friday, Nov 21 Sunday, Nov 23
MP11 A Transition Semantics Evaluator for CPS Friday, Nov 21 Friday, Dec 5 None

Hand Written Assignments for Fall 2014
Topic: Issued: Due at 23:59pm CT on: Automatic extension
(with 20% penalty)
until 23:59pm CT on:
HW1 Evaluation and Evironments Tuesday, Aug 28 Tuesday, Sep 2 Thursday, Sep 4
HW2 Evaluating the application of a function Tuesday, Sep 2 Tuesday, Sep 9 Thursday, Sep 11
HW3 Order of Evaluation Tuesday, Sep 9 Tuesday, Sep 16 Thursday, Sep 18
HW4 CSP Transformation; Working with Mathematical Specifications Thursday, Sep 18 Thursday, Sep 25 Saturday, Sep 27
HW5 Algebraic Datatypes Thursday, Sep 25 Thursday, Oct 2 Saturday, Oct 4
HW6 Polymorphic Type Inference Thursday, Oct 2 Tuesday, Oct 14 Thursday, Oct 16
HW7 Unification Tuesday, Oct 14 Tuesday, Oct 21 Thursday, Oct 23
HW8 Regular Expressions Tuesday, Oct 21 Tuesday, Oct 28 Thursday, Oct 30
HW9 Parse Trees, Ambiguous Grammars and Recursive Descent Parsing Tuesday, Oct 28 Thursday, Nov 6 Saturday, Nov 8
HW10 Operational and Transition Semantics Friday, Nov 14 Friday, Nov 21 Sunday, Nov 23
HW11 Lambda Calculus Not Assigned

Note: The late penaly is 20% of the total number of points possible on the base part of the assignment, plus 20% of the total points possible on the extra credit, if you attempt the extra credit. It is not 20% of the number of points your earn.

Instructions for Submitting Assignments
  • Each student is given an svn directory that needs to be checked out once before it can be used for submission as follows:
    mkdir <working_directory>
    svn co https://subversion.ews.illinois.edu/svn/fa14-cs421/<your_netid> <working_directory>
  • After the initial checkout, <working_directory> will contain a subdirectory assignments. Once an assignment (MP or HW) has been announced, if you do an
    svn up
    you will add a directory named after the assignment (e.g. mp1) in the assignments directory. That directory will contain the information posted on the web for that assignment.
  • For an HW, the directory will contain the file hwX.pdf, whereX 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 will need to be called hwX-submission.pdf, but check the assignment's instructions. To submit your assignment, you will need to do the following:
    svn add hwX-submission.pdf
    svn commit -m "<your comment here>"
    Submissions for HWs should be in pdf format.
  • When you retrieve an MP via svn up the directory added will contain a pdf named mpX.pdf describing the work to be done for the assignment, a file with a name (typically mpX.ml) that is the same name as the file you must submit, and infrastructure to help you test your code. The file mpX.ml is just a stub. You need to delete or comment out the stub code and add your own. The next section Guide for Doing MPs contains further information about how to test your code. For submission, you will only need do
    svn commit -m "<your comment here>"
    in the directory where your MP is. You do not need to add it, since we added it is as a stub for you. Please try to avoid committing the .cmo and .cmi files into the svn repository; it only occupies unnecessary space on the server and wastes unnecessary network traffic. You may always restrict svn commit to a specific collection of files and directories by adding a list to the end of the command.

    Before submitting an MP assignment, you MUST make sure that your MP compiles with the student grading script supplied with the assignment. If your MP fails to compile with the student grading script, your assignment will get NO CREDIT. There will be no partial credit for assignments that fail to compile.

  • You may do multiple commits of either the MPs or the HWs. We will only grade the last version committed before the Extension deadline. Each homework will be classified as on time if its last submission is logged before the Due date of the assignment. If the last submission before the Extension deadline is after the Due date, you will receive a late penalty as described in Extensions.
  • <-- You may do multiple commits of either the MPs or the HWs; the version that is in the repository at the time specified by the due date in the assignment instructions is the one that will be collected and graded. -->
Guide for Doing MPs
A guide for how to attack an MP:
  1. In your svn repository dircetory, or its subdirectory assignments, do an svn up to retrieve the directory mpX for the MP and all its contents. Go into that directory. (If we need to revise an assignment, you will need to repeat the svn up to obtain the revision.)
  2. To make sure you have all the necessary pieces, 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.
  3. Read and understand the problem for the handout on which you wish to begin working. (Usually, working from top to bottom makes most sense.) There is a tests file in this directory. This is an important file containing the 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 in the mpX directory. 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.
  4. 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. Consider submitting your partial result so that you will at least get credit for what you have accomplished so far, in case something happens to interfere with your completing the rest of the assignment.
  5. 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.
  6. When you have finished all problems (or given up and left the problem with the stub version originally provided), you will need to submit your file to the svn repository, and described in the previous section.
Interactive Debugging
In addition to running "make" and "grader", you probably want to test and debug your code interactively at the top level:
  1. Enter the directory with your source file.
  2. Type ocaml at the command line.
  3. 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).
  4. 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.
  5. 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...
  6. 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.