Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!uwm.edu!csd4.csd.uwm.edu!markh
From: markh@csd4.csd.uwm.edu (Mark William Hopkins)
Newsgroups: comp.lang.prolog
Subject: Re:  general data structures are impossible
Summary: Pointer have graph theoretic semantics.  Prolog works on graphs.
Message-ID: <9729@uwm.edu>
Date: 24 Feb 91 02:02:20 GMT
References: <1991Feb15.101435.16112@ecrc.de> <17914@cs.utexas.edu> <1489@quintus.UUCP>
Sender: news@uwm.edu
Organization: University of Wisconsin - Milwaukee
Lines: 72

In article <1489@quintus.UUCP> dave@quintus.UUCP (David Bowen) writes:
>
>The point of using Prolog is to program at a "higher level" than is
>possible with languages like C; that is, to write code which is more
>closely related to the problem that you are trying to solve than to the
>machine on which the program is to be run.
>
>Pointers are a low-level concept.  The lack of pointers in Prolog is one of
>its major advantages.  Since there are no pointers there are no dangling
>pointers, and one major source of difficult-to-debug programming errors is
>entirely eliminated.

I disagree with the premise that there are no pointers in Prolog.  They're
just called something else (see below).

Anyhow...

I used to think this way several years ago too before I began to intuit and
experience the inherent relationship between pointers and associative
memory.  The conclusions of these experiences (and the consequent innovations
in my programming practice) are that pointers are an extremely high level
concept that would be used in programs whose behavior borders on the same
kind of intelligence we have.

The mathematics underlying their use is graph theory.  They're difficult to
deal with NOT because they're low-level (as if low-level things are supposed
to somehow be difficult), but because their mathematics are so substantial.

The tendency to try and cast the whole universe into trees (not to mention
directed acyclic graphs), and eliminate the inherently graph theoretical
concept of pointers only serves in the long run to re-introduce the very kinds
of redundancies that intelligence was supposed to eliminate.  Also, trying to
cast everything into trees is just a cop-out from having to do Real Graph
Theory.

For instance, I know of an efficient parsing algorithm that could be
characterized as breadth-first non-deterministic LR(k), which uses pointers in
a non-trivial way to enable such extensive sharing amongst its parse trees.
The parse graph a sentence with a 1000-fold ambiguity would take up the space
and time to create maybe 5 to 10 larger than that of the individual trees
(polynomial parsing for exponential ambiguity).

Pointers figure into this application via the concept of "aliasing" and
"sharing", which are the high-level concepts ultimately that have to do with
graph theory.

A good data base-handling program, if it needed to organize the same
information sorted several ways at once would also do this by sharing.  Each
sorted structure would be a structure consisting only of pointers to the
actual data objects.

A program I wrote to read in Context-Free Grammars's made non-trivial use of
cyclic structures to represent CFG's as cyclic AND/OR trees.  This enabled the
high-level and more or less standard set of tools for dealing with AND/OR
trees to be used in processing the grammar.

The semantics of these kinds of programs will often use the concept of
"Least-Fixed Points".  CFG's can be represented by Context-Free Expressions
(analogous to Regular Expressions) defined by mutually recursive systems
of equations involving regular expressions, whose meanings are defined by
least-fixed point semantics.  And this fact is effectively used in programs
like the one described above.

There's this inherent relation between cyclic structures and recursion.

In any case, I thought Prolog was supposed to be so powerful partly because
of the way of integrates pointers into logic programming.  Only you call them
logical variables.  Unification is really a graph algorithm in disguise...

So my perspective today is that something which does NOT use pointers or
something equivalent where associative memory or sharing is required is
low-level, rather than the opposite.