COS 371: Programming Languages

Spring 2022

Exam 3 information

1. Allowed materials

You are permitted one letter-size handwritten notes sheet (both sides) for use as a reference during the exam.

You may only use electronic devices (computer, smart phone) to the extent of following exam logistics (below).

In particular, you should NOT use clang or DrRacket during the exam.

2. How to study

Please see tips from first exam.

3. Exam content

The exam covers everything we have done. While the exam is cumulative, we will focus on what was not already tested (starting with recursive descent parsing).

Students should be able to:

• Write Scheme and C code on paper to do specified tasks.
• Evaluate Scheme code using the environment model, including drawing environment diagrams as we have done in class.
• Be able to explain what an LL grammar is, and how it is distinguished from an LR grammar. For a simple grammar, assess whether or not it is LL.
• Describe, trace, or otherwise answer questions to show understanding of what recursive descent parsing is, how it works at a high level, and distinguish recursive descent parsing from the kind of parsing that we did for our Scheme interpreter. Be able to produce FIRST, FOLLOW, and PREDICT sets for a particular grammar.
• Show understanding of how C compilation works, with regards to header files and compilation of multiple files. Be able to demonstrate how/why include guards are used.
• Distinguish between static and dynamic scoping, and be able to evaluate trade-offs. Be aware of scoping behaviour for languages regularly used in this course. (I.e., you do not need to memorize the classification of all the one-off languages used to demo scoping.)
• Evaluate the results of pseudocode using different parameter passing methods, including pass by value, by reference, by value-result, and by sharing. Be aware of parameter passing methods for languages regularly used in this course. Be able to think through considerations regarding how they are implemented underneath.
• Define, explain, compare, and contrast garbage collection techniques, such as reference counting, mark-and-sweep (including tri-color marking), stop-and-copy, and generational approaches.
• Regarding the interpreter project: Be able to answer questions about what we did at each stage, and why we did it. Be able to write variations of aspects of the project by writing C code, modifying provided C code, or describing what your technique might be. Specifically, be able to do the above regarding questions about:
  • frames
  • bindings
  • lambda expressions
  • closures
  • primitives / function pointers

As usual, please note that this document is not a contract. I may have inadvertently left something off that ends up on an exam question. Moreover, I will not be able to test all of this material given the time limitations of the exam. I will have to pick and choose some (small) subset of it.

4. Logistics

Logistics will be identical to Exam 1; review it if you don't remember the procedure.