Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!elroy.jpl.nasa.gov!sdd.hp.com!spool.mu.edu!uunet!mcsun!ukc!newcastle.ac.uk!turing!ncmh
From: Chris.Holt@newcastle.ac.uk (Chris Holt)
Newsgroups: comp.lang.prolog
Subject: Re: general data structures are impossible
Message-ID: <1991Feb28.153621.3524@newcastle.ac.uk>
Date: 28 Feb 91 15:36:21 GMT
References: <1991Feb12.013413.24312@cs.ubc.ca> <4765@goanna.cs.rmit.oz.au> <1991Feb19.235323.7748@newcastle.ac.uk> <4818@goanna.cs.rmit.oz.au>
Sender: news@newcastle.ac.uk
Organization: University of Newcastle upon Tyne, UK, NE1 7RU
Lines: 69

ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes, in response to
my rather confused attempt to describe when circular data structures
might be useful:

>>       [Chris Holt]       Given a large data base, with many ways
>> of accessing a given piece of data (e.g. "snow" can be accessed
>> via "white", "crystalline", and "cold"); where updates are allowed
>> (since one cannot create an entire new copy of the data base with
>> the updated value).  There has to be an axiom that insists that
>> the terminus of all the access paths is always the same.  And the
>> usual declarative model, although fine for trees, isn't good enough
>> for graphs.

>2) The response is rather vague, so I am far from sure that I understand
>   it.  As I understand it, we have two mappings:
>	st : strings -> termini
>	tv : termini -> values
>   and an interface like
>	fetch(s:string) = s.st.tv
>	create(L: string*, v: value) is
>	    t := NEW terminus; t.tv := v; for s in L do s.st := t
>	update(s:string, v:value) is s.st.tv := v
>   modulo hand-waving.

>Cyclic terms have nothing to offer for this problem; indeed cyclic
>terms only make updates very much harder.

The problem involves cycles when values contain strings and/or termini.
E.g. where "snow".st returns a terminus and "snow.st.tv" returns
a value that is a function, whose domain includes name and properties:
        "snow".st.tv.name = "snow"
        "snow".st.tv.properties = {"white","crystalline","cold"}.
We can also have substances in value domains:
        "white".st.tv.substances = {"snow","paper","salt"}
        "crystalline".st.tv.substances = {"snow","salt","diamond"}
        "cold".st.tv.substances = {"snow","liquid nitrogen"}
        "frozen".st.tv.substances = {"snow","ice cream"}.
Now suppose we want to add that snow melts at 32 degrees F.  We
create a new value,
        "snow".st.tv + (melting_point -> 32_degrees_F)
where the latter just indicates a mapping from one value to the other.
We can create a new terminus if we know everything that returns the
old "snow".st as its value; in general, this may be difficult.  As
I've written it above, everything goes through "snow", so we can
change "snow".tv without worrying about dangling references;
        (("white" and "frozen").st.tv.substances).st.tv.melting_point
yields 32_degrees_F (where the and indicates intersection).

Don't read too much into this, I wasn't trying to be very profound.

>Nor is it clear to me what "the usual declarative model" is supposed to
>be, nor in what way it fails for graphs.  The usual declarative model of
>a graph is a pair containing a set of nodes and a set of edges (that's
>what all the textbooks I checked use) and that works just fine.

If one can get from node x to another node via either path a or path b,
there is an implicit invariant x.a=x.b.  Creating a new graph by
        x.a := new_node_value
doesn't maintain the invariant; that's all I meant.

>I am still interested in a *clear* description of
> - what "cones" _are_, and
> - what they are _for_.

Russell Turpin posted this; I assume you saw it.
-----------------------------------------------------------------------------
 Chris.Holt@newcastle.ac.uk      Computing Lab, U of Newcastle upon Tyne, UK
-----------------------------------------------------------------------------
       "A peace I hope with honour." - Disraeli 1878