Path: utzoo!attcan!uunet!aplcen!uakari.primate.wisc.edu!sdd.hp.com!decwrl!elroy.jpl.nasa.gov!ames!ncar!noao!arizona!gudeman
From: gudeman@cs.arizona.edu (David Gudeman)
Newsgroups: comp.lang.misc
Subject: Re: Pointers are abstractions
Message-ID: <26362@megaron.cs.arizona.edu>
Date: 13 Oct 90 00:37:56 GMT
Organization: U of Arizona CS Dept, Tucson
Lines: 56

I'm beginning to see why people have so much trouble with pointers.
Your problem is that you haven't grasped the idea of a pointer as an
abstraction.  I note the following (incorrect) comments:

In article  <PCG.90Oct12082045@odin.cs.aber.ac.uk> pcg@cs.aber.ac.uk (Piercarlo Grandi) writes:
]
]But pointers are a useful concretion, not an abstraction...

In article  <1576@enuxha.eas.asu.edu> nelan@enuxha.eas.asu.edu (George Nelan) writes:
]Uh, ahem.  Mathematics & Pointers.  Never shall the twain meet.  Why?
]Mathematics is about relations (implies functions).  Pointers are about
]memory...

Pointers are _not_ about memory.  Do you agree that sequences are
"mathematical"?  Then so are pointers.  Here is a partial
axiomatization:

Nat is the natural numbers
Seq is the set of sequences of X

the operation [] : Seq X Nat -> X is a partial one-to-one function
mapping S[i] into some unique x in X, for S in Seq and i in Nat.

Ptr is some set such that there exists a one-to-one function from
    Seq X Int to Ptr

let the operations

&[] : Seq X Nat -> Ptr		(written p = &S[i])
+ : Ptr X Nat -> Ptr
- : Ptr X Ptr -> Nat
* : Ptr -> X

be defined, subject to the following axioms

	p = &S[i] implies *p = S[i]
	p = &S[i] implies p + j = &S[i+j]
	(p1 = &S[i] and p2 = &S[j]) implies p2 - p1 = j - i.

I just took about 15 minutes to do this, so I don't give any
guarantees about rigour, but I'd say it is a pretty complete algebra
of pointers.  This is just as abstract as anything else in
mathematics.  It is _not_ in any sense an attempt to model computation
in any form, anymore than an axiomatization of arithmetic is an
attempt to model animal husbandry.  Yes, the original idea came from
machines.  But the idea of arithmetic probably came from counting
sheep and goats.

And no, this isn't an exact description of "real" pointers (it's an
abstraction remember?).  But then axiomatizations of arithmetic don't
really describe machine implementations of arithmetic either.
-- 
					David Gudeman
Department of Computer Science
The University of Arizona        gudeman@cs.arizona.edu
Tucson, AZ 85721                 noao!arizona!gudeman