Proper Treatment 正當作法/ Light seminar: Programs as data
2008-08-17 19:19

Fall 2007, Organizer: Chung-chieh Shan
Thursdays 3:20–4:40pm, Hill 482

Computer science is all about treating programs as data and vice versa. This light seminar will focus on programs that generate programs. They let us build more flexible languages in which to write shorter programs that run faster.


The course number is 16:198:500:03. The index number is 28631.

Each participant is required to

Please consult ahead of time with the organizer about the last two responsibilities.

Evolving calendar

9/6: Introduction

9/13: MetaOCaml practice

A side note on MetaOCaml installation: With the help of Fei, I finally managed to install the MetaOCaml on my Windows machine. Here is how to do that: After you install Cygwin, copy the directory of MetaOCaml into your user directory under “home” in the Cygwin directory you just created. Then just follow the instructions from the file “INSTALL-META”. Simple and straight forward. The only problem I had is that my username contains a space in it and that caused additional trouble because the directory seems unrecognizable with a space in the name. So if you run into the same problem try to switch a user to do it that problem will just disappear. -Jun

Below is the “self-modifying code” from today. -Ken

type closed_int_code = { cl : 'a. ('a, int) code }
let c = ref { cl = .<1>. }
let rec alt () =
  let x = .!((!c).cl) in
    if x = 1 then
      (c := { cl = .<2>. };
       alt ())
      (c := { cl = .<1>. };
       alt ())

9/20: Program generation

Neil D. Jones and Arne J. Glenstrup. 2002. Program generation, termination, and binding-time analysis. In Proceedings of GPCE 2002: 1st ACM conference on generative programming and component engineering, ed. Don S. Batory, Charles Consel, and Walid Taha, 1–31. Lecture Notes in Computer Science 2487, Berlin: Springer.

9/27–10/4: Tag elimination

As an exercise, please make a tweak to the code of:

Jacques Carette, Oleg Kiselyov, and Chung-chieh Shan. 2007. Finally tagless, partially evaluated: Tagless staged interpreters for simpler typed languages. Submitted.

10/11: A reflective interpreter

Stanley Jefferson and Daniel P. Friedman. 1996. A simple reflective interpreter. Lisp and Symbolic Computation 9(2-3):181-202.

10/18: Partial evaluation and reflection

The code is available online. Please play with it.

Kenichi Asai, Satoshi Matsuoka, and Akinori Yonezawa. 1996. Duplication and partial evaluation: For a better understanding of reflective languages. Lisp and Symbolic Computation 9(2–3):203–241.

10/25: Statistical models

Bernd Fischer and Johann Schumann. 2003. AutoBayes: A system for generating data analysis programs from statistical models. Journal of Functional Programming 13(3):483–508.


Rob will present:

G. W. Hamilton. 2007. Distillation: Extracting the essence of programs. In PEPM, 61–70.


Jun will present:

Jonathan Ragan-Kelley, Charlie Kilpatrick, Brian W. Smith, Doug Epps, Paul Green, Christophe Hery, and Frédo Durand. 2007. The Lightspeed automatic interactive lighting preview system. In SIGGRAPH.


Fei will present:

Dongxi Liu, Zhenjiang Hu, and Masato Takeichi. 2007. Bidirectional interpretation of XQuery. In PEPM, 21–30.


We will discuss:

Gabriele Keller, Hugh Chaffey-Millar, Manuel M. T. Chakravarty, Don Stewart, and Christopher Barner-Kowollik. 2008. Specialising simulator generators for high-performance Monte-Carlo methods. In PADL.

11/22–11/29: Thanksgiving hiatus


Pradip will present:

Tetsuo Yokoyama and Robert Glück. 2007. A reversible programming language and its invertible self-interpreter. In PEPM, 144–153.


If people are interested, we will discuss:

Morten Heine B. Sørensen, Robert Glück, and Neil D. Jones. 1994. Towards unifying deforestation, supercompilation, partial evaluation, and generalized partial computation. In ESOP, 485–500.

Other reading material

Partial evaluation

John Hatcliff. 1998. Foundations of partial evaluation and program specialization. Course notes.

Multi-stage programming

Jacques Carette and Oleg Kiselyov. To appear. Multi-stage programming with functors and monads: eliminating abstraction overhead from generic code. Science of Computer Programming.


Donald Davidson. 1979. Quotation. Theory and Decision 11(1):27–40.

Herman Cappelen and Ernest Lepore. 2005. Quotation. Stanford Encyclopedia of Philosophy.

See also

Verbs vs. Definitions in FORTH: A Language for Interactive Computing