On teaching programming with nondeterminism

Giora Alexandron, Michal Armoni, Michal Gordon, David HarelWiPSCE 2013 · DOI

TL;DR

This paper argues that teaching "operative non-determinism" (ND) – the kind found in concurrent and distributed systems – can be more effectively achieved by integrating it into programming courses using visual languages like Live Sequence Charts (LSC). Their study with high school students suggests this approach leads to a significant understanding of operative ND, enabling students to create and execute complex ND programs.

What Problem Does This Paper Address?

Non-determinism (ND) is a fundamental concept in computer science, appearing in areas like automata theory and programming languages. Traditionally, students are introduced to the ND found in automata theory, which is notoriously difficult to teach and learn. However, the prevalence of ND in modern systems, particularly in concurrent and distributed computing, necessitates a better pedagogical approach. The authors identify a gap in effectively teaching "operative non-determinism" – the type that arises in programming languages and concurrent systems, characterized by "true don't care" where multiple execution paths are equally valid. This type of ND is crucial for understanding modern computing but is often overlooked or poorly taught.

Methods

The authors propose and evaluate a teaching method that integrates operative ND into a programming course using Live Sequence Charts (LSC). LSC is a visual specification language for reactive systems that supports "scenario-based programming." The teaching approach involves theoretical lectures followed by hands-on lab experience, culminating in group projects.

To assess student understanding, they employed a two-dimensional taxonomy combining Bloom's taxonomy (focusing on "Applying" and "Creating" levels) and the SOLO taxonomy (focusing on "Unistructural," "Multistructural," and "Relational" levels). Data was collected through student projects, exam questions, class notes, and post-interviews. Both quantitative analysis of exam answers and qualitative analysis of projects and interviews were conducted.

Datasets

Not discussed in the paper. The study used student projects and exam answers from a high school computer science course.

Key Insights and Ideas

  • Two Flavors of ND: The paper clearly distinguishes between ND in formal languages/automata (where success criteria exist) and "operative ND" in programming/concurrent systems (where multiple paths are equally valid).
  • LSC as a Pedagogical Tool: Live Sequence Charts (LSC) are presented as an effective visual language for teaching operative ND. Its scenario-based approach and inherent non-determinism make it a natural fit.
  • Constructionism in Action: The teaching method aligns with constructionist principles, where students learn by building and experimenting with systems.
  • ND as an Abstraction: Students learned to use operative ND as an abstraction mechanism, allowing them to ignore unnecessary implementation details like execution order, thereby reducing cognitive load.
  • Challenges with Default ND: While LSC's default non-determinism is beneficial, students can struggle when needing to remove ND to achieve a specific deterministic outcome, especially in highly concurrent scenarios. This highlights a potential difficulty in transitioning from a non-deterministic default to deterministic control.

Key Results

Quantitative Findings: * Students demonstrated satisfactory achievement across assessed categories. * Applying/Unistructural: 83% (N=26) * Applying/Multistructural: 76% (N=18) * Creating/Multistructural: 100% (N=10)

Qualitative Findings: * Students could mentally simulate non-deterministic systems at a local or system-wide level. * They were able to create non-deterministic systems, often using ND as an abstraction to hide implementation details. * Challenges arose when students needed to eliminate ND to achieve a specific deterministic behavior, particularly when dealing with multiple concurrent charts.

Limitations and Future Work

Limitations: * The study was conducted with a relatively small group of 12th-grade high school students. * The "zipper principle" curriculum structure meant some courses were shortened, potentially impacting prior knowledge. * The elective nature of some exam questions led to varying numbers of answers per category, potentially introducing bias.

Future Work: The authors suggest that operative ND can and should be taught at the high school and pre-graduate levels. This can be achieved by integrating it into existing concurrent and asynchronous programming courses rather than creating a separate topic. They believe this approach, supported by their findings, promotes a better understanding of this crucial concept.

Summary updated

BibTeX
@inproceedings{alexandron2013teaching,
  author = {Giora Alexandron and Michal Armoni and Michal Gordon and David Harel},
  title = {{On teaching programming with nondeterminism}},
  booktitle = {WiPSCE},
  year = {2013},
  doi = {10.1145/2532748.2532762},
}
Figure