[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.

[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".

[Thomas Linder Puls]

The link names seems to be the same .

[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.

[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.

[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.

[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.

[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.