Discussions related to Visual Prolog
Martin Meyer
VIP Member
Posts: 328
Joined: 14 Nov 2002 0:01

Reverting changes on backtracking

Unread post by Martin Meyer »

Hello Thomas,

I am searching for a way of reverting a destructive change on backtracking which is made in a predicate with mode procedure.

This naive try does not work:

Code: Select all

class facts     state : string := "initial".   class facts     stack : string* := [].   class predicates     changeState : (string Update). clauses     changeState(Update) :-         stack := [state | stack],         state := Update.             changeState(_Update) :-         [State | RestStack] == stack,         state := State,         stack := RestStack,         fail.       %Raises:         %  The predicate 'main::changeState/1 (i)',         %  which is declared as 'procedure', is actually 'multi'   clauses     run() :-         stdIO::write("1) ", state, "\n"),         changeState("changed"),         stdIO::write("2) ", state, "\n"),         fail.       run() :-         stdIO::write("3) ", state, "\n").
However that way it seems to work:

Code: Select all

class facts     state : string := "initial".   domains     predicate = (string).   class predicates     changeState : (string Update). clauses     changeState(Update) :-         ChangeState = uncheckedConvert(predicate, changeState_mt),         ChangeState(Update).   class facts     stack : string* := [].   class predicates     changeState_mt : (string Update) multi. clauses     changeState_mt(Update) :-         stack := [state | stack],         state := Update.       changeState_mt(_Update) :-         [State | RestStack] == stack,         state := State,         stack := RestStack,         fail.   clauses     run() :-         stdIO::write("1) ", state, "\n"),         changeState("changed"),         stdIO::write("2) ", state, "\n"),         fail.       run() :-         stdIO::write("3) ", state, "\n").
It outputs:

1) initial
2) changed
3) initial


My question now is whether uses of uncheckedConvert like the above are legal in general. Is it always OK to unchecked convert a multi predicate, which has exactly one solution, to a procedure predicate?

Obviously the construction violates the rule that a predicate with mode procedure cannot return with an active backtrack point in it. Maybe above trick to circumvent the rule works out sometimes, but causes problems in other situations. Are there certain restrictions, which when respected, guarantee that the uncheckedConvert will not lead to exceptions or unwanted effects?
Regards Martin
User avatar
Thomas Linder Puls
VIP Member
Posts: 1398
Joined: 28 Feb 2000 0:01

Re: Reverting changes on backtracking

Unread post by Thomas Linder Puls »

The answer is no to everything.

Just try to add this little extra layer:

Code: Select all

class predicates     changeStateEx : (string Update). clauses     changeStateEx(Update) :-         changeState(Update),         core::nothing().
Calling that predicate will show that your attempt is not sound.

The problem is that a multi predicate leaves things on the stack to return to when backtracking. A procedure on the other hand leaves the stack empty. In your little example the stack happens to stay untouched, so even though it is not kept alive it just happens to contain what you need. But since the code surrounding a procedure call doesn't expect to keep the stack alive it will start using it and then your back tracking doesn't make sense anymore.

In the code above the call to nothing will ruin the part of the call stack that your backtracking relies on.
Regards Thomas Linder Puls
PDC
Martin Meyer
VIP Member
Posts: 328
Joined: 14 Nov 2002 0:01

Re: Reverting changes on backtracking

Unread post by Martin Meyer »

Thank you Thomas for the info!

To treat the problem I am using a class named reversion (see it in attached Example.zip). Using that class the example looks like:

Code: Select all

class facts     state : string := "initial".   class facts     stack : string* := [].   class predicates     changeState : (string Update). clauses     changeState(Update) :-         stack := [state | stack],         state := Update,         reversion::addUndoAction(             {  :-                 [State | RestStack] == stack,                 state := State,                 stack := RestStack             }).   clauses     run() :-         reversion::backTrackPoint(),         stdIO::write("1) ", state, "\n"),         changeState("changed"),         stdIO::write("2) ", state, "\n"),         fail.       run() :-         stdIO::write("3) ", state, "\n").
The huge drawback of the class reversion however is that the programmer must identify relevant backtrack point positions in the code and insert calls to predicate backTrackPoint there. The predicate backTrackPoint performs the undo-actions which revert the destructive changes. My wish for future VIP versions would be that you invent a way that these calls can be omitted.
Attachments
Example.zip
Reversion Example
(7.49 KiB) Downloaded 1588 times
Last edited by Martin Meyer on 19 Oct 2022 16:19, edited 1 time in total.
Regards Martin
Martin Meyer
VIP Member
Posts: 328
Joined: 14 Nov 2002 0:01

Re: Reverting changes on backtracking

Unread post by Martin Meyer »

Add-on: The example can be simplified. When using the reversion class, the stack fact is not needed:

Code: Select all

class facts     state : string := "initial".   class predicates     changeState : (string Update). clauses     changeState(Update) :-         State = state,         state := Update,         reversion::addUndoAction({  :- state := State }).   clauses     run() :-         reversion::backTrackPoint(),         stdIO::write("1) ", state, "\n"),         changeState("changed"),         stdIO::write("2) ", state, "\n"),         fail.       run() :-         stdIO::write("3) ", state, "\n").
Regards Martin
User avatar
Thomas Linder Puls
VIP Member
Posts: 1398
Joined: 28 Feb 2000 0:01

Re: Reverting changes on backtracking

Unread post by Thomas Linder Puls »

We have something similar in the type analysis in the compiler. It is somewhat irritating, but compared to all the other things the type analysis must deal with, this has been relatively unproblematic :wink: .
Regards Thomas Linder Puls
PDC
User avatar
Thomas Linder Puls
VIP Member
Posts: 1398
Joined: 28 Feb 2000 0:01

Re: Reverting changes on backtracking

Unread post by Thomas Linder Puls »

I should perhaps add that in the type analysis we are "happy" that the unbinding it not closely tied to backtracking. We register "type analysis backtrack points" in specific places where it we pursuit a certain type-choice. In such a pursuit we may do lots of regular backtracking which should not necessarily undo type bindings we have made.

One such scenario is the following:

Code: Select all

clauses     something(T, _S) = conflict(C) :-         bind(T, <somevalue>),         C = tryGetConflict().       something(_, S) = S.
We bind T in the first clause, but no matter whether we backtrack to the second clause or not we do not want to unbind T again. However, on some outer level a "conflict" may lead to pursuing another choice for something, and then T may need to be unbound.

So the binding and unbinding has to do with some domain specific backtrack points rather than the internal Prolog backtrack points.
Regards Thomas Linder Puls
PDC
Martin Meyer
VIP Member
Posts: 328
Joined: 14 Nov 2002 0:01

Re: Reverting changes on backtracking

Unread post by Martin Meyer »

I have a class named stateManager in which the undo functionality is also not tied to backtracking (see attached Example2.zip). Both classes reversion and stateManager are about turning an ephemeral data structure into a persistent data structure.

The reversion class only supports accessing the newest version of the data; thus the data structures produced through class reversion do not even meet the level of 'partially' persistence.

Whereas data structures produced via class stateManager are fully persistent. In Example2 arrayM is turned into a fully persistent data structure whereby the performance characteristics of ephemeral arrays are almost preserved. All operations in the persistent array will perform same fast as in arrayM in terms of the big O notation, provided one does not alternatingly access versions of the array with growing distance (for example versions 1 2 1 3 1 4 1 5 and so on).

It surprises me that you do not synchronize the unbinding in the compiler's type analysis with the backtracking. The purpose I intended for the not-tied-to-backtracking class stateManager is different from solving logic equations. I made it to provide support for undo/redo buttons.

I have a type analysis case -in a much easier and smaller scenario of course- in a predicate which tries to determine the simple type of a lambda expression in a typing context according to the typing rules of the simply typed lambda calculus.

The type analysis in my predicate relies on the unification of reference variables. The reference variables are introduced through a class named ref. Class ref in turn relies on the reversion class. The backtracking of the reversion class (via predicate reversion::backTrackPoint) must be sychronized to regular backtracking as told before.

Anyway, backtracking is a distinctive and outstanding feature of Visual Prolog and Prolog in general and I believe, it would be beneficial if undoing destructive changes could be easily tied to backtracking. The most rigorous way would probably be, to relax modes procedure and determ from "no backtrack point" to "one resp. max. one solution". Alternative ways, which generate less effort to implement, might exist.
Attachments
Example2.zip
(16.74 KiB) Downloaded 1644 times
Regards Martin
Martin Meyer
VIP Member
Posts: 328
Joined: 14 Nov 2002 0:01

Re: Reverting changes on backtracking

Unread post by Martin Meyer »

To be exact about the performance characteristics of the persistent array construction compared to the ephemeral arrayM: The characteristics are preserved in amortized costs. The cost to move n states forwards is in O(n), the cost to move backwards n states is also in O(n). Thus amortized, every single move in the persistent array construction is in O(1) - which is the same cost as a move in arrayM.
Regards Martin
Martin Meyer
VIP Member
Posts: 328
Joined: 14 Nov 2002 0:01

Re: Reverting changes on backtracking

Unread post by Martin Meyer »

Without adding "amortized", the performance claim is not correct. Because, when placing the undo calls right behind the regular backtrack points, a single failure can trigger many undo calls. Thus the backtracking initiated by a single failure executes in O(n) in the persistent array construction. But for the usual ephemeral array all backtracking is of course in O(1), because there is nothing to be done about the array in backtracking.
Regards Martin
Martin Meyer
VIP Member
Posts: 328
Joined: 14 Nov 2002 0:01

Re: Reverting changes on backtracking

Unread post by Martin Meyer »

I have been seeking for a way which solves the problem, but does not produce too much effort to implement. Can this one win your sympathy? Please check:

In backtrack points VIP is pushing some data on the stack. Let me call that data a backtrack-frame. Add one extra pointer to the backtrack-frame. The pointer is initialized to null.

When VIP backtracks, it first has to test whether the extra pointer is null. In the standard case, when it is null, VIP proceeds with backtracking just same as it does now. Thus this extra pointer will not hurt VIP's effiency much.

If the pointer is not null, it points to the first node of a chain of actions. The chain ends by a null pointer:

Code: Select all

interface node     open core   predicates     execute : ().   end interface   %--- class node : node     open core   constructors     newFirstNode : (node OldFirstNode, predicate Action).   end class node   %--- implement node     open core   facts     nextNode : node.     action : predicate.   clauses     newFirstNode(NextNode, Action) :-         nextNode := NextNode,         action := Action.   clauses     execute() :-         try             action()         catch _Exception do             succeed %treat the exception the same way as in object finalizers         end try,         if uncheckedConvert(pointer, nextNode) <> null then             nextNode:execute()         end if.   end implement node
Before VIP continues the backtracking in the usual way, it processes the chain by calling the first node's execute predicate.

To let the user add a new first node to the chain of the last backtrack-frame, invent a 1st language predicate like for example:

Code: Select all

onFailureDo : (predicate Action)
If there is no last backtrack-frame, i.e. no active backtrack point exists, onFailureDo does nothing. The special case that the user calls again predicate onFailureDo in predicate Action, should not rise a problem and does not need to be treated specially.

So far that could be one way. Or, consider this variant:

Currently the compiler issues an error message when a procedure wants to return with an active backtrack point to a clause that always fails (as in the initial naive try). Instead of the error message 'abstract' the call to the failure-clause and insert it to the before mentioned chain like in following example.

Say the predicate would be:

Code: Select all

class predicates     myChange : (string Something, unsigned SomeReturnCode [out]).   clauses     myChange(Something, SomeReturnCode) :-         update(Something, SomeReturnCode).             myChange(Something, _SomeReturnCode) :-         undo(Something),         fail.
Let VIP call only the first clause of myChange - it is a standard procedure, which leaves no backtrack points.

Put the call to the second clause in braces, so that it becomes an anonymous predicate which has captured the input variable Something (the output variable SomeReturnCode is of no relevance since the clause fails):

Code: Select all

Action = {  :- myChange(Something, _SomeReturnCode) /* 2nd clause */ }
To insert Action into the chain of the latest backtrack-frame, place a call to node::newFirstNode after the call to the first clause of myChange.

In the special case that the call to the first clause of myChange ends by raising an exception, the call to node::newFirstNode will not be reached.

From the view of the user that variant will look like mode procedure has been relaxed from "no backtrack point" to "exactly one solution". A new 1st language predicate is not needed in this variant.
Regards Martin
User avatar
Thomas Linder Puls
VIP Member
Posts: 1398
Joined: 28 Feb 2000 0:01

Re: Reverting changes on backtracking

Unread post by Thomas Linder Puls »

You absolutely have my sympathy :-).
I have already considered such a solution. I agree that it wouldn't take much effort to implement and wouldn't impose a serious overhead.

The problem I see is that this is not really a language feature; it is rather a kind of hook into the runtime system. The semantics is described in terms of backtracking, which is in some sense an implementation detail for the logical/declarative "or".

Such a feature will impose a restriction on the runtime system. We have recently made a very large change/extension of the backtracking mechanism in the runtime system (the most radical change in my time). But there is no conflict in that extension: registering on-backtrack-actions would also be possible in that context.

I will consider it, but I am not sure if we will implement it.
Regards Thomas Linder Puls
PDC
Martin Meyer
VIP Member
Posts: 328
Joined: 14 Nov 2002 0:01

Re: Reverting changes on backtracking

Unread post by Martin Meyer »

:D Thank you, Thomas !
Regards Martin
User avatar
Thomas Linder Puls
VIP Member
Posts: 1398
Joined: 28 Feb 2000 0:01

Re: Reverting changes on backtracking

Unread post by Thomas Linder Puls »

I have considered this once more and I (partially) accept the problem.

But for a number of reasons, I do not think that this is a good feature after all.

First of all, I only partially accept the problem. The problem as I see it is that we want to implement some "domain specific backtracking". We have a "target" problem-space in which we want to do searches and backtracking. The aim is to use Visual Prologs search and backtracking to implement the domain specific search and backtracking.

I accept that this is a good aim, I do however think it is a bad idea to tie the two things one-to-one to each other, because the backtracking in Visual Prolog is used for a number of other things in any regular code you write.

Consider for example this little piece of code:

Code: Select all

foreach T in <something> do     handle(T) end foreach
Any "bindings" made in handle(T) will be reverted, because internally foreach will backtrack. Also consider this code:

Code: Select all

if 7 = handle(T) then write("It was 7") end if.
Here bindings made in handle(T) will also be unbound if the test fails, and they will be lost if the test succeed, because unbind actions will be registered on the backtrack point that is made for the if-then-else and it will either be invoked or cut-away.

This code will work differently:

Code: Select all

V = handle(T), if 7 = V then write("It was 7") end if.
But the compiler could/would assume that both these behaved the same (i.e., one could safely be rewritten to the other). I do not think this is a compiler problem right now; but who will remember such non-language semantics restrictions.

Also consider code like this:

Code: Select all

S = openStream(), try     handle(T),     canFail() finally    S:close() end try
Assuming that canFail is determ a backtrackpoint will be created by the try-finally and any "unbind" actions will be registered on that backtrack point, but that backtrack point will be cut away if canFail succeeds, so any unbind actions made in handle(T) will be lost.

The overall problem is that backtracking is used for a number of things, and it is not at all certain that your actions should be registered on the current backtrack point, the logically correct backtrack point may be somewhat down in the chain.

Secondly, (as illustrated above) the feature imposes restrictions both on language and runtime system which does not really relate to the main semantics of the language. I.e., because this would be a hook into the runtime system rather than a genuine language feature.

Thirdly, I doubt that this feature will be used by anyone except you. The problem is that even though somebody else encounter the problem they will not know where to look for the solution. They will have to locate a single "special" predicate among everything and realize that it can (perhaps) solve their problem. Because that predicate will be the only visible impact on the entire system.

Therefore, I think that it is all in all better to explicitly mark create domain specific backtrack (i.e., domains specific unbind points) using a predicate like your reversion::backTrackPoint().
Regards Thomas Linder Puls
PDC
Martin Meyer
VIP Member
Posts: 328
Joined: 14 Nov 2002 0:01

Re: Reverting changes on backtracking

Unread post by Martin Meyer »

Thank you again for the detailed answer. If I had to pay you for all the time, you have invested over the years in answering my posts, I would be a poor man.


I understand that the proposed construction is a hook into the runtime system rather than a genuine language feature and the if-rewrite you presented is not sound with the runtime system hook. Before the rewrite could be done safely, the compiler had to check that no undo-actions are added in predicate handle.

Currently the rewrite is also not sound unconditionally. It is necessary to first check that predicate handle has mode procedure. Thus implementing the undo-on-backtrack feature would take to add another precondition to that rewrite.

The feature could but also be implemented without a back-hook: The idea to accomplish that is in short, to let the compiler internally insert the same calls, which I am now adding manually, when I emulate the feature via class reversion. If that way would however take you less implementation effort, is questionable.


It is the correct behavior that any "bindings" made in the foreach loop in handle(T) will be reverted at the end of each pass. If it is intended to preserve some result from the loop, it can be done in the usual well known ways.

One way is to instead set up a list, maybe by a list comprehension construct, recursively process the list, and thereby build the result. Alternatively, to preserve results in the foreach loop, results can be stored in a fact, a varM, or else object.

When the value of a (emulated) reference variable shall be preserved over backtracking, then instead of the original value a deep copy of it must be stored, in which free variables are replaced with fresh variables. That is, because bindings in the original variable could be reverted in backtracking. Moreover the value would change later on when any of the free variables becomes bound.

Thus the foreach construct would work just as usual with the undo-on-backtrack feature. I do not see a problem there.


In an implementation of the undo-on-backtrack feature the try-catch-finally construct (incl. all variants of it) must get a special treatment. In the reversion class I tried to address the issue in the description of predicate undoUpTo. I suppose, if you implemented the feature, you would need to treat try-catch-finally similarly:

Code: Select all

        S = openStream(),         StackMark = reversion::createUndoStackMark(),         try             handle(T),             canFail()         finally             reversion::undoUpTo(StackMark),             S:close()         end try
Or incl. catching exceptions:

Code: Select all

        S = openStream(),         StackMark = reversion::createUndoStackMark(),         try             handle(T),             canFailOrRaiseException()         catch TraceId do             reversion::undoUpTo(StackMark),             handleException(TraceId)         finally             reversion::undoUpTo(StackMark),             S:close()         end try

Basically there exist two sensible backtrack strategies. 1st is, to undo an action automatically on the return to that backtrack point, which had been current, when the action has been done. And 2nd is, to backtrack 'manually' via explicit undo-commands.

Your argument "it is not at all certain that actions should be registered on the current backtrack point, the logically correct backtrack point may be somewhat down in the chain" is not followed by VIP itself (neither by any other Prolog, I suppose). VIP exposes the 1st strategy to users. It is not possible in VIP to let the bindings made in a unification be reverted (or say 'forgotten') some backtrack points down in the chain.

I think, none of the strategies is better than the other in general. Both have their use cases. It is absolutely perfect, that VIP itself employs the 1st strategy. The concept of reference variables also requires to apply the 1st strategy, because the backtracking of the reference variables has to go exactly with VIP's backtracking.

But in other use cases, the 2nd strategy might be the better choice, like you told about the type analysis of the compiler. Depending on the case I am using class stateManger (i.e. 2nd strategy) or the reversion class (i.e. 1st strategy - but it suffers from the calls to predicate backTrackPoint).

B.t.w. some hybrid of 1st and 2nd strategy does not seem appropriate. I guess, the program flow of a hybrid strategy would confuse the programmer (at least me) more than it would benefit.


You may be correct, "this feature will not be used by anyone except me". But people would use it indirectly, if they are supplied with classes, which internally making use of the feature.

A class, which emulates reference variables, would probably find its users, provided it does not need inserting backTrackPoint calls. Introducing reference variables via a class instead of a built-in feature has the advantage that their internal data structure, which is some kind of tree, is accessible to users. Thus features like for example anti-unification and term indexing can be added at the user level.

The attached example objSetM_chain_Demo shall give another idea of a class that internally uses the undo-on-backtrack feature. The example is about the collection type objSetM_chain. By the undo-on-backtrack feature the modifiable collection type could be turned into persistent one objSetP_chain whereby the performance characteristics of the modifiable collection are almost preserved. Both variants of the collection can resp. could be used same easily as setM_redBlack and setP_redBlack.

A collection of type objSetM_chain is a set of objects as well as doubly linked list. That is, objects can be inserted before/after other objects and objects can also be tested for membership. The performance characteristics are: Once the needed memory has been allocated, calling any of its predicates (resp. backtracking into a nondeterm one) runs in constant time. Thus it is faster than a red-black tree.

The member objects must support an interface which provides them with a positive ID number. Objects, which support that interface, can be member of arbitrary many objSetM_chain collections. Conversely the naive construction, in which the object contains a pair of predecessor/successor pointers, enables only the membership of an object in a single chain.


In very principle the specification of a procedure as "has exactly one solution" seems more 'clean' than "succeeds without a backtrack point". Because the former specification is of logical nature, while the later one is of rather technical character. Nevertheless that the specification "has exactly one solution" would internally cause difficulties, it would make VIP look even more sound from the users' perspective.
Attachments
objSetM_chain_Demo.zip
(29.29 KiB) Downloaded 1648 times
Regards Martin
User avatar
Thomas Linder Puls
VIP Member
Posts: 1398
Joined: 28 Feb 2000 0:01

Re: Reverting changes on backtracking

Unread post by Thomas Linder Puls »

Well, that was a lot. Not sure I fully get everything. Before I go into details, I can tell you the conclusion: you have not changed my view on the matter.

Regarding "analysis" in the compiler. Implementing this as a hook into the runtime system instead of making this a first-class language feature implies that the compiler should not analyze anything in this respect. But without any analysis the feature would get "random" behavior with various other compiler/language updates. Secondly, such an analysis is impossible unless the behavior is declared. Consider for example that handle (from my code above) is actually a fact variable. It would be impossible to analyze whether or not such a predicate would or would not use the feature.

Regarding the two backtrack strategies you mention, then there is obviously only one backtracking strategy. But there can be several (at least 2) ways to deal with "unbinding", my point is that tying unbinding closely to the backtracking imposes a lot of restrictions on what code you can write. Features that work in recursion will break in foreach, list comprehensions, and try-finally. The programmer(s) can of course learn the rules and restrict themselves. But all in all, it will be rather fragile and cumbersome. Subsequently, it is in my opinion not worth to supporting such a tight connection between backtracking and "unbinding".

I fully agree that such features may "spread" to common usage through libraries implemented by few, but such libraries should not impose that kind of coding restrictions on their users.

A data structure that can "unbind" on backtracking or the like is not a persistent data structure. A persistent data structure is one where every operation returns a new data structure but also preserves the old one:

Code: Select all

P2 = P1:insert(5),
After this operation we have two data structures P1 which may or may not contain 5 and P2 which contains 5.
Regards Thomas Linder Puls
PDC
Post Reply