Back to search

Rice University

Reasoning About Multi-stage Programs

Abstract

dc:description.abstract

Multi-stage programming (MSP) is a style of writing program generators---programs which generate programs---supported by special annotations that direct construction, combination, and execution of object programs. Various researchers have shown MSP to be effective in writing efficient programs without sacrificing genericity. However, correctness proofs of such programs have so far received limited attention, and approaches and challenges for that task have been largely unexplored. In this thesis, I establish formal equational properties of the multi-stage lambda calculus and related proof techniques, as well as results that delineate the intricacies of multi-stage languages that one must be aware of. In particular, I settle three basic questions that naturally arise when verifying multi-stage functional programs. Firstly, can adding staging MSP to a language compromise the interchangeability of terms that held in the original language? Unfortunately it can, and more care is needed to reason about terms with free variables. Secondly, staging annotations, as the term ``annotations'' suggests, are often thought to be orthogonal to the behavior of a program, but when is this formally guaranteed to be the case? I give termination conditions that characterize when this guarantee holds. Finally, do multi-stage languages satisfy extensional facts, for example that functions agreeing on all arguments are equivalent? I develop a sound and complete notion of applicative bisimulation, which can establish not only extensionality but, in principle, any other valid program equivalence as well. These results improve our general understanding of staging and enable us to prove the correctness of complicated multi-stage programs.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy
Level thesis:degree_level
Doctoral
Discipline thesis:degree_discipline
Engineering
Department thesis:degree_department
Computer Science
Grantor
Rice University
Year dc:date.issued
2013

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Inoue, Jun
Advisor dc:contributor.advisor
  • Cartwright, Robert S.
Committee members dc:contributor.committeemember
  • Taha, Walid
  • Sarkar, Vivek
  • O'Malley, Marcia K.

Subjects

dc:subject × 5

Rights

dc:rights
Statement dc:rights
  • Copyright is held by the author, unless otherwise indicated. Permission to reuse, publish, or reproduce the work beyond the bounds of fair use or other exemptions to copyright law must be obtained from the copyright holder.
Language dc:language.iso
eng

Identifiers

dc:identifier.*
Dc Identifier Citation
Inoue, Jun. "Reasoning About Multi-stage Programs." (2013) Diss., Rice University. <a href="https://hdl.handle.net/1911/71663">https://hdl.handle.net/1911/71663</a>.
Dc Identifier Other
123456789/ETD-2012-12-93

Chain of custody

source
Harvested from
Rice University
Base URL
repository.rice.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Inoue, Jun. Reasoning About Multi-stage Programs. Doctoral thesis, Rice University, 2013. https://hdl.handle.net/1911/71663