Notional Machines and Programming Language Semantics in Education
( 07. Jul – 12. Jul, 2019 )
- Mark J. Guzdial (University of Michigan - Ann Arbor, US)
- Shriram Krishnamurthi (Brown University - Providence, US)
- Juha Sorva (Aalto University, FI)
- Jan Vahrenhold (Universität Münster, DE)
- Michael Gerke (für wissenschaftliche Fragen)
- Susanne Bach-Bernhard (für administrative Fragen)
- Capturing and Characterising Notional Machines : article in ITiCSE '20: Proceedings of the 2020 ACM Conference on Innovation and Technology in Computer Science Education - Fincher, Sally; Miller, Craig S.; Donaldson, Peter; Mühling, Andreas; Hellas, Arto; Boulay, Benedict du; Jeuring, Johan; Hauswirth, Matthias; Hermans, Felienne; Lewis, Colleen; Pearce, Janice L.; Petersen, Andrew - New York : ACM, 2020. - pp. 502–503.
- Engage Against the Machine : Rise of the Notional Machines as Effective Pedagogical Devices : article in ITiCSE '20 : Proceedings of the 2020 ACM Conference on Innovation and Technology in Computer Science Education - Dickson, Paul E.; Brown, Neil Christopher Charles; Becker, Brett A. - New York : ACM, 2020. - Pages 159–165.
- Purpose-first Programming : A Programming Learning Approach for Learners who Care Most About What Code Achieves : article in ICER '20 : Proceedings of the 2020 ACM Conference on International Computing Education Research - Cunningham, Kathryn - New York : ACM, 2020. - Pages 348–349.
A formal semantics of a language serves many purposes. It can help debug the language’s design, be used to prove type soundness, and guide optimizers to confirm that their work is correctness-preserving. In addition, it also serves as a comprehension tool. Semanticists assume that programmers can use a semantics to understand how a particular program will behave without being forced to resort to deconstructing the output from a black-box evaluator. Indeed, different semantic models vary in what aspects of program behavior they highlight and suppress.
Unfortunately, we know relatively little about how non-experts, such as students, actually employ a semantics. Which models are they able to grasp? How useful are these as they explain or debug programs? How does their use of models evolve with the kinds of programs they write? And does studying these kinds of questions yield any new insights into forms of semantics?
In contrast, formal semantics are evaluated by several criteria: full abstraction, adequacy, soundness and completeness, faithfulness to an underlying implementation, and so on. However, two dimensions have not been considered at all: utility to correcting misunderstandings, and usability by learners. Considering these will result in a better understanding of the role of semantics in learning. It will also identify and categorize semantic misunderstandings that learners suffer from. It may also result in insights that lead to new styles of semantics.
This Dagstuhl Seminar intends to bridge this gap. It will bring together representatives of the two communities—who usually travel in non-intersecting circles—to enable mutual understanding and cross-pollination. The programming languages community uses mathematics and focuses on formal results; the CER community uses social science methods and focuses on the impact on humans. Neither is superior: both are needed to arrive at a comprehensive solution to creating tools for learning.
The main aim of the seminar is to try to create a “notional machines” community by combining expertise in computing education and formal semantics. The seminar will educate each group on the methods and results of the other. It will then attempt to synthesize knowledge between the two, trying to identify solutions from semantics that aid education, and identify open problems.
Towards this aim, the seminar has several specific goals:
- Bring together key members of these different communities, with an eye towards people who are open-minded and receptive to the perspective of the other.
- Create tutorial sessions to educate participants on the existing knowledge, as well as methods, of each side.
- Enable Computing Education Research members to present open problems and look for solutions in semantics.
- Try to formulate interesting examples and test problems that can be used to evaluate results.
- Dagstuhl trip report: learning and teaching programming language semantics
Blog entry by Andy J. Ko in Bits and Behaviour on Medium, July 12, 2019
- Tag Archive: #dagstuhlnm
Live blog entries by Felienne, July 8 - 12, 2018
- What Help Should We Provide to Students Learning to Program?
Blog entry by Mark Guzdial in BLOG@CACM on Communications of the ACM, July 14, 2019
A formal semantics is often intended as a tool to comprehend the behavior of a language or other system. Semanticists assume, for instance, that programmers can use a semantics to understand how a particular program will behave without being forced to resort to deconstructing the output from a black-box evaluator. Indeed, different semantic models vary in what aspects of program behavior they highlight and suppress.
Every semantics has an intended audience. Formal semantics typically assume a readership with high computing or mathematical sophistication. These therefore make them inappropriate for students new to computing. What forms of description of behavior would be useful to them? In computing education, the term notional machine is often used to refer to a behavior description that is accessibble to beginners.
Our meeting therefore focused on what we know, and what we need to learn, about notional machines. In particular, we studied and discussed:
- Different formulations of notional machines for a variety of languages.
- The distinction between a general description of behavior, independent of a specific program, and the explication of behavior of a specific program. We argued for the value of having both the general and the specific, since learners might need to shift between the two.
- The different forms that a notional machine can take, and their styles: [MARK fill in]
- The many analogies employed in notional machines, with their respective strengths and weaknesses.
- The different forms of theories that apply to generating and understanding notional machines, including cognitive and social.
- Analogies to notional machines in other domains, from models in physics to rulebooks in board games.
We accomplished most of our stated goals: to bring together the semantics and education communities (though with much greater representation from the latter than the former); to create tutorials to educate each on the knowledge and methods of the other; and to formulate interesting examples. While there did not appear to be many long-standing "open questions", and there was not enough time to engage in editing Wikipedia, groups did organized community-wide activities (such as surveys to be conducted at upcoming conferences) and large banks of research questions (which are concrete and valuable outcomes that we had not anticipated). In sum, we believe the seminar successfully accomplished its overall stated goals.
- Thomas Ball (Microsoft Research - Redmond, US) [dblp]
- Titus Barik (Microsoft Research - Redmond, US) [dblp]
- Brett A. Becker (University College Dublin, IE) [dblp]
- Neil Brown (King's College London, GB) [dblp]
- Franziska Carstens (Universität Münster, DE)
- Luke Church (University of Cambridge, GB) [dblp]
- Kathryn Cunningham (University of Michigan - Ann Arbor, US) [dblp]
- Paul Denny (University of Auckland, NZ) [dblp]
- Brian Dorn (University of Nebraska - Omaha, US) [dblp]
- Benedict du Boulay (University of Sussex - Brighton, GB) [dblp]
- Rodrigo Duran (Aalto University, FI) [dblp]
- Barbara Ericson (University of Michigan - Ann Arbor, US) [dblp]
- Sally Fincher (University of Kent - Canterbury, GB) [dblp]
- Kathi Fisler (Brown University - Providence, US) [dblp]
- Robert L. Goldstone (Indiana University - Bloomington, US) [dblp]
- Mark J. Guzdial (University of Michigan - Ann Arbor, US) [dblp]
- Reiner Hähnle (TU Darmstadt, DE) [dblp]
- Matthias Hauswirth (University of Lugano, CH) [dblp]
- Arto Hellas (University of Helsinki, FI) [dblp]
- Geoffrey L. Herman (University of Illinois - Urbana Champaign, US) [dblp]
- Felienne Hermans (Leiden University, NL) [dblp]
- Matthew C. Jadud (Bates College - Lewiston, US) [dblp]
- Johan Jeuring (Utrecht University, NL) [dblp]
- Antti-Juhani Kaijanaho (University of Jyväskylä, FI) [dblp]
- Philipp Kather (Universität Münster, DE) [dblp]
- A. J. Ko (University of Washington - Seattle, US) [dblp]
- Shriram Krishnamurthi (Brown University - Providence, US) [dblp]
- Thomas D. LaToza (George Mason University - Fairfax, US) [dblp]
- Colleen Lewis (Harvey Mudd College - Claremont, US) [dblp]
- Elena Machkasova (University of Minnesota - Morris, US) [dblp]
- Craig Miller (DePaul University - Chicago, US) [dblp]
- Andreas Mühling (Universität Kiel, DE) [dblp]
- Markus Müller-Olm (Universität Münster, DE) [dblp]
- Greg Nelson (University of Washington - Seattle, US) [dblp]
- Andrew Petersen (University of Toronto, CA) [dblp]
- Joseph Gibbs Politz (UC - San Diego, US) [dblp]
- André L. Santos (University Institute of Lisbon, PT) [dblp]
- Carsten Schulte (Universität Paderborn, DE) [dblp]
- Otto Seppälä (Aalto University, FI) [dblp]
- R. Benjamin Shapiro (University of Colorado Boulder, US) [dblp]
- Juha Sorva (Aalto University, FI) [dblp]
- Anya Tafliovich (University of Toronto, CA) [dblp]
- Jan Vahrenhold (Universität Münster, DE) [dblp]
- J. Ángel Velázquez Iturbide (Universidad Rey Juan Carlos - Madrid, ES) [dblp]
- Eugene Wallingford (University of Northern Iowa - Cedar Falls, US) [dblp]
- David Weintrop (University of Maryland - College Park, US) [dblp]
- Steven A. Wolfman (University of British Columbia - Vancouver, CA) [dblp]
- programming languages / compiler
- semantics / formal methods
- society / human-computer interaction
- formal semantics
- notional machines
- computing education research