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):

A Gentle Introduction to Multi-stage Programming.
Taha, 2004
A Methodology for Generating Verified Combinatorial Circuits.
Kiselyov, Swadi and Taha, 2004

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.