Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!spool.mu.edu!uunet!munnari.oz.au!goanna!ok From: ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) Newsgroups: comp.lang.prolog Subject: Re: general data structures are impossible Message-ID: <4818@goanna.cs.rmit.oz.au> Date: 25 Feb 91 07:21:57 GMT References: <1991Feb12.013413.24312@cs.ubc.ca> <4765@goanna.cs.rmit.oz.au> <1991Feb19.235323.7748@newcastle.ac.uk> Organization: Comp Sci, RMIT, Melbourne, Australia Lines: 104 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.