Subject: RE: UNDERSTANDING LISTS

From: "Arun Majumdar (Genumerix)" <[email-masked]>
Date: Fri, 28 Apr 2000 03:04:34 -0400

Hi,

This is for all those students out there - and with many thanks to the
wisdom of Richard O'Keefe who so patiently has (indirectly in my case,
through his works) helped us all.  Excuse the long-windedness - I have been
a user for some time, and I never post - except this once, as I feel it
bears some thought and that there may be an underlying pattern to think
about.

Lists in Prolog are no different than any other data structure (I personally
see all data structures as abstractions - but that point is quite fine).

In order to access middle-elements of finite prolog lists with great speed,
you can maintain nested sets of differences (lists), so that a binary bit
string will yield, in one go, the address you are looking for --- whether it
is the middle element or any other element (see the graphics GEMS books for
many such cool algorithms - although these are for C-coders, the same
applies for Prolog - good algorithms and tricks are good anywhere).

All computer programming languages provide various models of how we want
things done --- so, the idea of saying that doing lists in prolog was some
attempt at doing something else is a bit off the mark --- in fact, lists,
stacks, queues, arrays and strings are all structures with a certain pattern
of data indexing: what is different is the indexing algorithm and what is
different are the names we give to these different ways of indexing.

Learning to rely on the given solidity and the good foundations of a secure
programming language is a sign of experience: sometimes, when we are
learning a new language, some may tend to question efficacity: at these
times, it is always good to remind oneself that the alternative choice, is
assembly or hexadecimal.   Personally, I prefer Prolog and C++.

Using operator notation for list manipulation will remove the apparent
complexity (same as you would do in C++).  Encapsulation and modular design
with well thought out algorithms will do more to increase speed than
assembly code programming than in a brute force approach.

Prolog offers a programmer a unique opportunity to truly meet their minds
challenge: if you open yourself up to the idea of looking, of observing, of
watching the essential programming patterns, the underlying idioms which all
use metaphors (ex: objects, processes, events, "fly-weights",
object-factory, "envelopes", handles etc...), then you can begin to really
use the power of Prolog in far more sophisticated and beautiful ways than
just struggling with homeworks of "append" or "lenght" and other such
excercises.  This is because Prolog is the ultimate language of metaphors
and idioms for programming  --- the beginner will have difficulty very often
because it means that you have to choose a metaphor or an idiom and stick
with it --- in fact, good object oriented design relies on patterns of
programming, and most very experienced programmers, when shown how patterns
apply in prolog, will immediately see the benefits of this language in any
domain of pattern oriented object programming (sophisticated call-flow
management, scheduling, knowledge management, etc...).

C++ is a great language too: I use it for GUI's, Client-Server, Systems
Level and hardware interfacing.   Prolog with C++ is even better, depending
on your application.

The key idea here is the word APPLICATION.  All programming languages have
certain syntactical features that help us to formulate our program goals in
various ways.  Prolog was designed to bridge the gap between purely
procedural and declarative programming ---- in fact, the very best C++
programs do just that.  Perfectly designed objects interact through their
interfaces only, and produce results through strictly defined return
mechanisms.  In Prolog, this is the de-facto way to work.  Instead of
objects as in C++, you have predicates.  For object-oriented prolog, which
by the way may be more "sophisticated" than C++ because of the support
mechanisms for other types of work (you could do it in C++ too), you can
look at LogTalk, and at BinProlog Objects and at other such systems.

Schoolwork is sometimes best done with a partner to discuss and understand
and solve problems: we learn by interaction --- posting questions to a
prolog system user list is relying on the gentility of its members (which is
another form of interaction).  However, struggling with a problem and, in
particular, struggling with someone else to solve the problem, is the best
way to learn and for things to really "sink" in.

The internet is a great library, and its use-groups are wonderful: however,
I personnally would like to see that effort has been made before posting a
question to a user group --- the user group, I believe, is there for the
specificity of SWI prolog and its particularities and particular uses under
trying circumstances.  This does not mean that "homeworks" are not welcome,
it just means that I suggest some teamwork and thought prior to using a news
group --- create your own "user" groups on campus --- code "demos", have
fun --- programming is a human activity, and in any serious effort, you will
have to work in teams, not alone.  So start now.

BUT: When all else fails, a news group is there to answer some questions.

Thank you for your patience in my long-winded note.

-Arun Majumdar
Genumerix Inc.

----- Original Message -----
From: Richard A. O'Keefe <[email-masked]>
To: <[email-masked]>; <[email-masked]>;
<[email-masked]>
Cc: <[email-masked]>
Sent: Thursday, April 27, 2000 9:36 PM
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 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/