Path: utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!clyde.concordia.ca!nstn.ns.ca!news.cs.indiana.edu!samsung!cs.utexas.edu!turpin
From: turpin@cs.utexas.edu (Russell Turpin)
Newsgroups: comp.lang.prolog
Subject: Re:  general data structures are impossible
Summary: OK, not impossible, just impenetrable
Message-ID: <17899@cs.utexas.edu>
Date: 15 Feb 91 00:24:16 GMT
References: <1991Feb12.013413.24312@cs.ubc.ca> <4765@goanna.cs.rmit.oz.au> <1991Feb13.235655.6202@cs.ubc.ca> <17853@cs.utexas.edu> <1948@n-kulcs.cs.kuleuven.ac.be>
Organization: U. Texas CS Dept., Austin, Texas
Lines: 29

-----
I wrote:
>> As a computational engine, Prolog is Turing complete.  The issue
>> is not whether the application can be implemented Prolog, but
>> whether one can implement this particular data structure, with
>> its particular performance characteristics.)

In article <1948@n-kulcs.cs.kuleuven.ac.be> bimandre@saturnus.cs.kuleuven.ac.be (Andre Marien) writes:
> Don't blame Prolog; some Prologs can do it: you need support for 
> infinite terms. PrologII and PrologIII are the leading examples,
> I think.  (not that others don't have it)
>
> The following program works as requested with inf tree support:

Point taken. 

After some study, I was even able to understand how the infinite
terms corresponded to this simple data structure.  But Jesus!
H! Christ!  What is the point of putting into a *logic* language
a mechanism by which even simple data structures become impenetrable
mazes.  I suspect it would be easier to prove correct the C program,
in which the intended data structure is clear.

If a simple data structure such as two mutual referencing lists
is impenetrable in Prolog, what will become of a complex data
structure like a cone?  (A cone of depth N is N circular queues.
The i-th queue has i elements, each of which point to the first
i elements of the (i+1)-st queue.

Russell