Path: utzoo!mnetor!uunet!lll-winken!lll-lcc!lll-tis!mordor!sri-spam!sri-unix!quintus!ok
From: ok@quintus.UUCP (Richard A. O'Keefe)
Newsgroups: comp.lang.prolog
Subject: Re: Triangle Puzzle
Message-ID: <721@cresswell.quintus.UUCP>
Date: 2 Mar 88 07:35:22 GMT
References: <652@cresswell.quintus.UUCP> <1863@ubc-cs.UUCP>
Organization: Quintus Computer Systems, Mountain View, CA
Lines: 65
Keywords: Modifiable Variables, State Transition, TRILOGY.
Summary: nit-picking

In article <1863@ubc-cs.UUCP>, voda@ubc-cs (Paul Voda) writes:
>  ii) A state must be described by a complicated list even if the problem
>      naturally calls for arrays.
Neither my program nor Bart Demoen's used a list to represent a state.
A compound term in Prolog, such as the f(_,_,_,_,_,_,_,_,_,_,_,_,_,_,_)
terms I used to represent states of the triangle puzzle, *is* an array;
the space required for such a term is no more than would be required for
an array with that many elements (+/- a small constant), and read access
to elements of such a data structure is constant time.

Yes, everyday Prolog does not have array *update*, but any competent Prolog
programmer would approximate updatable arrays by trees, not lists.

> This technique applies only to such problems (maze traversal, tiling problems,
> constraint satisfaction problems, etc.)
> where the state changes exactly once for each of its parts.
> I will mention here two examples, both of which appeared in the Prolog digest:
> T. Evans's solution of the Cube Packing Problem and the Baage's solution
That's Evan Tick, not Tick Evan.

> The formula
> 
>     x := 6 & Incr(x) & Incr(x) & P(x)
> 
> is only an abreviation for the formula
> 
>     x1 = 6 & Incr(x1,x2) & Incr(x2,x3) & P(x3)
> 
Interesting!  Please explain this some more.  If I write

	x := 6 & Incr(x) & y = x & Incr(x) & P(x)

which version of x does y get?  (The answer should be obvious, but I'd like
to see how it's done.)  What if we have some larger structure, and I do

	x := NewThing & Update(x,1) & y = x & Update(x,2) & Update(y,3)

How does one avoid interference between the updates to x and y?  Or is this
disallowed somehow?  {This is also a problem with the 'var' hack in Prolog,
by the way.  It is not a problem with pure versions using trees.}

> Following is the implementation of the Triangle Puzzle in Trilogy.
Great stuff.
> i) The variables of Trilogy start with small letters. Predicates,
>   types and constants, being identified by proper names, are
>   capitalized.
As a matter of fact, words like "hole" and "board" and so on are
_common_ nouns, not _proper_ nouns, so in English orthography should
_not_ take a capital letter.  I find it very confusing that "i" is a
variable, but "if" is a keyword.  If constants begin with capitals,
shouldn't keywords do the same?

>    The first solution is found on an 8MHz AT in 0.8 seconds as follows:
Sounds good.

>  vii) The reader will note that the arrays of Trilogy allow fast indexing
>     as opposed to the list traversal of Prolog.
Just a reminder:  Prolog doesn't require the use of lists for anything,
and a good Prolog programmer would not use them here.

But let's hear more about Trilogy.  Have I understood correctly that an
'in' or 'in out' parameter, cannot be unresolved, so that if the actual
parameter is defined by constraints, those constraints must be solved
before the call can happen?  Does this mean that an 'in' or 'in out'
parameter must be completely ground, or may such a parameter contain
constrained elements?