Parameter Passing and Control Stack Management in Prolog Implementation Revisited

Machine (WAM), the most widely used abstract machine for Prolog implementation, arguments are passed through argument registers, and the information associated with procedure calls is stored in possibly two frames. Although accessing registers is faster than accessing memory, this scheme requires the argument registers to be saved and restored for backtracking and makes it difficult to implement full tail recursion elimination. These disadvantages may far outweigh the advantage in emulator-based implementations because registers are actually simulated by using memory. In this article, we reconsider the two crucial issues and describe a new abstract machine called ATOAM (yet Another Tree-Oriented Abstract Machine) . The ATOAM differs from the WAM mainly in that (1) arguments are passed directly into stack frames, (2) only one frame is used for each procedure call, and (3) procedures are translated into matching trees if possible, and clauses in each procedure are indexed on all input ar..