CW 471

Bart Demoen and Phuong-Lan Nguyen
Suspension frames on the WAM heap

Abstract

A suspension encapsulates everything needed to execute a piece of code many times in the same context: the need for this feature exists in constraint solver programming, where (part of) a predicate checking the satisfiability of a set of a constraints needs to be re-executed every time the domain of a concerned variable changes. Traditional extensions of the WAM support a heap term and meta-call based approach to this issue. The most efficient implementation of suspensions in the context of Prolog exists in B-Prolog. B-Prolog is based on the TOAM and suspension frames are put in the execution stack. They are notorioulsy cheap to re-enter. It is clear that the WAM could be adapted to allow suspension frames on the local stack. However, it is worth exploring a scheme that puts suspension frames on the WAM global stack (the heap). We describe in detail the few additions to a traditional WAM system to achieve this. Together with attributed variables that is enough to compile B-Prolog's Action Rules to almost plain Prolog. We have enhanced hProlog with the required features to support suspension frames on the heap. We compare the performance of our Action Rules implementation with B-Prolog on a set of benchmarks previously used by the author of Action Rules.