Efficiently Implementing Pure Prolog or: Not "YAWAM"

High performance hardware and software implementations of Prolog are now being developed by many people, using the Warren Abstract Machine (or "WAM") [Warr83]. We have designed a somewhat different machine which supports a more powerful language than Prolog, featuring: - efficiency similar to the WAM for sequential programs, - tail recursion optimization (TRO) [Warr86], - sound negation, - pseudo-parallelism (co-routining) with full backtracking, - dynamic optimization of clause order, - efficiency {\em if-then-else} ("shallow" backtracking), - simple, regular instruction set designed for easily optimized compilation, - efficient memory utilization, - integrated object-oriented virtual memory, - predicates as first class objects. Our design gives the programmer more flexibility in designing programs than is provided by standard Prolog, yet it retains the efficiency of more limited designs.