Skip to content
#small language model Book Open access

The Choose-Your-Own-Adventure Calculus

Oct 2026 · Proceedings of the 2026 ACM SIGPLAN International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software · 0 citations · 62 references

TL;DR

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.

Abstract

In many programming systems, the user can interactively construct a program by repeatedly triggering a completion mechanism and choosing one of the offered options. This is the case with code editors for object-oriented languages (choosing a member), data exploration environments (choosing a transformation), but also with theorem provers (choosing a tactic) and structure editors (choosing a grammar~rule). We capture the essence of this interaction pattern through a small formal model called the choose-your-own-adventure calculus. The model serves three roles. First, it reveals subtle differences between instances of the interaction pattern. Second, it enables transfer of interaction techniques across different domains by describing them abstractly in terms of the calculus. Examples include mixed-initiative interaction, AI assistants and programming by demonstration. Third, it lets us characterise desirable properties of a programming system, including correctness, completeness and uniqueness. More generally, the paper shows that programming language theory can be used to study not just languages, but also rich interactive programming systems. We argue that such systems deserve at least as much attention as languages.

Read PDF

Similar papers

Sep 2026

Compiling with the Sequent Calculus

This work is a continuation, and generalization, of Andrew Appel's landmark work on “Compiling with Continuations”, but instead of natural-deduction-based languages like the lambda calculus, it uses sequent-calculus-inspired languages throughout all intermediate stages.

Marius Müller, David Binder, Marco Tzschentke et al. · 0 citations
Book Open access Oct 2026

Assignment Has Never Existed: Programs Have Always Been Difference Equations

The assignment statement x = x + 1 is a difference equation with its time index removed. Program verification research has shown that restoring the index simplifies reasoning, but only specification languages have incorporated this idea. We present , a programming language that uses difference equations with a time ind...

A. Sane · 0 citations
Book Aug 2026

Tikka: An Interpreter and Debugger for a Pedagogical Subset of Haskell

Tikka is introduced, an interpreter for a carefully-selected subset of Haskell with concise, beginner-friendly error messages, evaluation tracing, and a bespoke IDE.

Alex Hobbs, Alex Dixon · 0 citations
Open access

Program Sketching with Types & Examples

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.

N. Mulleners · 0 citations

Related blog posts

Microsoft Research Blog Nov 16, 2026

TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient

AI coding agents are increasingly help developers fix bugs and build features largely on their own, but every interaction with their models consumes tokens. In each session, an agent sends instructions, tool descriptions, and session history to its model. Most efforts to reduce this cost focus on individual tasks. Yet developers return to the same […] The post TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient appeared first on Microsoft Research.

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