Multi Stage Programming Tutorial

GPCE Tutorial #3 (GP3)

"Multi-stage Programming in MetaOCaml" by Walid Taha, Rice University

Date: Oct 23, morning

Abstract

Multi-stage programming is a paradigm for writing generic programs that do not pay a runtime overhead. The key underlying technology is program generation. In addition, languages designed to support this paradigm (such as MetaOCaml) help the programmer avoid many of the difficulties that are traditionally encountered in developing program generators. This tutorial will introduce you to the basics of this paradigm as well as of programming in MetaOCaml. Numerous examples will be used to illustrate the practice of multi-stage programming.

Duration

Half day tutorial.

Level / required experience

The tutorial level is introductory (requires almost no experience with any specific programming language). Familiarity with OCaml would be helpful, but is not essential. Familiarity with a genericity and higher-order typing would be useful, but is not necessary.

Outline

Each session is 1.5 hours.

• Session 1:
  • Why MSP programming
  • Small example
  • Collecting performance measurements
  • Two larger examples
  • Binding time improvements
  • Differences between byte code and native code settings

• Session 2:
  • Staged interpreter -- a killer app for MSP
  • Effective staging of interpreters with error handling
  • Tag elimination
  • Indexed types
  • Controlled in-lining
  • Staging dynamic programming problems
  • Staging and the Fast Fourier Transform and comparison with FFTW
  • Summary and pointers to the literature

Bio of speaker

Walid Taha lead the development of the semantics of staged computation, type systems for multi-stage languages, and implementing multi-stage languages like MetaOCaml and MetaOCaml Concoqtion. Currently, he leads the Resource-aware Programming (RAP) research group at Rice University, Houston, TX. He is the principal investigator on a number of NSF, Texas ATP, and SRC research grants and contracts on various aspects of resource aware programming. Taha is actively involved in development of both the embedded software and generative programming research communities.