#
Metaprogramming and Program Generation

One person's program is another program's data.

Tiark Rompf, Fall 2014, 3 credits

# Assignment 4

## Reading

Read the following two papers and write a short summary (0.5 pages for each):

Your summary should identify the main insights and scientific contribution of the paper: what is the key idea?
what is possible after the paper came out that wasn't possible before? (It is a good idea to skim some of
the related work to answer these questions).

Here is some additional advice,
by Kathryn S McKinley (thanks to Keith Chapman for the link).

Summaries are due before midnight on Monday, September 29 (submit per email to the instructor).

## Hacking

Clone the course repo
from GitHub.
Solutions are due before midnight on Wednesday, October 1
(submit per email to the instructor).

Follow instructions here to install LMS:
https://github.com/TiarkRompf/virtualization-lms-core

### The Posterchild of Staging

Specializing the `power`

function for a given exponent is the posterchild of staging.
The code template contains an implementation using LMS. Your tasks are:
- Implement a more clever algorithm that uses only log n multiplications
- Implement both algorithms in MetaOCaml, too (see here for download)
- how does the generated code differ between LMS and MetaOCaml?

### Generating FFT Circuits

The code template contains an (incomplete) FFT implementation using LMS. Finish the implementation
and add some test cases. See previous week's paper for details.