🚀 go-pugleaf

In article <1991Feb19.235323.7748@newcastle.ac.uk>, Chris.Holt@newcastle.ac.uk (Chris Holt) writes:
> ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes:
> >What, for example, is the task for which `cones' are an appropriate
> >tool?  (I've never met them before, so this is a genuine question.
> >From the brief description we've had so far, I've no idea what they
> >represent or what the operations on them are.)

> Not cones, exactly, but: 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.  Does this help?

No, it doesn't help, and that for two reasons.
1) "cones" were presented as an example of something Prolog *should* do.
   It doesn't help to explain something else instead.
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.  Assuming this interface
it is very simple to implement the required mappings.  Assume that
we have
	empty_mapping(-EmptyMapping)
	lookup_mapping(+Key, +Mapping, -Val)
	update_mapping(+Key, +OldMapping, +Val, -NewMapping)
We'll represent an instance of this problem by a pair
	db(ST, TV)
where ST is a mapping which maps names to representatives (think
UNION-FIND) and TV is a mapping which maps representatives to values.

	empty_data_base(db(E,E)) :-
		empty_mapping(E).

	create_data_base_cluster(Keys, db(ST0,TV0), Val, db(ST,TV)) :-
		/* from library(Ordered), picks the smallest */
		min_member(Representative, Keys),
		update_mapping(Representative, TV0, Val, TV),
		update_cluster(Keys, ST0, Representative, ST).

	update_cluster([], ST, _, ST).
	update_cluster([Key|Keys], ST0, Representative, ST) :-
		update_mapping(Key, ST0, Representative, ST1),
		update_cluster(Keys, ST1, Representative, ST).

	update_data_base(Key, db(ST,TV0), Val, db(ST,TV)) :-
		lookup_mapping(Key, ST, Representative),
		update_mapping(Representative, TV0, Val, TV).

	lookup_data_base(Key, db(ST,TV), Val) :-
		lookup_mapping(Key, ST, Representative),
		lookup_mapping(Representative, TV, Val).

The asymptotic cost of these operations is determined by the
asymptotic cost of the "mapping" operations, which depends on what
sort of indexing you have available.  Given that you have to enter
and look up the keys *somehow*, the absolute maximum that some
non-logical construct could buy you would be a factor of two.

If you want to add new equivalences dynamically, a UNION-FIND data 
structure is appropriate for ST.

I don't quite grasp what "one cannot create an entire new copy of the
data base with the updated value" means.  That is precisely what one
normally does in Prolog, EXCEPT that the new copy shares most of the
structure of the old.  If I do
	X = db(ST,TV0),		% unpack X
	foo(...TV0...TV...),	% make a "new copy" of TV
	Y = db(ST,TV)		% construct Y
then the "ST" component of Y will be the same physical storage structure
as the "ST" component of X, and in practice, virtually all of TV will be
shared with TV0.  It turns out that in Prolog, updating data structures
involves building new ones, thus turning over garbage, but that has low
cost in good implementations.

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.

I am a bear of very little brain.  I can understand quite well what it
means to have several mappings, but cyclic data structures confuse me
in _any_ programming language.  I have used Lisp systems that could
print cyclic terms (CIRCLPRINT in InterLisp) and I'm afraid that anyone
who calls X = #1=[a,#2=[#1^]|#2^] or the like "readable" is considerably
more intelligent than I.  {Read #n= as defining n, #n^ as referring to n.}

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

-- 
The purpose of advertising is to destroy the freedom of the market.