Visualizing evaluation in applicative languages

Reviewer: Patrick Miller

A new way of visualizing the semantics of the eval and apply operations within an applicative language (LISP) is presented. Understanding the workings of these operations is crucial to understanding the entire LISP computation process, but they are initially difficult for students to grasp. The new notation is known as “EvalTrace,” to distinguish it from simple execution traces. The paper supports the use of graphical indicators (arrows) to represent evaluation and application within function scopes. Three types of arrows are used: the evaluation arrow (thin), the application arrow (thick), and the scoping arrow (double). This notation differs from the way the contour model represents frames, and it is more suitable for a textual listing. The authors note that EvalTrace is closer to Plotkin's operational semantics notation. The paper gives complete examples with illustrations for nested applications, evaluation of global variables, function closures, and macro expansion. The examples are helpful in understanding the notation, but no means are provided to automatically generate it. Support is provided, however, for typesetting it with L A T E X macros available from the authors (note that the FTP address given in the paper is obsolete). This notation would be difficult to generate by hand and is most suitable for typesetting. It is evidently intended for textbook writers or for classroom examples.