reference type for C

[James Kuyper]

On 05/23/2013 06:00 PM, Malcolm McLean wrote:
....

Array notation you can understand purely in terms of op zero. You
don't need to abstract it to addition. We tend to do this because
we're so familiar with addition.

No - we do it for two reasons that have nothing to do with that. First
of all, all of the memory hardware I'm familiar with provides built-in
instructions that do the equivalent of performing addition, NOT counting
on. Those instructions are the ones that all C implementations I'm
familiar with use to implement subscripting. I don't know of any memory
hardware that fails to provide such instructions, nor of any C compiler
that fails to use them for that purpose. Of course, there's lots of
hardware that I'm not familiar with, and lots of C implementations, too,
so I can't be sure there aren't obscure systems that work that way.
However, your words imply that implementation of array subscripts as
"counting on" is not merely an obscure alternative to more mainstream
approaches; it's not even merely the mainstream approach; you imply that
it's universal, and I'm quite sure that's not the case.

The second reason, which is actually the consequence of the first
reason, is that the C standard defines array subscripting in terms of
conversion of the array lvalue into a pointer the start of the array,
and it defines pointer subscripting in terms of addition.

... But really array[42] isn't
"take array, add 42, find the value and dereference it", it's
"take array and count on 42 places".

In what sense is that "real"? Can you cite any examples of any
implementation of C where array[n] is implemented in a way that makes it
an O(n) process? I'd like to make sure that I don't use that implementation.

 

[Geoff]

"Counting on" simply means that you count up to, say, a hundred, or
start from a hundred, then go "one hundred and one", "one hundred and
two" and so on.
Its a semantic argument whether we call it "arithmetic" or not, but
generally we don't. That's because most people are able to count low
integers at least as a function of knowing the names of the numbers
in their native language. But they can't add two integers unless
they've had at least a few terms of primary school.

I don't know how they do it in the UK but I was doing addition and
number lines in first grade in the US. This is the second year after
kindergarten. But then, I was a bit precocious, I was doing the
Lorentz transformation equations by the 5th grade which means I had
the concepts of addition/subtraction, multiplication/division,
squares/square roots, and the concept of space-time as a property of
nature. All from independent reading, mind you.

You cite this "counting on" as a semantic argument but I'd call it
more artificial than semantic. Counting is "adding 1" to a number and
it may be argued that numbers can be counted "by rote" but inherent in
counting is the concept of addition and the number base. If you can
add 1 to a number and you know the base symbols then you can count to
any number by addition and rollover and this is fundamentally
"mathematics". In fact, you can begin with zero plus one is one, one
plus one is two, etc. and you are doing "mathematics". You are
manipulating symbols in a systematic way, the heart of mathematics as
well as computer programming. (i.e., as A. Turing referred to it)

I seem to recall a tribe of herdsmen that had no numbers beyond a
hundred or so head of cattle, calling a number beyond that "many".
This was the limit of their counting. Their system was limited to a
finger counting method that, while intricate, was useless as a
mathematical tool beyond their number space. Of course, if a man had
50 cattle he was wealthy enough not to need to count more.

A pointer is a symbol and adding 1 to it is mathematics, not merely
counting on. You can't cut it off at 1 and say that adding the symbol
1 to a number is counting and adding the symbol 42 to a number is
mathematics. They are both mathematics. The Chinese used a blank space
for the number zero and used pictograms for numbers, yet they were
able to count and do mathematics just as well as we do it today. The
I-Ching is in fact a binary counting method up to 2^6 or 64 symbols.

 

[Seebs]

"Counting on" simply means that you count up to, say, a hundred, or
start from a hundred, then go "one hundred and one", "one hundred and
two" and so on.

This is a usage I have never encountered before. And I've asked around,
and I've yet to encounter anyone else who has ever heard of this usage.

Its a semantic argument whether we call it "arithmetic" or not, but
generally we don't.

That may be, but that doesn't change the fact that, from the point of
view of a programming language, it's still arithmetic.

Array notation you can understand purely in terms of op zero. You
don't need to abstract it to addition. We tend to do this because
we're so familiar with addition. But really array[42] isn't
"take array, add 42, find the value and dereference it", it's
"take array and count on 42 places".

Even if I stipulate to the other two things I disagreed with, I still
don't accept this, especially not in C where it's quite common that
&array[42] ends up yielding a pointer which, if dumped with %p, would
not look like it were 42 higher (or 0x2a higher) than &array[0].

But really, no. I don't do it by counting from 0, I do it by adding.
And even if I didn't, the processor does. And even if the processor did
too, it would still be horrendously confusing to anyone I've ever known
who speaks English to refer to this as "counting on".

-s

 

[gwowen]

yes if they are pointers or array , but they modify not itself but the
mem they point to...

An array doesn't point to anything. It's an array, with a hidden pass-
by-reference ("pointer decay") as part of the calling convention. So,
in effect, C already has pass-by-reference, but it only happens for
arrays.

 

[roland.arthaud]

Well, I think that all along Malcolm has been trying, with his words, to describe sequential versus random access.

Back to my previous post, there is behavior and there is implementation.
If my implementation has a mandatory sequential access mechanism, then indexing has a high cost : my quantum computer has sequential, though light(ening) fast access. Your C programs will still work, be it by indexing or pointer, but it will be costly - behaviour is still honored, but the taken for granted that indexing is natural bears a mindset from current technology.
Without going too far, if the object you are indexing implements a single linked list, you have the same situation - but this is C++ realm with objects and iterators, and C-ish.

 

[roland.arthaud]

Without going too far, if the object you are indexing implements a single linked list, you have the same situation - but this is C++ realm with objects and iterators, and C-ish.

not C-ish, I mean.

 

[Malcolm McLean]

On Thu, 23 May 2013 15:00:19 -0700 (PDT), Malcolm McLean


You cite this "counting on" as a semantic argument but I'd call it
more artificial than semantic. Counting is "adding 1" to a number and
it may be argued that numbers can be counted "by rote" but inherent in
counting is the concept of addition and the number base.

What comes next in this series:

m n o p ...?

Probably you can instantly answer.

What's the index of q in the alphabet? You might know this off by heart,
but a lot of people don't.

So was the first question arithmetic?

 

[Ike Naar]

What comes next in this series:

m n o p ...?

Probably you can instantly answer.

What's the index of q in the alphabet? You might know this off by heart,
but a lot of people don't.

So was the first question arithmetic?

Was the second question supposed to be arithmetic? (I think it wasn't).

 

[Geoff]

What comes next in this series:

m n o p ...?

Probably you can instantly answer.

Yes, q.

What's the index of q in the alphabet? You might know this off by heart,
but a lot of people don't.

It's index is q in the base 26 alphabet. In base 10 it's 17 and in
base 16 it's 11. These are all merely symbols.

So was the first question arithmetic?

Yes.

 

[Geoff]

Yes, q.


It's index is q in the base 26 alphabet. In base 10 it's 17 and in
base 16 it's 11. These are all merely symbols.


Yes.

I am so ashamed. I used it's instead of its index.

 

[Malcolm McLean]

On Fri, 24 May 2013 00:50:29 -0700 (PDT), Malcolm McLean


It's index is q in the base 26 alphabet. In base 10 it's 17 and in
base 16 it's 11. These are all merely symbols.

Most people know off by heart that q comes after p in the alphabet.
But they've lost track by then of the index. So most people wouldn't say
that knowing q is the next one on after p is enough to constitute arithmetic.

 

[James Kuyper]

not C-ish, I mean.

Why not? C has objects, and though the meaning of "object" is different
in C++ than in C, the difference is irrelevant to the feasibility of
using linked lists. Because C doesn't have user-defined operator
overloading, it does not allows creation of something meeting C++'s
requirements for a bidirectional iterator that accesses a linked list,
but the same functionality can be supported in C using other syntax. The
only difference in C++ is that a type safe generic linked list is
provided as part of the standard library; it's not a fundamental
difference in the base language.

 

[roland.arthaud]

Well, I think that the notion of "counting on" is what is usually called "next relationship" which is related to sets and total order in mathematics which is different from arithmetics - though it is true that following the order can be made one to one with the set of integers.

 

[roland.arthaud]

not C-ish, I mean.

using linked lists. Because C doesn't have user-defined operator
overloading, it does not allows creation of something meeting C++'s

that's what I meant : using [] in C only works for arrays and cannot be using to index a different object like a (an underlying) linked list

 

[James Kuyper]

using linked lists. Because C doesn't have user-defined operator
overloading, it does not allows creation of something meeting C++'s

that's what I meant : using [] in C only works for arrays and cannot be using to index a different object like a (an underlying) linked list

Actually, it can be. "next" and "prev" don't have to be pointers; they
could be indices into an array, with -1 reserved to indicate there is no
such item:

for(current = head; current > 0; current = list[current].next)
{
}

That's the Fortran way, rather than the C++ way or the C way, but it's
perfectly feasible to use the Fortran way to implement linked lists in C
(or C++, for that matter). Linked lists stored in this fashion serialize
more easily than C-style linked lists.

 

[James Kuyper]

What comes next in this series:

m n o p ...?

Probably you can instantly answer.

What's the index of q in the alphabet? You might know this off by heart,
but a lot of people don't.

So was the first question arithmetic?

No, but, your claims to contrary not-withstanding, it's also completely
unrelated to both the theory and practice of array subscripting.

 

[Malcolm McLean]

No, but, your claims to contrary not-withstanding, it's also completely
unrelated to both the theory and practice of array subscripting.

We need to establish that counting - knowing the names of the numbers and
the next one - isn't arithmetic. Which was disputed but now seems to have
been accepted (counting isn't "adding one").

That accepted, is array[42] adding 42 to array, taking the result, and
dereferencing it, or going to the collection marked "array" and taking item
42? Internally, somewhere, we're going to have to generate the address of
item 42 in the array, but at machine code level the address might well never
appear, it could just as easily be a base (probably not array) and an offset,
depending on the exact instruction set used.

 

[Eric Sosman]

An array doesn't point to anything. It's an array, with a hidden pass-
by-reference ("pointer decay") as part of the calling convention. So,
in effect, C already has pass-by-reference, but it only happens for
arrays.

In all but three contexts (operand of &, sizeof, or _Alignof),
any array name appearing in an expression "decays" to a pointer to
the array's first element. There's nothing special about array
names in expressions that are arguments; the substitution is in no
way specific to function calls.

IMO, your final sentence is sort of true if you squint real
hard and tilt your head to one side, but is mostly misleading.

 

[gwowen]

     In all but three contexts (operand of &, sizeof, or _Alignof),
any array name appearing in an expression "decays" to a pointer to
the array's first element.  There's nothing special about array
names in expressions that are arguments; the substitution is in no
way specific to function calls.

It is in some way specific to function calls.

IMO, your final sentence is sort of true if you squint real
hard and tilt your head to one side, but is mostly misleading.

Arrays are passed by reference. To say that "decaying to a pointer"
is not the same as being passed by reference is a distinction without
a difference. That this invisible-conversion-of-an-object-to-
reference occurs in some other contexts isn't really relevant.

// Function on
void mutate(int bar[])
{
bar[0] = 1; //
}

int foo[3] = {0}; // Foo is an array. It is not a pointer.
mod(foo); // mutate does modify a copy of foo, it modifies foo
printf("%d\n",foo[0]);

However you want to phrase it, that's the semantics of "foo was passed
by reference".
Sure you can say "Actually, the address of foo was passed by value",
but on a fundamental level *that's what pass by reference* means.

class myarr {
public:
int arr_[3];
};

void mutate_by_reference(myarr& x)
{
x.arr_[0] = 1; //
}

void mutate_by_value(myarr x)
{
x.arr_[0] = 1; //
}


Which of those has the same semantics as the C example?

 

[Malcolm McLean]

Well, I think that the notion of "counting on" is what is usually called
"next relationship" which is related to sets and total order in mathematics
which is different from arithmetics - though it is true that following the
order can be made one to one with the set of integers.

Yes.
The way it is actually done is "what's 373 and 249 ?"
So start at 373 and count on in hundreds, 373, 473, 573.
Then count on in tens 573, 583, 593, 603, 613.
Then count on in ones, 613, 614, 615, 616, 617, 618, 619, 620, 621, 622
(You'll probably need to use fingers for the last, counting down on your
fingers as you count on).
So you can do addition without knowing any arithmetic facts, just knowing
which comes after which. However at this point it maybe becomes hard to
convince someone that's it's not really arithmetic.