[comp.lang.prolog] Shallow backtracking

hansm@duteca8.uucp (Hans Mulder) (11/23/89)

I am in need of some data points on shadow-register performance of PROLOG/WAM
programs to verify a calculation I made. The data I need is the frequency of
choice-point creations which encounter a valid shadow set, and the frequency of
fails (backtracks) which encounter an empty shadow set. If you have some data
or have a running systems which can generate this information for arbitrary
(large) benchmarks or know of someone who knows, please mail ? 
For completeness I describe my shadowing implementation below.

Thanks in advance.

Hans Mulder
hansm@duteca.tudelft.nl

Shadow-register implementation:
------------------------------

Let us assume two sets of WAM state registers: 
	STATE and SHADOW. 
STATE is always valid, but SHADOW has a FLAG associated with meaning: 
	VALID or INVALID. 
There are two operations which exchange information between STATE and SHADOW: 
	FREEZE, SHADOW := STATE; 
	MELT,   STATE := SHADOW. 
There are two operations which exchange information betwen SHADOW and memory:
	STORE,	memory := SHADOW;
	LOAD,	STATE := memory.

Choice point creation (try):
	if FLAG = VALID then begin
		STORE
		end
	FREEZE
	FLAG := VALID

Backtracking (fail):
	if FLAG = INVALID then begin
		LOAD
		FLAG := VALID
		end
	MELT

Choice point disposing (cut):
	FLAG := INVALID