Posted on January 6, 2018 and last updated on February 15, 2018

# Compiler Construction Example Sheet III

1. Read the paper by Reynolds (1972) up to and including section seven. Later sections are delightful as well, but less relevant to the course. Section one can be skimmed, but it nicely sets up the scene. He talks about Algol a lot. For the unfamiliar it is the archetype of block structured programming languages e.g. C, but unlike C it has some high-order function support.

This is a great paper in computer science. Apart from historical value, it is also what the lecturer basis his interpreter upon. It will allow you to deeply understand how and why we bother with defunctionalisation & continuation passing style.

I strongly suggest you read it before you attempt the rest of the workset.

2. CPS and defunctionalisation exercise sheet (from the course site)

3. How is the state data type in interpreter 1 used? What is the difference between EXAMINE and COMPUTE constructors? Discuss in detail.

4. How can multiple source files can be compiled separately and linked together? How and which parts of ELF help you do that?

5. 2017/3/4

6. Write a program with the following specification on Linux outputting an ELF binary using x86_64 instruction set:

Input: An integer N (supplied as command line argument or standard input)

Output: N lines. In the first of which there is a * and in each subsequent lines there is an extra star.

Example:

Input: 5
Output:
*
**
***
****
*****


Reynolds, J.C., 1972. Interpreters for higher-order programming languages, in: Proceedings of the Acm Annual Conference-Volume 2. ACM, pp. 717–740.