Questions 4-6 refer to the contents of HW2.lhs. Include two files in your submission: a text file with the answers to questions 1-3, and the completed HW2.lhs file.

1. (3 points)

Imagine you’re given an interpreter for C++ and asked to build a compiler from C++ to x86 machine code that implements the same semantics as the interpreter. What does it mean to claim your compiler is correct? How would you test this claim?

2. (4 points)

Consider the following Haskell code:

data Shape = Circle Double | Rect Double Double

area :: Shape -> Double

area (Circle radius) = 3.1415 * radius * radius

area (Rect width height) = width * height

Write out the full sequence of tokens in this program, in the order that they appear.

3. (8 points)

For each of the first four phases of a typical compiler pipeline (source input, lexical analysis, parsing, and semantic analysis), describe a small specific change that you could make to the code in question 2 that would trigger an error in that phase (and not any previous phase). Justify each answer. (You might find it helpful to copy the code into a Haskell file and load it in an interpreter to try to trigger errors there.)

4. (4 points)

Fill in the definitions of the Sing and (:.:) cases for the “check” function.

5. (2 points)

Fill in the definition of the “star” function.

6. (6 points)

Write at least three more regexes and at least two tests for each that demonstrate that “check” and “star” are working correctly.