The Choose-Your-Own-Adventure Calculus

Tomas Petricek, Jan Liam Verter, Mikoláš Fromm

Unpublished Draft.

Some of the most remarkable results in mathematics reveal connections between different branches of the discipline. The aim of this paper is to point out a modest, but still remarkable, similarity between a range of different interactive programming systems. In many programming systems, the user can interactively construct a program by repeatedly triggering some kind of completion mechanism and choosing one of the offered options. This is the case with code editors for object-oriented languages (choosing object members), data exploration environments (choosing an applicable transformation), but also theorem provers (choosing an applicable tactic) and structure editors (choosing a grammar rule).

In this paper, we formally capture the essence of this interaction pattern through a small formal model called the choose-your-own-adventure calculus. We show how a wide range of different systems fits the model. Looking at the examples through a common perspective reveals multiple subtle differences. To formally capture those, we characterise basic properties of choose-your-own-adventure systems, resembling those from other areas of programming language research, including correctness, completeness and uniqueness. We further show how the choose-your-own-adventure calculus can be used as the basis for formally studying more advanced interaction patterns including mixed-initiative interaction, AI-based programming assistants and programming by demonstration.

We strongly believe that interaction with programming systems deserves as much attention as the underlying programming languages. Our work is one step in this direction. It provides a way of talking about commonalities and subtle differences between multiple interactive programming systems and enables a transfer of ideas between interactive systems from very different domains.

Draft and more information

• Download paper draft (PDF)
• Check out the earlier blog post on the topic

Comments are welcome!

If you have any comments, suggestions or related ideas, I'll be happy to hear from you! Send me an email at tomas@tomasp.net or get in touch via Twitter at @tomaspetricek.