Christmas assignment (Compilers)

Copyright © 2024 J. M. Spivey
Jump to navigation Jump to search

To encourage participants to develop practical skills, and to give them an opportunity to demonstrate them, the course culminates in a practical assignment done over the Chritmas vacation. Participants are asked to perform a programming task, then to write up their work in a report. The task is usually involves extending one of the toy compilers used during the lab sessions with new language features. The assignment often asks for additional test cases that demonstrate the working of the new features.

  • A sample report shows a workable format, with a small (and relatively unchallenging) part of one of the lab exercises written up as if it were the practical assignment.

What follows is a list of assignments set in previous years, some written by Mike and some by others, together with partial solutions by Mike; these solutions show the gist of what is required to carry out the task, without always being a perfect answer to the assignment. In particular, I haven't always created as many test cases as would be ideal to demonstrate the proper functioning of all aspects. Sometimes, if part of an assignment seems too open-ended for a definitive solution, I've just omitted it; and at other times, it seemed to me easier to implement something more general than what was asked for, or to adopt an approach that did not quite follow the outline given in the instructions. I hope that I would not be penalised for these excesses, but have never quite plucked up the courage to slip my own attempt in with the scripts to see what marks I would get.

For the 2023 edition of the course, the representation of code fragments in Lab 4 has changed. As part of my assessment of whether the change was viable, I've updated these solutions to past Christmas assignements to match.

  • From 2017: implementing the for statement from Algol 60, a slightly baroque looping construct from a bygone age. Assignment, Solution. Links to the Revised Report and Knuth's article on semantic trouble spots appear on the main page of this site.
  • From 2018: adding a continue statement like that provided in C, branching immediately to the next iteration of a loop, and also adding parameters passed by name. Assignment, Solution.
  • From 2019: adding a form of loop that iterates over an array. Assignment, Solution. A second part of the assignment asked for a compiler test that determined when two fragments of code could safely be commuted, but that part is not attempted here.
  • From 2020: implementing a break statement for nested loops, and reducing the need for padding between record elements and local variables by sorting them according to their alignment requirements. Assignment, Solution.
  • From 2021: implementing block expressions, where statements can be embedded in expressions, and reversing excessive common subexpression elimination. Assignment, Solution. Note: the reversal of excessive CSE is now incorporated already in the compiler used for the lab exercises.
  • From 2022: implementing simultaneous assignment. Assignment. Solution.

Some helpful hints

There are various options for setting up an environment for completing the task on your own computer, listed on the software setup page. Among them is a new 'virtual appliance' that runs under VirtualBox, and immediately provides everything you might need.

I wrote my solutions using the same TEX (not LaTEX) format as the coursebook, with nicely printed ML code, but you need not do anything similar: a simple word-processed document with code shown in a monospaced font will be enough. Sometimes the instructions ask for code changes to be shown as diff listings, and for this it's convenient (even if not required) to use version control software. I habitually use Mercurial rather than Git for reasons I've explained elsewhere, but GIT can provide listings in an identical format. To get the printed form shown in the sample reports, where changes are highlighted in bold, I used enscript with the command line

enscript -Ediffu -o - diffs >

followed by ps2pdf >diffs.pdf to convert enscript's Postscript output to PDF, and pdfunite to join the result with the main report.

Some specific recommendations that come from the author's experience in marking assignments:

  • The marker may want to print your report for marking. Please make it easy by formatting your report in black and white, and not using elements such as hyperlinks in a way that is necessary for understanding.
  • Use page numbers, and put your candidate number in the header or footer of the page. This makes it much easier for the marker to keep the pages straight after printing a whole pile of reports for marking.
  • Use a spell checker before submitting your report. Your spelling may be above reproach, but we can all make typing mistakes, and they do create a poor impression.
  • When quoting fragments of code, try to do it by pasting them as fragments of text, not as screenshots. If you must use screenshots, then at least make the background white and the text dark, so that they are still readable when printed.