Warren's Abstract Machine: A Tutorial Reconstruction
Author : Hassan Aït-Kaci
, School of Computing Science
, Simon Fraser University
ISBN : 0-262-51058-8
Publisher : MIT Press
Publication Date : February 1999
Terms and Conditions:
|Hassan Aït-Kaci wrote:
|I now own the copyright and do not mind distributing it for free to anyone who wants to use it for non-commercial purposes.
In 1983, David H. D. Warren designed an abstract machine for the execution of Prolog consisting of a memory architecture and an instruction set. This design became known as the Warren Abstract Machine (WAM)
and has become the de facto standard for implementing Prolog
compilers. Warren described the WAM in a minimalist's style, making understanding very difficult for the average reader, even with a foreknowledge of Prolog's operations. Too much is left untold, and very little is justified in clear terms.
This monograph serves as a definitive tutorial on the WAM. It has been kept deliberately short and for reasons pertaining to the specificity of the topic covered, it was purposefully decided not to structure it as a real textbook, with abundant exercises and lengthy comments. The point is to make the WAM explicit as it was conceived by David H. D. Warren and to justify its workings to the reader with convincing, albeit informal, explanations. The few proposed exercises are meant more as an aid for understanding than as food for further thoughts.
The reader may find, at points, that some design decisions, clearly correct as they may be, appear arbitrarily chosen among potentially many other alternatives, some of which he or she might favor over what is described. Also, one may feel that this or that detail could be "simplified" in some local or global way. Regarding this, this book underscores two points: (1) it chooses to follow Warren's original design and terminology, describing what he did as faithfully as possible; and, (2) it warns against the casual thinking up of alterations that, although that may appear to be "smarter" from a local standpoint, will generally bear subtle global consequences interfering with other decisions or optimizations made elsewhere in the design. This being said, this book did depart in some marginal way from a few original WAM details. However, where this book's deviations from the original conception are proposed, an explicit mention will be made and a justification given.
It is expected that the reader already has a basic understanding of the operational semantics of Prolog in particular, of unification and backtracking. Nevertheless, to make this work also profitable to readers lacking this background, this book also provides a quick summary of the necessary Prolog notions in Appendix A. As for notation, this book implicitly uses the syntax of so-called Edinburgh Prolog, which is recalled in that appendix. Finally, Appendix B contains a recapitulation of all explicit definitions implementing the full WAM instruction set and its architecture so as to serve as a complete and concise summary.
View/Download Warren's Abstract Machine: A Tutorial Reconstruction