What's in a Trace: The Box Model Revisited

In this paper we investigate trace protocols of PROLOG programs. We present a precise mathematical specification of the box model for definite programs as it was informally introduced by Byrd. We also give a sketch of how to generalize this specification to normal logic programs. 1 Introduction The box model as introduced by Byrd (cf. [1, 2]) describes the process of finding an answer to a query wrt a logic program by means of a chronological trace protocol. This protocol contains entries for primitive events associated with the execution of PROLOG procedures. Basic events are call (a procedure is being entered), exit (a procedure was left signaling a success), redo (another solution to the call associated with the procedure is sought for), and fail (there is no (other) solution). Byrd only gives an informal account of how to visualize procedural aspects of the execution of PROLOG programs. He e.g. does not explicitly consider goals with variables and does not show how to keep track o..