Making Fatal Hidden Assumptions

On 2006-03-22, Keith Thompson <kst-u@mib.org> wrote:
> Andrew Reilly <andrew-newspost@areilly.bpc-users.org> writes:
>> On Tue, 21 Mar 2006 19:02:55 -0600, Stephen Sprunk wrote:
>>> If a system traps on a prefetch, it's fundamentally broken.  However, a 
>>> system that traps when an invalid pointer is loaded is not broken, and the 
>>> AS/400 is the usual example.  Annoying, but not broken.
>>
>> And I still say that constraining C for everyone so that it could fit the
>> AS/400, rather than making C-on-AS/400 jump through a few more hoops to
>> match traditional C behaviour, was the wrong trade-off.  I accept that
>> this may well be a minority view.
>
> It is.  The C standard wouldn't just have to forbid an implementation
> from trapping when it loads an invalid address; it would have to
> define the behavior of any program that uses such an address. 

Why? It's not that difficult to define the behavior of a program that
"uses" such an address other than by dereferencing, and no problem to
leave the behavior undefined for dereferencing

> A number of examples have been posted here where that could cause
> serious problems for some implementations other than the AS/400.

In article <Pine.LNX.4.60-041.0603212039060.21985@unix42.andrew.cmu.edu> "Arthur J. O'Dwyer" <ajonospam@andrew.cmu.edu> writes:
 > On Wed, 22 Mar 2006, Dik T. Winter wrote:
 > > Andrew Reilly <andrew-newspost@areilly.bpc-users.org> writes:
 > > ...
 > > > > Interesting features. I'm not sure how much different multiple value
 > > > > returns would be from values returned via reference parameters
 > > > > (pointers).  it sounds like a good idea.
 > > >
 > > > The significant difference is that reference parameters (pointers) can't
 > > > be in registers.
 > >
 > > Why not?  I have worked with a lot of implementations where the first few
 > > parameters were passed through registers.  (Depending on the processor,
 > > from four to eight.)  And i many cases no need at all to put those pointers
 > > on the stack.
 > 
 > I believe Andrew means
 > 
 >        void foo(int & x)

I thought we were talking about C.
-- 
dik t. winter, cwi, kruislaan 413, 1098 sj  amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn  amsterdam, nederland; http://www.cwi.nl/~dik/

In article <slrne21c2l.17jl.random832@random.yi.org> Jordan Abel <random832@gmail.com> writes:
 > On 2006-03-22, Keith Thompson <kst-u@mib.org> wrote:
 > > Andrew Reilly <andrew-newspost@areilly.bpc-users.org> writes:
...
 > >> And I still say that constraining C for everyone so that it could fit the
 > >> AS/400, rather than making C-on-AS/400 jump through a few more hoops to
 > >> match traditional C behaviour, was the wrong trade-off.  I accept that
 > >> this may well be a minority view.
 > >
 > > It is.  The C standard wouldn't just have to forbid an implementation
 > > from trapping when it loads an invalid address; it would have to
 > > define the behavior of any program that uses such an address. 
 > 
 > Why? It's not that difficult to define the behavior of a program that
 > "uses" such an address other than by dereferencing, and no problem to
 > leave the behavior undefined for dereferencing

But that would have locked out machines that strictly separate pointers
and non-pointers, in the sense that you can not load a pointer in a
non-pointer register and the other way around.  Note also that on the
AS/400 a pointer is longer than any integer, so doing arithmetic on them
in integer registers would require quite a lot.
-- 
dik t. winter, cwi, kruislaan 413, 1098 sj  amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn  amsterdam, nederland; http://www.cwi.nl/~dik/

On 2006-03-22, Dik T. Winter <Dik.Winter@cwi.nl> wrote:
> In article <slrne21c2l.17jl.random832@random.yi.org> Jordan Abel <random832@gmail.com> writes:
>  > On 2006-03-22, Keith Thompson <kst-u@mib.org> wrote:
>  > > Andrew Reilly <andrew-newspost@areilly.bpc-users.org> writes:
> ...
>  > >> And I still say that constraining C for everyone so that it could fit the
>  > >> AS/400, rather than making C-on-AS/400 jump through a few more hoops to
>  > >> match traditional C behaviour, was the wrong trade-off.  I accept that
>  > >> this may well be a minority view.
>  > >
>  > > It is.  The C standard wouldn't just have to forbid an implementation
>  > > from trapping when it loads an invalid address; it would have to
>  > > define the behavior of any program that uses such an address. 
>  > 
>  > Why? It's not that difficult to define the behavior of a program that
>  > "uses" such an address other than by dereferencing, and no problem to
>  > leave the behavior undefined for dereferencing
>
> But that would have locked out machines that strictly separate pointers
> and non-pointers, in the sense that you can not load a pointer in a
> non-pointer register and the other way around.  Note also that on the
> AS/400 a pointer is longer than any integer, so doing arithmetic on them
> in integer registers would require quite a lot.

Surely there's some way to catch and ignore the trap from loading an
invalid pointer, though. I mean, it stops _somewhere_ even as it is now,
unless the register melts the silicon and drips through the floor, then
accelerates to the speed of light.

On Wed, 22 Mar 2006 03:03:47 +0000, Dik T. Winter wrote:

> In article <Pine.LNX.4.60-041.0603212039060.21985@unix42.andrew.cmu.edu> "Arthur J. O'Dwyer" <ajonospam@andrew.cmu.edu> writes:
>  > On Wed, 22 Mar 2006, Dik T. Winter wrote:
>  > > Andrew Reilly <andrew-newspost@areilly.bpc-users.org> writes:
>  > > ...
>  > > > > Interesting features. I'm not sure how much different multiple value
>  > > > > returns would be from values returned via reference parameters
>  > > > > (pointers).  it sounds like a good idea.
>  > > >
>  > > > The significant difference is that reference parameters (pointers) can't
>  > > > be in registers.
>  > >
>  > > Why not?  I have worked with a lot of implementations where the first few
>  > > parameters were passed through registers.  (Depending on the processor,
>  > > from four to eight.)  And i many cases no need at all to put those pointers
>  > > on the stack.
>  > 
>  > I believe Andrew means
>  > 
>  >        void foo(int & x)
> 
> I thought we were talking about C.

We were.  Sure, you can put a pointer into a register argument.

The point is that you can't take the address of a register state variable,
so you can't pass that "by reference" as a way to get multiple return
values out of a function.

Specifically;

double foo(double **pp)
{
	double *p = *pp;
	result = *p++;
	if (result > 0.0) result += *p++;
	*pp = p;
	return result;
}

void bar(double info[], int N)
{
	register double state = 0.0;
	register double *p = info;
	while (--N >= 0)
		state -= foo(&p);
}

Doesn't work, because &p doesn't work.

Another way to make this sort of thing "nice" (as far as code
factorization goes) is either dynamic scoping or nested function
definitions.  Then you could have:

void bar(double info[], int N)
{
	register double state = 0.0;
	register double *p = info;
	double foo() {
		double result = *p++;
		if (result > 0.0) result += *p++;
		return result;
	}
	while (--N >= 0)
		state -= foo();
}

That puts more limitations on code structure: you may well want to build
a library of foo-like mutators, and use them in functions other than
bar().  Multiple return values would help with that, by making the state
mutation explicit.

Cheers,

-- 
Andrew

Jordan Abel <random832@gmail.com> writes:
> On 2006-03-22, Keith Thompson <kst-u@mib.org> wrote:
>> Andrew Reilly <andrew-newspost@areilly.bpc-users.org> writes:
>>> On Tue, 21 Mar 2006 19:02:55 -0600, Stephen Sprunk wrote:
>>>> If a system traps on a prefetch, it's fundamentally broken.
>>>> However, a system that traps when an invalid pointer is loaded is
>>>> not broken, and the AS/400 is the usual example.  Annoying, but
>>>> not broken.
>>>
>>> And I still say that constraining C for everyone so that it could fit the
>>> AS/400, rather than making C-on-AS/400 jump through a few more hoops to
>>> match traditional C behaviour, was the wrong trade-off.  I accept that
>>> this may well be a minority view.
>>
>> It is.  The C standard wouldn't just have to forbid an implementation
>> from trapping when it loads an invalid address; it would have to
>> define the behavior of any program that uses such an address. 
>
> Why? It's not that difficult to define the behavior of a program that
> "uses" such an address other than by dereferencing, and no problem to
> leave the behavior undefined for dereferencing

The problem is pointer arithmetic.  For example, given:

    #define BUFFER_SIZE /* some big number */
    int buf[BUFFER_SIZE];
    int *ptr = buf + BUFFER_SIZE;
    int offset = /* some number */

Requiring (ptr + offset - offset == ptr) probably wouldn't be too much
of a burden for most systems, but requiring (ptr + offset > ptr) could
cause problems.  Given the current requirements, buf can be placed
anywhere in memory; there just (on some systems) needs to be a single
extra byte just past the end of the array.  Requiring out-of-bounds
pointer arithmetic to work "correctly" in all cases could be much more
burdensome.

And avoiding creating invalid pointers really isn't all that
difficult.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
San Diego Supercomputer Center             <*>  <http://users.sdsc.edu/~kst>
We must do something.  This is something.  Therefore, we must do this.

Andrew Reilly <andrew-newspost@areilly.bpc-users.org> writes:
> On Wed, 22 Mar 2006 03:03:47 +0000, Dik T. Winter wrote:
>> In article
>> <Pine.LNX.4.60-041.0603212039060.21985@unix42.andrew.cmu.edu>
>> "Arthur J. O'Dwyer" <ajonospam@andrew.cmu.edu> writes:
[...]
>>  > I believe Andrew means
>>  > 
>>  >        void foo(int & x)
>> 
>> I thought we were talking about C.
>
> We were.  Sure, you can put a pointer into a register argument.

"void foo(int & x)" is a syntax error in C.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
San Diego Supercomputer Center             <*>  <http://users.sdsc.edu/~kst>
We must do something.  This is something.  Therefore, we must do this.

On Wed, 22 Mar 2006 03:17:38 +0000, Dik T. Winter wrote:

> In article <slrne21c2l.17jl.random832@random.yi.org> Jordan Abel <random832@gmail.com> writes:
>  > On 2006-03-22, Keith Thompson <kst-u@mib.org> wrote:
>  > > Andrew Reilly <andrew-newspost@areilly.bpc-users.org> writes:
> ...
>  > >> And I still say that constraining C for everyone so that it could fit the
>  > >> AS/400, rather than making C-on-AS/400 jump through a few more hoops to
>  > >> match traditional C behaviour, was the wrong trade-off.  I accept that
>  > >> this may well be a minority view.
>  > >
>  > > It is.  The C standard wouldn't just have to forbid an implementation
>  > > from trapping when it loads an invalid address; it would have to
>  > > define the behavior of any program that uses such an address. 
>  > 
>  > Why? It's not that difficult to define the behavior of a program that
>  > "uses" such an address other than by dereferencing, and no problem to
>  > leave the behavior undefined for dereferencing
> 
> But that would have locked out machines that strictly separate pointers
> and non-pointers, in the sense that you can not load a pointer in a
> non-pointer register and the other way around.  Note also that on the
> AS/400 a pointer is longer than any integer, so doing arithmetic on them
> in integer registers would require quite a lot.

You don't have to do that at all.  As you said, AS/400 uses long,
decorative pointers that are longer than integers.  So no one's going
to notice if what your C compiler calls a pointer is actually a (base,
index) tuple, underneath.  Being object/capability machines, these
tuples point to whole arrays, not just individual bytes or words.  The
compilers could quite easily have managed all of C's pointer arithmetic as
actual arithmetic, using integers and indices, and only used or formed
real AS/400 pointers when the code did memory references (as base[index]).
There's no need for pointer arithmetic outside this model, against
different "base" pointers, so that's a straw-man argument.

Cheers,

-- 
Andrew

On Wed, 22 Mar 2006 03:41:07 +0000, Keith Thompson wrote:

> Jordan Abel <random832@gmail.com> writes:
>> On 2006-03-22, Keith Thompson <kst-u@mib.org> wrote:
>>> Andrew Reilly <andrew-newspost@areilly.bpc-users.org> writes:
>>>> On Tue, 21 Mar 2006 19:02:55 -0600, Stephen Sprunk wrote:
>>>>> If a system traps on a prefetch, it's fundamentally broken.
>>>>> However, a system that traps when an invalid pointer is loaded is
>>>>> not broken, and the AS/400 is the usual example.  Annoying, but
>>>>> not broken.
>>>>
>>>> And I still say that constraining C for everyone so that it could fit the
>>>> AS/400, rather than making C-on-AS/400 jump through a few more hoops to
>>>> match traditional C behaviour, was the wrong trade-off.  I accept that
>>>> this may well be a minority view.
>>>
>>> It is.  The C standard wouldn't just have to forbid an implementation
>>> from trapping when it loads an invalid address; it would have to
>>> define the behavior of any program that uses such an address. 
>>
>> Why? It's not that difficult to define the behavior of a program that
>> "uses" such an address other than by dereferencing, and no problem to
>> leave the behavior undefined for dereferencing
> 
> The problem is pointer arithmetic.  For example, given:
> 
>     #define BUFFER_SIZE /* some big number */
>     int buf[BUFFER_SIZE];
>     int *ptr = buf + BUFFER_SIZE;
>     int offset = /* some number */
> 
> Requiring (ptr + offset - offset == ptr) probably wouldn't be too much
> of a burden for most systems, but requiring (ptr + offset > ptr) could
> cause problems.

This is a really lame argument, IMO.

Given that we're working with fixed-word-length machines, rather than
scheme's bignums, p + offset > p doesn't even necessarily hold for
integers, so why should it hold more rigerously for pointers?  Wrap-around
or overflow is a fact of life for fixed-range machines.  You just deal
with it.  Don't go too close to the edge, or make damn sure you're
checking for it when you do.

>  Given the current requirements, buf can be placed
> anywhere in memory; there just (on some systems) needs to be a single
> extra byte just past the end of the array.  Requiring out-of-bounds
> pointer arithmetic to work "correctly" in all cases could be much more
> burdensome.

Correctness depends on what you're trying to do.  The one-byte-extra
argument doesn't help the fact that the flat memory model of C will still
"work OK" even if buf[BUFFER_SIZE-1] occupies the very last word in the
address space of the machine: there's no room for even that single byte
extra. Sure, in that instance, ptr = buf + BUFFER_SIZE will equal 0, and
your pointer comparison may break if you do it carelessly, but ptr[-1]
will still point to the last word in the array, and there are no dumb
restrictions against iterating backwards through the array, or forwards
with non-unit stride.

> And avoiding creating invalid pointers really isn't all that difficult.

No, of course it isn't.  Just use pointers as object handles, and do your 
pointer arithmetic with integers.  Whoopee: exactly the same syntax and
semantics as Pascal and Java.  I wonder why we bothered with pointers in
the first place?

-- 
Andrew

On Wed, 22 Mar 2006 03:48:19 +0000, Keith Thompson wrote:

> Andrew Reilly <andrew-newspost@areilly.bpc-users.org> writes:
>> On Wed, 22 Mar 2006 03:03:47 +0000, Dik T. Winter wrote:
>>> In article
>>> <Pine.LNX.4.60-041.0603212039060.21985@unix42.andrew.cmu.edu>
>>> "Arthur J. O'Dwyer" <ajonospam@andrew.cmu.edu> writes:
> [...]
>>>  > I believe Andrew means
>>>  > 
>>>  >        void foo(int & x)
>>> 
>>> I thought we were talking about C.
>>
>> We were.  Sure, you can put a pointer into a register argument.
> 
> "void foo(int & x)" is a syntax error in C.

I didn't use that syntax.  I believe that Arthur was probably confused by
the use of the term "pass by reference", for which the C idiom is to pass
(by value) a pointer to the argument, which doesn't work if the argument
is a register variable.

Now: did you have a useful point to make?

-- 
Andrew