How Does a Program Run? A Visual Model Based on Annotating Abstract Syntax Trees

摘要

How does a program run? A correct mental model relies on an approach that uses rewriting of programs into canonical forms or juggling with variables, assignment statements and stacks. The rewriting process is, however, quite cumbersome, and the stack method inadequate for understanding functional programming because of the presence of closures. For the last several years, we have been experimenting with a diagrammatic way of teaching how functional and imperative programs run. Programs are drawn as abstract syntax trees and evaluation is explained as an annotation of the tree. Evaluation may also include replicating parts of a tree (e.g., when doing a function call). Each programming language defines a particular evaluation model, and each evaluation model entails a particular way of annotating the tree. Using this method, we have taught many standard topics in the Principles of Programming Languages course: lexical scope, closures, recursion, parameter passing, variable assignment, and continuations. The annotation framework turns out to be an excellent preparation for students attempting to write full-blown interpreters, as done in several popular text books on programming languages. In this paper, we introduce this method of understanding how programming languages run and also report experimental results of using it in a class of approximately 200 students during the last year.