Program Synthesis & Metaprogramming

By the end, you can

• Explain what homoiconicity means and describe the roles of `quote` and `eval`.
• Define metaprogram, object program, and reflection, and distinguish compile-time from runtime metaprogramming.
• Identify the multiple-evaluation and variable-capture traps in text macros, and explain how hygienic macros prevent them.
• Contrast introspection and intercession and name the trade-offs of runtime reflection.
• Describe how program synthesis inverts the compiler arrow, and state what "you describe the what, it finds the how" means.
• Map the two axes of the synthesis design space (specification style and search strategy) and give one example of each.
• Trace one iteration of the CEGIS loop and explain the correctness guarantee it provides.
• Explain sketching and SyGuS and state how each restricts the synthesis search space.
• Identify FlashFill as a programming-by-example system and name the two algorithmic ideas behind it.
• Explain why synthesis is undecidable in general and name the strategies used to make practical systems tractable.