Re: Ann: SWI-Prolog 7.1.0

On 28/11/2013, at 5:30 AM, Alan Baljeu wrote:
> 
> This argument demonstrates that atom(X) and empty_list(X) are unneeded in 
> well-designed code.  However, I fail to see the argument that atom([]) 
> is essential or good and not just a historical relic.

Let me try one more time.

(There is a link
http://www.cs.otago.ac.nz/cosc345/2013-A/L08-notes.htm#record
mentioned about half way down.  It's not about Prolog, but it
is germane.  I would be grateful for feedback about it.)

The idea is a straightforward steal of "sum-of-products" data types
from Cartwright's typed Lisp, Edinburgh ML, NPL, and HOPE.  (Other
languages since then have the same idea, notably SML, Haskell, F#,
Clean, Goedel, and Mercury.)

Step 1.  You have a vague idea of representing some kind of
information.  Consider all the case analyses you think you will
need to make.

Step 2.  Give each of these an intention-revealing name.
>>>>>> This name will be an atom, because it will be used
>>>>>> as the function symbol of a term.

Step 3.  For each of these cases, what are the pieces of information
that you will need?  Give each piece a variable name that you will
usually use as the stem of a variable to match it. [The variable
name part is not in Craft.]

Step 4.  Make these pieces of information the arguments of
its term.  If there are no arguments, the term will be an atom.
If there are arguments, it will be a compound term.

Step 5.  If there is only one case, and it has precisely one
piece of information, eliminate the wrapper.

Step 6.  Write down your design.  If you have the DEC-10 Prolog
type checker, or you using Mercury or Goedel, you can write it
as code to be enforced.  Otherwise write it as a comment.  Add
any extra information you cannot represent this way as comments,
such as the precision or range of numbers.

There's a web page I wrote for a software engineering course
that talks about this.
http://www.cs.otago.ac.nz/cosc345/2013-A/L08-notes.htm#record
That second considers adequate documentation for a
(latitude, longitude, height) record defined in Ada, PL/SQL,
and C.

Step 7.  This was pointed out by Leon Sterling.  Because you
constructed your data type to be suitable for the case
analyses you need to make, the shape of your code will tend
to mirror the shape of the data structure.  It's a good idea
to write a predicate that you can use to check that an
instance of the data type is well formed, including the bits
you had to leave as comments.  This is not wasted effort.
You will be able to use it in debugging.  It will also serve
as a template that you can revise for various other tasks.

Step 8.  Not written down anywhere, but revise, revise, revise.

So let's consider designing a sequence data type.

A sequence can be two or more elements,
or one element,
or no elements.

Let's call the first case 'two_or_more',
the second case 'one', and the last case 'zero'.

In the first case, the things to know are the
first element (let's call that X1), the second
element (let's call that X2), and the remaining
elements (let's call that Xs).

In the second case, the thing to know is the
one element (let's call that X).

In the last case, there is nothing else to know.

/* type list2(T)
   ---> two_or_more(T, T, list2(T))
      ; one(T)
      ; zero.
*/

is_list2(Xs) :- var(Xs), !, fail.
is_list2(two_or_more(_,_,Xs)) :-
    is_list2(Xs).
is_list2(one(_)).
is_list2(zero).

Hmm.  For Prolog, it's usually a good idea to put
base cases first.

member2(X, one(X)).
member2(X, two_or_more(X1,X2,Xs)) :-
   ( X = X1 ; X = X2 ; member2(X, Xs) ).

append2(zero, Ys, Ys).
append2(one(X), Ys, Zs) :-
    append2_1(Ys, X, Zs).
append2(two_or_more(X1,X2,Xs), Ys,
        two_or_more(X1,X2,Zs)) :-
    append2(Xs, Ys, Zs).

append2_1(zero, X0, one(X0)).
append2_1(one(X1), X0, two_or_more(X0,X1,zero)).
append2_1(two_or_more(X1,X2,Xs), X0, two_or_more(X0,X1,Zs)) :-
    append2_1(Xs, X2, Zs).

And there we have the beginnings of a list data type that
has been unrolled by a factor of two.

If a compound term with N arguments costs N+1 words,
and lists are not a special case, then
a plain list with L elements costs 3L words,
and an 2-unrolled list costs 2L words.

Unrolling a list by a factor of k means that you get
k elements in k+2 words, for a cost of 1 + 2/k words.
I've used unrolling by 4 when I wanted to keep space
down and wasn't doing that much appending.

Now here's the thing.  We have designed our unrolled list.
Prolog would let us distinguish by name+arity, but this
technique gives EACH case a unique name, WHICH IS AN ATOM.

How are plain lists different from this?

THEY AREN'T.  They have special *syntax*, but the
run-time *data structure* is just a sum-of-products
data structure with each case labelled by a different
atom.

And that's the point.  There is this simple practice for
designing data structures which tends to result in
understandable and efficient code.  And there is built
in support for lists WHICH USES PRECISELY THAT APPROACH.
There aren't two ways to design possibly-recursive data
structures, one for lists and one for everything else,
but *one* approach.

What good reason, then, could there be for making lists
*not* an instance of the general approach.
Why make '[]' a special case  without making the atom 'zero',
used here, a special case?

Well, there is an excuse.  The argument goes that it is
hard to tell the code list "" from the atom [].

The problem with that argument is that in the *SAME* set
of changes that breaks [], THIS ARGUMENT GOES AWAY FOREVER,
because "" will be an empty string, not any kind of list.
All confusion between "" and [] will be gone forever,
WITHOUT doing anything to [].

With the change of "" from lists to strings,
almost all of the reason to do anything about [] went away.
All the reasons for _not_ changing it remain.