Skip to content
Open access

Program Sketching with Types & Examples

TL;DR

Techniques for finding contradictions between tests and polymorphic types, and for proving the absence of such contradictions are developed in the context of interactive program synthesis, a form of programming from specifications.

Abstract

Computer programs describe instructions for the computer to follow, and the computer will happily follow those instructions without asking questions. Humans, however, tend to make mistakes, leading the computer to do the wrong thing. To try and avoid these situations, programmers often write specifications. These describe some expectation of the programmer about the program in question. This thesis focuses on two common types of specifications: tests and types. Tests describe which output the programmer expects for specific inputs. Types express the programmer’s expectation about the structure of the data handled by the program. The main reason for writing a specification is that the computer can check automatically whether the program matches the programmer’s expectation. It is often encouraged to write specifications before writing the program: it forces the programmer to think about their expectations, and it allows the computer to take those expectations into account when helping the programmer along. In practice, however, specifications are often not used to their full potential. For example, the computer may fail to recognize that (1) the programmer has introduced a mistake while the program cannot yet be executed, (2) the specification contains a contradiction, or (3) there is a way to fill in gaps in the program so that it meets the specification. In this thesis, I develop techniques to get more out of specifications. These techniques are developed in the context of interactive program synthesis, a form of programming from specifications. In Chapter 2, I explore how bidirectional evaluation can be used to find mistakes in incomplete programs that are generated during program synthesis. In Chapter 3, I develop techniques for finding contradictions between tests and polymorphic types, and for proving the absence of such contradictions. In Chapter 4, I expand on these techniques and explore how to fill in gaps in a program so that it matches the specification. In Chapter 5, I look at different scenarios in which the techniques developed in this thesis can be applied.

Read PDF

Similar papers

#small language model Book Open access Oct 2026

The Choose-Your-Own-Adventure Calculus

The paper shows that programming language theory can be used to study not just languages, but also rich interactive programming systems, and argues that such systems deserve at least as much attention as languages.

T. Petříček, J. Verter, Mikolas Fromm · 0 citations
Review Oct 2026

Passages

Donald E. Knuth's Literate Programming is only the second Knuth book I have reviewed here, but his sensibility and example have informed many Passages columns, including those on Brooks' The Mythical Man- Month and Martin Gardner's recreational mathematics columns. Literate Programming, in the title, explains why that...

Alex Groce · 0 citations
#artificial intelligence Preprint Oct 2026

Compiling Expert Procedures into Verified Programs: When a Small Model Is Enough

In procedural tool-use domains, how much of the gap between base models is procedure rather than capability? We build an explicit program from a teacher's traces and run it in front of unchanged small models, including an 8B model. The construction, PLVR , takes the reasoning traces of a teacher, Kimi-K3, clusters thei...

Vishvesh Bhat, Asad Aali, Muhammad Ahmed Mohsin · 1 citation
Open access Sep 2026

A Mathematical Theory of Correct Computation

In 1970, Dana Scott proposed his highly influential “mathematical theory of computation” to define the relationship between the text of a program and what the program computes (or denotes)—the “semantics” of the program. Scott used a complete lattice based on the “information ordering”, with the bottom element represen...

L. Naish, B. Pope, H. Søndergaard · 0 citations

How Researchers Use and Verify AI Coding Assistants: Tasks and Validation Practices in Scientific Programming

Validating AI contributions to scientific code rested largely on individual judgment, outside shared infrastructure for testing or review, and interfaces could support task-appropriate evaluation rather than leave it to the user.

Gabrielle O'Brien, Reed Milewicz, Nasir U. Eisty · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.