Subject: RE: UNDERSTANDING LISTS

From: andrew <[email-masked]>
Date: Tue, 2 May 2000 09:38:28 +0300

Hi,

My apology to SWI Prolog mail readers since this stuff is not too 
SWI-specific. Anyway, I think it can be interesting to all Prolog 
programmers/developers.

Speaking of the access to middle elements of a list, I meant 
pattern matching for lists rather than access to the element placed 
exactly in the middle of the list. In Planner language, pattern 
matching was done when calling "daemons" - antecedent and 
consequent theorems (i.e. procedures): when some list L is added
or deleted from the Planner database, a theorem, whose head =matches= 
list L, is called automatically. This is similar to Prolog clause 
call: if a clause head matches the goal or a temporarily generated 
sub-goal, then the clause body is activated. However, in Prolog, 
matching is done for terms with finite arity, not for unconstrained 
lists (I'll discuss this limitation below).

Refal and Snobol (as far as I remember) are based entirely on list 
matching; the lists may contain atoms, variables and operators, which 
constrain matching. Besides, (in Planner) a variable may match not only
a member but also a segment of the matched list. Unlike Prolog, the 
mentioned languages treat lists not only as "something beginning from 
the only directly accessible part" but as "something that can interact 
with something else as a whole". I suspect that limitation of Prolog, 
related to this, has resulted in its unpopularity: remember that 10 
years ago it was extremely popular, but 5 years ago most people regarded 
it as a dead language, and I am not sure it comes to popularity now. 

Once more, imagine that you are programming in C or Pascal, and somebody 
is forcing you to use stacks instead of arrays. You think of a sequence 
as of an entity, but have direct access only to its first element 
(probably you will have to write something like member/2, append/3, 
reverse/2 etc to operate with these objects as with entities). My (not 
too small) experience with Prolog lists reminds the same: I think of a 
list as of an entity, but have direct access only to its first elements. 
Probably I should not use Prolog lists, but I don't have other options
for working with sequences. Sampletalk is an attempt to bridge this gap: 
you build a program in Prolog style, but your objects (called "samples") 
interact more fluently as entities, not only via their first elements.

[H | T] notation probably resulted as implementation of Peanot's formal 
arithmetic, and needless to say that understanding a sequence of 
entities x1, x2, x3 ... as a functor .(x1,.(x2,.(x3,.(...))) is 
unnatural and non-intuitive when modeling simple things. 

Why both [H1,H2,...,Hn | T] and F(a1,a2,...,aN) notations in Prolog? 
Remember that (a1,a2,...,aN) is =list= of arguments. Is it possible to 
do without arg/3 and univ/2 and operate with these objects in one 
universal manner? Sampletalk =samples= can be considered as 
generalization of  [H | T] and F( , , ,) notations into one universal 
notation, and this results in almost unconstrained object interaction. 

Pattern matching as operation on lists is more general than logic term 
unification. Indeed, you can literally consider logic term F( , , ,) as 
a =sample= or represent it as a Planner list. Matching of this object to 
other such objects, in terms of Planner or Sampletalk, will be exactly 
Prolog term unification. 

So (I think), treatment of lists is a weak point of Prolog language, which
causes difficulties in UNDERSTANDING LISTS for novices, and this is exactly 
because you have direct access only to the first elements of a list. (I 
hope this observation can help in the UNDERSTANDING LISTS). Let's remember 
classic recursive definition of lists: a list is either an atom or an 
ordered sequence of lists. You can reformulate this as follows: A list is 
either
 - empty, in which case there is nothing else to know
 - or non-empty, in which case it has a first element and
   a sequence of remaining elements.

These two definitions are formally equivalent (provided definition of 
atoms, as basic elements, and recursion), but the last one makes us 
concentrated on the first element of the list rather than on the entire 
list. I prefer thinking of lists as of entire objects (with segments), 
that may interact with other objects (containing segments of interest), 
but Prolog limits my ability in doing so, or rather provokes me writing 
sophisticated calls of append(...), member(...) etc for getting to
the segments of interest.

The promised example of sophisticated calls will appear immediately if 
you will try to translate almost any of 37 Sampletalk program examples 
into Prolog. Try doing this, for example, for NL processing or Logic 
formula transformation examples, or compare Clocksin & Mellish's classic 
Parts Inventory program to its Sampletalk equivalent.

Thanks for reading all this 
Regards
Andrew Gleibman
Sampletalk: Build a program immediately from data processing examples 
http:\\sampletalk.8m.com

-----Original Message-----
From: Richard A. O'Keefe [mailto:[email-masked]]
Sent: Friday, April 28, 2000 2:36 AM
To: [email-masked]; [email-masked];
[email-masked]
Cc: [email-masked]
Subject: RE: UNDERSTANDING LISTS

	I think Prolog lists is not too intuitive logic model of a
	sequence of entities - they probably resulted as an attempt
	to incorporate something similar to arrays in logic. 
	
WRONG.

Prolog lists are identical to lists in (pure) Lisp, ML, Haskell, Clean,
Hope, NPL, lots of other things.  Lists of this kind are the standard
way to represent sequences in declarative languages.

In particular, they are *not* intended to resemble arrays.

A sequence is either
 - empty, in which case there is nothing else to know
 - or non-empty, in which case it has a first element and
   a sequence of remaining elements.

Turn that into a DEC-10 Prolog type definition:
 :- type list(T) --> empty | non_empty(T, list(T)).
Now you have Prolog lists, except for the spelling of the functors.

Simple, declarative, about as far from arrays as you can imagine.
It is the simplest possible data type that can do the job.

Come to think of it, if you look up "linked list" in a Pascal
data structures book, you'll be told about

    type
	ListElt = Char;       (* or whatever you want *)
        ListPtr = ^ListRec;
        ListRec = record Tail: ListPtr; Head: ListElt end;

    function Cons(Head: ListElt; Tail: ListPtr): ListPtr;
        var Result: ListPtr;
    begin
	new(Result);
	Result^.Tail := Tail;
	Result^.Head := Head;
	Cons := Result;
    end;

which is precisely (a mutable version of) Prolog/ML/Lisp lists.

	The bad thing is that, on the high level, there is no essential 
	difference between a list and a stack (although stacks keep
	only plain numbers).

Yes there is.  To start with, stacks have nothing to do with numbers.
More importantly, "stack" is an ABSTRACT data type providing operations
"make empty stack, is empty stack?, push, pop".  But "list" is a
CONCRETE data type.

	In our intuition we apply to middle and 
	last elements of a list, but Prolog limits our access only to 
	the first elements.

Well, intuitions vary.  [] hasn't any middle or last element.
Prolog does NOT limit your access to only the first element.
It only provides _direct_ access to the head and tail, but precisely
the same is true of standard linked lists in Ada, C, C++, Pascal, ...

	last([H|T], X) :- last_(T, X, H).
	last_([], X, X).
	last_([H|T], X, _) :- last_(T, X, H).

I don't know what is the middle element of a even-length list.

	As the result, you see sophisticated calls of 
	member(...), append(...), concat(...) etc when doing trivial 
	things with sequences of entities (ses below).
	
Just as you would in Pascal or Lisp or Haskell or Clean or ...

	Imagine that you have to use stacks instead of arrays in C or 
	Pascal: you still can work with sequences of things, but your 
	access to middle elements will be painful.
	
Lists are not and were never intended to be a substitute for arrays.
If you want a substitute for arrays, use a 3+4 tree.

	Access to middle elements of a list was made in Planner, 
	Snobol,

It's a long time since I read the Planner manual, but Planner used
Lisp syntax.  I know SNOBOL fairly well, and it DOESN'T provide access
to middle elements of a list.  SNOBOL has arrays.  It also lets you
define standard linked lists, but does NOT offer you any special
access to middle elements.

We were promised an example of "sophisticated calls ... when doing
trivial things".

	 As the result, you see sophisticated calls of 
	member(...), append(...), concat(...) etc when doing trivial 
	things with sequences of entities (ses below).
	
The example never materialised.
And it never materialised for a very simple reason.
It is *easy* to do trivial things with lists in Prolog.
Not many things can be done with simple pattern matches,
but that's true of any data structure.

----------------
* To UNSUBSCRIBE, please use the HTML form at

    http://www.swi.psy.uva.nl/projects/SWI-Prolog/index.html#mailinglist

or send mail to [email-masked] using the Subject:
"unsubscribe"
(without the quotes) and *no* message body.

** An ARCHIVE of this list is maintained at

    http://www.swi.psy.uva.nl/projects/SWI-Prolog/mailinglist/archive/