Stratego -- Strategies for Program Transformation

After a strategy fails, variables that have been bound in matches should be unbound. This
is not supported by the current compilation scheme.
The following example illustrates the problem. The strategy `f`

should behave the same
as the choice between `g`

and `h`

.

module unbind-on-backtrack strategies f = (?(x, y); ?(x, x) <+ ?(y, x)); ![y,x] g = ?(x, y); ?(x, x); ![y,x] h = ?(y, x); ![y,x] main = <g <+ h> ("a", "b") => ["a", "b"] ; <f> ("a", "b") => ["a", "b"]

-- EelcoVisser - 22 Nov 2001

One way: only bind unbound variables when choice is committed: Consider

?F(x, y); s1 <+ s2and assume that x is bound before invocation of this strategy and that y is not (y value is looked for). transform this into

{y: ?F(x, y); s1; split(id,!y)}; ?(_,y); Fst <+ s2This has the same effect as the earlier expression (can this insight be made more efficient? turned into primitive operations?)

Note: this assume one can determine statically which variables are unbound when entering a choice. Although this scheme works when y is bound, it might turn out very expensive, because a failing match to y is discovered after doing s1.

-- EelcoVisser - 2000

Solution: Save (the status of) all variables that are bound in the left branch of a choice and restore after failure. Shouldn't be too difficult.

-- EelcoVisser - 22 Nov 2001

CategoryBugs