strange warning

[Ben Bacarisse]

As an aside, C99 allows the same information to be conveyed in the
second case like so:

void DoMove(SQUARE board[Nsquares], int Nsquares, int playerid, int diceroll);

(This is particularly useful when dealing with 2D (and higher) arrays as
the information enables you to index the arrays in a natural way.)

Shouldn't 'int Nsquares' come before 'board[Nsquares]' in order for this
to work? Like

void DoMove(int Nsquares, SQUARE board[Nsquares], int playerid, int diceroll);

Yes, it should. I edited the original with brain in neutral. Thanks.

 

[Malcolm McLean]

It just occurred to me to wonder: do you consider buffers and
McLean-arrays to be conflicting or non-overlapping sets? Specifically,
do you think that buffers cannot "be indexed in 0 constant time by an
integer subscript"?

It's like the terms "bit" and "real", as in "real number".
Real numbers are represented in the computer by bits, so in a sense you
could say that reals are a subset of the bits. But that's only when you're
thinking in pure memory layout terms. Reals aren't a subset of bits
in any higher level or mathematical sense. And in fact a real on a
digital computer isn't really real. This bit me yesterday. (A line
was represented by y1 = y2 - epsilon. So of course it wasn't horizontal.
But there was no ray y = (y1 + y2)/2 which would intersect it.

Let's consider a version of C which was modified to "tighten up the
distinction between a buffer and a [McLean-]array.". Does this mean that
you would impose this rule only for McLean-arrays, and not for buffers?
If so, what should happen when indexed a buffer with a negative value,
or one >=N?

Until those are
answered, it's hard to say what sorts of pointer conversions should
be considered "sloppy".

If C were tightened up as you suggest, what distinctions should the
standard make between the conversions allowed for pointers to buffers
and pointers to McLean-arrays?

You could do it like this.

void buffer[1024];

buff[0] = 0; /* illegal, it's a buffer, not an array */

int mclean_array[] = buffer; /* we've got a McLean array, it's
empty and of size 0, it uses the memory space buffer */

mclean_array[0] = 0; /* illegal, the mclean array has length 0 */

mclean_array.push_back(0); /* legal, as in C++ */
mclean_array[0] = 42; /* legal now */

char mclean_array2[] = buffer + mclean_array.memsize(); /*create another
mclean_array, in the buffer, after the first array, this time holding
chars */

mclean_array2.push_back('x'); /* put some data into it */
mclean_array.push_back(123); /* legal, but we've overwritten mclean_array 2*/

printf("%c", mclean_array2[0]); /* accepted, technically undefined behaviour,
we've set up two arrays over the same space in the same buffer, but it's
C and presumably we know what we're doing, prints a garbage character */

printf("%d", mclean_array[1]); /* defined and legal, must print 123 */

 

[Ian Collins]

If C were tightened up as you suggest, what distinctions should the
standard make between the conversions allowed for pointers to buffers
and pointers to McLean-arrays?

You could do it like this.

void buffer[1024];

buff[0] = 0; /* illegal, it's a buffer, not an array */

int mclean_array[] = buffer; /* we've got a McLean array, it's
empty and of size 0, it uses the memory space buffer */

mclean_array[0] = 0; /* illegal, the mclean array has length 0 */

mclean_array.push_back(0); /* legal, as in C++ */
mclean_array[0] = 42; /* legal now */

char mclean_array2[] = buffer + mclean_array.memsize(); /*create another
mclean_array, in the buffer, after the first array, this time holding
chars */

mclean_array2.push_back('x'); /* put some data into it */
mclean_array.push_back(123); /* legal, but we've overwritten mclean_array 2*/

printf("%c", mclean_array2[0]); /* accepted, technically undefined behaviour,
we've set up two arrays over the same space in the same buffer, but it's
C and presumably we know what we're doing, prints a garbage character */

printf("%d", mclean_array[1]); /* defined and legal, must print 123 */

I was going to suggest you shift to C++ in response to one of your
earlier posts, but seeing this it looks like C++'s std::vector and
std::array would meet your needs.

 

[Malcolm McLean]

Malcolm McLean wrote:

I was going to suggest you shift to C++ in response to one of your
earlier posts, but seeing this it looks like C++'s std::vector and
std::array would meet your needs.

Basically yes.
The idea that an array is a data-representation level object, a buffer
an implementation-level object, isn't one that I invented, and there
are plenty of languages which offer arrays but discourage treating them
as buffers.

 

[Malcolm McLean]

What languages other than C family do you treat an array as a "Buffer"?
(not that Ive ever seen that in anywhere half way decent code : anything
that assumes a contiguous memory block would malloc it to be sure to be
sure and if not use array indexing to access the "cells")

All programming languages are fundamentally equivalent.
So in a high-level language, say Matlab, I can declare a matrix
of 64K real values, then treat each real as a byte value 0-255.
Then I can write Z80 instructions, in Matlab code, to move
the byte values about in that array. Then I can download the
Zx81 ROM from the web, and write a little Basic program,
and play Space Invaders.

So I'm using the Matlab matrix as an array, in one context, as
a buffer in another, context. To my Matlab Z80 simulator, it's
an array, even if I set all the values to random on startup, they
have to have defined values, the Z80 instructions have defined
effects on them. But to the Space Invaders, it's a buffer, we
can peek and poke bytes to move the Space Invaders about, it
doesn't inherently represent or mean anything until we
give it a meaning.

 

[Malcolm McLean]

A tad overstatement. Only in that you "program something with them". They all have
different ways of handling arrays, recursion, overloading, etc etc.

It's a basic fundamental theorem of computer science. Interestingly, you don't
have to know it to be a perfectly competent programmer.

But you havent said what addressing you are using to address the
cells. In what languages other than C do you know that two array
elements are actually in adjacent memory locations?

Matlab provides a C interface, so you can implement Matlab functions in
C, and of course matrices are arrays of doubles, contiguous in memory.
But Matlab itself has no address of operator. You could rewrite the matrices
to be column-major, or to use strides, and you wouldn't break any Matlab
code.

Im not sure that makes any sense in the context. Can you explain
further.

A Matlab matrix is, in my terminology, an "array" rather than a buffer.
You can't create one with uninitialised values, at least not easily - there
might be a hack that allows you to defeat the system in Matlab code
but I'm not aware of it. So typically Matlab programmers create matrices
initialised to zeroes, or ones, or the identity matrix, whatever makes
most sense in context.But all programming languages are fundamentally equivalent. Though
Matlab sees the matrix as defined object, holding data, not as a buffer,
we can treat it as a buffer again in higher level code. So we can write a
Z80 simulator, in Matlab, run the ZX81 ROM on it, which includes a
Basic interpreter, and implement peek and poke. Now in terms of the
Z80 simulator, we've got a buffer, not an array.

 

[James Kuyper]

That concept may in fact be useful, but it is not part of C as currently
defined. ....
The behavior is undefined ".. by the omission of any explicit definition
of behavior ..." (4p2). The only definition for the behavior of pointer
arithmetic is in terms of positions in an array of objects of the
pointed-at type, and the pointer points at a object which is not such an
array, so that definition does not apply.

So are you saying that:

int *pi = malloc(5 * sizeof(int) );

if(pi) {
pi = pi + 1;
}

has undefined behavior since I haven't given the block of memory
returned by malloc an effective type, so it isn't an object, so pi isn't
pointing to an object yet??

The standard defines that malloc returns a value (unless it returned
NULL) suitable for any object with size up to 5*sizeof(int), and that
includes an array int[5], which makes the arithmetic defined.

But no such array object exists yet. I consider this a flaw in the
standard's definition of pointer arithmetic, not in your example code.

 

[Ben Bacarisse]

It's a basic fundamental theorem of computer science.

No, not as stated. As most people use the term "programming language",
it is, in effect, a definition not a theorem.

If I present you with a new notation for expressing rote sequences of
computational steps (let's call it BB/1) and I ask you "is this a
programming language?" you will want to determine two things about it.
First, is it Turing complete? Can it express every computation that a
Turing machine can perform? If it isn't, you won't call it a
programming language. The second thing you'd do is determine if it is
Turing equivalent, i.e. that there is no computation it can describe
that can't be computed by a Turning machine. If it passes both tests,
BB/1 will be declared to be a programming language.

Maybe you have some other definition of programming language, in which
case it might well be a theorem, but it's not one I've come across.

There are various fundamental theorems about what minimal constructs are
needed for a notation to be Turing complete, and it is widely believed
that any practical Turing complete notation would be Turing equivalent
(that's the Church-Turing thesis) but that's not a theorem.

<snip>

 

[Malcolm McLean]

No, not as stated. As most people use the term "programming language",
it is, in effect, a definition not a theorem.

Most English speakers can use the term "programming language" perfectly
competently, and they mean a notation that is used to give instructions
to computers.
They might well know that Fortran is designed for numerical programming,
whilst Snobol is designed for non-numerical problems. Then won't know,
unless they've done a smidgen of computer science, that any Snobol
program can be rewritten as a Fortran program, and vice versa. It's not
obvious that this is the case, and as a practical proposition, often it isn't
possible.

Maths is tautology, ultimately. I'm not a mathematician, and I might lack a
deep insight into the nature of mathematical proof and what a theorem
is. But, like most native English speakers, I can use the term "theorem"
competently enough for general use.

 

[Ben Bacarisse]

Most English speakers can use the term "programming language" perfectly
competently, and they mean a notation that is used to give instructions
to computers.

Using that definition what you stated as a theorem is not a theorem.
There are many notations for giving instructions to computers which are
not Turing complete (many macro processors (C's for example), regular
expressions, SQL...). You will, maybe, counter by saying "but most
people don't consider those as programming languages" which was exactly
my point. Or maybe you will complain that these don't "run" on
hardware, but that means that, say, Python is not a programming
language.

They might well know that Fortran is designed for numerical programming,
whilst Snobol is designed for non-numerical problems. Then won't know,
unless they've done a smidgen of computer science, that any Snobol
program can be rewritten as a Fortran program, and vice versa. It's not
obvious that this is the case, and as a practical proposition, often it isn't
possible.

Maths is tautology, ultimately.

Yes, in that narrow sense I was wrong: the claim that the members of the set
of even numbers are all divisible by two is a theorem.

I'm not a mathematician, and I might lack a
deep insight into the nature of mathematical proof and what a theorem
is. But, like most native English speakers, I can use the term "theorem"
competently enough for general use.

Does the "all programming languages are equivalent" theorem have a name?

 

[Malcolm McLean]

Using that definition what you stated as a theorem is not a theorem.
There are many notations for giving instructions to computers which are
not Turing complete (many macro processors (C's for example), regular
expressions, SQL...). You will, maybe, counter by saying "but most
people don't consider those as programming languages" which was exactly
my point. Or maybe you will complain that these don't "run" on
hardware, but that means that, say, Python is not a programming
language.

And they managed to work Turing completeness into C++ template notation.
But most people wouldn't consider the subset of C++ that consists of the
template system as a "programming language", except in a geeky conversation.

Things like SQL and regular expressions are marginal cases, also html, a
lot of people use the term "html programming". So in that sense, the claim
that "all programming languages are equivalent" was wrong. It extends to the
core members of the set, and many of the marginal members, but not all
marginal members. That's commonly the case with natural language. Terms
denote what computer scientists call "fuzzy sets".

Does the "all programming languages are equivalent" theorem have a name?

It follows very simply from Turing equivalence. But that wasn't quite what I
meant when I first said "all programming languages are equivalent". I meant
that all popular languages in current use are based on a procedural paradigm
that allows for loops, integer indices, and so on. All (existing, practical, in
common use) programming languages are fundamentally equivalent in ways
that go deeper than Turing equivalency.

All programming languages are fundamentally equivalent.

What that means is that the ideas "array" and "buffer" are not tied to C, they
are language independent. In a straightforwards way for the vast majority
of languages, and kind of for every language, So "all" is the appropriate word.

Then we have

A tad overstatement. Only in that you "program something with them". They all have
different ways of handling arrays, recursion, overloading, etc etc.

That's a kind of misunderstanding. Structures are essentially independent of the
implementation details. And it's a deep sort of misunderstanding.

 

[Ben Bacarisse]

It follows very simply from Turing equivalence. But that wasn't quite
what I meant when I first said "all programming languages are
equivalent". I meant that all popular languages in current use are
based on a procedural paradigm that allows for loops, integer indices,
and so on. All (existing, practical, in common use) programming
languages are fundamentally equivalent in ways that go deeper than
Turing equivalency.

I was not commenting on that. I was commenting on what you said was a
fundamental theorem of computer science. What is it's conventional
name? I'd like to know which theorem you were thinking of and I can't
work that out from what you've said about it.

[At this point the quoting goes wrong and you attribute to me things that
other people said so I'll just snip the rest.]

 

[Malcolm McLean]

I was not commenting on that. I was commenting on what you said was a
fundamental theorem of computer science. What is it's conventional
name? I'd like to know which theorem you were thinking of and I can't
work that out from what you've said about it.

The conventional name is Turing equivalence. This means that any computing
device many emulate any other, given only unlimited memory or storage
space. It follows from that that, given a few conditions, any computer
language may emulate any other. So all languages have a fundamental
similarity.

Now you might object that, if we implement a simple Turing machine with
a pencil, rubber, read head, and infinite paper tape, we can write a
C compiler for it, but we can't possibly provide O(constant) time
access to an array. The fundamental theorem is that all computations
are at root the same thing. The real observation is that most if not
all rational, practical, in-use etc programming languages on real,
existing devices will operate in much the same way. That follows
from the fundamental theorem, but it's not actually imposed by it.
Everyone who implements an array is going to calculate a memory
index then index into it, for example. The array may be broken up,
it may have strides it it, it may have a layer of indirection under
it via a hash table. But it's still at bottom going to work in the
same way.

If you're going to argue, you have to understand natural language.
You speak English fluently, probably as first language, so you
do have an intuitive understanding of language which is good enough
to discuss technical points. Your understanding is not good
enough for you to participate competently in a philosophical debate.
You try to nitpick on the word theorem. "Theorem" means, "something
which is known form pure logical deduction, as opposed to know
from observation", in normal usage. It might have a technical
mathematical definition that I an the normal person is unaware
of, and you can point that out. But you have to be careful that
you're not just being a clever dick.
Similarly "programming language" is a class which has core members
and marginal members. The word "all" doesn't necessarily cover
the marginal members of the set, it also excludes some special
case ("All Britons are subjects of the Queen" - well no, not the
Queen herself, it doesn't mean that the claim is in any normal
sense false).

Now I don't believe you don't know I'm talking about Turing
equivalence. But what the main thrust of what I was saying
wasn't a claim about mathematical equivalence. You have to
understand that the mathematical equivalence is there before
you can really appreciate what I am saying, however.

 

[Ian Collins]

So what? This doesnt mean all programming languages are basically the
same.

This is total high brow nonsense.

Unless you have the definition of "the same" as meaning all objects in
the world are "the same" because they are formed from molecules.

Nice!

 

[Malcolm McLean]

So what? This doesnt mean all programming languages are basically the
same.

This is total high brow nonsense.

Unless you have the definition of "the same" as meaning all objects in
the world are "the same" because they are formed from molecules.

"As in elephant, so in E. coli". All biochemistry is fundamentally "the same",
because all organisms are facing essentially the same problem, and they
have essentially the same toolset to deal with it.
It's a similar situation with programming languages. They are bound by
logical laws rather than physical laws, which gives a limited set of
fundamental operations. Then, just as all organisms evolved from a common
ancestor, all processing chips were built by engineers from the same culture,
using each other's designs. So the "toolkit" is the same.

 

[Keith Thompson]

The conventional name is Turing equivalence. This means that any computing
device many emulate any other, given only unlimited memory or storage
space. It follows from that that, given a few conditions, any computer
language may emulate any other. So all languages have a fundamental
similarity.

Turing equivalence is not a theorem, it's a characteristic that a given
language may or may not have. There might be a theorem that says that a
given language is Turing equivalent, but I know of no actual theorem
that says that all languages are Turing equivalent (and in fact there
could be no such theorem, since not all languages *are* Turing
equivalent).

I think what you're talking about might be a definition, not a theorem.

[...]

 

[James Kuyper]

The standard defines that malloc returns a value (unless it returned
NULL) suitable for any object with size up to 5*sizeof(int), and that
includes an array int[5], which makes the arithmetic defined.

But no such array object exists yet. I consider this a flaw in the
standard's definition of pointer arithmetic, not in your example code.

So, when the STANDARD defines something that doesn't match your model,
and that means it is the standard that has the defect?

It's not what the standard defines that's a problem: it's what the
standard fails to define. It's not a failure to match my model, it's a
failure by the standard to specify what happens in certain cases. It's
not just "my" model. Just about everyone has expectations about what
will happen in those cases, and as far as I know, every compiler I've
ever used has conformed to those expectations.

I find the definition of pointer arithmetic with respect to arrays to be
reasonable, as the PURPOSE of pointer arithmetic is to move through
arrays. How would you envision defining it otherwise?

I would have it modified so that it makes sense even when referring to
pointers that, according to the standard, point at objects that have
neither a declared type nor an effective type, and which therefore
cannot, in particular, have an array type. The simplest approach would
be to specify that there's always an underlying array of char type, and
to define arithmetic on T* objects in terms of movement though that
underlying array in steps of sizeof(T).

My understanding is that the object that malloc "creates" is effectively
a union of every possible type that could fit into the space (or array
of objects). This isn't formally defined by the standard,

It isn't defined at all, formally or not. Adding such a definition would
resolve the issue I'm talking about, but it has some unfortunate side
effects.

Currently, if you write to a block of dynamically allocated memory using
an lvalue of float type, it acquires the effective type of 'float'. If
you subsequently try to read that memory using an lvalue of 'int' type,
the behavior is undefined (6.5p7). This rule enables optimizations that
are based upon the assumption that, for example, an lvalue of float type
never aliases an lvalue of int type. As a result, a function that takes
a float* argument and an int* argument can read a float value using the
first pointer, and then write things through the second pointer, and
never have to worry about having to reload the float value. The int*
might alias the same memory location as the float*, so that such writes
might change the value represented when the same memory is read as a
float. However, the compiler is relieved of the responsibility of
checking for that possibility, and re-loading the float value, if
necessary, because 6.5p7 says that it won't be necessary.

Unions can render such optimizations invalid, but only when the union
type is in scope, and only for pairs of types both involved in the same
union. Your approach would have the union always in scope, and since
it's a universal union, it would affect all possible pairs of object types.

 

[Malcolm McLean]

Turing equivalence is not a theorem, it's a characteristic that a given
language may or may not have. There might be a theorem that says that a
given language is Turing equivalent, but I know of no actual theorem
that says that all languages are Turing equivalent (and in fact there
could be no such theorem, since not all languages *are* Turing
equivalent).

I think what you're talking about might be a definition, not a theorem.

You're making the same mistake as Ben.

Of course Turing equivalence is a "theorem". Just as the theorem that
any two squares are identical part from translation, rotation, and scaling.
Ok, but what if we're not talking about the Euclidean plane? What about
Trafalgar square - that's a square, isn't it?

It becomes tautological. If a computer isn't Turing complete, or if it is
capable of determining a non-computable function (e.g. if it can use
natural language), then it's not a "computer". It doesn't mean that
Turing was saying nothing.

 

[Kenny McCormack]

You're making the same mistake as Ben.

I don't think you are allowed to say that Kiki is wrong.

Not in this newsgroup.

--
BigBusiness types (aka,
Republicans/Conservatives/Independents/Liberatarians/whatevers)
don't hate big government. They *love* big government as a means for
them to get rich, sucking off the public teat. What they don't like is
*democracy* - little people actually having the right to vote and stuff
like that.

 

[Keith Thompson]

You're making the same mistake as Ben.

Of course Turing equivalence is a "theorem". Just as the theorem that
any two squares are identical part from translation, rotation, and scaling.
Ok, but what if we're not talking about the Euclidean plane? What about
Trafalgar square - that's a square, isn't it?

Can you give a brief statement of this "theorem"?

A given language or system either is or is not Turing equivalent.
A theorem might say that some system or set of systems *are*
Turing equivalent.

Using your analogy, "identical to a square apart from translation,
rotation, and scaling" is not a theorem. "Some particular entity is
identical ..." or "some set of entities are identical ..." might be a
theorem.

You're just misusing the word "theorem", that's all.