CS 421: Programming Languages and Compilers

Note: You can find the complete set of questions in a pdf, and a tarball containing a testing harness for the question set at the link in the first column (Tarball Link). You can practice the experience of using PrairieLearn to do and submit you work by following the link in the second colunm, and selecting the assessment of the name given in the second column.

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

Machine Problems for Fall 2021
Tarball
Link:
Topic: Issued: Due at 22:00 CT
(10:00pm CT) on:
Automatic extension
(with 20% penalty)
until 22:00pm CT (10:00pm CT) on:
Solution
MP1 OCaml: Basic OCaml Sep 4, 2021 Sep 11, 2021 Sep 13, 2021 mp1 sol
MP2 Pattern Matching and Recursion Sep 10, 2021 Sep 17, 2021 Sep 19, 2021 mp2 sol
MP3 Patterns of Recursion, Higher-order Functions Sep 17, 2021 Sep 24, 2021 Sep 26, 2021 mp3 sol
MP4 Continuations and Continuation-Passing Style Sep 23, 2021 Oct 7, 2021 Oct 9, 2021 mp4 sol
MP5 Working with ADTs: Implementing CPS Transformation Oct 8, 2021 Oct 15, 2021 Oct 17, 2021 mp5 sol
MP6 A Unification-Based Type Inferencer Oct 14, 2021 Oct 21, 2021 Oct 23, 2021 mp6 sol
MP7 Unification Algorithm Oct 21, 2021 Oct 28, 2021 Oct 30, 2021 mp7 sol
MP8 A Lexer for PicoML Oct 28, 2021 Nov 11, 2021 Nov 13, 2021 mp8 sol
MP9 A Parser for PicoML Nov 15, 2021 Dec 1, 2021 Dec 3, 2021 mp9 sol
MP10 An Evaluator for PicoML Nov 18, 2021 Dec 4, 2021 Dec 6, 2021 mp10 sol
MP11 A Transition Semantics Evaluator for CPS Nov 27, 2021 Dec 8, 2021 Dec 11, 2021 mp11 sol

Web Assignment (WA) Problems for Fall 2021
Topic: Issued: Due at 22:00 CT (10:00pm CT) on: Automatic extension
(with 20% penalty)
until 22:00 CT (10:00pm CT) on:
WA1 Evaluation and Evironments Sep 17, 2021 Sep 24, 2021 Sep 26, 2021
WA2 Evaluating the Application of a Function TBA TBA TBA
WA3 Order of Evaluation TBA TBA TBA
WA4 CSP Transformation; Working with Mathematical Specifications TBA TBA TBA
WA5 Algebraic Datatypes TBA TBA TBA
WA6 Polymorphic Type Inference
WA7 Incremental Unification Algorithm
WA8 Regular Expressions
WA9 Parse Trees, Ambiguous Grammars and Recursive Descent Parsing
WA10 Natural and Transition Semantics
WA11 Lambda Calculus TBA TBA TBA
WA12 Hoare Logic TBA TBA TBA

Instructions for Submitting Assignments ---- This needs revision below here!
  • For a WA, the assignment will be available through PrairieLearn and will be collected there. You can optain the pdf writeup and tarball for each ML and MP at the links given above. You can also obtain them through PrairieLearn, and the MPs may be submitted there. The MLs are
  • When you retrieve an MP or ML via the above links, you will be able to collect a pdf named mpX.pdf or mlX.pdf giving background information describing the work to be done for the assignment. You will also be able to collect a tarball named mpX.tar.gz or mlX.tar.gz. You can unpack the tarball with
    tar -xzf mpX.tar.gz
    or tar -xzf mpX.tar.gz
    as approriate. The resulting directory added will contain the pdf for the assignment, a file with a name (typically mpX.ml or mlX.ml) and infrastructure to help you test your code. The file mpX.ml or mlX.ml is just a stub. To test, 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.

    MPs, like WAs, will be turned in by entering your answer into text windows (typically one per problem) in PrairieLearn.

    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.

    For each ML, we give you the whole set of problems before you need to go to the lab to be checked on them. Typically, in the lab you will be asked to do only a fraction (typicaly about a fifth, but may be smaller or larger) of the problem(s) you were given in the pdf. You may go to PrairieLearn to take sample runs of the lab before going to the Computer-Based Testing Facility (CBTF), but only the version of your work you submit in the CBTF will count for your grade. The code you submit in the CBTF must compile to receive credit for it. You will have access to the ocaml compiler and the test suite for you to check before you submit. The next section Guide for Doing MPs is useful for preparing for MLs as well as doing MPs.

  • You may do multiple commits of either the MPs or the WAs. Work submitted before the late deadline will not be subject to the late penalty, but work submitted after will.
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. You can submit one problem at a time in earlier assignments. In later assignments, problems tend to be pieces of functions. It is still worth your while to incremental uploads.
  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 code to PrairieLearn.

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 "common.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 "common.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 find out what it does on an input, say 39.2, you may execute the solution's version of splat by typing Solution.splat 39.2;;. Notice the capitalization.