Play
How do programming languages show up in the world of play, in digital media such as video games and interactive fiction? Certainly, many digital media are programs, and programming languages are used to implement them, as well as to implement the engines that are used to build games.
In the first half of this chapter, we take a playful approach to exploring the relationship between programming languages and digital media, particularly interactive fiction. As a case study, we will use programming language syntax and semantics to model Twine4 , a code-free tool for developing interactive fiction. In doing so, we illustrate how broad the notion of a programming language can be, while also exploring how theoretical results about programming languages can be developed even for seemingly-exotic applications.
The second half of the chapter is more focused on the social context of interactive fiction, and how it can be used not only as entertainment, but how it can be used for communicating personal narratives in important contexts such as academic research3 .
Twine is an open-source, web-based environment for developing interactive fiction (such as text adventures and visual novels), first released in 2009. One of it selling points is that it allows new users to create games without programming, strictly using the graphical interface, but then to add more complicated functionality using HTML, Javascript, and CSS if and when they’re ready to. We will explore the core language, how to model its extensibility, and how Twine has been used.
Check your understanding: Play a short Twine game. What mathematical structure best explains the structure of a Twine game?
Answer: The basic structure of a Twine game is a directed graph.
Formal Semantics of Twine
We develop a formal operational semantics for Twine based around the understanding of Twine games as directed graphs, so that we explore theoretical properties of Twine games. To interpret a Twine game as a directed graph, we treat each passage of text as a node and each directed edge represents a link in the text from one passage to a successor passage. For example, if a node has two out-edges, then the player gets to pick which passage of the two passages of text comes next, and if the node has one out-edge, the player gets no choice. In serious Twine usage, it is essential that the language is extensible beyond basic graph structure, using HTML, Javascript, and CSS. However, that adds complexity to the formalism, so we begin with a non-extensible Twine and then add extensibility.
Non-Extensible Semantics
The runtime state of a Twine program consists of a program graph G and current state s. For use the variable m to range over these runtime states, short for “machine configuration”:
m ← (G, s)
where a graph G consists of vertices and edges
G ← (V, E)
and the start state identifies a vertex. Each vertex v ∈ V is a pair (n, p) of vertex identifier n and passage of text p. We write VN = {n | exists p such that (n,p) ∈ V} for the set of vertex names, then the start state satisfies s ∈ VN.
Each edge e ∈ E is a triple (u, v, l) where u ∈ VN is the source, v ∈ VN is the destination, and l ∈ String is a label identifying the edge. A state s is just a string s ∈ VN. We do not develop a full type system for Twine, but we make basic well-formedness assumption about programs, such as u,v ∈ VN for all edges in E.
The operational semantics of Twine will seek to explain which vertices are explored as the player plays the game, step-by-step. Our first observation is that because we execute the program step-by-step, we will need a small-step semantics as opposed to a big-step semantics. Secondly, we observe that the vertices explored depend on the player’s actions. Actions are indicated by edge labels l, and an entire playthrough of a Twine game with length k is indicated by a sequence l₁,...,l of k edge labels. We write ls for such a sequence of lables.
We write m ↦ₗ m’ to mean that m steps to m’ in one step along label l and m doneₗₛ to mean that m is done executing, where ls is the sequence of remaining actions to be executed. We write m ↦*ₗₛ, where ls is a sequence of k labels, to mean that m steps to m’ in k steps, each following the given edge label. Then, the semantics of Twine programs are defined by the following rules:
The judgement m doneₗₛ consists of a single rule: execution is done if no actions remain to be executed.
Rule DoneEmp
*
m doneₗₛ
(where ls is the empty sequence)
The judgement m ↦ₗ m’ has a single rule:
Rule StepOne
G = (V, E)
(s, s’, l) ∈ E
(G, s) ↦ₗ (G, s’)
and the judgement ↦* is defined in terms of the prior two judgements:
StepsDone
m doneₗₛ
m ↦*ₗₛ m
Rule StepsNext
m ↦ₗ m’
m’ ↦*ₗₛ m’’
m ↦*ₗ ₗₛ m
In rule StepsNext, the notation l ls means a sequence whose first element is l and whose remaining elements are collectively named ls.
Automata Theory
This computational model of Twine is surprisingly similar to a specific formal model of computation, which comes not from programming language theory but from automata theory (If you do not have prior exposure to automata theory, consulting standard texts may assist in reading this section)
Check your understanding: What formal model of computation are Twine programs closely related to?
Theorem: Not-extensible Twine is equivalent to deterministic finite automata (DFAs), once extended in the following fashion:
- DFAs divide their states into accepting and non-accepting states. The equivalent of an accepting state in a game is a victory state, i.e., a state in which the player has won the game. Thus we define a set of victory states.
- In DFAs, every action can be applied from every state, but this is typically not the case in Twine games. Thus, we define a new stuck state and, for every previously-undefined action, define it to go to the stuck state.
Proof: Exercise.
Once we establish the formal relationship between Twine games and DFAs, we can apply classic results from the theory of DFAs to establish surprisingly direct results about the behavior of Twine games.
Corollary: The number of moves in the shortest winning play is at most the number
of prompts in the game.
Proof: By the Pumping Lemma.
Corollary: If any winning play contains a cycle, then arbitrarily long winning plays exist.
Proof: By the Pumping Lemma.
Corollary: The set of all winning plays forms a regular language, i.e., there exists
a regular expression which detects all winning plays.
Proof: By definition of regular languages, which are the languages of DFAs.
These theoretical results were not designed into the fabric of Twine, and it is likely that most Twine developers never even consider these results while developing their Twine games. Rather, this overlap between Twine and DFAs is a happy coincidence for the Theorist.
Extensible Semantics
How should we formally define an extensible language? One of the easiest ways to do this is to treat the extensions as entirely abstract. All we know about extended Twine is that there exists some extra state (set ES) beyond the vertex names, and there exist some extended actions that can affect the extended state in arbitrary ways (write action(s,l) for the state resulting from label l on state s).
It now suffices to redefine the state s from a vertex identifier n to a pair (n,es) where es ∈ ES is extended state, and to redefine action sequences so that each l is an arbitrary string, not necessarily one that has an edge out of the current vertex. We need only add one new stepping rule
Rule StepExt
G=(V, E)
s=(n, es)
(n, n’, l) ∉ E (for all n’ ∈ VN)
(G,s) ↦ₗ (G, action(s,l))
and slightly modify rule StepOne
Rule StepOne
G = (V, E)
s = (n, es)
(n, n’, l) ∈ E
s’ = (n’, es)
(G,s) ↦ₗ (G, s’)
Twine in Human Subjects Research
This section discusses a series of papers which employed Twine in human subjects research, specifically research on the design of antiracist technology. The use of Twine was explored in this context as a tool to address the fundament question: “How should an HCI researcher or practitioner conduct design workshops where the participants will explore their lived experiences of interpersonal racism, while minimizing re-exposure to racial trauma?“. The answer chosen by the researchers was to explore those lived experiences through making fiction in Twine.
We explore three concepts in HCI that contextualize this work: participatory design (the broader class of research approaches into which the work fits), design fiction, and foundational fiction.
Participatory Design
In HCI research, Participatory Design2 (PD) refers to many design approaches that seek to democratize the research participants by allowing research participants to play a role in the design of the design artifact. In the least radical forms of PD, participants provide formative input to the design team, who then use it in their design process. In more radical forms of PD, the participants typically play a direct role in design and have direct co-ownership of the design outputs. Even radical PD typically maintains a distinction between designer (or researcher) and the research participants. For approaches that blur that distinction by elevating the participant, see “Research-Practice Partnerships”; for an approach that blurs the distinction by making the researcher the subject, see “Autoethnography,” both described in the Qualitative Studies chapter.
In the research discussed here, the role of PD is thus: the researchers’ goal in running workshops about lived experiences of interpersonal racism is to ultimately design software tools that would be used to support victims of racism in its aftermath.
The participants’ participate in the design of those tools, particularly by identifying what the function of that software should be in order to help them. The challenge is that to design technologies in response to any sort of intepersonal trauma, one must first relive and explore that trauma, which poses high emotional cost and risk of retraumatization even in an optimal environment, let alone a setting with strangers. The use of fiction is meant to provide mental distance from trauma and minimize re-exposure to trauma.
Design Fiction
Design Fiction1 is the use of fiction to explore future possibilities realities, typically to speculate on the role of the design artifact in those realities. Those realities could range from utopias to dystopias, and from social to technical. We could ask:
- What phone apps would be important in a post-climate-catastrophe world?
- What online democratic procedures would be best in a totally honest world?
- How could use wearables in new ways if we had perfect Internet everywhere on Earth?
- How should modern software be designed for communities that still have very limited access to modern computing hardware?
In Design Fiction, the role of the fiction in the design is quite direct. It creates a space for design exploration. It performs worldbuilding, then stops, leaving room for the designers to fill in new possibilities.
Foundational Fiction
Foundational fiction stands in contrast to Design Fiction. In contrast to Design Fiction, Foundational Fiction is about participants who exist in the here and now, so named because it provides a new foundation for discussions between the participants. Its key feature is that it provides the participants with greater agency about how much personal information they reveal during the interactions. Fiction always contains an element of its author, and the power of fiction here is that the participants can choose how much of themselves to put into their stories; whether they write autobiography or fantasy, the other participants might never even know the difference.
The goal of this foundational fiction is to improve sense of safety among participants, but sense of safety is difficult to measure directly. Instead, the researchers measured it indirectly, via another key objective. A major practical end of increasing felt safety was to increase participant engagement and creativity in proposing technological solutions. On these metrics, the authors deemed the work successful: the 26 participants generated 122 ideas, of which they produced storyboards of 20 (as a follow-up step). This metric highlights that Foundational Fiction, like Design Fiction, still plays an important role in generating design ideas, but its role is more indirect.
Why Twine?
The choice of Twine is contingent; the authors could have chosen another tool to complete their study. However, the fact that Twine does not require writing code was likely a major motivating factor. The goal of the research was to collect knowledge from lived experiences that are widely distributed throughout the populace, not concentrated only in programmers.
Classroom Activities
- Play a Twine game to warm up the class. If the class is small, play as a group and let students take turns suggesting moves for you to enter. If the class is large, students can play individually or in small groups
- Draw a small DFA, then translate it to Twine to demonstrate the connection between the two languages
- Visually demonstrate the Pumping Lemma by drawing cycles in a DFA
Exercises
- Write a short Twine game
- Convert the following DFA to Twine: q0 → a q0 | b q1 | c q2; q1 → a q2 | b q2 | c q0; q2 → a q2 | b q2 | c q2. In this notation, semicolons separate the definition of each state, vertical bars separate the rules for each character, and a character followed by a state indicates that the given character leads to the given state
- State the DFA-Twine correspondence theorem formally
- Prove the DFA-Twine correspondence theorem.
- Prove the corollaries of the DFA-Twine correspondence theorem
References
Theresa Tanenbaum (2014). Design fictional interactions: why HCI should care about stories. Interactions.
Clay Spinuzzi (2005). The methodology of participatory design. Technical Communication.
Alexandra To, Hillary Carey, Riya Shrivastava, Jessica Hammer, and Geoff Kaufman (2022). Interactive fiction provotypes for coping with interpersonal racism. CHI.
Interactive Fiction Technology Foundation (2023). Twine 2.6.2. twinery.org.