Typed Self-Applicable Meta-Programming

PhD Thesis by Matt Brown, published 2017


Self-applicable meta-programming has its roots in the early days of computer science. Two early examples were published in 1936: the universal Turing machine, and a self-interpreter for the λ-calculus. These were major advances in computability theory, but self-application has a long history of practical uses as well. Many languages have self-interpreters or self-hosting compilers. Others support self-applicable meta-programming as a general-purpose technique that enables elegant solutions to many problems. Until now, these techniques have been incompatible with static type checking, which has many benefits of its own. In this thesis I present techniques for practical self-applicable meta-programming for statically typed languages.