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

Re: Stack Inspection

Unread post by Martin Meyer »

I have tried above cutBackTrack test in 32 bit. That revealed a problem. It outputs:

Code: Select all

1 begin 2 begin 3 begin 3 fail
I suppose the problem which you have mentioned in the disclaimer is showing up here. Do you have an idea how to fix it?

I also tried the eight queens demo in 32 bit. That however worked well.
Regards Martin
User avatar
Thomas Linder Puls
VIP Member
Posts: 1389
Joined: 28 Feb 2000 0:01

Re: Stack Inspection

Unread post by Thomas Linder Puls »

Instead of delegating all the individual predicates you can just write:

Code: Select all

delegate     interface array2M{@ItemType} to ar2M
An advantage (but perhaps also a danger) is that future extension of the array2M interface will automatically be handled by this.

Anyways, concerning your questions.

1) No, I don't know of any such example; but I have not given it a lot of considerations. Also, I cannot ensure that it will not break in future releases.

2) I have tried your example on the current version and it works. But the language will contain a new feature for "suspending" (~asynchronous) code and I am quite certain that your approach can break in that context. But I doubt that that will be a problem for you, because it is unlikely that you will use it in such a context.

3) The function also exist in teh vip9 kernel. I believe you can simply mimic the declaration from vip10 (but have not tried it). The link names are:

32bit:

Code: Select all

    getBackTrackTop = "?GetBackTrackTop@Kernel@VIP@@YAQAVTBackTrackBlock@12@XZ".
64 bit:

Code: Select all

    getBackTrackTop = "?GetBackTrackTop@Kernel@VIP@@YAQAVTBackTrackBlock@12@XZ".
Regards Thomas Linder Puls
PDC
User avatar
Thomas Linder Puls
VIP Member
Posts: 1389
Joined: 28 Feb 2000 0:01

Re: Stack Inspection

Unread post by Thomas Linder Puls »

The link names seems to be the same :-).
Regards Thomas Linder Puls
PDC
Martin Meyer
VIP Member
Posts: 328
Joined: 14 Nov 2002 0:01

Re: Stack Inspection

Unread post by Martin Meyer »

Many thanks Thomas for the info!

A truly useable solution to the "undo destructive changes when backtracking" problem requires a construction which is supported by you. I know I've annoyed you already lots with this, but still: it would be great if you could somehow turn the demo construct (by vip internal changes) into a valid one that doesn't violate invariants.
Regards Martin
User avatar
Thomas Linder Puls
VIP Member
Posts: 1389
Joined: 28 Feb 2000 0:01

Re: Stack Inspection

Unread post by Thomas Linder Puls »

It is never annoying to hear from you.

What I write below may be stuff that you choose to "ignore" in a concreate usage of your approach. But for general support it must be handled.

You have only considered the "positive" cases. To make this fully/generally correct you will also need to deal with exceptions. You should also perform undo actions when exiting out of code. There is a similar chain for exceptions, and both of these chains contains the corresponding entry in the other chain because when one is "activated" the other one needs to be restored correspondingly.

Also what happens if an undo action registers an undo action (or raises an exception)?

Finally the use of a class facts for trail and execUndoAddress, means that it will not work in a multithreaded context. Each thread will need its own instances of these facts. (The btop and ttop are in thread local storage).

I will consider "first class" support of such a feature once more. But there is a general penalty on all backtracking and exception handling, not just in situations where undo actions are actually used.
Regards Thomas Linder Puls
PDC
Martin Meyer
VIP Member
Posts: 328
Joined: 14 Nov 2002 0:01

Re: Stack Inspection

Unread post by Martin Meyer »

Maybe it could be implemented in VIP with little expense like this:

Code: Select all

class btReversion     open core   predicates     addUndoAction : (predicate Undo).   predicates     undoOnFailure_mt : () multi.   end class btReversion   %---   implement btReversion     open core   domains     trailEntry = trailEntry(programControl::stackMark StackMark, predicate Undo).   class facts     trailTree : redBlackTree::tree{multiThread_native::threadID ThreadID, varM{trailEntry*} TrailM} := redBlackTree::emptyUnique().   class predicates     getTrailM : () -> varM{trailEntry*} TrailM. clauses     getTrailM() = TrailM :-         ThreadId = multiThread_native::getCurrentThreadId(),         if TrailM = redBlackTree::tryLookUp(trailTree, ThreadId) then         else             TrailM = varM::new([]),             trailTree := redBlackTree::insert(trailTree, ThreadId, TrailM)         end if.   clauses     undoOnFailure_mt().       undoOnFailure_mt() :-         TrailM = getTrailM(),         undoOnFailure_fl(TrailM).   class predicates     undoOnFailure_fl : (varM{trailEntry*} TrailM) failure. clauses     undoOnFailure_fl(TrailM) :-         [trailEntry(StackMark, Undo) | RestTrail] = TrailM:value,         StackMark <= programControl::getBackTrack(),         TrailM:value := RestTrail,         try             Undo()         finally             undoOnFailure_fl(TrailM)         end try.   clauses     addUndoAction(Undo) :-         TrailM = getTrailM(),         StackMark = programControl::getBackTrack(),         TrailM:value := [trailEntry(StackMark, Undo) | TrailM:value].   end implement btReversion   %===   interface array2B{@ItemType} supports array2M{@ItemType} end interface array2B   %---   class array2B{@ItemType} : array2B{@ItemType}     open core   constructors     new : (positive SizeX, positive SizeY).   constructors     newInitialize : (positive SizeX, positive SizeY, @ItemType InitValue).   constructors     newPointer : (pointer Data, positive SizeX, positive SizeY).   end class array2B   %---   implement array2B{@ItemType}     open core, btReversion   delegate     interface array2M{@ItemType} to ar2M   facts     ar2M : array2M{@ItemType}.   clauses     new(SizeX, SizeY) :-         ar2M := array2M::new(SizeX, SizeY).   clauses     newInitialize(SizeX, SizeY, Init) :-         ar2M := array2M::newInitialize(SizeX, SizeY, Init).   clauses     newPointer(Buffer, SizeX, SizeY) :-         ar2M := array2M::newPointer(Buffer, SizeX, SizeY).   clauses     set(X, Y, Value) :-         OldValue = ar2M:get(X, Y),         ar2M:set(X, Y, Value),         addUndoAction({  :- ar2M:set(X, Y, OldValue) }).   clauses     set(tuple(X, Y), Value) :-         set(X, Y, Value).   clauses     set_optional(tuple(X, Y), some(Value)) :-         set(X, Y, Value).       set_optional(XY, none) :-         ar2M:set_optional(XY, none). %raises exception   clauses     insert(tuple(XY, Value)) :-         set(XY, Value).   clauses     insertList(TupleList) :-         OldAr2M = ar2M:createCopy(),         ar2M:insertList(TupleList),         addUndoAction({  :- ar2M := OldAr2M }).   clauses     insertCollection(TupleCollection) :-         OldAr2M = ar2M:createCopy(),         ar2M:insertCollection(TupleCollection),         addUndoAction({  :- ar2M := OldAr2M }).   clauses     insertEnumerator(TupleEnum_nd) :-         OldAr2M = ar2M:createCopy(),         ar2M:insertEnumerator(TupleEnum_nd),         addUndoAction({  :- ar2M := OldAr2M }).   end implement array2B   %===   implement main     open core   constants     boardSize : positive = 8.   class facts     boardB : array2B{unsigned8} := array2B::new(boardSize, boardSize).     solutionCount : positive := 0.   clauses     run() :-         stdIO::nl(),         solve_nd(0, 0),         fail.       run() :-         stdIO::writeF("Total solutions for a %ux%u board: %u.\n", boardSize, boardSize, solutionCount).   class predicates     show : (). clauses     show() :-         stdIO::writeF("Solution %u:\n", solutionCount),         foreach Y = std::downTo(boardSize - 1, 0) do             stdIO::writeF("%2u", Y + 1),             foreach X = std::fromTo(0, boardSize - 1) do                 Field = if boardB:get(X, Y) = 0 then '.' else 'Q' end if,                 stdIO::write(Field)             end foreach,             stdIO::nl()         end foreach,         stdIO::write('  '),         foreach X = std::fromTo(0, boardSize - 1) do             stdIO::write(string::getCharFromValue(string::getCharValue('a') + X))         end foreach,         stdIO::nl(),         stdIO::nl().   class predicates     solve_nd : (positive QueenX, positive QueenY) nondeterm. clauses     solve_nd(QueenX, QueenY) :-         btReversion::undoOnFailure_mt(), %internally insert a call to undoOnFailure_mt at each backtrack point         boardB:set(QueenX, QueenY, 1),         not(canCaptureHorizontal(0, QueenX, QueenY)),         not(canCaptureDiagonal1(0, QueenX, QueenY)),         not(canCaptureDiagonal2(0, QueenX, QueenY)),         if QueenX = boardSize - 1 then             solutionCount := solutionCount + 1,             show()         else             solve_nd(QueenX + 1, 0)         end if.       solve_nd(QueenX, QueenY) :-         QueenY < boardSize - 1,         solve_nd(QueenX, QueenY + 1).   class predicates     canCaptureHorizontal : (positive N, positive QueenX, positive QueenY) determ. clauses     canCaptureHorizontal(N, QueenX, QueenY) :-         N < QueenX,         if boardB:get(N, QueenY) = 0 then             canCaptureHorizontal(N + 1, QueenX, QueenY)         end if.   class predicates     canCaptureDiagonal1 : (positive N, positive QueenX, positive QueenY) determ. clauses     canCaptureDiagonal1(N, QueenX, QueenY) :-         N < QueenX,         N < QueenY,         N1 = N + 1,         if boardB:get(QueenX - N1, QueenY - N1) = 0 then             canCaptureDiagonal1(N1, QueenX, QueenY)         end if.   class predicates     canCaptureDiagonal2 : (positive N, positive QueenX, positive QueenY) determ. clauses     canCaptureDiagonal2(N, QueenX, QueenY) :-         N < QueenX,         N1 = N + 1,         N1 < boardSize - QueenY,         if boardB:get(QueenX - N1, QueenY + N1) = 0 then             canCaptureDiagonal2(N1, QueenX, QueenY)         end if.   end implement main
The only essential change in VIP would be that you needed to insert internally a call to btReversion::undoOnFailure_mt at each backtrack point like I am doing it in above at the programmer's level.

I haven't tried it but I presume that the above construct neither poses problems with exceptions resp. handling them nor in a multithreaded context. Also I don't see a problem when an undo action registers an undo action. Or am I overlooking something?

There might even be a medicine to avoid a penalty on backtracking where undo actions are not used. A simple solution would be a compiler directive to turn the feature on. All existant programs don't use the compiler directive and the calls to undoOnFailure_mt would not be inserted.
Regards Martin
User avatar
Thomas Linder Puls
VIP Member
Posts: 1389
Joined: 28 Feb 2000 0:01

Re: Stack Inspection

Unread post by Thomas Linder Puls »

There are problems in Vip11 which you cannot know anything about. While this approach can be made working in ordinary code it will not work in suspending code (a new language feature).

While you may not need to worry about this because you don't intend to use it in suspending code (at least not at first ;-)); we will have to make a supported feature working more generally. So we would have to use a strategy which also fits into suspending code.

And this displays a major problem about features in general. A feature not only have a code to implement it also put restrictions and burdens on future development. Assume that we in Vip10 had introduced the feature and implemented in more or less like this, then we would have to figure out how to deal with that feature in the context of suspending predicates. So this "simple-to-implement-at-some-point" feature may later require a different strategy in a new context.

Anyway there is some problem with the trail: There are also places where undo actions should be removed from the trail without being performed (the trail should be restored to some earlier state). But right now I am uncertain on where that is; but I believe you may end up undoing things that should not be undone.
Regards Thomas Linder Puls
PDC
User avatar
Thomas Linder Puls
VIP Member
Posts: 1389
Joined: 28 Feb 2000 0:01

Re: Stack Inspection

Unread post by Thomas Linder Puls »

I take the last words back ;-), the trail should not be reset at any point and using the stack depth as an indicator of which undo actions to performs will work (I think).

But not for suspending predicates. Suspending predicates are not tied to a run stack in any way. When a suspending predicate suspends (which is what they can) they are removed completely from the stack of that thread. When they are resumed (which is the other thing they can) it can be on the stack of a different thread, meaning that the run stack is now a different one (and subsequently you cannot use stack marks for anything).

A correct way to deal with this (in all contexts) is to store trail-marks in the backtrack records. When adding an undo action it will be chained into the trail from the current/top backtrack record. When backtracking (or exiting) you will perform all undo actions from the overall trail until you meet the undo action in the new current/top backtrack record.

When cutting you will transfer the current/top trail to the backtrack record that becomes the new current/top. Effectively this means that all undo actions from all cut backtrack records will now belong to the new current/top backtrack record.
Regards Thomas Linder Puls
PDC
Post Reply