SCOUG-Programming Mailing List Archives

>> Next Message >>

Date:	Sun, 14 Sep 2003 11:08:57 PDT7
From:	"Lynn H. Maxson" <lmaxson@pacbell.net >
Reply-To:	scoug-programming@scoug.com
To:	"SCOUG Programming SIG" <scoug-programming@scoug.com >
Subject:	SCOUG-Programming: List processing

Content Type: text/plain

I have "Let's Talk LISP" by Laurent Siklossy in my library,
another amongst a number of skimmed but otherwise unread
of my books. However, before we talk LISP we might first
talk about "lists", specifically "linked" lists.

That we have "linked" lists implies that we have "non-linked"
or "contiguous" lists. Thus lists come in one of two forms,
contiguous and non-contiguous. Though visually we may
represent a list as [7 5 11 22] an implementation in a given
programming language may have this as four numbers in
contiguous space or as four numbers in non-contiguous space
(linked). What operations we can perform upon this or any
set of values differs depending upon implementation.

We will consider non-contiguous or linked lists only here.
Linked lists themselves come in one of two forms:
single-linked (next) or double-linked (previous, next). As the
processing logic for link maintenance differs between them
we will use only double-linked examples in what follows.

We "anchor" lists, which implies that we have two entities,
the list and its anchor. An anchor consists of a structure
which contains two addresses (pointers in PL/I), one to the
first list entry and the other to the last:
dcl 1 father,
2 (first,last) ptr;

Initially we have no list entries, i.e. an "empty" list. To
represent this we set the "first" and "last" pointers in the
anchor to a "null" value:
father.first, father.last = null;
Here we have used "name" qualification as we may have
many lists, thus many anchors in a program. We need some
means to distinguish which "first" or "last" we mean in an
expression. In this instance we use the structure name
"father".

Now we need to create a list entry, a member of the list. In
this instance the entry consists of a previous and next pointer
and two character fields, for fields in all, i.e. a structure:
dcl 1 list1 based (p1),
2 (prev, next) ptr,
2 (rel1, rel2) char(20);
Now by "implication" we have declared "p1" a pointer.
Though not necessary in PL/I we will explicitly declare it:
dcl p1 ptr;

Note that "list1" has the "based" attribute. As such it exists
as a "template", whose instances "reside" wherever we have
"pointed" or "set" them. That means we have to create an
instance. We do this through means of an "allocate"
statement:
allocate list1;
This dynamically allocates space for all the fields in list1,
setting the address (pointer value) of this space in p1.

Now to follow the example in the tutorial on "Fundamental
Prolog" we want to implement "father("Bill","John"). As this
is the first entry in the list "prev" and "next" have no entries
to point to. Thus we set them to null:
list1.prev, list1.next = null;

We set rel1 and rel1 to "Bill" and "John" respectively:
rel1 = 'Bill'; rel2 = 'John';
Now we have to set the pointers (first and last) in our anchor
to the address of this entry (p1):
father.next, father.last = p1;

Now we have to create another instance for
father("Pam","Bill"):
allocate list1;
rel1 = 'Pam'; rel2 = 'Bill';
Note that p1 now "points to" the new instance. Now we have
to decide if we want to "prepend" or "append" this new entry
to the list. If we prepend it, i.e. make it the first entry on the
list, then we will create a LIFO (Last In First Out) list. If we
append it, then we will create a FIFO (First In First Out) list.
We have a third option to place an entry based on the value,
ascending or descending, of any field in the list. If we do this
we create an "value-ordered" list.

Note that these list possibilities represent queue possibilities
(FIFO, LIFO, Ordered). Thus if we issue a "put" to add a new
entry to a queue where it gets added (append, prepend,
value-based) will depend on the queue type (FIFO, LIFO,
Ordered)

Here we will choose to append new entries, i.e. create a FIFO
list. As "father.last" points to the "current" last entry we
must set the current last entry's next pointer from null to p1,
the new last entry's address:
father.last->list1.next = p1;
Here we use "pointer qualification", the double-byte "->", in
addition to "name qualification". Remember list1 is a based
variable which "resides" wherever it is pointed, in this
instance to the value in father.last, our previous p1 the
address of our previous list1 instance.

Now we want to set our new list1.prev value to the current
last entry address:
p1->list1.prev = father.last;
We set our new list1.next to null:
p1->list1.next = null;
We set the father.last value to reflect the address of the new
last entry:
father.last = p1;

For convenience let's put them all in one place:
father.last->list1.next = p1;
p1->list1.prev = father.last;
p1->list1.next = null;
father.last = p1;
We had four pointer values (addresses) to set. If I haven't
screwed up somewhere, then this is correct.

This represents an "append". We could have created a
procedure for doing this:
append:
proc (anchor, p3);
dcl 1 anchor,
2 (first, last) ptr;
dcl 1 entry based,
2 (prev, next),
2 field char(*);
dcl p3 ptr;
if anchor.first ^= null
then do;
anchor.last->entry.next = p3;
p3->entry.prev = anchor.last;
p3->entry.next = null;
anchor.last = p3;
end;
else do; /* first entry in list */
p3->entry.prev, p3->entry.next = null;
anchor.first, anchor.last = p3;
end;
end append;

We could have done something similar for "prepend" (LIFO)
and "insert" (Ordered). We could do some similar to perform a
"delete". Note also that we could have created another
procedure to invoke in any of these to "add" the first entry to
the list as the logic is the same regardless.

So it would appear that we can "prepend", "append", "insert",
and "delete" entries in a list. We should make the clarification
that we can perform them on "any" list, that lists themselves
are "generic", not "specific" like queues with LIFO, FIFO, and
Ordered.

Notice that in Intel architecture the stack is a contiguous list,
not a linked one. Thus you can overflow it. IBM software for
the S/360 family of machines use the stack only for expression
evaluation, where the maximum depth, i.e. size, needed can be
determined at compile time. For module calls, i.e. subroutine,
it uses a linked list for "stacking" them. Thus you cannot get
a stack overflow in IBM software unless (and until) you
absolutely run out of virtual storage. For a 64-bit
architecture that's like "never".

Now we haven't shown a "search", "find", "query", "select" or
anything which would scan a list for values in one or more
fields. However, I do hope that you can see that we could
implement
"grandFather(Person, GrandFather) :-
father(Person, Father), father(Father, GrandFather)"
by doing one or more sequential searches for assertions like:
?- father("Sue", "John").
?- father("Pam", X).
?- grandFather("Pam", "John").

This part of logic programming is based on simple list
processing. "Facts" with respect to a given relationship are
entries in a list. "Rules" are relationships among facts. a
"Theory" is a collection of both in support (or denial) of
"assertions". In turn these "assertions" represent "goals".
The solution of a goal may require solutions of sub-goals and
so on.

Logic programming then is based on a "goal hierarchy" in
much the same manner as the "module" or "logical" hierarchy
of imperative languages. The difference lies in who does the
"logical ordering". In imperative languages the programmer
does. In declarative, i.e. logic programming, the software
does. While it may not seem important with respect to initial
ordering (although it is), it definitely becomes so with respect
to re-ordering. It's something on the order of
100,000,000:1.

=====================================================

To unsubscribe from this list, send an email message
to "steward@scoug.com". In the body of the message,
put the command "unsubscribe scoug-programming".

For problems, contact the list owner at
"rollin@scoug.com".

=====================================================

Return to [ 14 | September | 2003 ]

SCOUG, Warp Expo West, and Warpfest are trademarks of the Southern California OS/2 User Group. OS/2, Workplace Shell, and IBM are registered trademarks of International Business Machines Corporation. All other trademarks remain the property of their respective owners.