CS 421: Programming Languages and Compilers

Note: All assignments, MPs and WAs, and done in PrairieLearn . MPs additionally require you to click on Open workspace to open a new browser tab running VSCode. There are instructions on each question telling you how to do this.

Note: We are using the PrairieLearn Late Submission policy, which caps your total score at 80%. Doing extra credit can only lift your score to 80%, and will count for nothing after you have got to 80%.

Machine Problems for Spring 2023
MP No.:
Link:
Topic: Issued: Due at 23:59 CT
(11:59pm CT) on:
Automatic extension
(with 20% penalty)
until 23:59pm CT (11:59pm CT) on:
MP1 OCaml: Basic OCaml Jan 18, 2023 Jan 25, 2023 Jan 27, 2023
MP2 Pattern Matching and Recursion Jan 25, 2023 Feb 1, 2023 Feb 3, 2023
MP3 Patterns of Recursion, Higher-order Functions Feb 1, 2023 Feb 8, 2023 Feb 10, 2023
MP4 Continuations and Continuation-Passing Style Feb 8, 2023 Feb 22, 2023 Feb 24, 2023
MP5 Working with ADTs: Implementing CPS Transformation Feb 15, 2023 Mar 1, 2023 Mar 3, 2023
MP6 A Unification-Based Type Inferencer Mar 1, 2023 Mar 10, 2023 Mar 12, 2023
MP7 Unification Algorithm Mar 8, 2023 Mar 22, 2023 Mar 24, 2023
MP8 A Lexer for PicoML Mar 22, 2023 Apr 5, 2023 Apr 7, 2023
MP9 A Parser for PicoML Apr 3, 2023 Apr 19, 2023 Apr 21, 2023
MP10 An Evaluator for PicoML Apr 12, 2023 Apr 26, 2023 Apr 28, 2023
MP11 A Transition Semantics Evaluator for CPS Apr 19, 2023 May 1, 2023

Web Assignment (WA) Problems for Spring 2023
WA No." Topic: Issued: Due at 23:59 CT (11:59pm CT) on: Automatic extension
(with 20% penalty)
until 23:59 CT (11:59pm CT) on:
WA1 Evaluation and Evironments Jan 20, 2023 Jan 27, 2023 Jan 29, 2023
WA2 Order of Evaluation Jan 27, 2023 Feb 3, 2023 Feb 5, 2023
WA3XC Evaluating the Application of a Function Feb 3, 2023 May 3, 2023
WA4 CSP Transformation; Working with Mathematical Specifications Feb 17, 2023 Feb 24, 2023 Feb 26, 2023
WA5 Polymorphic Type Inference Feb 24, 2023 Mar 5, 2023 Mar 7, 2023
WA6 Incremental Unification Algorithm Mar 3, 2023 Mar 20, 2023 Mar 22, 2023
WA7 Regular Expressions Mar 10, 2023 Mar 31, 2023 Apr 2, 2023
WA8 Parse Trees Mar 24, 2023 Apr 7, 2023 Apr 9, 2023
WA9 Natural and Transition Semantics Apr 7, 2023 Apr 21, 2023 Apr 23, 2023
WA10 Lambda Calculus Apr 12, 2023 Apr 28, 2023 Apr 30, 2023
WA11 Hoare Logic Apr 28, 2023 May 3, 2023

Instructions for Submitting Assignments ---- This needs revision below here!
  • All assignments, both MPs and WAs, will be available through PrairieLearn and will be collected there.
  • When you do an MP in PrairieLearn, you will do your work for each problem in a VSCode Workspace. The introductory webpage for the problem gives you instructions for how to do the problem, including the problem statement. To actually do the problem, you will need to click the button "Open workspace", which will open a new tab in your browser running the VSCode editor/programming environment. It will present you with a directory, the ability to open and edit files in that directory, and an ability to start a terminal window, running linux, in which you can run ocaml, to build and test your code. The directory provided will contain a file with a name (typically problem.ml) and infrastructure to help you test your code. The file problem.ml is just a stub. A copy of this stub is provided as problem-skeleton.ml, which we recommend you never open, but copy to problem.ml, in case the problem.ml becomes to confused. To build your answer, you need to delete or comment out the stub code and add your own. However, do not change the name of the file, as that a file of that name from this directory is the one that will be officially graded when you push "Save & Grade". The next section Guide for Doing MPs contains further information about how to test your code.
    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 WAs. Your score will be the best of all your submissions, but the score of late submissions will have a late penalty applied, meaning it will only help your assignment score if the best score you received was less than 80% before the on-time due date. 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. For each problem in the assignment, go into the VSCode Workstation for the problem, and start a terminal window. To make sure you have all the necessary pieces, in that terminal window, start by executing make. This will create the grader executable. Still in the terminal window, 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 all tests will fail and the score will be 0.
  2. Read and understand the problem from the assignment 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 a partial set of test cases; you'll want to add more cases to test your code more thoroughly. Reread the problem from the main webpage for the problem, examining any sample output given. Open the tests file in the WORKSPACE directory. Review 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.
  3. If necessary, reread the statement of the problem once more. Place your code for the solution in problem.ml (or problem.mll or problem.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. On MPs adn WAs, 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 a single function or just a few with teh description broken into pieces of the functions. It is still worth your while to do incremental submissions.
  4. A typical test in the tests looks like:
    TEST1ARG(1, cube, 5);
    The number between TEST and ARG is the number of arguments the function being tested takes. The first component of the triple passed to TEST1ARG is the number of points you wish to give to the problem. This usually is 1, but might be 0 if it is a test checking that the code compiles as it should. The second component, here code is the name of the function to be tested. The third component is the expression that will be evaluated and have its value passed to the second component. That is, the above test causes each of the solution and your work to compute cube 5, compare the results and return 1 if the results are the same (or in more complicated instances equivalent by a notion of equivence specified in the tests file), a 0 otherwise. You are encouraged to add more tests to the tests file. A word of caution, though. If you put in a bad test, it may tell youthe Solution is broken, when in fact, it is your test.
  5. When you are satisfied with your code and it no longer generates any errors for the problem on which you were working, go back to the webpage with the problem statement, and press "Save & Grade" one last time to be sure it has been saved, and then return to the assessment main page to to proceed with the next problem you wish to solve, until there are no more problems to be solved. Each problem is submitted in PrairieLearn indepentantly of the others, but some later assignments have only one problem.
  6. When you have finished all problems (or given up and left some problems with the stub version originally provided, or incomplete but still able to compile), 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, if there is such a file in the workspace directory. (This loads in the common stuff that we give you in compiled form by default).
  4. Type #use "problem.ml";; at the OCaml prompt, where problem is the name of the problem, which is typically the name function being implemented. You do type a #, in addition to the # the system prints as a line prompt. 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" if there is one, 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.