Re: RM and abstract syntax trees
Date: Sun, 11 Nov 2007 19:45:22 -0400
Message-ID: <47379231$0$5280$9a566e8b_at_news.aliant.net>
David Cressey wrote:
> "David BL" <davidbl_at_iinet.net.au> wrote in message
> news:1194798913.080431.70540_at_i38g2000prf.googlegroups.com...
>
>>On Nov 11, 1:08 am, "David Cressey" <cresse..._at_verizon.net> wrote: >> >>>"David BL" <davi..._at_iinet.net.au> wrote in message >> >>>>The mathematician in me axiomatizes the concept of pointer in terms of >>>>its abstract properties, which (ignoring null pointers) are >>> >>>> 1) the existence of an associated address space, which is just a >>>>set of objects >>>> 2) a bijection between objects in the address space and pointer >>>>values >>>> In one direction this bijection is "address of" and in the >>>>other >>>> it is "dereference" >>>> 3) the ability to compare pointer values >>> >>>>This encompass physical address spaces, virtual address spaces, C++ >>>>smart pointers, persistent OIDs and pointer swizzling etc. >>> >>>>It also encompass node identifiers of an AST if we regard the DB as >>>>defining an address space of AST nodes, and an appropriate select >>>>query represents a dereference that logically binds to precisely one >>>>node of the AST. >>> >>>>My perspective conflicts with your statement above. >>> >>>First, the term "pointer" originates in computer science, not
>
> mathematics.
>
>>>This is unlike the term "relation" which originates in mathematics and
>
> is
>
>>>transferred to the world of computer science, where it presumably
>
> retains
>
>>>all the properties that made it important from a mathematical
>
> perspective.
>
>>Yes the term "pointer" originates in computer science and its meaning >>is not at all precise. Wouldn't it be nice if the software >>development discipline was generally treated as a branch of >>mathematics, and there were many standardised axiomatic definitions to >>give it the proper foundations. >> >> >>>Second, your analysis overlooks the difference between address based >>>addressing and content based addressing. If you retrieve a row by >>>specifying an OID to be matched, you are still engaging in content based >>>addressing. If you specify a pointer, there is no law that says that
>
> the
>
>>>object pointed to is going to contain a copy of the pointer you used for >>>access. >>> >>>In most pointer based systems, the pointer is not included in the
>
> contents,
>
>>>being seen as redundant to its location. >>> >>>The distinction between content based addressing and pointer based >>>addressing is fundamental to the comparison of databases built on the >>>relational model and databases built on the graph model. >> >>This is an interesting and important distinction. I assume you are >>suggesting pointers by definition never use content based addressing. >>However I regard the following as a counter example...
>
> I am claiming that the word "pointer" as used in computer science and going
> back at least as far as the invention of Lisp in the 1950s, by definition
> refers to address based addressing. That any use of the word "pointer" that
> conflicts with this use is technically incorrect, and may be useful only to
> the extent that it suggests an analogy to the purpose for which pointers are
> used.
>
> An analogy is only an analogy. It isn't a definition.
A pointer is defined as something that points. One can specify a computational model that depends entirely on pointers without requiring addressible memory.
>>In the literature on pointer swizzling, persistent OIDs are classified >>as being of two different types : physical or logical. This is >>exactly your distinction above with different terminology.
>
> Fien. I don't propose to criticise you for the terminology you've been
> exposed to, nor do I intend to accept criticism for my use of terminology
> that I've been exposed to. A trend towards more uniform terminology would
> be welcome, but we won't make any progress in that direction by finger
> pointing.
In which case, a finger is also a pointer. Regardless whether physical or logical, OIDs point.
>>A physical >>OID directly specifies the location of the object on disk. For >>example, in the commercial product ObjectStore, the low 32 bits of the >>OID represents a seek position within a "cluster".
>
> A physical OID corresponds to what I call a "pointer".
Any OID corresponds to a "pointer".
>>By contrast a >>logical OID uses an indexing data structure allowing for objects to be >>relocated. A Log Structured Store for example will typically use >>this latter approach.
>
> The only indexing structures I'm directly familiar with are the ones in SQL
> DBMS products like Oracle RDBMS, or in indexed file systems like RMS (a
> facility within VMS). In the former case, the index is a data structure
> that serves to map what you are calling a "logical OID" to what I am
> calling a "pointer". The pointer that the DBMS retrieves from an index
> serves for direct lookup of the thing pointed to (a table row or table row
> fragment, in this case)
>
>
>>Despite such an important and useful >>distinction, it is only relevant to the underlying physical >>implementation of the Persistent Object Store (POS). It has no impact >>whatsoever on the fact that clients of a POS like to think of OIDs as >>persistent pointers between objects.
>
> I tend to use the acronym "POS" with a different expansion, but we'll let
> that pass for now.
An appropriate expansion in this case, I might add.
> It may or may not have any impact on what the clients like to think. It
> does however have a great impact on the delay time needed to access the
> thing referenced by the pointer. It also has a great impact on the
> consequences of shuffling data within the address space. (What you are
> calling "swizzling" might be the same as what I'm calling "shuffling".
>
> If there are physical pointers beyond the control of the DBMS, then
> shuffling data can result in the invalidation of such pointers with no
> possibility of raising an exception at the appropriate point in time.
>
> So we can at least table the discussion on terminology by agreeing that
> "pointer", in strict usage, should ONLY refer to physical OIDs.
I disagree. I see no reason to redefine pointer to mean something new and overly constrained. An OID is a pointer based on the fact that it points.
[snip] Received on Mon Nov 12 2007 - 00:45:22 CET