references/addrresses in imperative languages

[Kaz Kylheku]

Walter Roberson wrote:
> In article <1119220461.626477.56110 at g49g2000cwa.googlegroups.com>,
> Xah Lee <xah at xahlee.org> wrote:
> >In hindsight analysis, such language behavior forces the programer to
> >fuse mathematical or algorithmic ideas with implementation details. A
> >easy way to see this, is to ask yourself: how come in mathematics
> >there's no such thing as "addresses/pointers/references".
>
> There is. Each variable in predicate calculas is a reference.
> No matter how large the formulae, a change in a variable
> is, in mathematics, immediately propagated to all occurances
> of the variable (potentially changing the references of other
> variables).

Variables don't change in mathematics, at least the run-of-the-mill
everyday mathematics. :)

> If the predicate calculas variables were not equivilent to references,
> then the use of the variable in a formula would have to be a
> non-propogating copy. and a change to the original value whence not
> be reflected in all parts of the formula and would not change
> what the other variables referenced.
>
> Consider for example the proof of Goedel's Incompleteness
> theorem, which involves constructing a formula with a free
> variable, and constructing the numeric encoding of that
> formula, and then substituting the numeric encoding in as
> the value of the free variable, thus ending up with
> a number that is "talking about" iteelf.

All these substitutions ``work'' in a way that is analogous to
functional programming. For example, substituting a variable into a
formula generates a new formula with occurences of that variable
replaced by the given value. You haven't destroyed the old formula.

> The process of
> the proof is *definitely* one of "reference" to a value
> in the earlier stages, with the formula being "evaluated"
> at a later point -- very much like compiling a program
> and then feeding the compiled program as input to itelf.

Actually no. The process specifically avoids the pointer problem by
using an arithmetic coding for the formula, the Goedel numbering. The
formula talks about an encoded version of itself. That's how the
self-reference is smuggled in, via the Goedel numbering.

> You
> cannot do it without a reference, because you need to
> have the entire number available as data at the time
> you start evaluating the mathematical formula.

The final result just /is/ self-referential. It's not constructed bit
by bit like a data structure inside a digital computer that starts out
being non-self-referential and is then backpatched to point to itself.

A mathematical derivation may give you the idea that something is
changing in place, because you always hold the most recent version of
the formula at the forefront of your mind, and can visualize the whole
process as a kind of in-place animation in your head. But really, at
each step you are making something completely new which stands on its
own.