Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!uunet!mcsun!hp4nl!dutrun!duteca!duteca8.uucp!hansm
From: hansm@duteca8.uucp (Hans Mulder)
Newsgroups: comp.lang.prolog
Subject: Shallow backtracking
Message-ID: <677@duteca.UUCP>
Date: 22 Nov 89 22:45:12 GMT
Sender: news@duteca
Reply-To: hansm@duteca8.uucp (Hans Mulder)
Organization: Delft University of Technology, Dept. of Electrical Engineering
Lines: 44


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