• [SIGPX10] Dagstuhl Seminar Report #22231 "Theories of Programming" - Japanese video report by Jun Kato for the 10th SIGPX

Mature scientific disciplines are characterized by their theories, synthesizing what is known about phenomena into forms which generate falsifiable predictions about the world. In computer science, the role of synthesizing ideas has largely been through formalisms that describe how programs compute. However, just as important are scientific theories about how programmers write these programs. For example, software engineering research has increasingly begun gathering data, through observations, surveys, interviews, and analysis of artifacts, about the nature of programming work and the challenges developers face, and evaluating novel programming tools through controlled experiments with software developers. Computer science education and human-computer interaction research has done similar work, but for people with different levels of experience and ages learning to write programs. But data from such empirical studies is often left isolated, rather than combined into useful theories which explain all of the empirical results. This lack of theory makes it harder to predict in which contexts programming languages, tools, and pedagogy will actually help people successfully write and learn to create software.

Computer science needs scientific theories that synthesize what we believe to be true about programming and offer falsifiable predictions. Whether or not a theory is ultimately found to be consistent with evidence or discarded, theories offer a clear statement about our current understanding, helping us in prioritizing studies, generalizing study results from individual empirical results to more general understanding of phenomena, and offering the ability to design tools in ways that are consistent with current knowledge.

Dagstuhl Seminar 22231 on Theories of Programming explored the creation and synthesis of scientific theories which describe the relationship between developers and code within programming and social activities. The seminar brought together researchers from software engineering, human-computer interaction, programming languages, and computer science education to exchange ideas about potential theories of programming. We identified and proposed theories that arose from many sources: untested but strongly-held beliefs, anecdotal observations, assumptions deeply embedded in the design of languages and tools, reviews of empirical evidence on programming, and applications of existing theories from psychology and related areas. Our aim was to bridge this gulf: formulating deeply-held beliefs into theories which are empirically testable and synthesizing empirical findings in ways that make predictions about programming tools and languages.

To achieve this aim, the seminar had three specific goals. 1) Bring together researchers with diverse expertise to find shared understanding. 2) Create a body of theories which make testable predictions about the effects of programming tools, languages, and pedagogy on developer behavior in specific contexts. 3) Propose future activities which can advance the use of theories, including identifying studies to conduct to test theories and ways to use theories to communicate research findings to industry.

During this seminar, a few short talks first reviewed the nature, creation, and use of theories as well as existing evidence about developer behavior during programming activities. The main activity of the seminar was working in small groups to sketch new theories of programming.

Seminar Overview

The seminar was divided into the following sessions across four days in June 2022:

• Tuesday: welcome, what is theory, describing theories, critiquing theories
• Wednesday: brainstorming unexplained programming phenomena, sketching theories, getting feedback on theories, and refining theories
• Thursday: presenting theory sketches, discussing ways of sharing theories, and skeptically examining whether developing theories of programming is really worth the time
• Friday: reflecting on takeaways and departure

The seminar was organized by Thomas Latoza, Amy J. Ko, Dag Sjoberg, David Shepherd, and Anita Sarma. Anita later had to drop out, leaving Thomas, Amy, Dag, and David as the four organizers who were able to attend.

What is Theory?

The goal of this opening session was to find common ground on what theory was. To achieve this, each organizer gave short presentations related to theories.

Thomas identified how researchers used theories to generate falsifiable predictions about the world. He described common characteristics of theories as abstract, explanatory, relevant, and operationalizable. An example of a theory of programming he provided was how violating constraints cause defects or reduces code quality.

Amy described an interpretivist framing of theories, where theories were cultural and experience-based. Some theories were folk theories (e.g. code is magic, Not Invented Here, and spaces vs tabs for white space). Some theories were personal, such as programming as common sense machines and tinkering towards correctness. Other theories came from research communities such as ICSE. For example, a theory of programming is that we can copy and adapt code from another location in a program to fix bugs.

Dag drew guidelines between what was and was not a theory. He identified multiple examples of what were not theories: scientific laws were not theories because they were missing the "why;" trivial statements were also not theories. The building blocks of theories included constructs, propositions, explanations, and scope. Theories can help us explain surprising empirical results, while empirical results can help us support or refute certain theories. Finally, Dag noted how premature theorizing is likely to be wrong, but can still be useful.

David emphasized the importance of keeping theories practical. He defined a relationship from theorems to corollaries to examples and applications. He provided an example of using different representations in music for different use cases and users.

In open discussions and breakout groups, attendees identified additional nuances to theories. We noted how it is useful for theories to enable ease of communication or shared understanding. But by defining a vocabulary, theories can also limit the scope of explanation. We can also use theories to understand what we observe or to justify interventions. Finally, there was discussion about creating theories inductively, deductively, and/or abductively.

Common themes that arose from discussion include how theories are seldom used to justify the design of programming languages and tools, and how programming is a social endeavor and drawing upon social science research (e.g. psychology) can support theory building.

Expressing Theories using a Theory Template

The goal of this session was to try to express theories using a theory template developed by the organizers. While the goal of this template was to support the creation of new theories, attendees used it to describe existing theories for this session. Attendees broke into five groups to attempt to apply the theory template to the following existing theories of programming:

• Asking and answering questions [1]
• Program comprehension as fact finding [2]
• Leaky abstractions [3]
• Information hiding [4]
• Theory of programming instruction [5]

After considering feedback from attendees, organizers revised the theory template. The revised theory template's section headers and helper text are as follows:

1. Theory's name: Choose a name that is memorable, short, and descriptive.
2. Summary: In a few sentences, summarize the phenomena, constructs, relationships, and a concrete example, hypothesis, and study.
3. Contributors: Who has contributed to this theory? Add your name here.
4. Phenomena: What programming phenomena is your theory trying to explain? And in what scope (people, expertise, contexts, tools, etc.)? This description should just describe what is being explained, should not offer an explanation; that below. (``Programming'' includes any and all interactions between people and code, in any context (e.g., software engineering, learning, play, productivity, science, and all of the activities involved in creating programs, including requirements, architecture, implementation, verification, monitoring, and more).
5. Prior Work: What prior work offers an explanation of this phenomena, or might help generate an explanation of this phenomena? For the purposes of the seminar, this does not need to be complete, but a complete description of this theory would have an extensive literature review covering theories that inspired this theory, as well as conflicting theories.
6. Concepts: Describe the key concepts of the theory and some concrete examples of them, building upon the phenomena above. These might be variables, processes, people, aspects of people, structures, contexts or other phenomena that are essential to the theory's account of the phenomena. Note: concepts should be descriptions of ideas that give some structure and precision to describing the phenomena, not operationalizations or measurements - those belong in example hypotheses and/or studies.
7. Relationships and Mechanisms: Using the constructs described above, explain the causality of how the phenomena works. What causes what and how? Provide a few concrete examples to illustrate the idea.
8. Example Hypotheses: What testable claims do the constructs, relationships, and mechanisms imply?
9. Example Studies: What are existing or envisioned example study methods that might investigate the hypotheses above? How might the concepts be operationalized and measured? Describe details about populations, samples, tasks, contexts, tools, observations. Remember that studies can involve many forms of observation and data, both qualitative and quantitative and even design contributions. Studies do not have to be feasible to be proposed and can vary in scope, from single-study sized methods to long-term research agendas that might explore a theory over many years and many projects.
10. Corollaries: What follows from this theory, if true? Provide potential implications, concrete or otherwise.

Unexplained phenomenon

After spending the first day discussing what theories were and applying a theory template, the goal of the second day was to identify unexplained phenomena related to programming and apply theories to explain them. After an informal voting process, attendees created groups to develop theories around the following phenomena:

• Debugging
• Types
• Neurodiversity in programming
• Data programming
• Code examples
• Developer tools
• Learning effects from code analysis

Groups spent all of Wednesday developing theories by filling out the theory template and then getting feedback from members of other groups. They then iterated and created presentations. See included abstracts of talks for descriptions of each presentation.

Sharing Theories

On Thursday after the presentations, attendees had discussions about how to share theories of programming to broader audiences. Many ideas included written dissemination, such as publishing research, writing books, creating a wiki, adding to reviewer guidelines, creating a website, defining syllabi for reading groups, speaking on podcasts, and posting on social media sites. Other ideas featured opportunities for further interaction, such as workshops, special interest groups, demonstrations of theories for practitioners, and stickers/flair for engagement at conferences. Other ideas focused on incentive structures, such as creating a ``best new theory'' award at conferences.

Group-wide discussions about sharing theories identified some structural barriers and opportunities. A barrier to broader theory creation and/or use is that most computing researchers do not have much training in theories. Workshops, reading groups, or changes to undergraduate or graduate level coursework could help address this. Another structural barrier is that most conferences lack instructions about theory. Adding instructions in paper calls and reviewer instructions as well as ``theory shepherds'' could help address this systemic barrier.

Do we really need theories?

The final session for Thursday was critically reflective about whether programming actually required theories. Given this session occurred after lunch on the final full day, this session got silly. After splitting into groups to discuss, groups shared eclectic presentations to reflect their discussions:

• a colorful whiteboard diagram about pros and cons of theories (Fig.1)
• Another whiteboard diagram about whether to use theory (Fig. 2)
• A list of bullets about challenges of making changes in publishing
• An humorous improv skit about a conference Q&A session on a theory paper.

Reflections on the week

The final session of this seminar asked attendees to reflect on the seminar as a whole. Attendees identified some high-level takeaways:

Attendees found theories useful for helping understand why things (e.g. languages or tools) do or do not work. They also found theories helpful for differentiating between how we think people work and how they actually work.

Attendees also felt that the engagement of computing researchers with theories of programming was often limited by the lack of interest and/or lack of expertise. Interdisciplinary research can help create the gestalt of expertise required to create theories of programming, but narrow conference and journal scopes often make this difficult. Specifically, many computing researchers lack expertise in empirical evaluations, making it difficult to develop rigorous evidence that is often foundational to theory building. Furthermore, much training in empirical evaluations focuses on lab settings, whereas most programming happens "in the wild."

Multiple attendees also felt that theories were more implicitly prevalent in computing research than was explicitly discussed. Some conversation focused on "lower case 't"' theories, or theories that we not fully formalized, but provided use and explanation. Many attendees felt that theories implicitly existing in papers, but were unaware of explanations into this work.

A concluding consensus was that theories of programming have existed in the background. Through explicit engagement and discourse, this Dagstuhl Seminar could serve as a catalyst to augment existing theories and craft new ones.

References

1. Sillito, Jonathan, Gail C. Murphy, and Kris De Volder. “Asking and Answering Questions during a Programming Change Task.” IEEE Transactions on Software Engineering 34, no. 4 (July 2008): 434–51. https://doi.org/10.1109/TSE.2008.26.
2. LaToza, Thomas D., David Garlan, James D. Herbsleb, and Brad A. Myers. “Program Comprehension as Fact Finding.” In Proceedings of the the 6th Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on The Foundations of Software Engineering, 361–70. ESEC-FSE ’07. New York, NY, USA: Association for Computing Machinery, 2007. https://doi.org/10.1145/1287624.1287675.
3. Spolsky, Joel. “The Law of Leaky Abstractions.” Joel on Software, November 11, 2002. https://www.joelonsoftware.com/2002/11/11/the-law-of-leaky-abstractions/.
4. Parnas, David L. “On the criteria to be used in decomposing systems into modules.” Pioneers and their contributions to software engineering. Springer, Berlin, Heidelberg, 1972. 479-498.
5. Xie, Benjamin, Dastyni Loksa, Greg L. Nelson, Matthew J. Davidson, Dongsheng Dong, Harrison Kwik, Alex Hui Tan, Leanne Hwa, Min Li, and Amy J. Ko. “A Theory of Instruction for Introductory Programming Skills.” Computer Science Education, January 25, 2019, 1–49. https://doi.org/10.1080/08993408.2019.1565235.

Creative Commons BY 4.0

Benjamin Xie, Amy Ko, Thomas D. LaToza, David C. Shepherd, and Dag Sjøberg