13:20-15:50 at W831

Submission

Method of Submission

OCW-i

Convert/save your essay as a single PDF file and upload it at the respective page of OCW-i

Due date

Due date will be announced on OCW-i

Delayed Submission

Each submission is weighed according to half-value period of 10 days. That means if you submit a perfect answer 30 days after the due date, you will receive \(1/8\) the full points. In other words, you lose \(1 - 1/2^{1/10} \approx 6.7\text {%}\) points each day after the due date has passed. It is very wise to keep the due date.¹

Assignment

You can choose from two kinds of report courses: (1) Essay Course or (2) Compiler Construction Course.

Essay Course

The report being submitted should contain essays on both project bundled as a single PDF file.

Answers to questions may seem simple. If you think that they can be answered in a short paragraph please think deeply more. At least take time to understand the schematic definitions described in mincaml/overview.pdf. The implementation may give insight to those who are more implementation-oriented people. If you think enough you may discover more profound issues being questioned on you.

Project A

Answer either question. If you answer both questions the better answer will be chosen for your evaluation.

1. What’s \(\alpha\)-conversion for? What kind of problems we will see if \(\alpha\)-conversion were not applied? Find Min-Caml programs that give incorrect answers in absence of proper \(\alpha\)-conversion.

   Note: You may want to consider the reason why inline.ml refers to Alpha.g.

2. Are optimization modules interdependent? Yes, but in what way? Find a pair of optimization modules \(A\) and \(B\) such that for a program \(P\), \(B\) is effective when it is applied after \(A\):

   \[^\exists P. B(P) = P \text { but } B(A(P)) \not= A(P)\]

Project B

Answer either question. If you answer both questions the better answer will be chosen for your evaluation.

1. Explain in detail the mechanism described in Figure 16, mincaml/overview.pdf.

   • Compare this algorithm with two previous algorithms (Figure 14 and Figure 15). Present a Min-Caml code fragment examples that exhibits superiority of the last algorithm.

   • For the examples you gave above, estimate the number of make_closure, apply_direct, and apply_closure executed at runtime when the generated code is executed.

2. Explain how min-caml compiler is organized to achieve the goal of being a multi-targeted native code compiler. (A multi-targeted native code compiler can generate native code targeted for different CPU architectures.)

Compiler Construction Course

This is an open-ended assignment. You may modify the Min-Caml compiler in an interesting way.

• Enhancement of Min-Caml syntax (exception handling, more arithmetics, general pattern matching, polymorphism, …)

• Enhancement of Min-Caml runtime library (garbage colleciton, multithreading, graphics library, TCP/IP, regular expression, …).

• Improvement efficiency of the compiler.

• Improvement of the generated code.

• Creation of a backend for new machine architecture (Intel 64bits architecture, ARM, JVM, …)

Fork https://github.com/esumii/min-caml on GitHub and commit your contribution to your repository. The report being submitted should contain essays that describes the purpose, design, implementation of your work. Do not forget to include the URL of your GitHub repository!

Back to Top