references/addrresses in imperative languages

[Xah Lee]

in coding Python yesterday, i was quite stung by the fact that lists
appened to another list goes by as some so-called "reference". e.g.

t=range(5)
n=range(3)
n[0]='m'
t.append(n)
n[0]='h'
t.append(n)
print t
in the following code, after some 1 hour, finally i found the solution
of h[:]. (and that's cheating thru a google search)

def parti(l,j):
'''parti(l,j) returns l partitioned with j elements per group. If j
is not a factor of length of l, then the reminder elements are dropped.
Example: parti([1,2,3,4,5,6],2) returns [[1,2],[3,4],[5,6]]
Example: parti([1,2,3,4,5,6,7],3) returns [[1,2,3],[4,5,6]]'''
n=len(l)/j
r=[] # result list
h=range(j) # temp holder for sublist
for n1 in range(n):
for j1 in range(j):
h[j1]=l[n1*j+j1]
r.append( h[:] )
return r

interesting that a dictionary has copy method, but not list. (the pain
is coupled with the uselessness of the Python doc)

------
Btw, behavior such as this one, common in imperative languages and info
tech industry, is a criminality arose out of hacks C, Unix, and from
there all associated imperative langs. (C++, csh, perl, Java... but
each generation improves slightly)

The gist of the matter is that these behaviors being the way they are
really is because they are the easiest, most brainless implementation,
as oppose to being a design decision.

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".

---------

PS is there any difference between
t=t+[li]
t.append(li)

---------
References:

for a analysis of the same situation in Java, see
http://xahlee.org/java-a-day/assign_array_to_list.html

How to write a tutorial
http://xahlee.org/Periodic_dosage_di...ami_cukta.html

Xah
xa*@xahlee.org
∑ http://xahlee.org/

[Lawrence D’Oliveiro]

In article <11*********************@g49g2000cwa.googlegroups. com>,
"Xah Lee" <xa*@xahlee.org> wrote:

A[n] easy way to see this, is to ask yourself: how come in mathematics
there's no such thing as "addresses/pointers/references".

Yes there are such things in mathematics, though not necessarily under
that name.

For instance, in graph theory, edges can be considered as "pointers".
After all, make a change to a node, and that change is visible via all
edges pointing to that node.

[Walter Roberson]

In article <11*********************@g49g2000cwa.googlegroups. com>,
Xah Lee <xa*@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).

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. 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. 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.
--
Ceci, ce n'est pas une idée.

[SM Ryan]

# easy way to see this, is to ask yourself: how come in mathematics
# there's no such thing as "addresses/pointers/references".

The whole point of Goedelisation was to add to name/value references into
number theory. Thus Goedel was able to add back pointers contrary to the
set hierarchy of the theory of types and reintroduce Russel's paradox.

--
SM Ryan http://www.rawbw.com/~wyrmwif/
The little stoner's got a point.

[Kaz Kylheku]

Walter Roberson wrote:

In article <11*********************@g49g2000cwa.googlegroups. com>,
Xah Lee <xa*@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.

[Kaz Kylheku]

SM Ryan wrote:

# easy way to see this, is to ask yourself: how come in mathematics
# there's no such thing as "addresses/pointers/references".

The whole point of Goedelisation was to add to name/value references into
number theory.
Is that so? That implies that there is some table where you can
associate names (or whatever type of locators: call them pointers,
whatever) with arbitrary values. But in fact that's not the case.
Thus Goedel was able to add back pointers contrary to the
set hierarchy of the theory of types and reintroduce Russel's paradox.

Nope. Goedel didn't add anything, he just revealed what was already
there: that you can have statements of number theory, well-formed
formulas constructed out of existing operators without any backpointer
tricks, which have true interpretations, but are not theorems.

Everything in a Goedel's string can be recursively expanded to yield an
ordinary formula! There is no infinite regress, no unchased embedded
pointer-like things left behind.

Self-reference is achieved using two tricks: Goedel numbering, and
indirect reference. Godel numbering allows a formula to talk about
formulas, by way of embedding their Godel numbers, and translating
formula-manipulations into arithmetic manipulations (of interest are
finite ones that will nicely unfold into finite formulas). In essence
that which used to be ``code'' can be now treated as ``data''', and
operations on code (logical derivations) become arithmetic operations
on data.

Indirect reference is needed because a formula G's Goedel number cannot
be inserted into itself directly. If you start with a formula G which
has some free variable V, and then produce some new formula by
substituting G's Goedel number into it directly for occurences of V,
you no longer have G but that other formula. You want whatever comes
out to be G, and so the input formula, the one with the free variable,
cannot be G, but perhaps a close relative which either talks about G,
or whose constituent formulas cleverly end up talking about G after the
substitution takes place.

Instead of a direct (Goedel number) reference, you can insert into a
formula some /procedure/ for making that formula's Goedel number out of
another formula's Goedel number and talk about it that way. As an
example, instead of saying ``here is a number'' by inserting its
literal digits, you can say ``the number that results by applying this
formula to this other number''. For instance, instead of writing the
number 4 we can write successor(3). or 2 + 2. We explicitly
mention some other number, and say how 4 is constructed out of it.

Douglas Hofstadter exposition of all this is very good. To allow the
formula G to mention its own Goedel number, Douglas Hofstadter uses
another formula which he calls U, the ``uncle''. The trick is that: the
procedure for making G's Goedel number out of U's number is the
arithmetic equivalent of the same procedure that's used to substitute
the Goedel number of U for the free variable in U itself. So as U (the
formula) is treated by substituting its own Godel number for its one
and only free variable, it produces G, and, at the same time, the
arithmetic version of that substitution, fully contained inside the U
formula itself, turns the now substituted copy of U into G also. U
contains the fully expanded ``source code'' for the arithmetic version
of the free-variable substitution procedure, and it contains a free
variable representing the arithmetic version of the formula on which
that algorithm is to be done. As that free variable within U is
replaced by the Goedel number U, the overall formula becomes G, and the
embedded free-variable-replacement procedure is instantiated concretely
over U's Goedel number, so it becomes a constant, unparameterized
calculation that produces G's Goedel number.

Voila, G contains a procedure that computes the arithmetic object
(Goedel number) that represents G's ``source code'' (the symbolic
formula), out of the embedded number representing U's source code.
Using that giant formula, G can assert things about itself, like ``I am
not a theorem'' (i.e. ``there exists no integer representing the Goedel
numbers of a list of true statements that represent a derivation
deducing myself as the conclusion'').

There are no name references or pointers or anything. All the functions
are primitive recursive, and so can be expanded into finite-length
formulas which contain only numbers and operators and variables---dummy
ones that are bound to existential quantifiers, not to concrete values
some external name/value table.

[Kaz Kylheku]

Lawrence D’Oliveiro wrote:

In article <11*********************@g49g2000cwa.googlegroups. com>,
"Xah Lee" <xa*@xahlee.org> wrote:

A[n] easy way to see this, is to ask yourself: how come in mathematics
there's no such thing as "addresses/pointers/references".

Yes there are such things in mathematics, though not necessarily under
that name.

For instance, in graph theory, edges can be considered as "pointers".
After all, make a change to a node, and that change is visible via all
edges pointing to that node.

Oh yeah, by the way, note how such destructive changes to a variable
become whole-environment derivations in the discipline of proving the
correctness of imperative programs.

E.g. say you have this assignment:

x <- x + 1

and you want to deduce what preconditions must exist in order for the
desired outcome x = 42 to be true after the execution of the
statement. What do you do? You pretend that the program is not
modifying a variable in place, but rather manufacturing a new
environment out of an old one. In the new environment, the variable X
has a value that is one greater than the corresponding variable in the
old environment. To distinguish the two variables, you call the one in
the old environment X' .

You can then transform the assignment by substituting X' for X in the
right hand side and it becomes

x <= x' + 1

and from that, the precondition x' = 41 is readily deduced from the
x = 42 postcondition.

Just to be able to sanely reason about the imperative program and its
destructive variable assignment, you had to nicely separate past and
future, rename the variables, and banish the in-place modification from
the model.

[SM Ryan]

"Kaz Kylheku" <kk******@gmail.com> wrote:
# SM Ryan wrote:
# > # easy way to see this, is to ask yourself: how come in mathematics
# > # there's no such thing as "addresses/pointers/references".
# >
# > The whole point of Goedelisation was to add to name/value references into
# > number theory.
#
# Is that so? That implies that there is some table where you can
# associate names (or whatever type of locators: call them pointers,
# whatever) with arbitrary values. But in fact that's not the case.

Do you really believe the Goedel number of a statement is the statement
itself? Is everything named Kaz the same as you?

--
SM Ryan http://www.rawbw.com/~wyrmwif/
So....that would make Bethany part black?

[Kaz Kylheku]

SM Ryan wrote:

"Kaz Kylheku" <kk******@gmail.com> wrote:
# SM Ryan wrote:
# > # easy way to see this, is to ask yourself: how come in mathematics
# > # there's no such thing as "addresses/pointers/references".
# >
# > The whole point of Goedelisation was to add to name/value references into
# > number theory.
#
# Is that so? That implies that there is some table where you can
# associate names (or whatever type of locators: call them pointers,
# whatever) with arbitrary values. But in fact that's not the case.

Do you really believe the Goedel number of a statement is the statement
itself? Is everything named Kaz the same as you?

The Goedel number is a representation of the statement in a way that
the name Kaz isn't a representation of me. You cannot identify parts of
the name Kaz with parts of me; there is no isomorphism there at all. I
am not the translated image of the name Kaz, nor vice versa.

A Goedel number isn't anything like a name or pointer. It's an encoding
of the actual typographic ``source code'' of the expression. There is
nothing external to refer to other than the encoding scheme, which
isn't particular to any given Goedel number. The encoding scheme is
shallow, like a record player; it doesn't contribute a significant
amount of context. If I decode a Goedel number, I won't have the
impression that the formula was hidden in the numbering scheme, and the
Goedel number simply triggered it out like a pointer. No, it will be
clear that each piece of the resulting formula is the direct image of
some feature of the Goedel number.

[Kaz Kylheku]

SM Ryan wrote:

"Kaz Kylheku" <kk******@gmail.com> wrote:
# SM Ryan wrote:
# > # easy way to see this, is to ask yourself: how come in mathematics
# > # there's no such thing as "addresses/pointers/references".
# >
# > The whole point of Goedelisation was to add to name/value references into
# > number theory.
#
# Is that so? That implies that there is some table where you can
# associate names (or whatever type of locators: call them pointers,
# whatever) with arbitrary values. But in fact that's not the case.

Do you really believe the Goedel number of a statement is the statement
itself? Is everything named Kaz the same as you?

The Goedel number is a representation of the statement in a way that
the name Kaz isn't a representation of me. You cannot identify parts of
the name Kaz with parts of me; there is no isomorphism there at all. I
am not the translated image of the name Kaz, nor vice versa.

A Goedel number isn't anything like a name or pointer. It's an encoding
of the actual typographic ``source code'' of the expression. There is
nothing external to refer to other than the encoding scheme, which
isn't particular to any given Goedel number. The encoding scheme is
shallow, like a record player; it doesn't contribute a significant
amount of context. If I decode a Goedel number, I won't have the
impression that the formula was hidden in the numbering scheme, and the
Goedel number simply triggered it out like a pointer. No, it will be
clear that each piece of the resulting formula is the direct image of
some feature of the Goedel number.