PARAMETER PASSING AND CONTROL STACK MANAGEMENT IN PROLOG IMPLEMENTATION REVISITED

Parameter passing and control stack management are two of the crucial issues in Prolog implementation. In the Warren Abstract Machine (WAM), the most widely used abstract machine for Prolog implementation, argu ments are passed through argument registers, and the information assoc iated with procedure calls is stored in possibly two frames. Although accessing registers is faster than accessing memory, this scheme requi res the argument registers to be saved and restored for backtracking a nd makes it difficult to implement full tail recursion elimination. Th ese disadvantages may far outweigh the advantage in emulator-based imp lementations because registers are actually simulated by using memory. In this article, we reconsider the two crucial issues and describe a new abstract machine caned ATOAM (yet Another Tree-Oriented Abstract M achine). The ATOAM differs from the WAM mainly in that (1) arguments a re passed directly into stack frames, (2) only one frame is used for e ach procedure call, and (3) procedures are translated into matching tr ees if possible, and clauses in each procedure are indexed on all inpu t arguments. The above-mentioned inefficiencies of the WAM do not exis t in the ATOAM because backtracking requires less bookkeeping operatio ns, and tail recursion can be handled in most cases like a loop statem ent in procedural languages. An ATOAM-emulator-based Prolog system-cal led B-Prolog has been implemented, which is available through anonymou s ftp from ftp.kyutech.ac.jp (131.206.1.101) in the directory pub/Lang uage/prolog. B-Prolog is comparable in performance with and can someti mes be significantly faster than emulated SICStus-Prolog. By measuring the numbers of memory and register references made in both systems, w e found that passing arguments in stack is no worse than passing argum ents in registers even if accessing memory is four times as expensive as accessing registers.