Subject: RE: UNDERSTANDING LISTS

From: "Richard A. O'Keefe" <[email-masked]>
Date: Wed, 3 May 2000 13:25:38 +1200 (NZST)

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.

Ok, this sounds like the kind of stuff in Interlisp, where a list
pattern can contain
 - literals
 - element patterns ?...
 - segment patterns $...

When I went to study at Edinburgh, I spent a couple of weeks figuring
out how to translate such things to Prolog (there are quite a few
details to consider).  I worked out how every aspect of Interlisp's
one-way matching could be handled.

And then I realised I just plain didn't *want* Interlisp patterns any more.
I liked the Prolog way better.

Which was a good thing, because unification is bidirectional, and
unifying patterns that contain segment variables is rather tricky.
If I remember correctly (which I probably don't) it's one of the
cases where unification can have infinitely many different answers.

	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: 

well, no.  It's more like

    planner_assert(Fact) :-
        \+(
	    functor(Fact, F, N),
	    functor(Test, F, N),
	    numbervars(Fact, 0, _),
	    clause(Test, true),
	    numbervars(Test, 0, _),
	    Test == Fact
	),
	assert(Fact),
	(  forward_chaining_rule(Fact, Action),
	   run(Action),
	   fail
	;  true
	).

	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.

I know nothing of Refal.
But I do know Snobol quite well (and still use it).
This is completely untrue of Snobol.
Pattern matching in Snobol *only* applies to character strings,
which are not any kind of list.
What's more, it is ONE-WAY pattern matching, NOT unification.

Snobol patterns are basically the same as Prolog DCGs, not single
unifications.  They even have ! (FENCE) and fail (FAIL).

	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'm sorry, but I don't understand that.  Prolog treats lists just exactly
like any other data structure.  They are values, and all Prolog values are
rooted labelled trees (ok, ok, so they're really cyclic graphs thanks to
the omission of the occurs check).

	I suspect that limitation of Prolog, 
	related to this, has resulted in its unpopularity: 

That cannot be true.  How popular are Planner, Refal, and SNOBOL?
Come to that, how popular is Interlisp?

Remember, I've *used* segment variables in Lisp, and rapidly found that
Prolog was simpler to use and more powerful.

	remember that 10 years ago it was extremely popular,

10 years ago I was working at Quintus; we were keenly interested in
the popularity or otherwise of Prolog, and I can assure you that any
claim that Prolog was "extremely popular" 10 years ago is untrue.
Prolog was much *talked about* 10 years ago, but then, 10 years ago,
it was (seen as) new.

Quintus's sales and marketing people were saying back then that Prolog's
biggest threat was C++.  If they were still in the Prolog business now,
they'd be saying that Prolog's biggest threat was Java.

	but 5 years ago most people regarded 
	it as a dead language, and I am not sure it comes to popularity now. 
	
This sounds like another factoid.  The vast majority of people in the world
have still never even _heard_ of Prolog.  With the built-in Prolog interpreter
in Windows NT (no kidding! it was used for configuration. I don't know if
it's still there) there may be more Prolog systems in use than ever before.

It would be absurd to imagine, and is absurd to claim, that Prolog lost
popularity because of the way it handles lists.  It's the *same* as Lisp,
Scheme, Haskell, Clean, SML, O'Caml, and even the *same* as singly linked
list handling in Pascal, Ada, or C.  The real issues were

    - thanks to a steadfast and explicit contempt for existing Prolog
      users, the ISO Prolog standard was delayed for an inexcusable
      length of time while the committee bickered about whose taste
      would dominate the changes.  For example, a textbook was published,
      based on ISO Prolog.  By the time the standard came out, it was
      very very different.  Because of this, the Prolog market remained
      fragmented.

    - Prolog vendors never got together to produce a common library
      specification.  I pleaded for this at Quintus.  One has to admit
      that the ELKS 95 specification for the Eiffel library is pretty
      minimal, but it's *something*, and it's more than Prolog has ever
      had.  Again, because of this, the Prolog market remained fragmented.
      (Heck, one Prolog vendor was even incompatible with itself!  Their
      PC product and their Mac product disagreed even about whether the
      argument of sin() was in degrees or radians.)

    - Prolog doesn't have assignment statements.  This is deeply upsetting
      to most programmers.  *No* declarative programming language has
      achieved popularity.

    - Prolog doesn't look like C.

    - Flavour-of-the-month-itis.  There is a rather touching belief in the
      programming world that _someone_ is going to find the silver bullet
      one day.  You try Prolog and find that it's just this programming
      language, y'know; more productive than most, less error-prone than
      most, but it's really not a silver bullet.  Hey, maybe this object
      oriented thang's the silver bullet!

    - The expansion of the net.  Programmers started wanting HTML parsers,
      CGI support, CORBA interfaces, interface to Active/X, you name it.
      Most Prologs didn't have it, and most of these interfaces were
      really designed with assignment-based languages in mind.  Take the
      W3C's Document Object Model, for example.  It couldn't be less
      suited to implementation in a declarative language if they'd sat
      down and worked it out on _both_ hands for a month.

    - The expansion of Microsoft.  One Microsoft author has made it clear
      that they had a policy of rapid change to keep all possible
      competitors wrong-footed.  Programmers developing for the Wintel
      platforms reasonably demanded fairly tight integration, which is
      very costly to develop and maintain.  Most Prolog companies didn't
      have the resources, so Visual C++, Visual Basic, Visual J++ and
      so on looked rather more attractive.

	Once more, imagine that you are programming in C or Pascal, and somebody 
	is forcing you to use stacks instead of arrays.

No I shan't.  This is a COMPLETLE AND TOTAL RED HERRING.

	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).

Here is how I access the Nth element of a sequence in Smalltalk, Java,
and Prolog:

	x := seq at: i.		"Smalltalk"
	x = seq.elementAt(i);	// Java
	nth0(I, Seq, X)		% Prolog

Given some version of the DEC-10 Prolog library, which, remember,
has been freely available since about 1982,

	ACCESS TO AN ARBITRARY LIST ELEMENT IN PROLOG
	IS AS EASY AS OR EASIER THAN ACCESS TO AN
	ARBITRARY VECTOR ELEMENT IN JAVA.

I didn't say "as _fast_ as", but "as _easy_ as" it certainly is.

Or take IBM's "Vm/Programming in Logic".  It has arrays.  Did that
make it a runaway success?  Nope.

	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.

That is totally false.  The Quintus library contains two others:
library(array)	constant expected time access to and update of elements
library(logarr) extendable arrays with logarithmic access time.
These things come from the DEC-10 Prolog library; library(array) came a
bit later so I can only claim that they have been freely available since
1983.
My book describes yet another: N+K trees.
And nothing stops someone designing their own data type.

	[H | T] notation probably resulted as implementation of Peanot's formal 
	arithmetic,

I have explained where [H|T] notation came from.  There is no need to
make up stories when the truth is known.

Marseilles Prolog used
	a.b.c.nil
for lists.  DEC-10 Prolog was developed at Edinburgh, where the developers
were experienced users of Pop-2.  Pop-2 list syntax uses square brackets,
but lacked the vertical bar.  Early DEC-10 Prolog syntax for lists was
in fact
	[X,Y,..T]
That is, the equivalent of Lisp's dot was ", ..".  Where does this notation
for lists come from?  Well, it's English, except for the use of square
brackets (which is Pop, and is needed to distinguish list brackets from
expression grouping parentheses).  Ultimately, it goes back to Lisp.

McCarthy certainly _was_ well aware of Peano's (not PeanoT's) axiomatisation
of the natural numbers, and may well have been influenced by it, but so what?
IPL-V had lists too.

	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. 
	
.(x1,.(x2,.(x3,.(...))) is not a functor.
(.)/2 is a functor.

This is really a very curious claim.
IF ANYONE WANTS TO THINK OF A LIST AS A SINGLE THING IN PROLOG
THEY ARE AT LIBERTY TO DO SO.
It's just like using vectors in Java.
There is no pattern matching syntax for vectors in Java;
you do everything using method calls.
Ok, you can do the _same_ things using predicate calls in Prolog.
The list cells aren't what you use for modelling,
they are just what a list is _made_ of.

	Why both [H1,H2,...,Hn | T] and F(a1,a2,...,aN) notations in Prolog? 

Because they do very different things.
You can only use f(T1,...,Tn) when you KNOW what n is.
It's the equivalent of a record.
You use lists when you *DON'T* know what the length is going to be,
especially when you want to build one incrementally.

	Remember that (a1,a2,...,aN) is =list= of arguments.

No it isn't.  It's a *tuple*.  Indeed, in Sigma Prolog and Poplog it
is or was *implemented* as a tuple, for good reason.

	Is it possible to 
	do without arg/3 and univ/2 and operate with these objects in one 
	universal manner?

It is obviously *possible*.  In fact Prolog *does* operate with those
objects in one universal manner, precisely because lists are just a
special case of absolutely ordinary terms.  What's more, there are any
number of Prolog dialects (micro-Prolog, LM-Prolog, and ScheLog are just
the first that spring to mind) which use lists for everything.  But that
sacrifices one of Prolog's debugging advantages, and in PRACTICAL terms
is no gain.

	So (I think), treatment of lists is a weak point of Prolog language,

In practical terms, this is not so.
Novices seem to learn how to handle lists perfectly well in Scheme and
Miranda, which use exactly the same list structure.
It's a typical aspect of declarative languages:  if you are willing to
learn the thing on its own terms, it is perfectly workable, but if you
insist on treating it as something else, you'll have trouble.

	Let's remember classic recursive definition of lists:  a list is
	either an atom or an ordered sequence of lists.

I have been familiar with lists since reading Knuth's AOCP volume 1,
not long after it came out.  I have never seen that definition before.

	You can reformulate this as follows:
	[the definition I posted]
	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),

No, they are not.  They are not only not equivalent, they are not COMPATIBLE.

Note also that the former definition appeals to the concept (ordered
sequence) that it is supposed to be defining.

	sophisticated calls of append(...), member(...) etc for getting to
	the segments of interest.
	
append/3 and member/2 are hardly *sophisticated*!.

	The promised example of sophisticated calls will appear immediately if 
	you will try to translate almost any of 37 Sampletalk program examples 
	into Prolog.

So where are they?  I'm very busy, so post just 3 of them, and I'll see
what I can do.  Note:  I feel free to use any of the Quintus library
predicates.