Post-mortem: Rewrite of non-monotonic means-end regression search monotonically in three styles

[jjtolton]

As referenced in a previous discussion: I rewrote the algorithm from Prolog Programming for Artificial Intelligence (source at bottom).

The results seem to be valid, but there are a LOT of inefficiences and redundant choice points:
Edit: fixed a few things, updated output below. There are still duplicates and it's taking a surprising amount of time to find |Plan|>2!
Edit2: now the results are just incorrect, [move(c,a,b),move(b,3,a), ...] is not a valid move sequence, as you cannot move block C onto block B and then move block B! >.<
Edit3: it was correct running originally, it's not nonterminating, it's just slow and inefficient!
Edit4: Wrote two DCG versions (forwards and backwards). There is plenty to be discussed about the various approaches below.

Output of monotic rewrite of the book version of the code:

% A state in the blocks world
%
%         c
%         a   b
%         = = = =
% place   1 2 3 4
state1([clear(2),clear(4),clear(b),clear(c),on(a,1),on(b,3),on(c,a)]).


?- state1(Start), plan(Start, [on(a,b)], Plan).   
%@    Start = [clear(2),clear(4),clear(b),clear(c),on(a,1),on(b,3),on(c,a)], Plan = [move(c,a,2),move(a,1,b)]
%@ ;  Start = [clear(2),clear(4),clear(b),clear(c),on(a,1),on(b,3),on(c,a)], Plan = [move(c,a,2),move(a,1,b)]
%@ ;  Start = [clear(2),clear(4),clear(b),clear(c),on(a,1),on(b,3),on(c,a)], Plan = [move(c,a,2),move(a,1,b)]
%@ ;  Start = [clear(2),clear(4),clear(b),clear(c),on(a,1),on(b,3),on(c,a)], Plan = [move(c,a,2),move(a,1,b)]
%@ ;  Start = [clear(2),clear(4),clear(b),clear(c),on(a,1),on(b,3),on(c,a)], Plan = [move(c,a,2),move(a,1,b)]
%@ ;  Start = [clear(2),clear(4),clear(b),clear(c),on(a,1),on(b,3),on(c,a)], Plan = [move(c,a,2),move(a,1,b)], dif:dif(clear(2),_A), dif:dif(clear(a),_A), dif:dif(clear(b),_A), dif:dif(on(a,1),_A), dif:dif(on(c,a),_A)
%@ ;  Start = [clear(2),clear(4),clear(b),clear(c),on(a,1),on(b,3),on(c,a)], Plan = [move(c,a,2),move(a,1,b)], dif:dif(clear(2),_A), dif:dif(clear(a),_A), dif:dif(clear(b),_A), dif:dif(on(a,1),_A), dif:dif(on(c,a),_A)
%@ ;  Start = [clear(2),clear(4),clear(b),clear(c),on(a,1),on(b,3),on(c,a)], Plan = [move(c,a,4),move(a,1,b)]
%@ ;  Start = [clear(2),clear(4),clear(b),clear(c),on(a,1),on(b,3),on(c,a)], Plan = [move(c,a,4),move(a,1,b)]

Output of iterative DFS DCG version of the algo:

?- solve([on(a,b),on(c,a)], Moves).
%@    Moves = [move(c,a,2),move(a,1,b),move(c,2,a)]
%@ ;  Moves = [move(c,a,4),move(a,1,b),move(c,4,a)]
%@ ;  Moves = [move(b,3,2),move(c,a,3),move(a,1,b),move(c,3,a)]
%@ ;  Moves = [move(b,3,2),move(c,a,4),move(a,1,b),move(c,4,a)]
%@ ;  Moves = [move(b,3,4),move(c,a,2),move(a,1,b),move(c,2,a)]
%@ ;  Moves = [move(b,3,4),move(c,a,3),move(a,1,b),move(c,3,a)]
%@ ;  Moves = [move(c,a,2),move(a,1,4),move(a,4,b),move(c,2,a)]
%@ ;  Moves = [move(c,a,2),move(a,1,b),move(c,2,1),move(c,1,a)]
%@ ;  Moves = [move(c,a,2),move(a,1,b),move(c,2,4),move(c,4,a)]
%@ ;  Moves = [move(c,a,2),move(a,1,c),move(a,c,b),move(c,2,a)]

Output of the goal regression DCG version of the algo:

?- solve(State, [on(a,b)], Moves).
%@    State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,2),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,2),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,2),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,2),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,3),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,3),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,3),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,3),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,3),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,3),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,3),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,3),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,4),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,4),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,4),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,4),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,a),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,c),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,c),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,c),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,c),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(c,a,3),move(b,3,2)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(c,a,3),move(b,3,2)]

I'd love it if anyone would be willing to brutally critique this code so that we can make it into a shining example of what good Scryer code should look like!

Goals:

• Correct
• monotonic (I believe these versions are all monotonic now, although they do not inherently enumerate fairly)
• Efficient
• Aesthetically pleasing
• rewritten in DCG notation (if that seems like it would be a better approach)

Original discussion of research direction

On the last point, comparing to @triska's [Zurg](https://www.metalevel.at/zurg/) and [Jug Pouring](https://www.metalevel.at/tist/jugs.pl) problem, which seem to work from beginning to end (which is how I'm used to approaching search problems), _this_ approach (means-end) starts from the end and works to be beginning, working backwards through non-conflicting goals. Part of this research is to determine if it's possible to write goal regression via DCG notation -- my guess is that it is, and it would be much cleaner to do it that way.

But I wanted to get a decent reference implementation setup first!

I put the code in a gist so we can track changes and refer to it more easily:
https://gist.github.com/jjtolton/f6416b8ed2942437d8894fa3fdfe99c3 Edit: moved to summary above

[jjtolton]

@ocharles

[jjtolton]

grumble ok it runs but it is not correct.

There certainly exist infinite plans but the current code does not terminate for plans greater than length 2.

?- state1(Start), plan(Start, [on(a,b)], Plan).   
%@    Start = [clear(2),clear(4),clear(b),clear(c),on(a,1),on(b,3),on(c,a)], Plan = [move(c,a,2),move(a,1,b)]
%@ ;  Start = [clear(2),clear(4),clear(b),clear(c),on(a,1),on(b,3),on(c,a)], Plan = [move(c,a,2),move(a,1,b)]
%@ ;  Start = [clear(2),clear(4),clear(b),clear(c),on(a,1),on(b,3),on(c,a)], Plan = [move(c,a,2),move(a,1,b)]
%@ ;  Start = [clear(2),clear(4),clear(b),clear(c),on(a,1),on(b,3),on(c,a)], Plan = [move(c,a,2),move(a,1,b)]
%@ ;  Start = [clear(2),clear(4),clear(b),clear(c),on(a,1),on(b,3),on(c,a)], Plan = [move(c,a,2),move(a,1,b)]
%@ ;  Start = [clear(2),clear(4),clear(b),clear(c),on(a,1),on(b,3),on(c,a)], Plan = [move(c,a,2),move(a,1,b)], dif:dif(clear(2),_A), dif:dif(clear(a),_A), dif:dif(clear(b),_A), dif:dif(on(a,1),_A), dif:dif(on(c,a),_A)
%@ ;  Start = [clear(2),clear(4),clear(b),clear(c),on(a,1),on(b,3),on(c,a)], Plan = [move(c,a,2),move(a,1,b)], dif:dif(clear(2),_A), dif:dif(clear(a),_A), dif:dif(clear(b),_A), dif:dif(on(a,1),_A), dif:dif(on(c,a),_A)
... snip ...
%@ ;  Start = [clear(2),clear(4),clear(b),clear(c),on(a,1),on(b,3),on(c,a)], Plan = [move(c,a,b),move(a,1,b)], dif:dif(clear(b),_A), dif:dif(on(a,1),_A), dif:dif(on(a,b),_A)
%@ ;  Start = [clear(2),clear(4),clear(b),clear(c),on(a,1),on(b,3),on(c,a)], Plan = [move(c,a,b),move(a,1,b)], dif:dif(clear(b),_A), dif:dif(on(a,1),_A), dif:dif(on(a,b),_A)
%@ ;  Start = [clear(2),clear(4),clear(b),clear(c),on(a,1),on(b,3),on(c,a)], Plan = [move(c,a,b),move(a,1,b)], dif:dif(clear(b),_A), dif:dif(on(a,1),_A), dif:dif(on(a,b),_A), dif:dif(clear(a),_B), dif:dif(clear(b),_B), dif:dif(on(a,1),_B), dif:dif(on(c,a),_B)
%@ ;  Start = [clear(2),clear(4),clear(b),clear(c),on(a,1),on(b,3),on(c,a)], Plan = [move(c,a,b),move(a,1,b)], dif:dif(clear(b),_A), dif:dif(on(a,1),_A), dif:dif(on(a,b),_A), dif:dif(clear(a),_B), dif:dif(clear(b),_B), dif:dif(on(a,1),_B), dif:dif(on(c,a),_B)
%@ ;  nontermination

[jjtolton]

Actually, that's not even all plans of length 2 🤔

[jjtolton]

Ok, I got it. I did my D'Morgan's Law incorrectly:

https://gist.github.com/jjtolton/f6416b8ed2942437d8894fa3fdfe99c3/revisions#diff-54867b325bf5189ccb938ac3e7744a989ec603095d4b022286abe2ce31e5cce9L109-R113

[jjtolton]

Ah, yikes, doing that made the results incorrect.

[jjtolton]

Ok, I DID apply demorgan's correctly the first time, and there are more results, it's just taking awhile! (still a LOT of redunandancies, though!)

[jjtolton]

Inefficient AND incorrect, yikes. You can't move C from A onto A. Well, you can, but.. why??

[librarianmage]

I feel like xs_ys_setdiff/3 could be simplified to

xs_ys_setdiff(Xs, Ys, Diff) :- tpartition(i_memberd_t(Ys), Xs, _, Diff).

I haven’t tested it, though.

[librarianmage]

…right, i_memberd_t isn’t exported. Nevermind!

[librarianmage]

If you don’t mind an auxiliary i_memberd_t(Xs, X, T) :- memberd_t(X, Xs, T). though…

[jjtolton]

That is VERY cool! Wow!

[librarianmage]

You can simplify any_impossible_t/3 using tmember_t/3 (you need an impossible_t predicate that swaps the single and list arguments, though).

[jjtolton]

Great, I'll look into that! I actually wasn't sure what tmember_t/3 did!

[librarianmage]

It basically does what your predicate does—given a _t predicate, test if any of the items of the given list are true.

[jjtolton]

I got so frustrated with the book version that I ended up writing a DCG version that is iterative DFS. It's much faster. Now I'm working on a version that uses the regression method.

:- use_module(library(dif)).
:- use_module(library(reif)).
:- use_module(library(lists)).

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   xs_ys_setdiff(Xs, Ys, Diff): Diff is the set difference of Xs and Ys.
   https://github.com/mthom/scryer-prolog/discussions/2507#discussioncomment-10471435
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
xs_ys_setdiff([], _, []).
xs_ys_setdiff([X|Xs], Ys, Diff0) :-
        if_(memberd_t(X, Ys),
            Diff0=Diff,
            Diff0=[X|Diff]
            ),
        xs_ys_setdiff(Xs, Ys, Diff).

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   xs_ys_setunion(Xs, Ys, Union): Union is the set union of Xs and Ys.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
xs_ys_setunion([], L, L).
xs_ys_setunion([X|Xs], Ys, Union0) :-
        if_(memberd_t(X, Ys),
           Union0=Union,
           Union0=[X|Union]
          ),
        xs_ys_setunion(Xs, Ys, Union).


/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   object(X): X is a place or a block.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
object(X) :-
        (   place(X)
        ;   block(X)
        ).


/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   State Change relations.

   clear(Block):     denotes a block that hgas nothing above it
   on(Block,Object): denotes a block being on either another block or place
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

%% can(Action, PreConditions): Preconditions are required to be in present for this move
%%                             to be admissible.
can(move(Block, From, To), [clear(Block), clear(To), on(Block,From)]) :-
        block(Block),
        object(To),
        dif(To, Block),
        object(From),
        dif(Block, From).

%% adds(Action, Effects): These are the effects added to the State when this move happens
adds(move(X, From, To), [on(X,To), clear(From)]).

%% deletes(Action, Undoes): The Undoes are removed from the world state when this move happens 
deletes(move(X,From,To), [on(X,From), clear(To)]).

%% supported(WorldState, Conditions): the world state contains the supporting conditions
supported(WorldState, Conditions) :-
        xs_ys_setdiff(Conditions, WorldState, []).

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -   
   results_in(IntitialWorldState, Undoes, Effects, WorldState):
   The new world state after removing the undoes and apply the effects
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
results_in(WorldState0, Undoes, Effects, WorldState) :-
        xs_ys_setdiff(WorldState0, Undoes, WorldState1),
        xs_ys_setunion(WorldState1, Effects, WorldState).

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   goal(WorldState, Goals): The goal is achieved if all Goals are
   present in the WorldState
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
goal(WorldState, Goals) :-
        xs_ys_setdiff(Goals, WorldState, []).

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   goal_t(WorldState,Goals,Truth): Truth=true if goal(WorldState, Goals)
   else Truth=false.

   It turns out I didn't need this, but I'm so excited to discover
   I can make a reif predicate using (=)/3 that I'm leaving it in
   so I remember.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
goal_t(WorldState,Goals,T) :-
        xs_ys_setdiff(Goals, WorldState, Result),
        =(Result, [], T).

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   moves(state(WorldState,Goals)):
   Possible moves carried out by the planner.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
moves(state(WorldState, Goals)) -->
        { goal(WorldState, Goals) }.
moves(state(WorldState0, Goals)) --> [Move],
        { can(Move, Conditions),               % action precondtions
          supported(WorldState0, Conditions),  % determine if action can happen
          adds(Move, Effects),                 % determine effects
          deletes(Move, Undoes),               % determine undoes
          results_in(WorldState0, Undoes, Effects, WorldState) % determine WorldState'
        },
        moves(state(WorldState, Goals)).


/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   Starting World State.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
block(a).
block(b).
block(c).

place(1).
place(2).
place(3).
place(4).


% A state in the blocks world
%
%         c
%         a   b
%         = = = =
% place   1 2 3 4
start([clear(2),clear(4),clear(b),clear(c),on(a,1),on(b,3),on(c,a)]).

solve(Goal, Moves) :-
        start(Start),
        length(Moves, _),
        phrase(moves(state(Start, Goal)), Moves).

?- solve([on(a,b),on(c,a)], Moves).
%@    Moves = [move(c,a,2),move(a,1,b),move(c,2,a)]
%@ ;  Moves = [move(c,a,4),move(a,1,b),move(c,4,a)]
%@ ;  Moves = [move(b,3,2),move(c,a,3),move(a,1,b),move(c,3,a)]
%@ ;  Moves = [move(b,3,2),move(c,a,4),move(a,1,b),move(c,4,a)]
%@ ;  Moves = [move(b,3,4),move(c,a,2),move(a,1,b),move(c,2,a)]
%@ ;  Moves = [move(b,3,4),move(c,a,3),move(a,1,b),move(c,3,a)]
%@ ;  Moves = [move(c,a,2),move(a,1,4),move(a,4,b),move(c,2,a)]
%@ ;  Moves = [move(c,a,2),move(a,1,b),move(c,2,1),move(c,1,a)]
%@ ;  Moves = [move(c,a,2),move(a,1,b),move(c,2,4),move(c,4,a)]
%@ ;  Moves = [move(c,a,2),move(a,1,c),move(a,c,b),move(c,2,a)]
%@ ;  Moves = [move(c,a,2),move(b,3,4),move(a,1,b),move(c,2,a)]
%@ ;  Moves = [move(c,a,2),move(c,2,4),move(a,1,b),move(c,4,a)]
%@ ;  Moves = [move(c,a,4),move(a,1,2),move(a,2,b),move(c,4,a)]
%@ ;  Moves = [move(c,a,4),move(a,1,b),move(c,4,1),move(c,1,a)]
%@ ;  Moves = [move(c,a,4),move(a,1,b),move(c,4,2),move(c,2,a)]
%@ ;  Moves = [move(c,a,4),move(a,1,c),move(a,c,b),move(c,4,a)]
%@ ;  Moves = [move(c,a,4),move(b,3,2),move(a,1,b),move(c,4,a)]
%@ ;  Moves = [move(c,a,4),move(c,4,2),move(a,1,b),move(c,2,a)]
%@ ;  Moves = [move(c,a,b),move(c,b,2),move(a,1,b),move(c,2,a)]
%@ ;  Moves = [move(c,a,b),move(c,b,4),move(a,1,b),move(c,4,a)]
%@ ;  Moves = [move(b,3,2),move(b,2,3),move(c,a,2),move(a,1,b),move(c,2,a)]
%@ ;  Moves = [move(b,3,2),move(b,2,3),move(c,a,4),move(a,1,b),move(c,4,a)]
%@ ;  Moves = [move(b,3,2),move(b,2,4),move(c,a,2),move(a,1,b),move(c,2,a)]
%@ ;  Moves = [move(b,3,2),move(b,2,4),move(c,a,3),move(a,1,b),move(c,3,a)]
%@ ;  Moves = [move(b,3,2),move(c,a,3),move(a,1,4),move(a,4,b),move(c,3,a)]
%@ ;  Moves = [move(b,3,2),move(c,a,3),move(a,1,b),move(c,3,1),move(c,1,a)]
%@ ;  Moves = [move(b,3,2),move(c,a,3),move(a,1,b),move(c,3,4),move(c,4,a)]
%@ ;  Moves = [move(b,3,2),move(c,a,3),move(a,1,c),move(a,c,b),move(c,3,a)]
%@ ;  Moves = [move(b,3,2),move(c,a,3),move(b,2,4),move(a,1,b),move(c,3,a)]
%@ ;  Moves = [move(b,3,2),move(c,a,3),move(c,3,4),move(a,1,b),move(c,4,a)]
%@ ;  Moves = [move(b,3,2),move(c,a,4),move(a,1,3),move(a,3,b),move(c,4,a)]
%@ ;  Moves = [move(b,3,2),move(c,a,4),move(a,1,b),move(c,4,1),move(c,1,a)]
%@ ;  Moves = [move(b,3,2),move(c,a,4),move(a,1,b),move(c,4,3),move(c,3,a)]
%@ ;  Moves = [move(b,3,2),move(c,a,4),move(a,1,c),move(a,c,b),move(c,4,a)]
%@ ;  Moves = [move(b,3,2),move(c,a,4),move(b,2,3),move(a,1,b),move(c,4,a)]
%@ ;     error('$interrupt_thrown',repl/0).

[librarianmage]

This is overthinking it to the point of uselessness, but you could write xs_ys_setunion/3 as

xs_ys_setunion(Xs, Ys, Union) :- 
  xs_ys_setdiff(Xs, Ys, UniqXs),
  append(UniqXs, Ys, Union).

[jjtolton]

overthinking it to the point of uselessness

I want this carved into my tombstone

[jjtolton]

So the regression case is turning out to be much harder.

Here's the basic algorithm:

moves(state(WorldState,Goals)) -->
        { 
          format("WorldState/Goals: ~t~w~t~w~t~250|~n", [WorldState, Goals]),
          xs_ys_setdiff(WorldState, Goals, [])
        }.
moves(state(WorldState, Goals0)) --> 
        /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
           Goal regression version
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
        {
         xs_ys_setdiff(WorldState, Goals0, Result),   % sanity check to make sure you aren't solving a solved problem
         =(Result, [], false),  
         adds(Move, Effects),                         % find a move with some effects
         member(Effect, Effects),                     % where there is at least one effect
         member(Effect, Goals0),                      % that is also a goal
         deletes(Move, Undoes),                       % get the undoes of the action
         member(Undo, Undoes),                        % and make sure there is no undo 
         memberd_t(Undo, Goals0, false),              % that is also a goal (or it would create an inconsistent state)
         can(Move, Conditions),                       % take the preconditions of the action
         xs_ys_setdiff(Conditions, Goals0, NewGoals), % check out any new goals
         any_impossible_t(NewGoals, Goals0, false),   % and make sure they do not create an impossible state
         xs_ys_setunion(NewGoals, Goals0, Goals),   % and union them with the goals, as if the action happened
         format("New Goal/Goals: ~t~t~w~t~w~250|~n", [NewGoals, Goals0])
        },
        [Move],
        moves(state(WorldState, Goals)).

from some (shameful) trace statements (because I don't know a better way yet), I have determined that the most likely point of failure is my any_impossible_t.

?- any_impossible_t([on(b,4)], [clear(1),on(b,a),clear(b),clear(c),on(b,1),on(b,c)], true).
%@    true
%@ ;  true
%@ ;  true
%@ ;  false.
?- any_impossible_t([on(b,4)], [clear(1),on(b,a),clear(b),clear(c),on(b,1),on(b,c)], false).
%@    true.

Ouch.

Block B cannot be on position 4 because block B is already on position 1 and somehow block C.

Here is the any_impossible_t implementation, again, if anyone has any thoughts:

i_impossible_t(on(X,X), _, true).
i_impossible_t(on(X,Y), Goals, true) :-
        (   memberd_t(clear(Y), Goals, true)              
        ;   memberd_t(on(X,Y1), Goals,true), dif(Y1, Y)
        ;   memberd_t(on(X1,Y), Goals,true), dif(X1, X)
        ).
i_impossible_t(clear(X), Goals, true) :-
        memberd_t(on(_,X), Goals, true).
i_impossible_t(_, _, false).


impossible_t(Goal, Goals, T) :-
        length(Goals, _),
        i_impossible_t(Goal, Goals, T).

any_impossible_t([], _, false).
any_impossible_t([Goal|Goals0], Goals, T0) :-
        if_(impossible_t(Goal, Goals),
            T0=true,
            (
             T0=T,
                any_impossible_t(Goals0, Goals, T)
            )
           ).

[jjtolton]

Ok just realized there's another problem --

I'm not doing the regression algo correctly, I need to be removing the effects from the union of the goals and the conditions, which I am currently not doing.

[librarianmage]

Note: I wrote this before seeing @jjtolton was having issues with any_impossible_t/3.

A change to i_impossible_t/3 that I think may eliminate more choice points:

i_impossible_t(on(X,Y), Goals, T) :- 
  if_(X = Y, T = true, tmember_t(conflicts_on_t(X, Y), Goals, T)). % could be further esoteric-icized as ';'(X = Y, tmember_t(conflicts_on_t(X, Y), Goals), T). lol
i_impossible_t(clear(Y), Goals, T) :- tmember_t(conflicts_clear_t(Y), Goals, T).

conflicts_on_t(X, Y, Goal, T) :- conflicts_on_t_(Goal, X, Y, T).

conflicts_on_t_(on(X1, Y1), X, Y, T) :- 
 ','(X1 = X, Y1 = 1, T0), 
  if_(T0 = true, T = false, T = true). % not entirely sure on this logic tbh
conflicts_on_t_(clear(Y1), _, Y, T) :- =(Y1, Y, T).

conflicts_clear_t(Y, Goal, T) :- conflicts_clear_t_(Goal, Y, T).

conflicts_clear_t_(on(_, Y1), Y, T) :- =(Y1, Y, T).
conflicts_clear_t_(clear(_), _, false).

[librarianmage]

(made some edits, writing Prolog on a phone is not easy)

[jjtolton]

(made some edits, writing Prolog on a phone is not easy)

you are so right about that. once the shared library is done we should make a scryer iOS app and @mthom can get 20 bucks profit from all six of us who buy it 🤣

[jjtolton]

Note: I wrote this before seeing @jjtolton was having issues with any_impossible_t/3.

A change to i_impossible_t/3 that I think may eliminate more choice points:

i_impossible_t(on(X,Y), Goals, T) :- 

  if_(X = Y, T = true, tmember_t(conflicts_on_t(X, Y), Goals, T)). % could be further esoteric-icized as ';'(X = Y, tmember_t(conflicts_on_t(X, Y), Goals), T). lol

i_impossible_t(clear(Y), Goals, T) :- tmember_t(conflicts_clear_t(Y), Goals, T).



conflicts_on_t(X, Y, Goal, T) :- conflicts_on_t_(Goal, X, Y, T).



conflicts_on_t_(on(X1, Y1), X, Y, T) :- 

 ','(X1 = X, Y1 = 1, T0), 

  if_(T0 = true, T = false, T = true). % not entirely sure on this logic tbh

conflicts_on_t_(clear(Y1), _, Y, T) :- =(Y1, Y, T).



conflicts_clear_t(Y, Goal, T) :- conflicts_clear_t_(Goal, Y, T).



conflicts_clear_t_(on(_, Y1), Y, T) :- =(Y1, Y, T).

conflicts_clear_t_(clear(_), _, false).

Oh niiiiice this is a GREAT technique!

[librarianmage]

A second attempt at rewriting any_impossible_t/3:

%% true iff any of NewGoals are impossible in the context of Goals
any_impossible_t(NewGoals, Goals, T) :- tmember_t(impossible_t(Goals), NewGoals, T).

%% true iff NewGoal is impossible in the context of Goals (either it is impossible intrinsically, or contextually)
impossible_t(Goals, NewGoal, T) :- ';'(impossible_t(NewGoal), tmember_t(conflicts_t(NewGoal), Goals), T).

%% true iff the goal is impossible intrinsically
impossible_t(on(X, Y), T) :- =(X, Y, T).
impossible_t(clear(_), false).

%% true iff the two goals are contradictory
conflicts_t(on(X, Y), Goal, T) :- conflicts_on_t(Goal, X, Y, T).
conflicts_t(clear(Y), Goal, T) :- conflicts_clear_t(Goal, Y, T).

%% true iff Goal conflicts on(X, Y)
conflicts_on_t(on(X1, Y1), X, Y, T) :- ';'((X1 = X, dif(Y1, Y)), (dif(X1, X), Y1 = Y), T).
conflicts_on_t(clear(Y1), _, Y, T) :- =(Y1, Y, T).

%% true iff Goal conflicts clear(Y)
conflicts_clear_t(on(_, Y1), Y, T) :- =(Y1, Y, T).
conflicts_clear_t(clear(_), _, false).

[librarianmage]

This is closer, but not quite correct, it seems:

?- any_impossible_t([on(b,4)], [clear(1),on(b,a),clear(b),clear(c),on(b,1),on(b,c)], true).
   true.
?- any_impossible_t([on(b,4)], [clear(1),on(b,a),clear(b),clear(c),on(b,1),on(b,c)], false).
   false.
?- any_impossible_t([on(b,4)], [clear(1),on(b,a),clear(b),clear(c),on(b,1),on(b,c)], T).
   T = true.
?- any_impossible_t([on(b,X)], [clear(1),on(b,a),clear(b),clear(c),on(b,1),on(b,c)], T).
   X = b, T = true
;  X = 1, T = true
;  X = a, T = true
;  T = true, dif:dif(1,X), dif:dif(a,X), dif:dif(b,X).
?- any_impossible_t([on(b,X)], [clear(1),on(b,a),clear(b),clear(c),on(b,1),on(b,c)], false).
   false.

[jjtolton]

I am not sure that this particular version is intended to work with nonground parameters-- those are treated specifically in the next session.

[jjtolton]

A second attempt at rewriting any_impossible_t/3:

%% true iff any of NewGoals are impossible in the context of Goals
any_impossible_t(NewGoals, Goals, T) :- tmember_t(impossible_t(Goals), NewGoals, T).

%% true iff NewGoal is impossible in the context of Goals (either it is impossible intrinsically, or contextually)
impossible_t(Goals, NewGoal, T) :- ';'(impossible_t(NewGoal), tmember_t(conflicts_t(NewGoal), Goals), T).

%% true iff the goal is impossible intrinsically
impossible_t(on(X, Y), T) :- =(X, Y, T).
impossible_t(clear(_), false).

%% true iff the two goals are contradictory
conflicts_t(on(X, Y), Goal, T) :- conflicts_on_t(Goal, X, Y, T).
conflicts_t(clear(Y), Goal, T) :- conflicts_clear_t(Goal, Y, T).

%% true iff Goal conflicts on(X, Y)
conflicts_on_t(on(X1, Y1), X, Y, T) :- ';'((X1 = X, dif(Y1, Y)), (dif(X1, X), Y1 = Y), T).
conflicts_on_t(clear(Y1), _, Y, T) :- =(Y1, Y, T).

%% true iff Goal conflicts clear(Y)
conflicts_clear_t(on(_, Y1), Y, T) :- =(Y1, Y, T).
conflicts_clear_t(clear(_), _, false).

These are some really cool predicates!

[jjtolton]

Ok, regression working:

moves(state(WorldState,Goals)) -->
        { 
          % format("WorldState/Goals: ~t~w~t~w~t~250|~n", [WorldState, Goals]),
          xs_ys_setdiff(WorldState, Goals, [])
        }.
moves(state(WorldState, Goals0)) --> [Action],
        /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
           Goal regression version
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
        {
         xs_ys_setdiff(WorldState, Goals0, Result),   % sanity check to make sure you aren't solving a solved problem
         =(Result, [], false),
         can(Action, Conditions),                       % take the preconditions of the action.
         adds(Action, Effects),                         % the effects of the action,
         deletes(Action, Undoes),                       % the "undoes" of the action,
         member(Effect, Goals0),                        % if there is an effect 
         member(Effect, Effects),                       % that is also a goal
         member(Undo, Undoes),                          % but no undo                                      
         memberd_t(Undo, Goals0, false),                % in goals                                      
         xs_ys_setdiff(Goals0, Effects, Goals1),        % as long as for the combined effects+goals                                      
         any_impossible_t(Conditions, Goals1, false),   % there is no invalid state
         xs_ys_setunion(Goals1, Conditions, Goals)      % then union the conditions as if the event happened  
         % start(Start),
         % xs_ys_setdiff(Start, Goals, Left)
         % format("New Goal/Goals: ~t~w~t~20|  ~t~w~t~80|-~t~w~t~80| + ~t~w~t~80|= ~w~80|(~w)~30|~n", [Action, Goals0, Effects, Conditions, Goals, Left])
        },
        
        moves(state(WorldState, Goals)).

It's not pretty:

?- solve(State, [on(a,b)], Moves).
%@    State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,2),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,2),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,2),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,2),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,3),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,3),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,3),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,3),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,3),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,3),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,3),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,3),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,4),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,4),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,4),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,4),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,a),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,c),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,c),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,c),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,c),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(c,a,3),move(b,3,2)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(c,a,3),move(b,3,2)]

There seem to be 4 redundant choice points.

Not great, but the IDFS version works better anyway, so I'm ok with that. However, it is REALLY cool to see that you can DCGs to generate a list of actions via a DFS traversal and backwards via goal regression!

For the sake of completeness:

:- use_module(library(dif)).
:- use_module(library(reif)).
:- use_module(library(lists)).

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   xs_ys_setdiff(Xs, Ys, Diff): Diff is the set difference of Xs and Ys.
   https://github.com/mthom/scryer-prolog/discussions/2507#discussioncomment-10471435
   Courtesy of Ulrich: https://github.com/UWN
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
xs_ys_setdiff([], _, []).
xs_ys_setdiff([X|Xs], Ys, Diff0) :-
        if_(memberd_t(X, Ys),
            Diff0=Diff,
            Diff0=[X|Diff]
            ),
        xs_ys_setdiff(Xs, Ys, Diff).

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   xs_ys_setunion(Xs, Ys, Union): Union is the set union of Xs and Ys.
   Courtesy of Rayh ttps://github.com/librarianmage
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
xs_ys_setunion(Xs, Ys, Union) :- 
  xs_ys_setdiff(Xs, Ys, UniqXs),
  append(UniqXs, Ys, Union).


/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   object(X): X is a place or a block.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
object(X) :-
        (   place(X)
        ;   block(X)
        ).


/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   State Change relations.

   clear(Block):     denotes a block that hgas nothing above it
   on(Block,Object): denotes a block being on either another block or place
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

%% can(Action, PreConditions): Preconditions are required to be in present for this move
%%                             to be admissible.
can(move(Block, From, To), [clear(Block), clear(To), on(Block,From)]) :-
        block(Block),
        object(To),
        dif(To, Block),
        object(From),
        dif(Block, From).

%% adds(Action, Effects): These are the effects added to the State when this move happens
adds(move(X, From, To), [on(X,To), clear(From)]).

%% deletes(Action, Undoes): The Undoes are removed from the world state when this move happens 
deletes(move(X,From,To), [on(X,From), clear(To)]).

%% supported(WorldState, Conditions): the world state contains the supporting conditions
supported(WorldState, Conditions) :-
        xs_ys_setdiff(Conditions, WorldState, []).

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -   
   results_in(IntitialWorldState, Undoes, Effects, WorldState):
   The new world state after removing the undoes and apply the effects
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
results_in(WorldState0, Undoes, Effects, WorldState) :-
        xs_ys_setdiff(WorldState0, Undoes, WorldState1),
        xs_ys_setunion(WorldState1, Effects, WorldState).

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   goal(WorldState, Goals): The goal is achieved if all Goals are
   present in the WorldState
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
goal(WorldState, Goals) :-
        xs_ys_setdiff(Goals, WorldState, []).

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   goal_t(WorldState,Goals,Truth): Truth=true if goal(WorldState, Goals)
   else Truth=false.

   It turns out I didn't need this, but I'm so excited to discover
   I can make a reif predicate using (=)/3 that I'm leaving it in
   so I remember.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
goal_t(WorldState,Goals,T) :-
        xs_ys_setdiff(Goals, WorldState, Result),
        =(Result, [], T).




/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   https://github.com/mthom/scryer-prolog/discussions/2513#discussioncomment-10493094
   courtesy of Ray https://github.com/librarianmage
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
%% true iff any of NewGoals are impossible in the context of Goals
any_impossible_t(NewGoals, Goals, T) :- tmember_t(impossible_t(Goals), NewGoals, T).

%% true iff NewGoal is impossible in the context of Goals (either it is impossible intrinsically, or contextually)
impossible_t(Goals, NewGoal, T) :- ';'(impossible_t(NewGoal), tmember_t(conflicts_t(NewGoal), Goals), T).

%% true iff the goal is impossible intrinsically
impossible_t(on(X, Y), T) :- =(X, Y, T).
impossible_t(clear(_), false).

%% true iff the two goals are contradictory
conflicts_t(on(X, Y), Goal, T) :- conflicts_on_t(Goal, X, Y, T).
conflicts_t(clear(Y), Goal, T) :- conflicts_clear_t(Goal, Y, T).

%% true iff Goal conflicts on(X, Y)
conflicts_on_t(on(X1, Y1), X, Y, T) :- ';'((X1 = X, dif(Y1, Y)), (dif(X1, X), Y1 = Y), T).
conflicts_on_t(clear(Y1), _, Y, T) :- =(Y1, Y, T).

%% true iff Goal conflicts clear(Y)
conflicts_clear_t(on(_, Y1), Y, T) :- =(Y1, Y, T).
conflicts_clear_t(clear(_), _, false).

?- any_impossible_t([on(b,4)], [clear(1),on(b,a),clear(b),clear(c),on(b,1),on(b,c)], true).
?- any_impossible_t([on(b,4)], [clear(1),on(b,a),clear(b),clear(c),on(b,1),on(b,c)], false).


moves(state(WorldState,Goals)) -->
        { 
          % format("WorldState/Goals: ~t~w~t~w~t~250|~n", [WorldState, Goals]),
          xs_ys_setdiff(WorldState, Goals, [])
        }.
moves(state(WorldState, Goals0)) --> [Action],
        /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
           Goal regression version
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
        {
         xs_ys_setdiff(WorldState, Goals0, Result),   % sanity check to make sure you aren't solving a solved problem
         =(Result, [], false),
         can(Action, Conditions),                       % take the preconditions of the action.
         adds(Action, Effects),                         % the effects of the action,
         deletes(Action, Undoes),                       % the "undoes" of the action,
         member(Effect, Goals0),                        % if there is an effect 
         member(Effect, Effects),                       % that is also a goal
         member(Undo, Undoes),                          % but no undo                                      
         memberd_t(Undo, Goals0, false),                % in goals                                      
         xs_ys_setdiff(Goals0, Effects, Goals1),        % as long as for the combined effects+goals                                      
         any_impossible_t(Conditions, Goals1, false),   % there is no invalid state
         xs_ys_setunion(Goals1, Conditions, Goals)      % then union the conditions as if the event happened  
         % start(Start),
         % xs_ys_setdiff(Start, Goals, Left)
         % format("New Goal/Goals: ~t~w~t~20|  ~t~w~t~80|-~t~w~t~80| + ~t~w~t~80|= ~w~80|(~w)~30|~n", [Action, Goals0, Effects, Conditions, Goals, Left])
        },
        
        moves(state(WorldState, Goals)).



/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   Starting World State.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
block(a).
block(b).
block(c).

place(1).
place(2).
place(3).
place(4).


% A state in the blocks world
%
%         c
%         a   b
%         = = = =
% place   1 2 3 4
%start([clear(2),clear(4),clear(b),clear(c),on(a,1),on(b,3),on(c,a)]).

start([on(a,1),on(b,3)]).


solve(Start, Goal, Moves) :-
        start(Start),
        length(Moves, _),
        phrase(moves(state(Start, Goal)), Moves).

?- solve(State, [on(a,b)], Moves).
%@    State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,2),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,2),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,2),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,2),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,3),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,3),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,3),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,3),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,3),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,3),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,3),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,3),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,4),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,4),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,4),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,4),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,a),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,c),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,c),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,c),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,c),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(c,a,3),move(b,3,2)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(c,a,3),move(b,3,2)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(c,a,3),move(b,3,3)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(c,a,3),move(b,3,4)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(c,a,3),move(b,3,4)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(c,a,3),move(b,3,c)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(c,a,3),move(b,3,2)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(c,a,3),move(b,3,2)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(c,a,3),move(b,3,3)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(c,a,3),move(b,3,4)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(c,a,3),move(b,3,4)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(c,a,3),move(b,3,c)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,2),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,2),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,2),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,2),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,3),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,3),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,3),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,3),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,3),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,3),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,3),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,3),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,4),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,4),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,4),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,4),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,a),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,c),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,c),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,c),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(b,a,c),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(c,a,3),move(b,3,2)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(c,a,3),move(b,3,2)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(c,a,3),move(b,3,3)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(c,a,3),move(b,3,4)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(c,a,3),move(b,3,4)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(c,a,3),move(b,3,c)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(c,a,3),move(b,3,2)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(c,a,3),move(b,3,2)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(c,a,3),move(b,3,3)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(c,a,3),move(b,3,4)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(c,a,3),move(b,3,4)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(c,a,3),move(b,3,c)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,3,b),move(a,1,3),move(b,3,2)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,3,b),move(a,1,3),move(b,3,2)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,3,b),move(a,1,3),move(b,3,3)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,3,b),move(a,1,3),move(b,3,4)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,3,b),move(a,1,3),move(b,3,4)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,3,b),move(a,1,3),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,3,b),move(a,1,3),move(b,3,c)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,3,b),move(a,1,3),move(b,3,c)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,3,b),move(a,1,3),move(b,3,2)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,3,b),move(a,1,3),move(b,3,2)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,3,b),move(a,1,3),move(b,3,3)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,3,b),move(a,1,3),move(b,3,4)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,3,b),move(a,1,3),move(b,3,4)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,3,b),move(a,1,3),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,3,b),move(a,1,3),move(b,3,c)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,3,b),move(a,1,3),move(b,3,c)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,3,b),move(a,1,3),move(b,3,2)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,3,b),move(a,1,3),move(b,3,2)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,3,b),move(a,1,3),move(b,3,3)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,3,b),move(a,1,3),move(b,3,4)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,3,b),move(a,1,3),move(b,3,4)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,3,b),move(a,1,3),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,3,b),move(a,1,3),move(b,3,c)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,3,b),move(a,1,3),move(b,3,c)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,3,b),move(a,1,3),move(b,3,2)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,3,b),move(a,1,3),move(b,3,2)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,3,b),move(a,1,3),move(b,3,3)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,3,b),move(a,1,3),move(b,3,4)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,3,b),move(a,1,3),move(b,3,4)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,3,b),move(a,1,3),move(b,3,a)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,3,b),move(a,1,3),move(b,3,c)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,3,b),move(a,1,3),move(b,3,c)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(a,1,1),move(a,1,3),move(b,3,2)]
%@ ;  State = [on(a,1),on(b,3)], Moves = [move(a,1,b),move(a,1,1),move(a,1,3),move(b,3,2)]
%@ ;  ... .
%@    error('$interrupt_thrown',repl/0).

[jjtolton]

I also notices it thrashes a lot on harder goal states than the IDFS version. I was never able to make it achieve this state:

start([clear(2),clear(4),clear(b),clear(c),on(a,1),on(b,3),on(c,a)]).

[jjtolton]

Ok let's begin the roast proper!

I'll be focusing primarily on the IDFS DCG version because it works the best and it's the easiest to understand, though I would love to know why goal regression version has so many redundant choice points.

The IDFS DCG version is pretty good, but it's a lot slower than I would like it to be. I believe the way I wrote it (trying to stay close to the book logic) is generating too many alternatives at each step.

The bulk of the work is done in moves//1 here:

moves(state(WorldState0, Goals)) --> [Move],
        { can(Move, Conditions),               % action precondtions
          supported(WorldState0, Conditions),  % determine if action can happen
          adds(Move, Effects),                 % determine effects
          deletes(Move, Undoes),               % determine undoes
          results_in(WorldState0, Undoes, Effects, WorldState) % determine WorldState'
        },
        moves(state(WorldState, Goals)).

and using can/2 is generating a lot of alternatives:

%% all_actions(Action): like `can/2` without filtering out any to actions so as to count all computations)
all_actions(action(Block, From, To)) :-
        block(Block),
        object(To),
        object(From).

action_count(Count) :-
        findall(Action, all_actions(Action), Actions),
        length(Actions, Count).

?- action_count(Count).
%@    Count = 147.

[jjtolton]

This makes me think that using a sparse adjacency matrix to represent the graph would be very effective for Prolog search. There's a few great books on this, including Mathematics for Big Data, that I think would be a great fit for Scryer!

[jjtolton]

I also think that there are some potential structural inefficiencies embedded into this simple world design which are ok for a problem at this small scale but would be a problem on a larger state space. For instance:

%% can(Action, PreConditions): Preconditions are required to be in present for this move
%%                             to be admissible.
can(move(Block, From, To), [clear(Block), clear(To), on(Block,From)]) :-
        block(Block),
        object(To),
        dif(To, Block),
        object(From),
        dif(Block, From).

%% adds(Action, Effects): These are the effects added to the State when this move happens
adds(move(X, From, To), [on(X,To), clear(From)]).

%% deletes(Action, Undoes): The Undoes are removed from the world state when this move happens 
deletes(move(X,From,To), [on(X,From), clear(To)]).

The idea with these 3 predicates is that the Preconditions are required to be present in the state for a move to be valid, and the state gets modified by adding the Effects and removing the Undoes. So for instance, placing on(X,To) as an Effect makes sense, but adding clear(From) should probably be handled by constraint logic programming and propagation. Likewise, all of the Undoes in the deletes/2 should probably be handled by constraint propagation rather than done manually. It seems like doing these by hand would be very error prone on more complex state spaces.

[jjtolton]

To reflect, some of the very interesting lessons that came out of this exercise so far --

1. How to use reif:if_/3 instead of !/0 to efficiently and monotonically do a set difference

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   xs_ys_setdiff(Xs, Ys, Diff): Diff is the set difference of Xs and Ys.
   https://github.com/mthom/scryer-prolog/discussions/2507#discussioncomment-10471435
   Courtesy of Ulrich: https://github.com/UWN
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
xs_ys_setdiff([], _, []).
xs_ys_setdiff([X|Xs], Ys, Diff0) :-
        if_(memberd_t(X, Ys),
            Diff0=Diff,
            Diff0=[X|Diff]
            ),
        xs_ys_setdiff(Xs, Ys, Diff).

2. A very elegant implementation of a set union using the definition of set difference:

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   xs_ys_setunion(Xs, Ys, Union): Union is the set union of Xs and Ys.
   Courtesy of Rayh ttps://github.com/librarianmage
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
xs_ys_setunion(Xs, Ys, Union) :- 
  xs_ys_setdiff(Xs, Ys, UniqXs),
  append(UniqXs, Ys, Union).

3. This really great reif:if_/3 compatible set of predicates which demonstrate use of reif:tember_t/3. I think it uses a great clean representation, really interesting use of (;)/3 which I didn't know about, and demonstrates an elegant, concise and confident language over the problem domain:

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   https://github.com/mthom/scryer-prolog/discussions/2513#discussioncomment-10493094
   courtesy of Ray https://github.com/librarianmage
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
%% true iff any of NewGoals are impossible in the context of Goals
any_impossible_t(NewGoals, Goals, T) :- tmember_t(impossible_t(Goals), NewGoals, T).

%% true iff NewGoal is impossible in the context of Goals (either it is impossible intrinsically, or contextually)
impossible_t(Goals, NewGoal, T) :- ';'(impossible_t(NewGoal), tmember_t(conflicts_t(NewGoal), Goals), T).

%% true iff the goal is impossible intrinsically
impossible_t(on(X, Y), T) :- =(X, Y, T).
impossible_t(clear(_), false).

%% true iff the two goals are contradictory
conflicts_t(on(X, Y), Goal, T) :- conflicts_on_t(Goal, X, Y, T).
conflicts_t(clear(Y), Goal, T) :- conflicts_clear_t(Goal, Y, T).

%% true iff Goal conflicts on(X, Y)
conflicts_on_t(on(X1, Y1), X, Y, T) :- ';'((X1 = X, dif(Y1, Y)), (dif(X1, X), Y1 = Y), T).
conflicts_on_t(clear(Y1), _, Y, T) :- =(Y1, Y, T).

%% true iff Goal conflicts clear(Y)
conflicts_clear_t(on(_, Y1), Y, T) :- =(Y1, Y, T).
conflicts_clear_t(clear(_), _, false).

?- any_impossible_t([on(b,4)], [clear(1),on(b,a),clear(b),clear(c),on(b,1),on(b,c)], true).
?- any_impossible_t([on(b,4)], [clear(1),on(b,a),clear(b),clear(c),on(b,1),on(b,c)], false).

4. Even though my implementation was not the most efficient (being my first serious effort at search in Prolog), I was extremely impressed by the versatility of DCGs for this work. @triska 's work and demonstrations on using DCGs for solving complex problems such as Zurg were really instrumental. I was also really surprised that a DCG could solve a problem not just from start to finish (as with the IDFS) but from finish to start, as demonstrated with the regression version:

moves(state(WorldState,Goals)) -->
        { 
          % format("WorldState/Goals: ~t~w~t~w~t~250|~n", [WorldState, Goals]),
          xs_ys_setdiff(WorldState, Goals, [])
        }.
moves(state(WorldState, Goals0)) --> [Action],
        /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
           Goal regression version
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
        {
         xs_ys_setdiff(WorldState, Goals0, Result),   % sanity check to make sure you aren't solving a solved problem
         =(Result, [], false),
         can(Action, Conditions),                       % take the preconditions of the action.
         adds(Action, Effects),                         % the effects of the action,
         deletes(Action, Undoes),                       % the "undoes" of the action,
         member(Effect, Goals0),                        % if there is an effect 
         member(Effect, Effects),                       % that is also a goal
         member(Undo, Undoes),                          % but no undo                                      
         memberd_t(Undo, Goals0, false),                % in goals                                      
         xs_ys_setdiff(Goals0, Effects, Goals1),        % as long as for the combined effects+goals                                      
         any_impossible_t(Conditions, Goals1, false),   % there is no invalid state
         xs_ys_setunion(Goals1, Conditions, Goals)      % then union the conditions as if the event happened  
         % start(Start),
         % xs_ys_setdiff(Start, Goals, Left)
         % format("New Goal/Goals: ~t~w~t~20|  ~t~w~t~80|-~t~w~t~80| + ~t~w~t~80|= ~w~80|(~w)~30|~n", [Action, Goals0, Effects, Conditions, Goals, Left])
        },     
        moves(state(WorldState, Goals)).

The versatility of DCGs alone is astonishing, even when used suboptimally. It is amazing that they were able to construct a sequence not just from front-to-back, but from back-to-front!

[jjtolton]

Some areas for improvement:

1. It's refreshing to solve problems by needing to reason about them instead of using a debugger, but I noticed some very strange things sometimes. For instance, when refactoring, there were no errors presented from typos in variable names. Sometimes the types were so subtle that they were hard to spot for a long time. This resulted in really unpredictable behavior that was hard to diagnose.

2. Without a debugger, it can be really hard to track down why you might have redundant choice points.

3. I hate using trace statements like format/2, but in this case it felt like my only choice. If it comes down to that I'd much rather prefer a debugger, especially when diagnosing nontermination, because otherwise my console or editor just get annihilated with 10's of thousands of lines of garbage before I can even cancel execution.

I think the main takeaway here is that it's probably time to learn to use (meta?)interpreters to get some more fine-grained control over execution. The will probably be important for a number of other reasons, anyway!

[jjtolton]

Another takeaway I had is that it would be really great, I think, to start to get some slightly better tooling for Scryer. Because Prolog is so amenable to metainterpreters, I have a feeling that the lsp-server pathway has a lot of viability and would play well with ediprolog.

[bakaq]

I hate using trace statements like format/2, but in this case it felt like my only choice. If it comes down to that I'd much rather prefer a debugger, especially when diagnosing nontermination, because otherwise my console or editor just get annihilated with 10's of thousands of lines of garbage before I can even cancel execution.

You should probably learn about failure slices and declarative debugging. It isn't applicable for every property (it doesn't help with determinism for example) but it does help with non-termination and making sure your predicate is actually the relation you meant. Those are techniques that are only really applicable for monotonic Prolog, and they are really powerful.

[triska]

The correct portable way to do this

Yes that's right! We should not rely on any specific translation methods for DCGs, so that other and potentially more efficient expansion methods can be used in the future!

Regarding telemetry: Personally, I stop using projects that add telemetry, and I hope Scryer can be kept forever safe from such developments. It's bad enough that forall/2 is currently provided by a library, since the name suggests more than the predicate provides, and I hope we can remove this overhead in the future. As I see it, the interesting engineering task is: What is the minimum we need to provide, a minimal engine and a minimal set of library predicates that suffice to implement all applications elegantly! Telemetry is definitely not necessary for this, and neither is forall/2. All such add-ons only detract from implementing the core correctly.

[jjtolton]

$(X) --> call($(X)).
$_(X, A, B) :- $ phrase(X, A, B).

is this supposed to be

$(X, A, B) :- $ phrase(X, A, B).

?

$_(X, A, B) :- $ phrase(X, A, B).

is not parsing correctly for me.

error(syntax_error(incomplete_reduction),read_term/3:172).

[bakaq]

It's call($_(X)) instead of call($(X)). You can give any name really for this helper predicate, or even just use library(lambda).

[bakaq]

Ok, $_ isn't a valid atom apparently. Whatever, just use library(lambda):

$(X) --> call(\A^B^($phrase(X, A, B))).

[jjtolton]

I know naming is important, so I just called mine hellsbells

$(X) --> call(hellsbells(X)).
hellsbells(X, A, B) :- $ phrase(X, A, B).

Works great :D

[jjtolton]

Thanks everyone for your wonderful suggestions! Next up: partial order planning!