PROLOG-REQUEST@SU-SCORE.ARPA (Chuck Restivo, The Moderator) (06/17/86)
PROLOG Digest Wednesday, 18 Jun 1986 Volume 4 : Issue 22
Today's Topics:
Query - Thanks,
Implementation - CP NQueens & TProlog & Standardization
----------------------------------------------------------------------
Date: Fri, 13 Jun 86 11:49:24 pdt
From: Peter Ludemann <ludemann%ubc.csnet@CSNET-RELAY>
Subject:
I wish to thank the people who responded to my query about
who is working on Warren (and other) logic machines.
One person mentioned work at Stanford on hardware called
PLM and/or SOAR. Also, there was a rumour of work going
on at NEC. Does anyone have any more details, please?
-- Peter Ludemann
------------------------------
Date: Thu 12 Jun 86 20:33:23-EDT
From: Vijay <Vijay.Saraswat@C.CS.CMU.EDU>
Subject: N-queens in CP[!,|,&].
Here is the CP[!,|,&] program for the N-queens problem.
/* queens(N,V) holds iff V is the list of N queens such
that a queen is placed at cell location (V[i],i) for
i=1...N. */
queens(N, V):- true |
board(0, N, L, V, R-R).
board(K!, N!, L, V, [O|R]-[NewR|Rt]):- K < N, K1 is K+1 |
line(K1, 0, N, H, V, L, [O|R]),
%Right shift the left lines as you go
%to the next row and left shift the
%right lines, introducing a new line
%at the ends.
board(K1, N, [NewL|L], V, R-Rt).
board(K, K, L, V, R-Rt):- true | true.
line(I, Jmax, Jmax, Hl, Vl, Ll, Rl):- true | true.
line(I, J!, Jmax!, H, [V|Vl], [L|Ll], [R|Rl]) :-
J < Jmax, J1 is J+1 |
cell(I, J1, H, V, L, R),
line(I, J1, Jmax, H, Vl, Ll, Rl).
cell(I!,J!, J, I, I, I):- true & true.
cell(I!,J!, _, _, _, _):- I =/= J & true.
cell(J!,J!, H!,V!, _, _):- true & true.
/*
If it is fair to deduce from the problem specification
that there may be at most one queen per row, then the
program may be considerably simplified,a nd a set of
pure Horn clauses results. These may be executed by a
Prolog processor. Here is the pure Horn clause
specification of the N-queens problem, modulo arithmetic
done for incrementing counters from 1 ... N.*/
queens(N, V):- board(0, N, L, V, R-R).
board(K, N, L, V, [O|R]-[NewR|Rt]):-
K < N, K1 is K+1,
line(K1, 1, N, V,L, [O|R]),
board(K1, N, [NewL|L], V, R-Rt).
board(K, K, L, V, R-Rt).
line(K, N, Nmax, [K|_], [K|_], [K|_]).
line(K, N, Nmax, [_|Ll], [_|Vl], [_|Rl]) :-
N < Nmax, N1 is N+1,
line(K, N1, Nmax, Ll, Vl, Rl).
------------------------------
Date: Thu Jun 12 16:19:22 1986
From: Herm Fischer <hermix!fischer@rand-unix.ARPA>
Subject: Comments to my review of Turbo Prolog
Larry,
Thank you for replying to my review of Borland Turbo Prolog.
I have a few responses to your comments.
(1) There seems to be a question of whether Borland's is
"true" Prolog. I made the comment that the syntax is Clocksin
& Mellish, and by that I meant it was not Micro-Prolog, or
some other varient. Micro-Prolog calls itself a true Prolog
also. So what is Prolog?
Coming from the Ada community, I have become a strong believer
in Standards. Borland, UNSW, and other implementations all
provide some renaming of built-in predicates, and all provide
some varients in the semantics of the built-in predicates. We
need a standard in this area, not just some adherants of one
implementation over another. I gather from industry contacts
that the U.S. does not seem strongly motivated or even care
much to back Prolog standardization. (I understand there are
overseas efforts, but no ANSI interest.) Without a standard
blessed by some coalition of U.S. industry and government, I
have no idea of what a "true" Prolog is.
(2) Conversion of working programs to Borland involves at least
two activities:
(a) converting built-in predicate names, and
(b) imposing typing on a working program.
Being a Unix (Xenix on PC/AT) user, I am not bothered when
built-in predicates are changed; while frustrating, simple
"sed" editing scripts fix that faster than one can reach for
a cup of coffee. Perhaps the next time I do that I'll send
Restivo the "sed" script for all to use. So much for
easy work...
Imposing typing on a working program can vary from being as
easy as using an editor to strip out all "left sides" of a
:- and slightly editing them, to efforts which consume labor
like celestial black holes consume matter. A large number
of Defense Department software shops are busily converting
their software to Ada (which generally requires the same
problem of typing an untyped program). My friends mostly
tell of stories where Ada conversion efforts had to be simply
abandoned and the Ada code written from scratch. I can
concieve of Prolog situations where this is an insurmountable
problem. In my own product, I griped and coped, and felt
that the resulting product was much "cleaner" and no less
"Prolog-ish". (I did not use DCG rules or need =..) In test
cases I tried before, the editor massaging trick was
sufficient.
Turbo-Prolog typed programs should, as far as I can tell,
need only minimum filtering (in the Unix "sed" sense) to be
converted to untyped Prolog.
(3) The few cases I've tried have not run out of memory on
Turbo-P. As to your question of what other Prologs on the PC
can take, my version of the UNSW Prolog for the PC is in huge
model, which under Xenix can take up to 60% of real memory
(and most Xenix AT's now have a couple of megabytes). At
just under $100 for 1 Megabyte of PC/AT memory, who even
cares any longer...
(4) I'd be interested in speed comparisons between a wider
range of Prolog's for the PC, and similar discussions of
conversion difficulties.
(5) As to missing features, it is my personal impression
that Borland is interested and listening. I have heard
several times that they have intents (but not commitments)
to add arg, functor, and those types of features. If you
need specific capabilities, such as DCG and run-time binding
of predicates, perhaps they need to hear constructive
suggestions from the user community.
-- Herm Fischer
------------------------------
End of PROLOG Digest
********************rsk@pucc-j (Wombat) (06/21/86)
Here is another solution to the eight queens problem; I found this one
easier to understand, though others may differ on that point. It was
written by Malcolm Slaney while he was at Purdue University; he is
reachable at pur-ee!malcolm.
% All of the work is done by not_threaten, queens and validlist.
findqueens :- repeat, % Find all possible solutions
queens([[0,Y0],[1,Y1],[2,Y2],[3,Y3],[4,Y4],[5,Y5],
[6,Y6],[7,Y7]|[]]),
write([0,Y0]), write(' '),
write([1,Y1]), write(' '),
write([2,Y2]), write(' '),
write([3,Y3]), write(' '),
write([4,Y4]), write(' '),
write([5,Y5]), write(' '),
write([6,Y6]), write(' '),
write([7,Y7]), write(' '),
nl,
fail.
not_threaten([X1,Y1],[X2,Y2]) :- % Check to see if two queens are ok
not(X1 = X2),
not(Y1 = Y2),
D1 is X1-X2,
D2 is Y1-Y2,
D3 is -D2,
not(D1 = D2),
not(D1 = D3).
queens([]). % Generate Valid list of Queens
queens([[X,Y]|List]) :- queens(List),
isvalid(Y),
validlist(X,Y,List).
validlist(X,Y,[]). % Check to see if List is OK.
validlist(X1,Y1,[[X2,Y2]|List]) :- not_threaten([X1,Y1],[X2,Y2]),
validlist(X1,Y1,List).
isvalid(0). % Generate Valid Board Positions
isvalid(1). % (There must to be a better way!!!)
isvalid(2).
isvalid(3).
isvalid(4).
isvalid(5).
isvalid(6).
isvalid(7).
--
Rich Kulawiec, pucc-j!rsk, rsk@j.cc.purdue.eduu-reddy@utah-cs.UUCP (Uday U-reddy) (06/25/86)
In article <1389@pucc-j> rsk@pucc-j.UUCP (Wombat) writes: >Here is another solution to the eight queens problem; I found this one >easier to understand, though others may differ on that point. It was >written by Malcolm Slaney while he was at Purdue University; he is >reachable at pur-ee!malcolm. >Rich Kulawiec, pucc-j!rsk, rsk@j.cc.purdue.edu I think Vijay's point was to give a "concurrent" prolog program for N queens in which (debatably logical) variables are used in an interesting way.