Christmas assignment

From Compilers
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 Andrzej Murawski, 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.

  • 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.

Some helpful hints

I wrote my solutions using the same TEX 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 >diffs.ps

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