An issue with findall?

[Leszek Buczkowski]

There is an elegant solution to n-queens problem in Prolog:

queens(N, Queens) :-
    length(Queens, N),
    place_queens(N, Queens, _, _).

place_queens(0, _, _, _) :- !.
place_queens(N, Cs, Us, [_|Ds]) :-
    M is N - 1,
    place_queens(M, Cs, [_|Us], Ds),
    place_queen(N, Cs, Us, Ds).

place_queen(N, [N|_], [N|_], [N|_]).
place_queen(N, [_|Cs], [_|Us], [_|Ds]) :-
    place_queen(N, Cs, Us, Ds).

All 92 solutions can be collected with:

?- findall(Queens, queens(8, Queens), Res).

The same thing implemented in Shen may look like:

(defprolog queens
  N Queens <--
    (len Queens N)
    (place_queens N Queens _ _);)

(defprolog place_queens
  0 _ _ _ <-- !;
  N Cs Us [_|Ds] <--
    (is M (- N 1))
    (place_queens M Cs [_|Us] Ds)
    (place_queen N Cs Us Ds);)

(defprolog place_queen
  N [N| _] [N| _] [N| _] <-- ;
  N [_|Cs] [_|Us] [_|Ds] <-- (place_queen N Cs Us Ds);)

(defprolog len
  [] 0 <-- ;
  [_|L] N <-- (len L M) (is N (+ 1 M));)

And it works well when queried for a single solution:

(prolog? (queens 8 Queens) (return Queens))

[1 7 5 8 2 4 6 3]

However, it fails with findall:

(prolog? (findall Queens (queens 8 Queens) Res) (return Res))

Invalid index 10000 for (SIMPLE-VECTOR 10000), should be a non-negative integer below 10000.

(prolog? (findall Queens (queens 8 Queens) Res) (len Res N) (return N))

Invalid index 10000 for (SIMPLE-VECTOR 10000), should be a non-negative integer below 10000.

Tested with kernel S33.1.2 under shen-scheme and with kernel S34.1 under SBCL.

Is this a bug or some subtle difference between Shen and Prolog?

Cheers,

Leszek

[Mark Tarver]

I tried this.

connecting to the web ...

Shen, copyright (C) 2010-2020 Mark Tarver
www.shenlanguage.org, Shen Professional Edition 33.02
running under Common Lisp, implementation: SBCL
port 3.2 ported by Mark Tarver
commercially licensed to Mark Tarver


(0-) (defprolog queens

  N Queens <--
    (len Queens N)
    (place_queens N Queens _ _);)

(fn queens)

(1-)

(defprolog place_queens
  0 _ _ _ <-- !;
  N Cs Us [_|Ds] <--
    (is M (- N 1))
    (place_queens M Cs [_|Us] Ds)
    (place_queen N Cs Us Ds);)

(fn place_queens)

(2-)

(defprolog place_queen
  N [N| _] [N| _] [N| _] <-- ;
  N [_|Cs] [_|Us] [_|Ds] <-- (place_queen N Cs Us Ds);)

(fn place_queen)

(3-)

(defprolog len
  [] 0 <-- ;
  [_|L] N <-- (len L M) (is N (+ 1 M));)

(fn len)

(4-) (defprolog ask
   X <-- (bind See (print X)) (when (not (y-or-n? "~%More? ")));)
(fn ask)

(5-) (prolog? (queens 8 Queens) (return Queens))

[1 7 5 8 2 4 6 3]

(6-) (prolog? (queens 5 Queens) (ask Queens))
[1 4 2 5 3]
More?  (y/n) y
[1 3 5 2 4]
More?  (y/n) y
[3 1 4 2 5]
More?  (y/n) y
[4 1 3 5 2]
More?  (y/n) y
[2 4 1 3 5]
More?  (y/n) y
[5 3 1 4 2]
More?  (y/n) y
[2 5 3 1 4]
More?  (y/n) y
[5 2 4 1 3]
More?  (y/n) y
[4 2 5 3 1]
More?  (y/n) y
[3 5 2 4 1]
More?  (y/n) y

Invalid index 10000 for (SIMPLE-VECTOR 10000), should be a non-negative integer
below 10000.

It seems that the problem is not in findall but in the maintenance of the binding vector.

This is deeper than the bug reported by Joel which was easy to fix.   I'm now working 

with a backlog of stuff created by being out with Covid.  I'll look at this when I have time.

Mark

[Mark Tarver]

I tried this

(8-) (prolog-memory 100000)
100000

(9-) !6

(prolog? (queens 5 Queens) (ask Queens))
[1 4 2 5 3]
More?  (y/n) y
[1 3 5 2 4]
More?  (y/n) y
[3 1 4 2 5]
More?  (y/n) y
[4 1 3 5 2]
More?  (y/n) y
[2 4 1 3 5]
More?  (y/n) y
[5 3 1 4 2]
More?  (y/n) y
[2 5 3 1 4]
More?  (y/n) y
[5 2 4 1 3]
More?  (y/n) y
[4 2 5 3 1]
More?  (y/n) y
[3 5 2 4 1]
More?  (y/n) y

debugger invoked on a SB-KERNEL::CONTROL-STACK-EXHAUSTED in thread
#<THREAD "main thread" RUNNING {1004A47743}>:
  Control stack exhausted (no more space for function call frames).
This is probably due to heavily nested or infinitely recursive function
calls, or a tail call that SBCL cannot or has not optimized away.

PROCEED WITH CAUTION.

Type HELP for debugger help, or (SB-EXT:EXIT) to exit from SBCL.

(no restarts: If you didn't do this on purpose, please report it as a bug

(|cl.equal?| #<unavailable lambda list>)
0]

It looks as if the allocated memory for the stack is exceeded in the original computation

after all solutions are computed and Prolog is searching for a .solution which does not

exist.  

When that memory is increased to 100,000, under SBCL, a call stack overflow kicks in

instead.

Mark

[Mark Tarver]

In Scheme-Shen  the behaviour is different.

(23-)  (prolog? (queens 5 Queens) (ask Queens))

[1 4 2 5 3]
More?  (y/n) y
[1 3 5 2 4]
More?  (y/n) y
[3 1 4 2 5]
More?  (y/n) y
[4 1 3 5 2]
More?  (y/n) y
[2 4 1 3 5]
More?  (y/n) y
[5 3 1 4 2]
More?  (y/n) y
[2 5 3 1 4]
More?  (y/n) y
[5 2 4 1 3]
More?  (y/n) y
[4 2 5 3 1]
More?  (y/n) y
[3 5 2 4 1]
More?  (y/n) y

(24-) (prolog? (findall Queens (queens 5 Queens) Res) (return Res))

However oddly, the computation terminates but no result is returned at all.

Mark

[Mark Tarver]

I expect the issue with Shen-Scheme is similar but error mesages are not bubbling up to the 

top level.

anyway I looked at this and found that this definition of len

(defprolog len
  [] N <-- (when (>= 0 N)) !;
  [_|L] N <-- (len L (- N 1));)

does work

(prolog? (findall Queens (queens 8 Queens) Res) (return Res))

[[3 6 4 2 8 5 7 1] [3 5 2 8 6 4 7 1] [5 2 4 7 3 8 6 1] [4 2 7 3 6 8 5 1] [4 7 3
8 2 5 1 6] [6 3 7 2 8 5 1 4] [6 3 7 2 4 8 1 5] [6 4 2 8 5 7 1 3] [3 7 2 8 6 4 1
5] [5 2 4 6 8 3 1 7] [4 2 7 3 6 8 1 5] [2 7 3 6 8 5 1 4] [5 3 8 4 7 1 6 2] [4 6
8 2 7 1 3 5] [4 7 5 2 6 1 3 8] [7 3 8 2 5 1 6 4] [3 6 8 2 4 1 7 5] [5 7 2 4 8 1
3 6] [7 4 2 8 6 1 3 5] [7 4 2 5 8 1 3 6] ... etc]

with 92 solutions.  However with the existing definition, an infinite regress

is set up when the last solution is found.   This runs the binding vector out

of memory and the error message is an out of bounds call to a vector. I

have yet to determine why this regress occurs.

Mark

[Mark Tarver]

In fact

(defprolog len
  [] 0 <-- !;

  [_|L] N <-- (len L (- N 1));)

works fine.

Mark 

[Mark Tarver]

Looking a bit deeper at the original program, it looks as if the structure of the top level.

(defprolog queens
  N Queens <--
    (len Queens N)
    (place_queens N Queens _ _);)

is such that when place_queens fails - which it must do when the last solution is computed - len is invited to find

another solution.   It is intended to fail, but it does not.  We can see this if we 'ask' len for an answer and then ask for more.

(defprolog len
  [] 0 <-- ;
  [_|L] N <-- (len L M) (is N (+ 1 M));)

(prolog? (len L 8) (ask L))

[Var3 Var5 Var7 Var9 Var11 Var13 Var15 Var17]
More?  (y/n)

len gives a list of 8 fresh variables as required but asking for more solutions creates an infinite regress ending

in a vector overflow.  

Mark

[Mark Tarver]

The shortest single fix to the original program is to place a cut in the top level

to prevent len looking for more solutions.

(defprolog queens
  N Queens <--
    (len Queens N)

    !

    (place_queens N Queens _ _);)

Mark

[Mark Tarver]

If you run the original program in SWI Prolog it does indeed work

but not in Shen Prolog.  The reason I believe is that the semantics

of is in SWI Prolog and Shen Prolog are slightly different.

Shen

(prolog? (is X Y))

true

SWI

?- is(X,Y).
ERROR: Arguments are not sufficiently instantiated
ERROR: In:
ERROR:    [8] _5124 is _5126
ERROR:    [7] <user>

Hence the regress is blocked in SWI but not in Shen.

Mark

[Mark Tarver]

This particular raised me from my sickbed; since the fact that it ran under SWI Prolog but not Shen

led me to believe there as a deep error in the kernel.   Not so happily.

M.  

[Leszek Buczkowski]

Mark, I hope that because of this bug, your recovery did not become longer.

By the way, it might be worth adding a description on the website how to install Shen on a platform other than Windows.
I made a round trip through most of these outdated ports and almost gave up on Shen before I discovered that it was enough to install SBCL on my mac, load install.lsp and rename the compiled file:

brew install sbcl
cd S34.2 # downloaded and unzipped kernel
sbcl --eval '(load "install.lsp")'
mv sbcl-shen.exe shen
./shen

or if one wants REPL with command history:

rlwrap ./shen

[Mark Tarver]

Well one must have some entertainment and it was an interesting problem.

However I was told I looked white after some work with Shen; one forgets the

body.   I certainly felt rather other worldly for a bit.

Re Linux, I haven't worked with it for some time.  But if somebody puts up a

Linux install I'll certainly link to it on the site.

M.

[Mark Tarver]

I wouldn't let my condition stop anybody putting up posts.  After all it is up to me

whether I respond and there are over 530 souls plugged into this group who might

well have an answer.

M.