In article <1992Dec20.201212.8974@lth.se> dag@bellman.control.lth.se (Dag Bruck) writes:
>I think we're sliding away from the original discussion.
>
>The goal was to write data structures that use the ordering of
>pointers to improve search time.  What I need is mechanism that
>compares the pointers -- what they actually point to is not relevant.

 Of course it is. You want < to be compatible with ==,
and the ARM says a==b if a and b point to the same object.

 Without this requirement, a<b==0 for all a,b is a perfectly
legal total order.

>
>I would finally like to return to a claim I made earlier, but nobody
>has commented on (as far as I know).  I belive that even if you
>imposed a total ordering on pointers in a segmented architecture
>(e.g., Inte 8086 family), compilers would be able to handle the
>follwing common case efficiently:

 Now hang on there. The 8086 in my view does not have a segmented
address space, it has a linear address space. The 286 and 386 have
real segmented address spaces.

 Doing < on the 8086 would be just about the same overhead
as == plus a bit (comparisons for equality are slightly simpler
than less). Just guessing that these operations would be about
5-20 times slower than a single register to register comparison.
I.e., significant but not insummountable.

 On the 386, if there was no aliasing, a slight mess
converting 32 bit pointer to 48 bit ones before a 48 bit
compare.
>
> void zap(int* a, unsigned n)
> {
>  for (int* p = a; p < a+n; p++)
>   *p = 0;
> }
>
>and produce the same code as today (without the total ordering).
>After all, the assignment "p = a" says that "p" must point to the same
>segment as "a".  Any comments?

 True. Sometimes the comparisons could be optimised.
(On the 386. On the 8086, if n>32K, you would not be able to
fit the array in one segment)

 So there remains the conformance issue. Existing
code will be broken. Note: actually it WONT be broken,
vendors simply wont implement this requirement of the standard
in some memory models. (Or they'll provided the dreaded compatibility
switch)



--
;----------------------------------------------------------------------
        JOHN (MAX) SKALLER,         maxtal@extro.ucc.su.oz.au
 Maxtal Pty Ltd, 6 MacKay St ASHFIELD, NSW 2131, AUSTRALIA
;--------------- SCIENTIFIC AND ENGINEERING SOFTWARE ------------------

In article <1992Dec18.204337.3084@lth.se> dag@bellman.control.lth.se (Dag Bruck) writes:
|In <comp.std.c++> maxtal@extro.ucc.su.OZ.AU (John MAX Skaller) writes:
|>
|>In fact, p==q iff objects equal is unimplementable on some machines.
|>That is, even the existing ARM requirement is unworkable.
|
|No, some machines are unworkable :-).

Agreed -- we just disagree on what machines.  The implementors of Smalltalk,
Smalltalk machines, the Mac systems, The Windows systems, OODBMSs, and I,
believe that machines with immovable objects, paging in 4K chunks,
are "unworkable" for serious object oriented work.  The basic problem is
that objects are typically about 100 bytes, implying an average of 40
objects per 4K page.  The 40 objects do not typically consistently remain
to the same temporal working set.  Thus paging needs finer granulaty,
or objects must be moveable.  Objects cannot in general be moveable to
an appropriate current temporal working set and simultaneously retain their
global address space orderings in memory.  Unless one had hardware paging
in much smaller chunks than 4K -- which in fact 386/486 machines DO support
in one addressing mode -- not commonly used in typical OS's.

In article <1992Dec20.201212.8974@lth.se> dag@bellman.control.lth.se (Dag Bruck) writes:
|The goal was to write data structures that use the ordering of
|pointers to improve search time.  What I need is mechanism that
|compares the pointers -- what they actually point to is not relevant.

On the contrary, you DO NOT then need such a mechanism, because alternate
approaches not using pointers can give you similar improvements to search times.

|C and C++ has some notion of equality between pointers.  You can
|clobber the semantics of this equality with memory mapping and what
|not, but that is in my view an issue beyond the language.

Agreed, as long as *you* stick to the C and C++ notion of equality
between pointers -- which is an extremely limited notion of equality.

|I would finally like to return to a claim I made earlier, but nobody
|has commented on (as far as I know).  I belive that even if you
|imposed a total ordering on pointers in a segmented architecture
|(e.g., Inte 8086 family), compilers would be able to handle the
|follwing common case efficiently:
|
| void zap(int* a, unsigned n)
| {
|  for (int* p = a; p < a+n; p++)
|   *p = 0;
| }
|
|and produce the same code as today (without the total ordering).
|After all, the assignment "p = a" says that "p" must point to the same
|segment as "a".  Any comments?

You statement is true, but does not imply your intended conclusion,
namely that thus one can efficiently implement total ordering.

In article <9235622.25712@mulga.cs.mu.OZ.AU> fjh@munta.cs.mu.OZ.AU (Fergus James HENDERSON) writes:
|A ptrcmp that always returned 0 would be useless, IMHO.

Such an implementation would allow people to write code that does the
ptrcmp.  If the ptrcmp is zero, then the pointers could be compared.
If the pointers didn't compare equal, then the invoking code would know
that this machine doesn't support ptrcmp, and then the invoking code would
fall back on a secondary, possibly slightly slower [but more globally
implementable] approach -- such as comparing object surrogates.

Thus such a ptrcmp would allow "optimal" performance on those systems
that can reasonably implement a total ordering, and would allow near
optimal performance on those machines that can't reasonably implement
a total ordering.  Rather than insisting that those systems that can't
reasonably implement ptrcmp do so anyway, or alternately not implement it
at all, leading to "portable" code that isn't in practice portable anyway.

jbn@lulea.trab.se (Johan Bengtsson) writes:

>Fergus James HENDERSON (fjh@munta.cs.mu.OZ.AU) wrote:
>: jbn@lulea.trab.se (Johan Bengtsson) writes:
>
>: >Markku Sakkinen (sakkinen@jyu.fi) wrote:
>: >: BTW, actually total order is
>: >: a simple thing within an OODB _because_ the identity of each object
>: >: is assured not to change.
>: >
>: >It would impose severe restrictions on how the virtual address space
>: >could be used though.  The OODBMS may end up in a situation where
>: >it can't get a persistent object into memory, not because it has used up
>: >all virtual memory addresses, but because all unused virtual memory
>: >adresses would violate the total ordering property.
>
>: I thought that the idea was that for OODBMSs, you DON'T compare virtual
>: addresses for pointers to persistent objects, instead you compare the object
>: ids. Maybe someone could explain the problems in a little more detail?
>
>As Stuart MacMartin said, if the OODBMs uses objects of class Handle
>(never mind the name) to represent references to persistent objects
>you will need to have
>
>ptrcmp(Handle,Handle), if you want templates to compare Handles the
>same way they compare pointers.  The OODBMs should provide that.
>Also it should provide ptrcmp(Handle,void*) and ptrcmp(void*,Handle).

Actually, I don't think that these last two are necessary (see below).

>_Some_ OODBMs use void* as their Handles (they play tricks by
>using virtual memory mapping to persistent storage), so they must
>provide a ptrcmp(void*,void*) that can tell the difference between
>pointers to persistent objects and normal memory pointers.  For persistent
>objects, it then finds the object ids and makes the comparison.
>
>My point is that this may be difficult, or slow (although I don't
>really have any data on that).  The alternative is to simply compare
>the void pointers, even for pointers to persistent objects, however
>that imposes the unacceptable restrictions I described in my previous
>posting.

For these OODBMSs, (void *) == (void *) will be implemented simply by
comparing the void pointers. The statement in the ARM that "two pointers
to the same object compare equal" will NOT always hold.
(As you have been arguing, to implement == with this guarantee would be
too difficult and too inefficient).

Since these systems aren't going to be standard-compliant anyway,
unless we change the standard, I don't really know what we can
conclude from them with regard to ptrcmp().

>A more difficult issue is what do you do if there is more than one
>OODBMs in use, or more realistically, one OODBM, and one distributed
>object manager (that similarly uses Handles to distributable objects).
>Who is responsible for providing the needed ptrcmp(OODB_Handle,Distr_Handle)
>and ptrcmp(Distr_Handle,OODB_Handle) functions?  This may become
>totally unmanageable if handle-based schemes become common.

The template classes are always going to be comparing objects of the
same type. If you have a collection of OODB_Handles, then use
ptrcmp(OODB_Handle, OODB_Handle). If you have a collection of
Distr_Handles, then use ptrcmp(Distr_Handle, Distr_Handle). If you have
a collection that you want to use to store both Distr_Handles and
OODB_Handles, then you will have to write your own type-safe union
class Any_Handle anyway, and then *you* are going to be the one who
will implement ptrcmp(Any_Handle, Any_Handle). There is no need for
ptrcmp(Distr_Handle, OODB_Handle).

>Hope this is a little bit clearer.

Quite a bit clearer. Thanks!

--
Fergus Henderson             fjh@munta.cs.mu.OZ.AU
This .signature virus is a self-referential statement that is true - but
you will only be able to consistently believe it if you copy it to your own
.signature file!

maxtal@extro.ucc.su.OZ.AU (John MAX Skaller) writes:

>daniel@cse.ucsc.edu (Daniel R. Edelson) writes:
[...]
>>Thus, this property need not be true in any program that
>>calls the operating system.
>
> That is in the spirit of what I wanted, but I'm
>not sure if a standard can say it in those words. Besides,
>I wanted to be more explicit: even if I do an operting
>system call somewhere, I want the system
>to guarrantee
>
> T* p=new T;
> T* q=p;
> if(!(p==q))cout<"Non conforming program";

I'm afraid that this is not possible.
For proof, consider the following hypothetical operating system call:

 random_poke() : sets a random memory location to a random value

After calling this operating system call, you can make NO further guarantees
about the behaviour of your system.

--
Fergus Henderson             fjh@munta.cs.mu.OZ.AU
This .signature virus is a self-referential statement that is true - but
you will only be able to consistently believe it if you copy it to your own
.signature file!

maxtal@extro.ucc.su.OZ.AU (John MAX Skaller) writes:

>fjh@munta.cs.mu.OZ.AU (Fergus James HENDERSON) writes:
>>maxtal@extro.ucc.su.OZ.AU (John MAX Skaller) writes:
>>
>>>pat@frumious.uucp (Patrick Smith) writes:
>>>>   p == q   =>   ptrcmp(p,q) == 0
>>>
>>> I'm NOT agreeing with this at present. I reject any relationship
>>>between p ? q and ptrcmp. On some machines any such relationship
>>>might make ptrcmp unimplementable, and thus defeat the proposal completely.
>>
>>I remain unconvinced that such a relationship is unimplementable on
>>some machines.
>
> On the 486 it is not in general possible to implement
>the comparison p==q for arbitrary logical addresses. If p and q
>are aliases only the operating system kernel could implement
>the comparison, and if the OS happened not to support this,
>p==q could not be implemented.

*In general* this is true, but we are not talking about the general case.
All that is required is that it be true for conformant C++ programs.
This does not require checking whether segment aliases exist, it just requires
ensuring that they won't occur for conformant C++ programs.

>>>It is only Jims suggestion that ptrcmp might always return 0 that
>>>makes it possible to make its existence mandatory.
>>
>>A ptrcmp that always returned 0 would be useless, IMHO.
>
> Not at all. My sort will still order the pointers
>into the total order, which in this case is anything.
>
> This is entirely different from the current situation
>where a sort based on the existing implementation defined <
>on pointers might not terminate.

Yes, you are correct. I retract that statement.

--
Fergus Henderson             fjh@munta.cs.mu.OZ.AU
This .signature virus is a self-referential statement that is true - but
you will only be able to consistently believe it if you copy it to your own
.signature file!

In article <5347@holden.lulea.trab.se> jbn@lulea.trab.se (Johan Bengtsson) writes:
>Dag Bruck (dag@seldon.control.lth.se) wrote:
>:  p == q   <=>   ptrcmp(p,q) == 0
>
>:  p != q   <=>   ptrcmp(p,q) != 0
>
>:  ptrcmp(p,q) < 0   <=>   ptrcmp(q,p) > 0
>
>I think ptrcmp() is a good way to resolve this issue.
>
>There is only one possible remaining weakness (I think):

 I disagree, but anyhow ...
>
>Any environment that relies on pointer translation (swizzling) to
>transport objects between executing processes will have difficulty
>maintaining a common total ordering for the pointers (IDs) of
>objects within those processes (Jim Adcock pointed this out).
>Examples include OODBMS and distributed systems.  Code relying
>on ptrcmp() may be unportable to those environments.
>
>Should those environments be required to (somehow) provide special
>ptrcmp() functions, that look at some object ID (not memory address)?
>What if a program uses more than one pointer swizzling scheme (e.g.
>distributing some objects over communication channels, and storing other
>objects in an OODBMS)?  Is it the users job to provide the ordering
>between those different object spaces?
>
>Anyone have a good solution for this?
>
 Yes. First look at ==. It is already flawed. The rules
must be rewritten so that == has the given semantics only
in 'domestic' cases. The results of == can be implementation
defined in any cases the pointers are not derived by
'ordinary' operations. That lets OODBMS off the hook.

 The same solution can be applied to ptrcmp now.

--
;----------------------------------------------------------------------
        JOHN (MAX) SKALLER,         maxtal@extro.ucc.su.oz.au
 Maxtal Pty Ltd, 6 MacKay St ASHFIELD, NSW 2131, AUSTRALIA
;--------------- SCIENTIFIC AND ENGINEERING SOFTWARE ------------------

In article <KANZE.92Dec10165804@slsvdnt.us-es.sel.de> kanze@us-es.sel.de (James Kanze) writes:
>|> alternative is of course to dismiss the idea as not worth the trouble.
>
>I favor the latter case.

 I think that MANY collections will be collections of pointers.
MANY of these types of collections will rely on there existing some
total ordering. SOME of these will also require some that

 p==q <==> ptrcmpeq(p,q)==0

where I used ptrcmpeq to denote the version of ptrcmp that supports
the above identity, whereas plain ptrcmp need not, and might
always return 0.

(A third version, ptrcmppo might also preserve partial ordering of <.)

Therefore I think it is worth persuing the issue,
especially as the 'ptrcmp' idea is an extension to the library,
and thus might be acceptable to the committee, whereas changing
the status of < might not.

 In fact I believe the status of == must be downgraded,
even at the expense of C compataibility, and that will be a tough
enough battle as it is.

--
;----------------------------------------------------------------------
        JOHN (MAX) SKALLER,         maxtal@extro.ucc.su.oz.au
 Maxtal Pty Ltd, 6 MacKay St ASHFIELD, NSW 2131, AUSTRALIA
;--------------- SCIENTIFIC AND ENGINEERING SOFTWARE ------------------

In article <1992Dec16.150144.6004@ucc.su.OZ.AU> maxtal@extro.ucc.su.OZ.AU (John MAX Skaller) writes:
|In article <1992Dec14.225659.24225@microsoft.com> jimad@microsoft.com (Jim Adcock) writes:
|>I think some flavor of "ptrcmp" makes sense on those implementations that
|>support casting pointers to integrals and back, and probably doesn't make
|>sense on those implementations that don't support the pointer/integral casts.
|
| Why not?

Because in the cases I can think of, if one fails to be reasonably implementable
on a given system, the other also fails to be reasonably implementable, and
since C already allows that systems NOT be required to support the
pointer/integral cast.

|>In either case, I would ask what kind of sense it makes to write a "standard"
|>that *requires* a certain behavior of *some* implementation but doesn't
|>*require* that behavior of *all* implementations?  How do you justify such
|>a dichotomy?
|
| ptrcmp is standard, required function, it must yield a total
| order.

I was referring to the pointer/integral cast.  It is not required of
all systems, only of some systems.  *Required* of *some* systems????
This certainly contradicts my expectations of what a "standard" means!

| In that case it is implementable on all systems
| where (opinion follows, please correct errors)
|
| a) void* is big enough to hold all pointer types
This assumption is almost univerally violated.

| b) conversions always pad systematically
| c) bitwise comparison is done
| d) the bits of a pointer cannot be magically changed by the system
Violated  by real mode Windows, Violated by evacuating GC'ed machines.
Violated by at least one GC'ed C++ implementation. Violated by
at least some OODBMSs.

| e) a pointer is implemented as an object in contiguous storage
Probably violated by some OODBMSs.

| Certainly, (e) might cause problems on the 80x86 where part of the
|pointer is implicit and not physically stored. Does it *actually*
|cause this problem?

No because implied segments can be made specific.  Segments can
be moved on some systems however, implying an ordering that requires
the segment part will not remain consistent.  Within a segment however,
object orderings remain consistent.  Unless the PC is running a system
with GC and ptr tracing, such that objects are moved to be compacted.
Since such systems by a large margin have the best memory management
that I've seen, I think it would be a big mistake to preclude them
for the kind of algorithm implemetation tricks you guys have been
talking about -- especially since surrogates or similar approaches
can accomplish your goals about as well as the ptrcmp stuff.

In article <1992Dec16.201044.2968@microsoft.com> jimad@microsoft.com (Jim Adcock) writes:
>In article <1992Dec15.162202.11231@ucc.su.OZ.AU> maxtal@extro.ucc.su.OZ.AU (John MAX Skaller) writes:
>|But Jim, it is not implementation defined, it is required that
>|pointers to the same object compare equal. It is therefore
>|legal to have a function:
>|
>| f(X* a, X*b) {
>| if(a==b) { /* special case, copy b object */ ... }
>| else *a+=*b;
>| }
>|
>However, if a strictly conforming implementation is presented with a
>non-strictly conforming program, such as a program that calls OS
>virtual memory mapping adjustment routines, or programs that send
>pointers off the ends of arrays, or programs who don't properly point
>at objects that correspond to the types of objects they pretend to point
>at .... in all such cases all bets are off.
>
 I know what you are saying but dont see it.
ARM p74:"two pointers to the same object compare equal".
Any program for which this is not true cannot be conforming,
neither strictly nor non-strictly, it is non-conforming, it is
not in fact a C++ program.

 Or have I got this wrong?

 For this reason I think the ARM requirement is unworkable,
and must be modified. The rule should state that pointers
derived from the same object directly in the program must
compare equal. Pointers obtained from the OS need not follow
this rule, in that case it is implementation defined.
This is the case for pointers way off the end of an array:
it is implementation defined.

 (When I say 'derived' from the same object, I
am defering the exact definition :-)

--
;----------------------------------------------------------------------
        JOHN (MAX) SKALLER,         maxtal@extro.ucc.su.oz.au
 Maxtal Pty Ltd, 6 MacKay St ASHFIELD, NSW 2131, AUSTRALIA
;--------------- SCIENTIFIC AND ENGINEERING SOFTWARE ------------------

pkt@lpi.liant.com (Scott Turner) writes:
|In article <1992Dec15.162202.11231@ucc.su.OZ.AU> John (Max) Skaller writes:
|It makes me uneasy, but I think Jim Adcock is correct: an implementation
|can define an extension, such as memory mapping, which overrides the usual
|execution time rules of C/C++, including the rule that pointers to the same
|object compare equal.  The rule that 1+1==2 would likewise be subject to
|"extension".

For C, this is my impression also.  Although I find the terminology
unfortunate; it's unsettling to think that a conforming implementation
could compile and run a conforming program - which could then compute
1+1 and get 3.

Has X3J16 adopted similar notions of conformity?


|Nevertheless, the C standard implies that the onus is on the invoker of memory
|mapping to be aware of libraries and other code which may rely on the usual
|execution time rules of C/C++, such as the rule that pointers to the same
|object compare equal.  If we don't want libraries to make that assumption,
|then John (Max) Skaller is also correct to say
|
|> So the question is really whether the requirement that pointers to
|> the same object compare equal should be left implementation defined.

Here I would disagree.  I think the question is whether, if the C++
standard adopts the same notions of conformity as the C standard,
pointers to the same object should be required to compare equal
in a conforming program.

And the answer is _no_.  I hope this requirement would exist for
_strictly_ conforming programs.  And it might be _reasonable_ to
expect it to hold in conforming programs.  But in a conforming
program which depends on behaviour undefined or unspecified by
the standard, none of the rules apply, so the standard doesn't
actually _require_ anything.  (It's not clear to me whether all
rules disappear if a program fails to be strictly programming
because it depends on implementation-defined behaviour, but it
doesn't depend on any undefined or unspecified behaviour.)

--
Patrick Smith
uunet.ca!frumious!pat
pat%frumious.uucp@uunet.ca

In article <BzCG7K.2sG@frumious.uucp> pat@frumious.uucp (Patrick Smith) writes:
>dag@seldon.control.lth.se (Dag Bruck) writes:
>| Suggested semantics: for any pointers p and q:
>|
>|       p == q   <=>   ptrcmp(p,q) == 0
>|
>|       p != q   <=>   ptrcmp(p,q) != 0
>|
>|       if p < q is defined,  ptrcmp(p,q) < 0   <=>  p < q
>
>On the other hand, this might be fairly cheap, given that
>we're already insisting on
>
>   p == q   =>   ptrcmp(p,q) == 0
>

 I'm NOT agreeing with this at present. I reject any relationship
between p ? q and ptrcmp. On some machines any such relationship
might make ptrcmp unimplementable, and thus defeat the proposal completely.
It is only Jims suggestion that ptrcmp might always return 0 that
makes it possible to make its existence mandatory.

In fact, p==q iff objects equal is unimplementable on some machines.
That is, even the existing ARM requirement is unworkable.

Consider that p < q is implementation defined, so it could mean
almosty anything. It does not have to obey ANY rules, unless
the pointers are into the same array.

As such tying < to ptrcmp, or any such function which requires
a total order immediately makes the specification inconsistent,
and thus it will have to be rejected.

Lets stop having 'wish lists' here and analyse the problem
properly. The first thing we have to do is fix the
unworkable requirement that p==q iff p,q point to same object.



--
;----------------------------------------------------------------------
        JOHN (MAX) SKALLER,         maxtal@extro.ucc.su.oz.au
 Maxtal Pty Ltd, 6 MacKay St ASHFIELD, NSW 2131, AUSTRALIA
;--------------- SCIENTIFIC AND ENGINEERING SOFTWARE ------------------

In article <1992Dec17.230520.13836@microsoft.com> jimad@microsoft.com (Jim Adcock) writes:
>Granted that an inverse mapping can
>give you the obid from the pointer, its just that such would typically
>be very slow compared to the address comparisons you expect.  Slower
>than using surrogates for example.  So why not use surrogates?

Not to mention the fact that some of us feel that the object id should
be private information of the OODBMS.  I would not like a specification
that effectively required the oid to escape into the application.
If I were an OODBMS developer, I might then be tempted to have 2 oids
per object, one for references and the other for ordering.

Stuart
--
: Stuart MacMartin                                    email: sjm@bnr.ca      :
: Bell-Northern Research                              phone: (613) 763-5625  :
: PO Box 3511, Stn C, Ottawa, K1Y-4H7, CANADA    Standard disclaimers apply. :

In <comp.std.c++> maxtal@extro.ucc.su.OZ.AU (John MAX Skaller) writes:
>>>
>>>In fact, p==q iff objects equal is unimplementable on some machines.
>>>That is, even the existing ARM requirement is unworkable.
>
>Perhaps we can conceive two types of pointers, type 1
>provides no comparisons at all, type 2 allows equality test.

I think we're sliding away from the original discussion.

The goal was to write data structures that use the ordering of
pointers to improve search time.  What I need is mechanism that
compares the pointers -- what they actually point to is not relevant.

Let me try to put it differently: the element type is "pointer to X",
not "X" itself.

C and C++ has some notion of equality between pointers.  You can
clobber the semantics of this equality with memory mapping and what
not, but that is in my view an issue beyond the language.

I would finally like to return to a claim I made earlier, but nobody
has commented on (as far as I know).  I belive that even if you
imposed a total ordering on pointers in a segmented architecture
(e.g., Inte 8086 family), compilers would be able to handle the
follwing common case efficiently:

 void zap(int* a, unsigned n)
 {
  for (int* p = a; p < a+n; p++)
   *p = 0;
 }

and produce the same code as today (without the total ordering).
After all, the assignment "p = a" says that "p" must point to the same
segment as "a".  Any comments?

  -- Dag

jbn@lulea.trab.se (Johan Bengtsson) writes:

>Markku Sakkinen (sakkinen@jyu.fi) wrote:
>: BTW, actually total order is
>: a simple thing within an OODB _because_ the identity of each object
>: is assured not to change.
>
>It would impose severe restrictions on how the virtual address space
>could be used though.  The OODBMS may end up in a situation where
>it can't get a persistent object into memory, not because it has used up
>all virtual memory addresses, but because all unused virtual memory
>adresses would violate the total ordering property.

I thought that the idea was that for OODBMSs, you DON'T compare virtual
addresses for pointers to persistent objects, instead you compare the object
ids. Maybe someone could explain the problems in a little more detail?

--
Fergus Henderson             fjh@munta.cs.mu.OZ.AU
This .signature virus is a self-referential statement that is true - but
you will only be able to consistently believe it if you copy it to your own
.signature file!

maxtal@extro.ucc.su.OZ.AU (John MAX Skaller) writes:

>pat@frumious.uucp (Patrick Smith) writes:
>>   p == q   =>   ptrcmp(p,q) == 0
>
> I'm NOT agreeing with this at present. I reject any relationship
>between p ? q and ptrcmp. On some machines any such relationship
>might make ptrcmp unimplementable, and thus defeat the proposal completely.

I remain unconvinced that such a relationship is unimplementable on
some machines.

>It is only Jims suggestion that ptrcmp might always return 0 that
>makes it possible to make its existence mandatory.

A ptrcmp that always returned 0 would be useless, IMHO.

--
Fergus Henderson             fjh@munta.cs.mu.OZ.AU
This .signature virus is a self-referential statement that is true - but
you will only be able to consistently believe it if you copy it to your own
.signature file!

maxtal@extro.ucc.su.OZ.AU (John MAX Skaller) writes:

>jimad@microsoft.com (Jim Adcock) writes:
>>maxtal@extro.ucc.su.OZ.AU (John MAX Skaller) writes:
>>|But Jim, it is not implementation defined, it is required that
>>|pointers to the same object compare equal. It is therefore
>>|legal to have a function:
>>|
>>| f(X* a, X*b) {
>>| if(a==b) { /* special case, copy b object */ ... }
>>| else *a+=*b;
>>| }
>>|
>>However, if a strictly conforming implementation is presented with a
>>non-strictly conforming program, such as a program that calls OS
>>virtual memory mapping adjustment routines, or programs that send
>>pointers off the ends of arrays, or programs who don't properly point
>>at objects that correspond to the types of objects they pretend to point
>>at .... in all such cases all bets are off.
>>
> I know what you are saying but dont see it.
>ARM p74:"two pointers to the same object compare equal".
>Any program for which this is not true cannot be conforming,
>neither strictly nor non-strictly, it is non-conforming, it is
>not in fact a C++ program.
>
> Or have I got this wrong?

I think you have got this wrong.
Such a program might be neither strictly nor non-strictly conforming,
but it is still a C++ program, at least in as far as that term is
commonly used.

> For this reason I think the ARM requirement is unworkable,
>and must be modified. The rule should state that pointers
>derived from the same object directly in the program must
>compare equal. Pointers obtained from the OS need not follow
>this rule, in that case it is implementation defined.
>This is the case for pointers way off the end of an array:
>it is implementation defined.

Remember that the ARM is a reference manual, not a standard.
I believe that the ANSI C standard makes it clear that for
programs that invoke code whose behaviour is "undefined", all
bets are off. (The usual remark is that the system is allowed
to spew frogs from the tape-drive, or something equally ridiculous,
so desires). This is equally true of programs that invoke the
operating system (other than by standard library functions
defined in the ANSI C standard). Any guarantees about the
behaviour of such programs must be made by a standard for that
particular operating system, not by the ANSI C standard.
The same will apply to the ANSI or ISO C++ standard, when
it arrives.

--
Fergus Henderson             fjh@munta.cs.mu.OZ.AU
This .signature virus is a self-referential statement that is true - but
you will only be able to consistently believe it if you copy it to your own
.signature file!

maxtal@extro.ucc.su.OZ.AU (John MAX Skaller) writes:

>However, lets consider that Unix file names are 'pointers' to files,
>and that links are allowed.
>
>Then the average program cant tell if two file names point to
>the same file or not, since computing the inode number is the only
>way to do that, and only super users can do this calculation.
>(Imagine I'm right even if this isnt the case. Is it the case?)

No. Computing the inode number is not a privileged operation.

>Would this make such a system 'unworkable'?

Not if the system had mandatory (as opposed to advisory) locks.

>The issue is whether pointers must provide any more functionality
>than the ability to access an object, that is, whether object
>identity can be established by pointer comparisons.

Like it or not (in many ways I don't!), it seems that this principle
is firmly entrenched in C++. Consider the requirement
empty classes must have non-zero sizes, etc.

>I suggest that whole classes of software can be written that
>do not rely on the ability to test if two pointers refer
>to the same object or not, other types of software require
>this information.
>
>Perhaps we can conceive two types of pointers, type 1
>provides no comparisons at all, type 2 allows equality test.
>
>Most of the code I've written uses type 1, and most uses
>of type 2 could be rewritten as type 1.

Equality tests are often needed in assignment operators, to
check for the special case of x=x.

>In those cases where type 2 pointers are desirable, it
>seems reasonable to restrict them to pointers
>to objects created directly by me, and not the operating
>system.
>
>Thus I would like to see the ARM == rewritten so the
>results of == on externally derived or otherwise mangled
>pointers are implementation defined.

As I said in a previous post, I think that this is already
the case for C, and I expect it to be the same for C++
when the ANSI or ISO C++ standard finally comes out.
Once you have invoked the operating system, all bets are off.

--
Fergus Henderson             fjh@munta.cs.mu.OZ.AU
This .signature virus is a self-referential statement that is true - but
you will only be able to consistently believe it if you copy it to your own
.signature file!

maxtal@extro.ucc.su.OZ.AU (John MAX Skaller) writes:

>kanze@us-es.sel.de (James Kanze) writes:
>>As it should.  The ARM (and the upcoming ANSI standard) can only
>>address what happens in the context of C++, not what happens to the
>>pointer once the OS gets its hands on it.
>
> No, this is not true IMHO. The ARM can and does explicitly
>or implicitly say "implementation defined" where it means that.
>When the ARM says "so and so will be the case" then it must
>always be the case.

No. The ARM described a contract between implementations and programmers,
such that IF the programmer abides by certain restrictions, then
the program will produce certain behaviour. If the programmer does
not abide by these restrictions, then the ARM does not guarantee anything
about the behaviour of the program.

>>In the same way, I would understand the ARM to be saying that all
>>pointers generated by a correct program to point to any object defined
>>(including a dynamic definition by new) in C++ will compare equal.  If
>>you give the pointer to the OS, and it gives it back to you, then any
>>guarantees must be made by the OS, and not the C++ language.
>
> I agree. But that is not the case. The ARM says different.
>It absolutely requires pointers to the same object to compare
>equal, without qualification. The system MUST ensure this
>to classify as conforming.

This statement is NOT without qualification. Virtually the whole of the
ARM is qualified by the caveat that if the program invokes undefined
behaviour, then all bets are off. Since the ARM is a reference manual,
not a standard, this caveat is implicit rather than explicit.

--
Fergus Henderson             fjh@munta.cs.mu.OZ.AU
This .signature virus is a self-referential statement that is true - but
you will only be able to consistently believe it if you copy it to your own
.signature file!

(Sorry for the zillions of articles I seem to have posted today,
I'm just trying to keep up with maxtal ;-)

maxtal@extro.ucc.su.OZ.AU (John MAX Skaller) writes:

> Thats not the issue. It might be UNIMPLEMENTABLE on
>some architectures. In fact, == is UNIMPLEMENTABLE in general
                                                    ^^^^^^^^^^
>on the 386 in protected mode, given the sloppy definition
>of 'same object' in the ARM. Its quite possible on the 386
>to have two logical addresses which convert to the
>same linear address, but NOT BE ABLE TO TELL THAT THIS IS THE CASE.
>Because to tell implies access to the LDT/GDT and the typical
>process is not able to read those tables. A special
>operating system function would be required to do this,
>and that would make C++ unimplementable on systems not
>having this function.

C++ implementations are not required to implement the correct
semantics for == in the general case, they only have to do so
for conforming programs. The compiler could ensure that
conforming programs never create two logical addresses which
map to the same linear address, and then the problem would not arise.

--
Fergus Henderson             fjh@munta.cs.mu.OZ.AU
This .signature virus is a self-referential statement that is true - but
you will only be able to consistently believe it if you copy it to your own
.signature file!

Fergus James HENDERSON (fjh@munta.cs.mu.OZ.AU) wrote:
: jbn@lulea.trab.se (Johan Bengtsson) writes:

: >Markku Sakkinen (sakkinen@jyu.fi) wrote:
: >: BTW, actually total order is
: >: a simple thing within an OODB _because_ the identity of each object
: >: is assured not to change.
: >
: >It would impose severe restrictions on how the virtual address space
: >could be used though.  The OODBMS may end up in a situation where
: >it can't get a persistent object into memory, not because it has used up
: >all virtual memory addresses, but because all unused virtual memory
: >adresses would violate the total ordering property.

: I thought that the idea was that for OODBMSs, you DON'T compare virtual
: addresses for pointers to persistent objects, instead you compare the object
: ids. Maybe someone could explain the problems in a little more detail?

As Stuart MacMartin said, if the OODBMs uses objects of class Handle
(never mind the name) to represent references to persistent objects
you will need to have

ptrcmp(Handle,Handle), if you want templates to compare Handles the
same way they compare pointers.  The OODBMs should provide that.
Also it should provide ptrcmp(Handle,void*) and ptrcmp(void*,Handle).

_Some_ OODBMs use void* as their Handles (they play tricks by
using virtual memory mapping to persistent storage), so they must
provide a ptrcmp(void*,void*) that can tell the difference between
pointers to persistent objects and normal memory pointers.  For persistent
objects, it then finds the object ids and makes the comparison.

My point is that this may be difficult, or slow (although I don't
really have any data on that).  The alternative is to simply compare
the void pointers, even for pointers to persistent objects, however
that imposes the unacceptable restrictions I described in my previous
posting.

A more difficult issue is what do you do if there is more than one
OODBMs in use, or more realistically, one OODBM, and one distributed
object manager (that similarly uses Handles to distributable objects).
Who is responsible for providing the needed ptrcmp(OODB_Handle,Distr_Handle)
and ptrcmp(Distr_Handle,OODB_Handle) functions?  This may become
totally unmanageable if handle-based schemes become common.

Hope this is a little bit clearer.

--------------------------------------------------------------------------
| Johan Bengtsson, Telia Research AB, Aurorum 6, S-951 75 Lulea, Sweden  |
| Johan.Bengtsson@lulea.trab.se; Voice:(+46)92075471; Fax:(+46)92075490  |
--------------------------------------------------------------------------
--
--------------------------------------------------------------------------
| Johan Bengtsson, Telia Research AB, Aurorum 6, S-951 75 Lulea, Sweden  |
| Johan.Bengtsson@lulea.trab.se; Voice:(+46)92075471; Fax:(+46)92075490  |
--------------------------------------------------------------------------

In article <1gtblgINN72@darkstar.UCSC.EDU> daniel@cse.ucsc.edu (Daniel R. Edelson) writes:
>
>> For this reason I think the ARM requirement is unworkable,
>>and must be modified. The rule should state that pointers
>>derived from the same object directly in the program must
>>compare equal. Pointers obtained from the OS need not follow
>>this rule, in that case it is implementation defined.
>
>Neither the C standard nor the C++ standard discusses any OS.
>(As far as I recall.)

 Precisely, nor should they, instead, they ought discuss
the conditions under which the rule is true, otherwise
it is implementation defined.
>
>A call to the operating system should be viewed as
>a call to an extension supplied by the language provider.
>A program that uses an extension can be conforming but
>not strictly conforming, as per the X3J16 definitions.

 Sure. But my interpretation of the p==q rule
is that any implementation in which it isnt true
is *non*-conforming. That is, there is no scope in the rule
for non-strict conformance.

>
>Thus, I think a better rule is:
> ``In a strictly conforming program, two pointers
> to the same object compare equal.''
>Thus, this property need not be true in any program that
>calls the operating system.

 That is in the spirit of what I wanted, but I'm
not sure if a standard can say it in those words. Besides,
I wanted to be more explicit: even if I do an operting
system call somewhere, I want the system
to guarrantee

 T* p=new T;
 T* q=p;
 if(!(p==q))cout<"Non conforming program";

But I want that

 q=alias(p); // OS call to alias pointer
 if(!(p==q))cout<"Not a strictly conforming program";

(Given that p and q point to the same object after aliasing).
In particular I dont want the above code to render the whole
program non-conforming.
>
>I think actually that ramifications of multiple inheritance
>and multiple object-addresses should be explicitly addressed
>in the rule, such as by saying that a pointer to a base-class
>subobject is not a pointer to the same object as a pointer
>to the most-derived class object.
>
 The rule only applies when p and q are the same type.
If a conversion from a derived to base type occurs a comparison
would quite correctly yield 1 if the base subobject was a
sub-object of the complete object.

 The other issue is whether empty subobjects are generated
or not, if they can be, pointers to different subobjects of the
same type might compare equal.

--
;----------------------------------------------------------------------
        JOHN (MAX) SKALLER,         maxtal@extro.ucc.su.oz.au
 Maxtal Pty Ltd, 6 MacKay St ASHFIELD, NSW 2131, AUSTRALIA
;--------------- SCIENTIFIC AND ENGINEERING SOFTWARE ------------------

In article <9235622.25712@mulga.cs.mu.OZ.AU> fjh@munta.cs.mu.OZ.AU (Fergus James HENDERSON) writes:
>maxtal@extro.ucc.su.OZ.AU (John MAX Skaller) writes:
>
>>pat@frumious.uucp (Patrick Smith) writes:
>>>   p == q   =>   ptrcmp(p,q) == 0
>>
>> I'm NOT agreeing with this at present. I reject any relationship
>>between p ? q and ptrcmp. On some machines any such relationship
>>might make ptrcmp unimplementable, and thus defeat the proposal completely.
>
>I remain unconvinced that such a relationship is unimplementable on
>some machines.

 On the 486 it is not in general possible to implement
the comparison p==q for arbitrary logical addresses. If p and q
are aliases only the operating system kernel could implement
the comparison, and if the OS happened not to support this,
p==q could not be implemented.

>
>>It is only Jims suggestion that ptrcmp might always return 0 that
>>makes it possible to make its existence mandatory.
>
>A ptrcmp that always returned 0 would be useless, IMHO.
>

 Not at all. My sort will still order the pointers
into the total order, which in this case is anything.

 This is entirely different from the current situation
where a sort based on the existing implementation defined <
on pointers might not terminate.

--
;----------------------------------------------------------------------
        JOHN (MAX) SKALLER,         maxtal@extro.ucc.su.oz.au
 Maxtal Pty Ltd, 6 MacKay St ASHFIELD, NSW 2131, AUSTRALIA
;--------------- SCIENTIFIC AND ENGINEERING SOFTWARE ------------------

In article <1992Dec16.150144.6004@ucc.su.OZ.AU>, maxtal@extro.ucc.su.OZ.AU (John MAX Skaller) writes:
|>  In that case it is implementable on all systems
|>  where (opinion follows, please correct errors)
|>
|>  a) void* is big enough to hold all pointer types

This assumption, as written, is violated by compact and medium model on Intel
chips.  I suggest rewording this to:
 a) void* is big enough to hold all object pointer types
        ^^^^^^
[function pointers are *not* guarenteed to be convertable to void *, and,
in C++, neither are member 'pointers'].

|>  b) conversions always pad systematically
|>  c) bitwise comparison is done
|>  d) the bits of a pointer cannot be magically changed by the system
|>  e) a pointer is implemented as an object in contiguous storage
|> ...
|>
|>  Certainly, (e) might cause problems on the 80x86 where part of the
|> pointer is implicit and not physically stored. Does it *actually*
|> cause this problem?

In 'small data' models, YES!  There is simply no reason for void* to contain
the segment when all data is in the same segment.

Of course, in paractice, the limitations on the 'small data' models make this lack
of little *practical* concern for ptrcmp() - that is since all data are in the
same segment a segmentless comparison will always work (as long as you use the
*stronger* form of (a) I mention above).

--
sarima@teradata.com   (formerly tdatirv!sarima)
  or
Stanley.Friesen@ElSegundoCA.ncr.com

Jim Adcock (jimad@microsoft.com) wrote:
: In article <5366@miramon.lulea.trab.se> jbn@lulea.trab.se (Johan Bengtsson) writes:
: |Other OODBMSs that use straight pointers to refer to persistent
: |objects (e.g. ObjectStore,Texas) must provide a rather special
: |ptrcmp(void*,void*), or disallow use of ptrcmp() for persistent
: |objects (may be difficult to check).

: What if ptrcmp [addrcmp] were allowed to return 0 for those objects
: and/or systems that don't define an ordering for those objects?

The problem is not to be able to order persistent objects, once
you know that you have a void* refering to one.  Also, I wouldn't
expect the comparison on persistent object IDs to be too slow to use,
since we are talking about objects that anyway needs to be transferred
to and from slow disks.

The real problem is distinguishing between void* to memory objects and
void* to persistent objects.

: The implication would be that one routine could be written that uses
: a fast ordering scheme on those OS's and/or objects that support the
: ordering, but a slower secondary scheme would have to be included for
: those cases of objects or OS's where the order is undefined.
: The secondary scheme would only have to be implemented by those programmers
: *really* interested in writing *really* portable code, since a defined
: ordering out of ptrcmp would be a common extension.

I think systems that can't completely support ptrcmp() should simply
refrain from defining it.  That will make the problem evident at an early
stage (link time).

--
--------------------------------------------------------------------------
| Johan Bengtsson, Telia Research AB, Aurorum 6, S-951 75 Lulea, Sweden  |
| Johan.Bengtsson@lulea.trab.se; Voice:(+46)92075471; Fax:(+46)92075490  |
--------------------------------------------------------------------------

dag@seldon.control.lth.se (Dag Bruck) writes:
| Suggested semantics: for any pointers p and q:
|
|       p == q   <=>   ptrcmp(p,q) == 0
|
|       p != q   <=>   ptrcmp(p,q) != 0
|
|       ptrcmp(p,q) < 0   <=>   ptrcmp(q,p) > 0


And transitivity:

   ptrcmp(p,q) <= 0 && ptrcmp(q,r) <= 0   =>   ptrcmp(p,r) <= 0
   ptrcmp(p,q) <= 0 && ptrcmp(q,r) <  0   =>   ptrcmp(p,r) <  0
   ptrcmp(p,q) <  0 && ptrcmp(q,r) <= 0   =>   ptrcmp(p,r) <  0


jss@lucid.com (Jerry Schwarz) writes:
|And
|
|       if p < q is defined,  ptrcmp(p,q) < 0   <=>  p < q


This strikes me as nice to have, but not essential.
Many applications of ptrcmp wouldn't need this property at all
(eg. using ptrcmp to navigate through a binary tree, with no
additional requirement on the ordering other than that it be
an ordering).

On the other hand, this might be fairly cheap, given that
we're already insisting on

   p == q   =>   ptrcmp(p,q) == 0

--
Patrick Smith
uunet.ca!frumious!pat
pat%frumious.uucp@uunet.ca

In article <1992Dec14.225659.24225@microsoft.com> jimad@microsoft.com (Jim Adcock) writes:
>In article <1992Dec12.154918.2220@ucc.su.OZ.AU> maxtal@extro.ucc.su.OZ.AU (John MAX Skaller) writes:
>|which cannot break existing implementations but provides a  total
>|order by way of a library function? If so, can we put this to
>|the library WG?
>
>I think some flavor of "ptrcmp" makes sense on those implementations that
>support casting pointers to integrals and back, and probably doesn't make
>sense on those implementations that don't support the pointer/integral casts.

 Why not?
>
>In either case, I would ask what kind of sense it makes to write a "standard"
>that *requires* a certain behavior of *some* implementation but doesn't
>*require* that behavior of *all* implementations?  How do you justify such
>a dichotomy?

 ptrcmp is standard, required function, it must yield a total
 order.

 No dichotomy. ptrcmp is mandatory.

 I'm not yet convinced it need bear ANY relation to
 ==, !=, < etc on pointers.

 In that case it is implementable on all systems
 where (opinion follows, please correct errors)

 a) void* is big enough to hold all pointer types
 b) conversions always pad systematically
 c) bitwise comparison is done
 d) the bits of a pointer cannot be magically changed by the system
 e) a pointer is implemented as an object in contiguous storage

c) ensures a total order by injective mapping of pointers to integers,
NOT necessarily long though.

b) ensures determinism

a) ensures ptrcmp(void*,void*) can be called without loss of bits

Such a function allows pointers to be, say, sorted, without any
expected correlation with the order of the objects they point to.

I am not sure of the wisdom or workability of having any additional
rules relating ==, < etc to ptrcmp.

>
>cast, and for the proposed "ptrcmp" macro.  Then, on Lisp machines, or
>C++ OODBMS's or whatever systens would find the total ordering
>practically unsupportable in their environment, they simply would not implement
>the "common extension."  This would be a quality of implementation issue then,
>not an issue of conformance.

 These 'lisp' machines must break rule (d) above then?

>
>In any case, "ptrcmp" would be a misnomer, because what is being compared
>is *not* pointers, but rather the underlying *assumed* implementation of
>pointers using machine addresses.  The correct name might be something like
>"addrcmp" then, so as to not further confuse programmers on the difference
>between language and implementation.

 I suggest the *actual* implementation be what is compared.

 Certainly, (e) might cause problems on the 80x86 where part of the
pointer is implicit and not physically stored. Does it *actually*
cause this problem?


--
;----------------------------------------------------------------------
        JOHN (MAX) SKALLER,         maxtal@extro.ucc.su.oz.au
 Maxtal Pty Ltd, 6 MacKay St ASHFIELD, NSW 2131, AUSTRALIA
;--------------- SCIENTIFIC AND ENGINEERING SOFTWARE ------------------

In article <1992Dec14.230730.24452@microsoft.com> jimad@microsoft.com (Jim Adcock) writes:
>In article <5366@miramon.lulea.trab.se> jbn@lulea.trab.se (Johan Bengtsson) writes:
>
>What if ptrcmp [addrcmp] were allowed to return 0 for those objects
>and/or systems that don't define an ordering for those objects?
>

 Given a set of pointers p1, p2, p3, and some function f,
we require that

 f(p1), f(p2), f(p3)

be a total order, and returning 0 always is clearly a trivial
total order *of f(p)* in that case.

 Dag wanted to have

 p1 == p2  <==> ptrcmp(p1,p2)==0    (DC)

and this imposes some constraint on 'f' which would certainly
mean that returning 0 always was not a total order.

Taking 'f' to be the underlying bits of a pointer makes
ptrcmp fast and useful, but DC will not be satisfied on
the 8086.

The purpose of ptrcmp, surely, is to allow say sorting or btree
algorithms to be applied to pointers AT ALL. It really
doesnt matter what the order produced actually is.
What's important is that the damn algorithms
work correctly, for example terminate in the case of a sort,
or retrieve the pointer from a btree.

A completely randomly chosen total order will work for
any algorithm not requiring equality tests.
Sorts not requiring uniqueness will work.

Btrees require uniqueness so wont. They need condition DC.
Otherwise they mnay fail to put some things into the tree
(thinking there is duplication) and put others in twice
(finding duplication where not intended).

So... how about TWO functions :-)

 anytorder(void*,void*); // might give 0 always
 obeysDC(void*,void*); // must obey DC above

Now it was ALSO suggested that if < implement a partial
order, the total order be compatible with it.
If I remember my maths, this can always be done
(assuming < is a partial order ... have to go back
to my maths books and 8086 manuals here :-)

Anyhow, can we list all the possible reasonable functions,
what properties they have, what the implications are, then
pick a standard set for inclusion in the library?

Furthermore, we can also have an optional set, the condition
is that they must have the listed properties IF they are
implemented, otherwise they must NOT be implemented.
(Or, they are all implemented, but might cause exceptions
if not defined .. if you know what I mean :-)

That ensures that correct code will either work or
fail gracefully, rather than yielding unexpected results.

--
;----------------------------------------------------------------------
        JOHN (MAX) SKALLER,         maxtal@extro.ucc.su.oz.au
 Maxtal Pty Ltd, 6 MacKay St ASHFIELD, NSW 2131, AUSTRALIA
;--------------- SCIENTIFIC AND ENGINEERING SOFTWARE ------------------

In article <1992Dec07.225634.19943@microsoft.com> jimad@microsoft.com (Jim Adcock) writes:
>
>|As long as we have C++ objects, i.e. in memory, their addresses (or at least the
>|valid pointer values to access them) _must_ stay constant, because C++ has no
>|means to automatically track down and modify all pointers to an object.
>
>Wrongo.  Again you confuse language and implementation.  On the contrary,
>I've written an internal implementation of C++ that does have the means to
>automatically track down and modify all pointers to an object.  There
>are other systems that do this kind of thing too.  Such as early versions of
>Windows.

 Certainly, such an internal tracking mechanism (Jim, you really
actually wrote such a routine??) is legal with the
current definition of C++ provided object identity is preserved.

 Clearly retaining a total order over such a routine,
especially an incremental one, would be a heavy constraint
on the sort of algorithm you would be allowed to implement.

 Even restricting the intent of such a routine
to say, compaction: At the moment the only requirement would be that all the
pointers to a moved object be changed in one increment.
(So equality tests continue to work)

You might reorder all the objects in memory. Preserving a total order
in an incremental system might be suboptimal. So that requirement
would break your system OR force you to make it suboptimal.
(Where suboptimal might include abandoning it altogether .. and then
maybe the program wont run at all .. totally breaking the program)

 So there is a tradeoff---a class of code using Jims
sneaky tricks breaks, or an as yet non-existant class
of code depending on total order breaks.

 Perhaps unfortunately such a tradeoff can only be resolved
one way by the committee---namely that of requiring
compatibility with existing code. Because no one can be
sure Jim is the only one doing sneaky tricks. Or there arent
other types of legal sneaky tricks.

(** 'sneaky tricks' is not meant to be anything than the first words
that popped into my head.)


--
;----------------------------------------------------------------------
        JOHN (MAX) SKALLER,         maxtal@extro.ucc.su.oz.au
 Maxtal Pty Ltd, 6 MacKay St ASHFIELD, NSW 2131, AUSTRALIA
;--------------- SCIENTIFIC AND ENGINEERING SOFTWARE ------------------

In article <BzCG7K.2sG@frumious.uucp> pat@frumious.uucp (Patrick Smith) writes:
>
>jss@lucid.com (Jerry Schwarz) writes:
>|And
>|
>|       if p < q is defined,  ptrcmp(p,q) < 0   <=>  p < q
>
>
>This strikes me as nice to have, but not essential.
>
>On the other hand, this might be fairly cheap, given that
>we're already insisting on
>
>   p == q   =>   ptrcmp(p,q) == 0
>

It makes me nervous to disagree with you, but haven't we already
hammered to death the concept that p < q might be defined (but
not generate a total ordering) if some ps and qs are not in the
same segment?  Or do the PC compilers only permit p < q for ps
and qs in the same array?

Suppose we have a compiler that uses segment offset to determine
if p < q but memory address to determine if p == q.

If p1 < q1 are near the end of segment 1,
   p2 < q2 are near the beginning of segment 2
and q1 == p2 (because they refer to the same memory location),

then

   p2 < q2 < p1 < q1   (because the segment is being ignored)
but
   p2 == q1   and   p2 != q2.

Stuart
--
: Stuart MacMartin                                    email: sjm@bnr.ca      :
: Bell-Northern Research                              phone: (613) 763-5625  :
: PO Box 3511, Stn C, Ottawa, K1Y-4H7, CANADA    Standard disclaimers apply. :

In article <1992Dec15.162202.11231@ucc.su.OZ.AU> maxtal@extro.ucc.su.OZ.AU (John MAX Skaller) writes:
|But Jim, it is not implementation defined, it is required that
|pointers to the same object compare equal. It is therefore
|legal to have a function:
|
| f(X* a, X*b) {
| if(a==b) { /* special case, copy b object */ ... }
| else *a+=*b;
| }
|
|where the += operation is destructive and wont work if a and b point
|to the same object. The above code is guarranteed in C++, but
|will fail on a suitably organised system. It is therefore not
|allowed to do this sort of memory mapping in C++ behind the scenes,
|which is what I'm concerned with...we actually want to.

If a strictly conforming implementation is presented with a strictly
conforming program, then the above works subject to some additional
constraints, such as a and b refering to disjoint objects.

However, if a strictly conforming implementation is presented with a
non-strictly conforming program, such as a program that calls OS
virtual memory mapping adjustment routines, or programs that send
pointers off the ends of arrays, or programs who don't properly point
at objects that correspond to the types of objects they pretend to point
at .... in all such cases all bets are off.

sjm@bcrki65.bnr.ca (Stuart MacMartin) writes:
|In article <BzCG7K.2sG@frumious.uucp> pat@frumious.uucp (Patrick Smith) writes:
|>
|>jss@lucid.com (Jerry Schwarz) writes:
|>|And
|>|
|>|       if p < q is defined,  ptrcmp(p,q) < 0   <=>  p < q
|>
|>
|>This strikes me as nice to have, but not essential.
|
|It makes me nervous to disagree with you, but haven't we already
|hammered to death the concept that p < q might be defined (but
|not generate a total ordering) if some ps and qs are not in the
|same segment?  Or do the PC compilers only permit p < q for ps
|and qs in the same array?

Please don't be nervous, Stuart!  I make _lots_ of mistakes.
(No smiley here, because it's quite true.)

This seems to depend on what one means by "p < q is defined".
I can't say what Jerry meant, but (without thinking about it
too much), I took him to mean something something like
"if the standard defines what p < q means".  Which I _thought_
meant p and q had to point to objects in the same array or
subobjects of the same object.  And p < q does have to behave
as expected in those cases (with some of the "subobjects
of the same object" cases being legal exceptions).

The emphasis on _thought_ is because then I looked at the
draft standard.  More on that in another posting...

--
Patrick Smith
uunet.ca!frumious!pat
pat%frumious.uucp@uunet.ca

maxtal@extro.ucc.su.OZ.AU (John MAX Skaller) writes:
| I'm not yet convinced it need bear ANY relation to
| ==, !=, < etc on pointers.

["it" == ptrcmp]


Surely one would want to insist on

   p == q   =>   ptrcmp(p,q) == 0

If this weren't true, one wouldn't be able to use ptrcmp as a basis
for organizing an ordered binary tree for searching.  Are there any
likely-to-be-common uses of ptrcmp which don't need this assumption?

Unfortunately, meeting this condition might be expensive on
segmented architectures (according to the many other postings
on this subject).


The converse,

   ptrcmp(p,q) == 0   =>   p == q

seems not quite as essential, but still very useful.  Can anyone
describe an otherwise reasonable implementation of ptrcmp which
would _not_ meet this condition?  If not, what's the harm in
asking for it?

--
Patrick Smith
uunet.ca!frumious!pat
pat%frumious.uucp@uunet.ca

jimad@microsoft.com (Jim Adcock) writes:

>I think some flavor of "ptrcmp" makes sense on those implementations that
>support casting pointers to integrals and back, and probably doesn't make
>sense on those implementations that don't support the pointer/integral casts.
>
>In either case, I would ask what kind of sense it makes to write a "standard"
>that *requires* a certain behavior of *some* implementation but doesn't
>*require* that behavior of *all* implementations?  How do you justify such
>a dichotomy?

ptrcmp() is intended to be universal, ie. required of *all* implementations.

>Such would be the proper designation, IMHO, for both the bidi pointer/integral
>cast, and for the proposed "ptrcmp" macro.  Then, on Lisp machines, or
>C++ OODBMS's or whatever systens would find the total ordering
>practically unsupportable in their environment [...]

Why would ptrcmp() be practically unsupportable in these environments?
OODBMS's maintain an object identity for each object, so it should be
possible to base a total ordering on this object identity. I don't see
the problems. What makes it difficult for Lisp machines? Are efficient
BTrees and such-like genuinely impossible on such machines?

>In any case, "ptrcmp" would be a misnomer, because what is being compared
>is *not* pointers, but rather the underlying *assumed* implementation of
>pointers using machine addresses.  The correct name might be something like
>"addrcmp" then, so as to not further confuse programmers on the difference
>between language and implementation.

The function should be named after its interface, not its implementation.
The function takes two (void *) _pointers_, and returns an integer which
is meant to be a comparison of those pointers according to some total
ordering.
Whether it is implemented by comparing addresses or by sending mail to
the Usenet Oracle and waiting for a reply is not relevant.

--
Fergus Henderson             fjh@munta.cs.mu.OZ.AU
This .signature virus is a self-referential statement that is true - but
you will only be able to consistently believe it if you copy it to your own
.signature file!

In article <1992Dec15.162202.11231@ucc.su.OZ.AU> John (Max) Skaller writes:
> In article <1992Dec11.230534.10499@microsoft.com> Jim Adcock writes:
> >No more nor less than any other virtual memory OS that allows
> >multiply mapped pages.  Since there is no functionality in the
> >language requiring such multiply mapped pages, you only get in
> >this situation by invoking some system dependency, in which case
> >you are making use of implementation dependencies.

> But Jim, it is not implementation defined, it is required that
> pointers to the same object compare equal.

> It is therefore not
> allowed to do this sort of memory mapping in C++ behind the scenes,
> which is what I'm concerned with...we actually want to.

It makes me uneasy, but I think Jim Adcock is correct: an implementation
can define an extension, such as memory mapping, which overrides the usual
execution time rules of C/C++, including the rule that pointers to the same
object compare equal.  The rule that 1+1==2 would likewise be subject to
"extension".

Nevertheless, the C standard implies that the onus is on the invoker of memory
mapping to be aware of libraries and other code which may rely on the usual
execution time rules of C/C++, such as the rule that pointers to the same
object compare equal.  If we don't want libraries to make that assumption,
then John (Max) Skaller is also correct to say

> So the question is really whether the requirement that pointers to
> the same object compare equal should be left implementation defined.
--
Prescott K. Turner, Jr.
Liant Software Corp. (developers of LPI languages)
959 Concord St., Framingham, MA 01701 USA    (508) 872-8700
UUCP: uunet!lpi!pkt                          Internet: pkt@lpi.liant.com

In article <1992Dec8.143504.5590@jyu.fi> sakkinen@jyu.fi (Markku Sakkinen) writes:
>In article <1992Dec07.225634.19943@microsoft.com> jimad@microsoft.com (Jim Adcock) writes:
>>
>>Agreed, and in general those changes have been practical and well motivated.
>>What you suggest is neither.  On the contrary, you ask to legalize your
>>favorite hacks.
>
>No, it's you who are crying for hacks:  programs that happen to work
>in a certain way because of the peculiarities of a certain compiler.
>Now you think it has been OK to break many "strictly conforming" programs!

 BOTH hacks! OK?

 Jims is a 'hack' because it is machine and compiler and even
memory model dependant. Fine. C was designed to handle that. It was
designed for controlling hardware every bit as much, and maybe moreso,
than general programming.

 Markku's is a hack because linear address machines,
for which pointer comparison makes the most sense, are just
one possible architecture. And one which went out of date
many years ago I thought. Aren't von Neumann machines considered
archaic? Isnt the segmented architecture (I mean real
segments like the 386 not 8086 bank switching) just an extension
of the Harvard architecture? Aren't BOTH of these
going to become obsolete with the advent of
distributed persistent object stores?

>
>You have been pleaded a dozen times to give an example.
>Why don't you present one, so we can get this discussion on more
>rational grounds!

 I presented one.. twice. If you want more,
look at almost every C program ever written
for the PC. Many use mixed pointer types.

 Here's an easy example from Microsoft's older
libraries:

 memcpy(void*d, void*s, int n);

Here d and s are only 16 bits. So they had better both
reside in the Data Segment, or all hell breaks loose.
This version of memcpy assumes this is the case.
If you want 20 bit addresses, use

 far_memcpy(void _far * d, void _far * s, int n);

(Or something similar, Borland's libraries never had this problem).

While this isn't an example where total ordering matters,
perhaps you might begin to see how bad things are for
8086 programmers. And perhaps you can understand that
there are sure to be dependencies on pointers being
ordered the 8086 way in 8086 code. On the 8086,
they can be used just like 16 bit integers, and often are.

 A function

 ptrcmp(void*,void*);

wouldnt work if the ptrs were 16 bits anyhow. The < version
is bound to use that implementation for consistency.
The true library function must be

 ptrcmp(void _far *, void _far *);

>>
>>Wrongo.  Again you confuse language and implementation.  On the contrary,
>>I've written an internal implementation of C++ that does have the means to
>>automatically track down and modify all pointers to an object.  There
>>are other systems that do this kind of thing too.  Such as early versions of
>>Windows.
>
>Maybe, but such a system must be terribly expensive in memory and
>processor time;  and your main motivation seemed to be to save
>a couple of processor cycles.

 Windows was expensive on processor time in order
to conserve memory. It had to run on the 8086, in 640K, and did.
Pointers in Windows (real version) were not allowed, except for transient
periods. It had automatic compaction, including chasing the stack
for stack frames. It dumped read-only segments automatically,
and reloaded them just as automatically when required.

 And the guys that wrote it are now the richest men in
the US because of it. And more people us it than any other
GUI. Dont laugh, Microsoft has NT running on MIPS, Unix beware!

>
>is not portable.  Some people indeed want to write portable software,
>and not only for a 1970s state-of-the-art Deci (one tenth) Operating System.

 Hey, others want to write for Unix, which is not
much of an operating system compared to say OS/2 or NeXT either :-).

>
>I already explained that the issue was not to program in terms of
>memory addresses!
>
 How then does one write an operating system, device
drivers, or any other code that MUST assume pointers are
memory addresses?

 The problem is that pointers should be useful BOTH
as memory addresses, and also as 'object accessors'.
Really, operations like p++ should not be legal on
pointers, but we're stuck with them.

 The real problem is that pointers have a meaning
defined by prior C definitions, and so much code
depends on those definition that its not possible
to change them.

 Now if we could write proper object accessors
efficiently and conveniently, we wouldn't need to use
pointers .. except for machine level access.
So perhaps we need operator.() and/or something else
to be able to do this, because at the moment we
cant emulate pointer behaviour in classes.

 Would it be more profitable to consider
why this is, and what we can do about it?

--
;----------------------------------------------------------------------
        JOHN (MAX) SKALLER,         maxtal@extro.ucc.su.oz.au
 Maxtal Pty Ltd, 6 MacKay St ASHFIELD, NSW 2131, AUSTRALIA
;--------------- SCIENTIFIC AND ENGINEERING SOFTWARE ------------------

In article <1992Dec18.193554.18588@ucc.su.OZ.AU> maxtal@extro.ucc.su.OZ.AU (John MAX Skaller) writes:
>In article <1992Dec16.201044.2968@microsoft.com> jimad@microsoft.com (Jim Adcock) writes:

> I know what you are saying but dont see it.
>ARM p74:"two pointers to the same object compare equal".
>Any program for which this is not true cannot be conforming,
>neither strictly nor non-strictly, it is non-conforming, it is
>not in fact a C++ program.

I think this is a requirement on implementations, rather than
a requirement on programs.

> Or have I got this wrong?

You might have it backwards.

> For this reason I think the ARM requirement is unworkable,
>and must be modified. The rule should state that pointers
>derived from the same object directly in the program must
>compare equal. Pointers obtained from the OS need not follow
>this rule, in that case it is implementation defined.

Neither the C standard nor the C++ standard discusses any OS.
(As far as I recall.)

A call to the operating system should be viewed as
a call to an extension supplied by the language provider.
A program that uses an extension can be conforming but
not strictly conforming, as per the X3J16 definitions.

Thus, I think a better rule is:
 ``In a strictly conforming program, two pointers
 to the same object compare equal.''
Thus, this property need not be true in any program that
calls the operating system.

I think actually that ramifications of multiple inheritance
and multiple object-addresses should be explicitly addressed
in the rule, such as by saying that a pointer to a base-class
subobject is not a pointer to the same object as a pointer
to the most-derived class object.

>        JOHN (MAX) SKALLER,         maxtal@extro.ucc.su.oz.au

Daniel Edelson
daniel@cse.ucsc.edu

In <comp.std.c++> maxtal@extro.ucc.su.OZ.AU (John MAX Skaller) writes:
>
>In fact, p==q iff objects equal is unimplementable on some machines.
>That is, even the existing ARM requirement is unworkable.

No, some machines are unworkable :-).

In article <KANZE.92Dec10171114@slsvdnt.us-es.sel.de> kanze@us-es.sel.de (James Kanze) writes:
>In article <1992Dec10.121935.19315@ucc.su.OZ.AU>
>maxtal@extro.ucc.su.OZ.AU (John MAX Skaller) writes:
>|> >different addresses, but are pointing to the same object, must they
>|> >compare equal?
>
>|>  The answer to this particular question is YES, they must
>|> compare equal according to the ARM. And I think this is a problem
>|> for OS design for the 386, for example, where the memory management
>|> kernel will just have to ignore the ARM.
>
>As it should.  The ARM (and the upcoming ANSI standard) can only
>address what happens in the context of C++, not what happens to the
>pointer once the OS gets its hands on it.

 No, this is not true IMHO. The ARM can and does explicitly
or implicitly say "implementation defined" where it means that.
When the ARM says "so and so will be the case" then it must
always be the case.

>
>In a similar vein, for example, the ANSI C standard states that the
>NULL pointer will not point to any object.  But all 8086 programmers
>know that if you compile with 32 bit pointers, it actually points to
>the interrupt vector table!  However, this is *not* an object defined
>in any C program, so this is perfectly legal.  (If it wasn't, you
>couldn't have C on machines without protected memory.)

 This is just your interpretation that "object"
means "object created by the program". It should not
be up to your interpretation IMHO.

>
>In the same way, I would understand the ARM to be saying that all
>pointers generated by a correct program to point to any object defined
>(including a dynamic definition by new) in C++ will compare equal.  If
>you give the pointer to the OS, and it gives it back to you, then any
>guarantees must be made by the OS, and not the C++ language.

 I agree. But that is not the case. The ARM says different.
It absolutely requires pointers to the same object to compare
equal, without qualification. The system MUST ensure this
to classify as conforming. Since we both agree this is undesirable,
as it would make conforming translators impossible to write,
we have to change the ARM (well, the standard) to say what we
actually mean.

>|>  If we dropped this requirement, however, there would
>|> be no easy way to identify objects.
>
>Once you leave the safe and easy world of your program, there is no
>easy way to identify objects.  C++ doesn't address such problems as
>persistance, transportability or shared memory.

 It doesnt have to if it leaves enough things
"implementation defined". If something is "ARM defined",
it isnt implementation defined, and the translator MUST
do what the ARM says to be ARM-conforming. Similarly,
if it is one of those things the translator CANT be
responsible for, a strictly conforming program must
follow those rules. (E.g. not pointing more than 1 past
the end of an array).

 The problem then is that it isnt possible
to write a C++ program to do 386 memory management
with the current rule for == for pointers.
Not even a non-stricty conforming one, because there is no
scope for implementation defined variation.

 IMHO there should be.

--
;----------------------------------------------------------------------
        JOHN (MAX) SKALLER,         maxtal@extro.ucc.su.oz.au
 Maxtal Pty Ltd, 6 MacKay St ASHFIELD, NSW 2131, AUSTRALIA
;--------------- SCIENTIFIC AND ENGINEERING SOFTWARE ------------------

In article <BzG1Jx.JH@frumious.uucp> uunet.ca!frumious!pat writes:
>|
>|> So the question is really whether the requirement that pointers to
>|> the same object compare equal should be left implementation defined.
>
>Here I would disagree.  I think the question is whether, if the C++
>standard adopts the same notions of conformity as the C standard,
>pointers to the same object should be required to compare equal
>in a conforming program.
>
>And the answer is _no_.

 Well, either way, this is not what the ARM says.
I would expect that pointers should compare equal after assignment
or initialisation (assuming they're the same type). And other
operations we could list.

 However, if raw pointers were supplied by an external source
such as the OS, I would prefer the answer be 'implementation defined'.
I dont know if this is workable, but the current status seems overly
restrictive.
--
;----------------------------------------------------------------------
        JOHN (MAX) SKALLER,         maxtal@extro.ucc.su.oz.au
 Maxtal Pty Ltd, 6 MacKay St ASHFIELD, NSW 2131, AUSTRALIA
;--------------- SCIENTIFIC AND ENGINEERING SOFTWARE ------------------

In article <1992Dec18.204337.3084@lth.se> dag@bellman.control.lth.se (Dag Bruck) writes:
>In <comp.std.c++> maxtal@extro.ucc.su.OZ.AU (John MAX Skaller) writes:
>>
>>In fact, p==q iff objects equal is unimplementable on some machines.
>>That is, even the existing ARM requirement is unworkable.
>
>No, some machines are unworkable :-).

I wont disagree with your sentiments.

However, lets consider that Unix file names are 'pointers' to files,
and that links are allowed.

Then the average program cant tell if two file names point to
the same file or not, since computing the inode number is the only
way to do that, and only super users can do this calculation.
(Imagine I'm right even if this isnt the case. Is it the case?)

Would this make such a system 'unworkable'?

The issue is whether pointers must provide any more functionality
than the ability to access an object, that is, whether object
identity can be established by pointer comparisons.
(A related issue is whether two pointers point INTO the same object,
or one points into an object the other points to)

I suggest that whole classes of software can be written that
do not rely on the ability to test if two pointers refer
to the same object or not, other types of software require
this information.

Perhaps we can conceive two types of pointers, type 1
provides no comparisons at all, type 2 allows equality test.

Most of the code I've written uses type 1, and most uses
of type 2 could be rewritten as type 1.

In those cases where type 2 pointers are desirable, it
seems reasonable to restrict them to pointers
to objects created directly by me, and not the operating
system.

Thus I would like to see the ARM == rewritten so the
results of == on externally derived or otherwise mangled
pointers are implementation defined.

Thus, if you write non-strictly conforming programs for
a linear address machine, I have no complaint
when your hacks dont work on my segmented machine because
you are using 'implementation defined' features of C++.

--
;----------------------------------------------------------------------
        JOHN (MAX) SKALLER,         maxtal@extro.ucc.su.oz.au
 Maxtal Pty Ltd, 6 MacKay St ASHFIELD, NSW 2131, AUSTRALIA
;--------------- SCIENTIFIC AND ENGINEERING SOFTWARE ------------------

In article <9235215.11144@mulga.cs.mu.OZ.AU> fjh@munta.cs.mu.OZ.AU (Fergus James HENDERSON) writes:
|Why would ptrcmp() be practically unsupportable in these environments?
|OODBMS's maintain an object identity for each object, so it should be
|possible to base a total ordering on this object identity. I don't see
|the problems. What makes it difficult for Lisp machines? Are efficient
|BTrees and such-like genuinely impossible on such machines?

Of course BTrees and such-like are NOT impossible -- you just don't
base them on pointers!  You base them on some other well defined total
ordering of the objects, such as based on object surrogates.

Consider the case of OODBMSs where you use virtual memory schemes
to trap on pointers to objects not in memory and then bring such
objects into memory.  Such objects have unique [large] obids globally
identifying them, and smaller pointers [addresses] to them in their
current incarnations in memory.  Granted that an inverse mapping can
give you the obid from the pointer, its just that such would typically
be very slow compared to the address comparisons you expect.  Slower
than using surrogates for example.  So why not use surrogates?

|The function should be named after its interface, not its implementation.
|The function takes two (void *) _pointers_, and returns an integer which
|is meant to be a comparison of those pointers according to some total
|ordering.
|Whether it is implemented by comparing addresses or by sending mail to
|the Usenet Oracle and waiting for a reply is not relevant.

I strongly disagree.  Because systems that DO implement ptrcmp by
sending mail to the Oracle are not going to be acceptable implementations
*in practice* of what you require.  You insist for pedagogical reasons
that *all* implementations support your hacks so that you can say your
code is portable to *all* implementations even when in fact your code does
not run acceptably on *all* machines.  Such code is NOT in fact portable.
The portability of such code is pure fiction.  You ask that system
implementors provide you with the implausible so that you can maintain
your fiction.  I disagree.  Rather we should look at those capabilities
that a *very* wide variaty of systems and implementations *can* reasonably
*in reality* support, standardize on the *reality* not the fiction,
and leave the rest implementation defined.

In article <BzDJHu.t2@frumious.uucp> uunet.ca!frumious!pat writes:
>maxtal@extro.ucc.su.OZ.AU (John MAX Skaller) writes:
>| I'm not yet convinced it need bear ANY relation to
>| ==, !=, < etc on pointers.
>
>["it" == ptrcmp]
>
>
>Surely one would want to insist on
>
>   p == q   =>   ptrcmp(p,q) == 0
>
>If this weren't true, one wouldn't be able to use ptrcmp as a basis
>for organizing an ordered binary tree for searching.  Are there any
>likely-to-be-common uses of ptrcmp which don't need this assumption?

 Of course: sorts will work perfectly well, as will any
algorithm that doesnt require uniqueness.

 That means this 'unconstrained' version of ptrcmp,
which might well always return 0 as Jim Adcock suggested,
can always be implemented on any machine. Returning 0 always
is a perfectly well defined total order, even if it
makes all pointers look the same.
>
>Unfortunately, meeting this condition might be expensive on
>segmented architectures (according to the many other postings
>on this subject).
>

 Thats not the issue. It might be UNIMPLEMENTABLE on
some architectures. In fact, == is UNIMPLEMENTABLE in general
on the 386 in protected mode, given the sloppy definition
of 'same object' in the ARM. Its quite possible on the 386
to have two logical addresses which convert to the
same linear address, but NOT BE ABLE TO TELL THAT THIS IS THE CASE.
Because to tell implies access to the LDT/GDT and the typical
process is not able to read those tables. A special
operating system function would be required to do this,
and that would make C++ unimplementable on systems not
having this function.

 Now assuming we clean up the ARM definition, we have to
look at

 a == b <==> ptrcmp(a,b)==0

first, before worrying about preserving partial orders that <
may or may not be. I think the above can be done
when a==b is made sensible, but I'm not sure.

 The condition

 a<b <==> ptrcmp(a,b)<0

cannot posibly be acceptable, since no language
in the ARM requires < to be a partial order, or anything else.
(Except if a,b point into the same array).

>
>The converse,
>
>   ptrcmp(p,q) == 0   =>   p == q
>
>seems not quite as essential, but still very useful.  Can anyone
>describe an otherwise reasonable implementation of ptrcmp which
>would _not_ meet this condition?  If not, what's the harm in
>asking for it?
>

 If ptrcmp just compared bits, this might be possible.
But then Jims stipulation that ptrcmp might always return
0 could not hold, and without this possibility a total
order might not be obtainable.

 (Recall this was suggested because some underlying
compaction mechanism might move stuff in memory around,
and adjust the pointers. The we might have

 a<b at time t0
 a>b at time t1

if we just did bit comparisons)

--
;----------------------------------------------------------------------
        JOHN (MAX) SKALLER,         maxtal@extro.ucc.su.oz.au
 Maxtal Pty Ltd, 6 MacKay St ASHFIELD, NSW 2131, AUSTRALIA
;--------------- SCIENTIFIC AND ENGINEERING SOFTWARE ------------------

Stuart MacMartin (sjm@bcrki65.bnr.ca) wrote:
: In article <1992Dec10.051649.10282@jyu.fi> sakkinen@jyu.fi (Markku Sakkinen) writes:
: >
: >Second, the _identity_ of a persistent object in the database does not
: >change when the object is brought (or copied) to main memory.
: >The ordering is not supposed to be connected with the other
: >semantics of the objects, nor with their location in physical or
: >virtual memory (except as already dictated by the existing language
: >rules for array elements and class members, in C++).

: Thus the database
: will have to provide a routine, say ptrcmp(Handle,Handle) to compare the
: total ordering of two objects.  It could also provide ptrcmp(Handle,void *)
: and ptrcmp(void *,Handle), arbitrarily deciding that all C++ objects are
: less than all database objects, say.

Note that some OODBMS has the equivalent of
typedef void* Handle;

which I imagine slightly complicates things.

--
--------------------------------------------------------------------------
| Johan Bengtsson, Telia Research AB, Aurorum 6, S-951 75 Lulea, Sweden  |
| Johan.Bengtsson@lulea.trab.se; Voice:(+46)92075471; Fax:(+46)92075490  |
--------------------------------------------------------------------------

In article <1992Dec10.051649.10282@jyu.fi> sakkinen@jyu.fi (Markku Sakkinen) writes:
>In article <5343@holden.lulea.trab.se> jbn@lulea.trab.se (Johan Bengtsson) writes:
>>Markku Sakkinen (sakkinen@jyu.fi) wrote:
>
>You must have misunderstood the idea somehow in two ways.
>First, no matter how an object identifier is represented, it can always
>be interpreted as an integer or bit string for the purpose of
>ordering:  "violating the total ordering property" is impossible.
>

 I think you missed something here. It may well be possible
to have < > <= >= and the operator @ satifying

 a @ b means !(a<b) && !(a>b)

form a total order using bitwise comparisons (provided the pointers
are void *). However the operator @ need not be the operator ==,
it is quite possible for

 a < b && a == b

to be true, where < is bitwise and == the proper pointer comparison.
This will be immediately true on the 8086 unless all far
pointers are normalised. (== must normalise them, < need not).

--
;----------------------------------------------------------------------
        JOHN (MAX) SKALLER,         maxtal@extro.ucc.su.oz.au
 Maxtal Pty Ltd, 6 MacKay St ASHFIELD, NSW 2131, AUSTRALIA
;--------------- SCIENTIFIC AND ENGINEERING SOFTWARE ------------------

In article <5357@holden.lulea.trab.se> jbn@lulea.trab.se (Johan Bengtsson) writes:
>Put differently: the database ID total order and the corresponding
>transient pointer orders must be order-isomorphic (look it up, I did :-),
>to ensure that the total pointer order for the addresses of
>persistent objects mapped into transient memory is consistent between
>different runs of the same program.

Aren't we talking about a total ordering that is consistent for the
duration of the process?  The OODBMS objects can have an ordering that
is persistent, but obviously the transient objects won't have a persistent
ordering.  Do we care if the ordering of persistent objects is the same
between different runs of the program?  Am I missing something?

And as I said in an earlier post (which you might not have read when you
posted this), several OODBMSs allow multiple handles on the same object.
Furthermore, Objectivity (for example) has a handle in which the actual
address of the object in core is swizzled.  This swizzling is safe
because it is private to the handle, and the user's program never sees
the address of the actual object (if he is practicing safe programming).
In fact, the object might not be in core even if the handle is valid, and
the address in core may change unbeknownst to the user.  So the user
does not have the address of the object, so he won't be comparing
C++ pointers to these objects.  And in fact, comparing the address of
the actual object will not give you the consistent ordering for the
duration of the process unless you explicitly restrict the capabilities of
the OODBMS.  Since this is all OODBMS specific, it is much better to
let the OODBMS manage the ordering and forget about trying to get an
ordering out of whatever handles it gives you.

All that long-winded explanation aside, I would like to be able to
define a total ordering on my objects - my persistent objects (stored in
various OODBMSs) and my transient C++ objects - that is consistent for
the lifetime of the objects and the duration of the process.  I don't
have any specific need for it at the moment, but I expect I would use this
if I had it available.

Stuart

--
: Stuart MacMartin                                    email: sjm@bnr.ca      :
: Bell-Northern Research                              phone: (613) 763-5625  :
: PO Box 3511, Stn C, Ottawa, K1Y-4H7, CANADA    Standard disclaimers apply. :

In article <1992Dec10.121935.19315@ucc.su.OZ.AU> maxtal@extro.ucc.su.OZ.AU (John MAX Skaller) writes:
| The answer to this particular question is YES, they must
|compare equal according to the ARM. And I think this is a problem
|for OS design for the 386, for example, where the memory management
|kernel will just have to ignore the ARM.

No more nor less than any other virtual memory OS that allows
multiply mapped pages.  Since there is no functionality in the
language requiring such multiply mapped pages, you only get in
this situation by invoking some system dependency, in which case
you are making use of implementation dependencies.  If you will,
a common C/C++ implementation defined extension to the language
is to allow the use of OS calls in order to map various regions
of memory to the same underlying page, allowing the same object
to be accessed via differing addresses.  Implementation defined,
no more nor less.

In article <9234601.10277@mulga.cs.mu.OZ.AU> fjh@munta.cs.mu.OZ.AU (Fergus James HENDERSON) writes:
|Actually, nested functions can be handled quite transparently.
|Gnu C handles pointers to nested functions by creating a "trampoline"
|function on the stack, and using the address of the trampoline
|function. When the trampoline function is called, all it does is push
|the pointer to the stack frame, and then jump to original nested
|function. This way, the nested function does receive a hidden stack
|frame parameter, but you can use pass the address of the nested
|function to any function such as qsort() that just expects a normal
|function pointer, since the address which will be automatically
|converted to the address of a newly-created trampoline.

So that taking the address of a nested function in different scopes
causes differing trampolines to be created, and differing pointers returned?

In article <KANZE.92Dec10174617@slsvdnt.us-es.sel.de> kanze@us-es.sel.de (James Kanze) writes:
|We already *have* this function.  Try the following:
|
| void* ptr1 ;
| void* ptr2 ;
| int cmp = memcmp( &ptr1 , &ptr2 , sizeof( void* ) ) ;
|
|This works on all implementations I can think of.  Is it guaranteed?
|(Ie: can pointers also hold undefined padding information which may
|vary in a random fashion.  Note that "memcmp" is *not* guaranteed to
|work on struct's.)

Not guaranteed, nor does there have to be random padding for it to not
be guaranteed.  All the bits could be used, but there could be multiple
bit combinations mapping to the same underlying memory address.  Early
PCs and OSs being an example.

In article <KANZE.92Dec10174617@slsvdnt.us-es.sel.de> kanze@us-es.sel.de (James Kanze) writes:
| int cmp = memcmp( &ptr1 , &ptr2 , sizeof( void* ) ) ;
|
|This works on all implementations I can think of.  Is it guaranteed?

Also, Cray uses very different pointer implementations for char* verses
other types of pointers, since the natural address granularity on the Cray
is too large to make a good char*.  Thus sizeof(char*) != sizeof(int*)
for example. [I don't know what sizeof(void*) would compare to -- char*
or int*]

In article <1992Dec11.231131.10956@microsoft.com> jimad@microsoft.com (Jim Adcock) writes:

> So that taking the address of a nested function in different scopes
> causes differing trampolines to be created, and differing pointers returned?

It shouldn't need to do that.  At most one trampoline is ever necessary
for a given nested function during its lifetime, namely the one that
binds the lexically surrounding context that was current when the
block containing the definition of that function was entered.

Moreover, that trampoline address is unique until the corresponding
function has gone out of scope, at which point the address is moot.
--
    --Andrew Koenig
      ark@europa.att.com

In article <1992Dec9.075125.22405@lth.se> dag@bellman.control.lth.se (Dag Bruck) writes:
> p != q   <=>   p < q   |   p > q
>
>for all pointers.  I'm not asking for a particular ordering, just an
>implementation defined behaviour that meets the equivalence above.
>
 Since existing 8086 implementations do not satisfy the above
condition, yet are conforming programs, would you accept Fergus
Henderson's suggestion:

 p != q <=>  ptrcmp(p,q)<0 || ptrcmp(p,q)>0

which cannot break existing implementations but provides a  total
order by way of a library function? If so, can we put this to
the library WG?


--
;----------------------------------------------------------------------
        JOHN (MAX) SKALLER,         maxtal@extro.ucc.su.oz.au
 Maxtal Pty Ltd, 6 MacKay St ASHFIELD, NSW 2131, AUSTRALIA
;--------------- SCIENTIFIC AND ENGINEERING SOFTWARE ------------------

In article <1992Dec9.133956.29659@lth.se> dag@seldon.control.lth.se (Dag Bruck) writes:
>In <comp.std.c++> fjh@munta.cs.mu.OZ.AU (Fergus James HENDERSON) writes:
>>
>>What I propose is that we define a *standard library function* which computes
>>a total ordering on pointers.
>>
>>int compare_pointers(const void *, const void *);
>>    /* Returns negative, zero, or positive in the same manner as strcmp().
>>       Perhaps in the interests of tradition and unreadability it should
>>       be called ptrcmp() instead of compare_pointers() :-) */
>
>Suggested semantics: for any pointers p and q:
>
> p == q   <=>   ptrcmp(p,q) == 0

 Are you SURE you need this? Why should == and ptrcmp
be in any way related? In particular, on the 8086 if
ptrcmp was a bitwise compare it would yield a total order,
but we would have

 p == q && ptrcmp(p,q) !=0


--
;----------------------------------------------------------------------
        JOHN (MAX) SKALLER,         maxtal@extro.ucc.su.oz.au
 Maxtal Pty Ltd, 6 MacKay St ASHFIELD, NSW 2131, AUSTRALIA
;--------------- SCIENTIFIC AND ENGINEERING SOFTWARE ------------------

In article <24392@alice.att.com> ark@alice.UUCP () writes:
>In article <1992Dec11.231131.10956@microsoft.com> jimad@microsoft.com (Jim Adcock) writes:
>
>> So that taking the address of a nested function in different scopes
>> causes differing trampolines to be created, and differing pointers returned?
>
>It shouldn't need to do that.  At most one trampoline is ever necessary
>for a given nested function during its lifetime, namely the one that
>binds the lexically surrounding context that was current when the
>block containing the definition of that function was entered.

 Are you saying that if I have a recursive function with a nested
function in it, and store the address of the nested function in scope
at the time of entering the n'th recursion into an array in slot n,
then executing the j'th slot will access the n'th activation record
and not the j'th one? (I.e. all the functions in the array
access the most recent activation record?)

>
>Moreover, that trampoline address is unique until the corresponding
>function has gone out of scope, at which point the address is moot.

 Irrespective of how it is implemented, and even if
taking the address of a nested function is allowed, I would like
to see C++ allow nested functions.

 There are several levels to which this could be done:

 1) Same as non-nested function: no access to environment,
 BUT the name is function local, also no address taking.

 2) Allow access to environment, but not taking address.

 3) Full hog: allow address taking.

One could also restricted nesting to one level.

Andrew,
Would any of these be likely to be accepted by the committee?
Do you personally favour nested functions?
If not, why not?
Anyone else? Anyone with GNU actually using them?
Anyone hate them?



--
;----------------------------------------------------------------------
        JOHN (MAX) SKALLER,         maxtal@extro.ucc.su.oz.au
 Maxtal Pty Ltd, 6 MacKay St ASHFIELD, NSW 2131, AUSTRALIA
;--------------- SCIENTIFIC AND ENGINEERING SOFTWARE ------------------

In article <1992Dec12.162211.5076@ucc.su.OZ.AU> maxtal@extro.ucc.su.OZ.AU (John MAX Skaller) writes:

> >It shouldn't need to do that.  At most one trampoline is ever necessary
> >for a given nested function during its lifetime, namely the one that
> >binds the lexically surrounding context that was current when the
> >block containing the definition of that function was entered.

>  Are you saying that if I have a recursive function with a nested
> function in it, and store the address of the nested function in scope
> at the time of entering the n'th recursion into an array in slot n,
> then executing the j'th slot will access the n'th activation record
> and not the j'th one? (I.e. all the functions in the array
> access the most recent activation record?)

No, that's just the opposite of that I said.

I said `the context that WAS current.'

Perhaps an example will make it clearer:

 void (*p)(void);
 void f(int n)
 {
  void g() { printf("%d\n", n); }
  if (n == 3)
   p = &g;
  if (n == 5)
   (*p)();
  else f(n+1);
 }

I am claiming that calling f(0) should print 3, not 5, because the
address stored in p should correspond to the stack frame in which
n is 3.  Indeed, that is just what gcc does.  It is also what every
other language I know does that supports such functions at all.
--
    --Andrew Koenig
      ark@europa.att.com

In article <1992Dec12.162211.5076@ucc.su.OZ.AU> maxtal@extro.ucc.su.OZ.AU (John MAX Skaller) writes:

> Andrew,
> Would any of these be likely to be accepted by the committee?

It's hard for me to say -- I am in the Core working group, which
meets concurrently with the Extensions group.  Since the latter would
consider any such proposal, and since I don't really know the dynamics
of that group, I'm ill-placed to comment.

> Do you personally favour nested functions?

In general, yes.  For C++, I'm not sure.

> If not, why not?

The main argument against it is that C doesn't have them, which means
that having them in C++ would make C interoperability more difficult.
It would also be more difficult to interface C++ programs with
low-level assembly-language things like on-board controllers.  I don't
care about that personally, but I know that other people do.
--
    --Andrew Koenig
      ark@europa.att.com

In <comp.std.c++> maxtal@extro.ucc.su.OZ.AU (John MAX Skaller) writes:
>In article <...> dag@seldon.control.lth.se (Dag Bruck) writes:
>>
>>Suggested semantics: for any pointers p and q:
>>
>> p == q   <=>   ptrcmp(p,q) == 0
>
> Are you SURE you need this? Why should == and ptrcmp
>be in any way related?

Because it would be very counter-intuitive, hence error-prone, if that
equality did not hold.

I also support the additional rule suggested by Jerry Schwarz:

 if (p < q) is defined:

 p < q   <=>   ptrcmp(p,q) < 0

Stuart MacMartin (sjm@bcrki65.bnr.ca) wrote:
: In article jbn@lulea.trab.se (Johan Bengtsson) writes:
: >Put differently: the database ID total order and the corresponding
: >transient pointer orders must be order-isomorphic (look it up, I did :-),
: >to ensure that the total pointer order for the addresses of
: >persistent objects mapped into transient memory is consistent between
: >different runs of the same program.

: Aren't we talking about a total ordering that is consistent for the
: duration of the process?

Yes, primarily.

: The OODBMS objects can have an ordering that
: is persistent, but obviously the transient objects won't have a persistent
: ordering.  Do we care if the ordering of persistent objects is the same
: between different runs of the program?  Am I missing something?

A persistent structure that depends on total object ordering needs the
same ordering for all program runs.  As I think you pointed out in
another posting, the ordering need/should not be pointer based for OODBMSs
that use handle objects to refer to persistent objects.

Other OODBMSs that use straight pointers to refer to persistent
objects (e.g. ObjectStore,Texas) must provide a rather special
ptrcmp(void*,void*), or disallow use of ptrcmp() for persistent
objects (may be difficult to check).

--
--------------------------------------------------------------------------
| Johan Bengtsson, Telia Research AB, Aurorum 6, S-951 75 Lulea, Sweden  |
| Johan.Bengtsson@lulea.trab.se; Voice:(+46)92075471; Fax:(+46)92075490  |
--------------------------------------------------------------------------

Jim Adcock (jimad@microsoft.com) wrote:
: dag@control.lth.se (Dag Bruck) writes:
: |In <comp.std.c++> ralpht@meaddata.com (Ralph W. Trickey) writes:
: |>|> >
: |>|> >  I don't think that requiring total ordering would break any existing
: |>|> >program, but it would break quite a few existing compilers.
: |>
: |>This language change that would slow down existing programs. Possibly
: |>to the point where they no longer meet specifications. I consider this
: |>breaking programs.
: |
: |Could someone do the net a great favour and check it?  There's a lot
: |of speculation but nobody has measured how severe the slow-down would be.

: People who are experienced with PCs don't have to measure this problem
: because they are well aware of the issues and the code sizes involved.
: What you ask for is essentially the same thing as "Huge" model which
: PC compilers support but *which PC programmers don't use* -- because its too
: expensive.

: But, since *you* request the numbers, here's a simple example:

: Compaq Deskpro 386/20
: C7 compiler all optimizations.

: Comparing an pointer inner loop, incrementing one pointer and comparing
: with another pointer within a loop.

: The "total ordering" approach loop executes approx 3X slower than
: the typical PC segment:offset approach.

Jim, I think your result is slightly misleading, since the "huge"
model involves other overhead than pointer comparison (as someone
already pointed out).  Here are more accurate measures:

Dell 486/33
MSC 6.00A compiler all optimizations (/Ozax).

Same test as Jim, test program at end.

The first two numbers are for the normal "large" memory model.
The last two numbers are for the "huge" model.
/AL: p1 < p2   28 sec.
/AL: (long)p1 < (long)p2 55 sec.
/AH: p1 < p2   96 sec.
/AH: (long)p1 < (long)p2 87 sec.

So, like Jim, I find a more than 3x worst-case speed reduction
when switching from "large" to "huge".

However, the real slowdown is just 2x (55/28).  Note that the figure
I gave in an earlier posting (33 %) was for unoptimized code.

Side note: It seems to pay off to cast to long in the "huge"
model.  In this case the programmers knows more than the compiler
is allowed to (that the pointer won't travel over more than 64 K).

I would think the size overhead Jim mentioned (28 bytes) is excessive too.

Other than the measurements, I agree with Jim.  The total
ordering penalty should only be payed when used.  The ptrcmp()
function proposed in another posting achieves just that.

Test program follows (press 'n' to skip).

#include <stdio.h>
#include <stdlib.h>

#define LOOPS 100L * 1000L

int main(void)
{
   char* ap = (char*) malloc(65000U);
   char* bp = (char*) malloc(65000U);
   char* aend = ap + 1000;
   long i;

   if ( ap < bp || bp < ap ) {
      printf( "p1<p2 is probably totally ordered.\n" );
   } else {
      printf( "p1<p2 is not totally ordered.\n" );
      if ( (long)(ap) < (long)(bp) || (long)(bp) < (long)(ap) ) {
         printf( "\tbut (long)p1<(long)p2 is probably totally ordered.\n" );
      }
   }

   system( "echo. | time" );
   for ( i = 0; i < LOOPS; ++i ) {
      char* p = ap;
      while ( p++ < aend )
         { }
   }
   system( "echo. | time" );
   for ( i = 0; i < LOOPS; ++i ) {
      char* p = ap;
      while ( (long)(p++) < (long)(aend) )
         { }
   }
   system( "echo. | time" );

   return 0;
}

--
--------------------------------------------------------------------------
| Johan Bengtsson, Telia Research AB, Aurorum 6, S-951 75 Lulea, Sweden  |
| Johan.Bengtsson@lulea.trab.se; Voice:(+46)92075471; Fax:(+46)92075490  |
--------------------------------------------------------------------------

In article <1992Dec12.154918.2220@ucc.su.OZ.AU> maxtal@extro.ucc.su.OZ.AU (John MAX Skaller) writes:
|which cannot break existing implementations but provides a  total
|order by way of a library function? If so, can we put this to
|the library WG?

I think some flavor of "ptrcmp" makes sense on those implementations that
support casting pointers to integrals and back, and probably doesn't make
sense on those implementations that don't support the pointer/integral casts.

In either case, I would ask what kind of sense it makes to write a "standard"
that *requires* a certain behavior of *some* implementation but doesn't
*require* that behavior of *all* implementations?  How do you justify such
a dichotomy?

On the contrary, I suggest that in a "standard" either something IS *required*
of *all* implementations, or something IS NOT *required* of *all*
implementations.  If the committee cannot agree that something IS or IS NOT
*required* of all implementations, then what they should do instead is list
this something as a "commonly implemented extension to the language."

Such would be the proper designation, IMHO, for both the bidi pointer/integral
cast, and for the proposed "ptrcmp" macro.  Then, on Lisp machines, or
C++ OODBMS's or whatever systens would find the total ordering
practically unsupportable in their environment, they simply would not implement
the "common extension."  This would be a quality of implementation issue then,
not an issue of conformance.

In any case, "ptrcmp" would be a misnomer, because what is being compared
is *not* pointers, but rather the underlying *assumed* implementation of
pointers using machine addresses.  The correct name might be something like
"addrcmp" then, so as to not further confuse programmers on the difference
between language and implementation.

In article <5366@miramon.lulea.trab.se> jbn@lulea.trab.se (Johan Bengtsson) writes:
|Other OODBMSs that use straight pointers to refer to persistent
|objects (e.g. ObjectStore,Texas) must provide a rather special
|ptrcmp(void*,void*), or disallow use of ptrcmp() for persistent
|objects (may be difficult to check).

What if ptrcmp [addrcmp] were allowed to return 0 for those objects
and/or systems that don't define an ordering for those objects?

The implication would be that one routine could be written that uses
a fast ordering scheme on those OS's and/or objects that support the
ordering, but a slower secondary scheme would have to be included for
those cases of objects or OS's where the order is undefined.
The secondary scheme would only have to be implemented by those programmers
*really* interested in writing *really* portable code, since a defined
ordering out of ptrcmp would be a common extension.

???

In article <24398@alice.att.com> ark@alice.UUCP () writes:
>In article <1992Dec12.162211.5076@ucc.su.OZ.AU> maxtal@extro.ucc.su.OZ.AU (John MAX Skaller) writes:
>
[deleted]
>No, that's just the opposite of that I said.
>
>I said `the context that WAS current.'

 Phew! Sorry, I think ...
>
>Perhaps an example will make it clearer:
>
> void (*p)(void);
> void f(int n)
> {
>  void g() { printf("%d\n", n); }

 of there being only *one* function 'g()' here,
not a new one for each activation record. I though you were saying
only ever one trampoline for 'g' was needed, what you meant
was at most one for each pair (g,activation of f)

--
;----------------------------------------------------------------------
        JOHN (MAX) SKALLER,         maxtal@extro.ucc.su.oz.au
 Maxtal Pty Ltd, 6 MacKay St ASHFIELD, NSW 2131, AUSTRALIA
;--------------- SCIENTIFIC AND ENGINEERING SOFTWARE ------------------

In article <1992Dec11.230534.10499@microsoft.com> jimad@microsoft.com (Jim Adcock) writes:
>In article <1992Dec10.121935.19315@ucc.su.OZ.AU> maxtal@extro.ucc.su.OZ.AU (John MAX Skaller) writes:
>| The answer to this particular question is YES, they must
>|compare equal according to the ARM. And I think this is a problem
>|for OS design for the 386, for example, where the memory management
>|kernel will just have to ignore the ARM.
>
>No more nor less than any other virtual memory OS that allows
>multiply mapped pages.  Since there is no functionality in the
>language requiring such multiply mapped pages, you only get in
>this situation by invoking some system dependency, in which case
>you are making use of implementation dependencies.  If you will,
>a common C/C++ implementation defined extension to the language
>is to allow the use of OS calls in order to map various regions
>of memory to the same underlying page, allowing the same object
>to be accessed via differing addresses.  Implementation defined,
>no more nor less.
>

But Jim, it is not implementation defined, it is required that
pointers to the same object compare equal. It is therefore
legal to have a function:

 f(X* a, X*b) {
 if(a==b) { /* special case, copy b object */ ... }
 else *a+=*b;
 }

where the += operation is destructive and wont work if a and b point
to the same object. The above code is guarranteed in C++, but
will fail on a suitably organised system. It is therefore not
allowed to do this sort of memory mapping in C++ behind the scenes,
which is what I'm concerned with...we actually want to.

So the question is really whether the requirement that pointers to
the same object compare equal should be left implementation defined.
Or perhaps more restrictions be made, like saying they must
compare equal if one is assigned from another, but not otherwise.



--
;----------------------------------------------------------------------
        JOHN (MAX) SKALLER,         maxtal@extro.ucc.su.oz.au
 Maxtal Pty Ltd, 6 MacKay St ASHFIELD, NSW 2131, AUSTRALIA
;--------------- SCIENTIFIC AND ENGINEERING SOFTWARE ------------------

Jim Adcock (jimad@microsoft.com) wrote:
: In article <1992Dec12.154918.2220@ucc.su.OZ.AU> maxtal@extro.ucc.su.OZ.AU (John MAX Skaller) writes:
: |which cannot break existing implementations but provides a  total
: |order by way of a library function? If so, can we put this to
: |the library WG?

: In any case, "ptrcmp" would be a misnomer, because what is being compared
: is *not* pointers, but rather the underlying *assumed* implementation of
: pointers using machine addresses.  The correct name might be something like
: "addrcmp" then, so as to not further confuse programmers on the difference
: between language and implementation.

No, this is not right.  You can require that a total ordering of all
pointers exist, without assuming anything about their representation.

The abstract ordering property will probably be implemented using
machine addresses if pointers are implemented that way, but it is not
a given that total pointer ordering needs machine addresses.

Therefore, "ptrcmp" is a much better name than "addrcmp".

--
--------------------------------------------------------------------------
| Johan Bengtsson, Telia Research AB, Aurorum 6, S-951 75 Lulea, Sweden  |
| Johan.Bengtsson@lulea.trab.se; Voice:(+46)92075471; Fax:(+46)92075490  |
--------------------------------------------------------------------------

In article <1992Dec4.093044.16823@jyu.fi> sakkinen@jyu.fi (Markku Sakkinen) writes:
|-- In the last few years there _have_ been gratuitous changes in the language
|that have made fully standard code illegal (or perhaps worse still, legal but
|with changed behaviour).

Agreed, and in general those changes have been practical and well motivated.
What you suggest is neither.  On the contrary, you ask to legalize your
favorite hacks.

|Please don't mix up C into this, C++ _is_ a separate language.

On the contrary, C++ _is not_ a separate language.  Eiffel is
a separate language.  If there was not a need for backwards compatibility
we could just chuck C/C++ and its shortcomings and start with a clean slate.

|(I don't know about the drafts of the ANSI committee, but at least the ARM does not
|use any terminology like 'conforming' and 'strictly conforming'.)

This is because the ARM is a reference manual and not a standard.  Once
the committee has taken the *two* C++ base documents -- namely the ARM *and*
the ANSI-C standard -- and molded the two into something worthy of being
called a "standard" then the C++ standard will have to use terminology
such as conforming, strictly conforming, constrained error, unconstrained error,
etc -- or equivalent terminology of their own invention -- in order to be
something worthy of being called a "standard."  Because a standard must be
something that is "testable" -- something of which we can reasonably and
honest ask: "does this compiler conform to the standard?" "does this program
conform to the standard?" "does this program compile correctly on any
conforming compiler?" "does this program compile correct on every
conforming compiler" ?? etc none of which can be asked meaningfully
unless the eventual C++ standard contains language allow us to distinguish
these kinds of cases.

|So you say that most C++ compilers for the PC used to be more or less broken
|(could not implement the full language), and programmers were therefore forced
|to dirty tricks as work-arounds?

No, on the contrary PC compilers implement the full language, its just that
the full language is something different that you desire it to be.  Programmers
made use of that langauge in legal ways that you pretend to ignore, and now
you want to take their legal programs, declare those legal programs as "hacks"
and require that no PC compiler be allowed to support those legal programs
anymore.

|Please calm down (your throat will get sore if you use so many exclamation signs)
|and try not to confuse things.  C++ as a language does not directly support
|an OODBMS.  C++ pointers are memory pointers, and object references within an OODBMS
|are a different thing (you will need a stronger and cleaner concept of object
|identity there anyway).

On the contrary C++ pointers are NOT memory pointers.  Two simple
counterexamples are null pointers and member pointers.  You continue
to confuse language and implementation.

|I'll try to explain:

First you must understand.

|As long as we have C++ objects, i.e. in memory, their addresses (or at least the
|valid pointer values to access them) _must_ stay constant, because C++ has no
|means to automatically track down and modify all pointers to an object.

Wrongo.  Again you confuse language and implementation.  On the contrary,
I've written an internal implementation of C++ that does have the means to
automatically track down and modify all pointers to an object.  There
are other systems that do this kind of thing too.  Such as early versions of
Windows.

|If the contents of some object are copied to or from the DB, that does not
|change or complicate the situation.  On the other hand, if some C++ object is deleted
|after having been copied to the DB, and the DB object is later restored into memory,
|it will be a _new_ C++ object.

What you suggest violates the fundamental tenents of OODBMSs -- namely that
an object maintains its identity no matter in what medium it is stored.

|Sorry, but IMO it's you who have been furiously defending hacks, not I.
|Perhaps there is this misunderstanding:  you think that the requirement
|of total ordering for pointers implies a linear address model.
|No, we don't require that the ordering should directly map into physical order,
|it's just as fine if a pointer consists of base and segment and relocation and index
|or whatever.  Punning would do, i.e. treating the pointer as if it were an integer value.
|However, the ARM does not require implementations to provide an integral type
|that is sufficient to store an arbitrary pointer.

Fine, then what you ask for is what PC compilers already provide.  Its just
that what you are asking for then is insufficient to accomplish what you
want to do.  Because PCs already allow pointers to be "punned" to ints,
its just that those ints are insufficient to store a pointer, and as
such you only get a partial ordering [over the offset part] rather than a
total ordering [over both segment:offset].  Thus, again, as I've said
all along, your proposed implementation is a "hack" -- that is to say, it'll
only work on some conforming implementations, and not others.

|One obvious case where a total order of pointers would be nice to depend on
|are (large) collections of pointers -- I think Andrew Koenig mentioned this
|many submissions ago.  With total order, you can organise such collections
|e.g. so that binary search can be used, requiring O(log N) time;
|otherwise you are stuck with linear search and O(N) time.

Again, if you want to do this, then arrange to do so.  Just don't ask
all compilers to support the hacks you'd want to implement it in.
"Pointers" have well established meaning in C/C++ -- they are not the
same thing as memory addresses.  If you want to implement your program
in terms of memory addresses then implement it in terms of memory addresses.
Don't insist that pointers BE memory addresses.

In <comp.std.c++> jimad@microsoft.com (Jim Adcock) writes:
>
>If you want to compare addresses, the following works on all computers
>and compilers I've ever had to deal with:
>
>if (((long)ptr_a) > ((long)ptr_b))
> blah();

I would be perfectly happy with a simple work-around, like the one
above.  If the standard guarantees that given two pointers of the same
type "p" and "q",

 p != q  <=>  long(p) > long(q)  |  long(p) < long(q)

I assume this is not the case now, but if a trivial change in the
standard document would give us this guarantee, the problem is solved
and we need not discuss it anymore.

If there are any problems, for example, if all significant bits of the
pointers will not fit into a long integer, I think we're back to
square one again and have to define "operator<" for pointers.  The
alternative is of course to dismiss the idea as not worth the trouble.


  -- Dag

In <comp.std.c++> jimad@microsoft.com (Jim Adcock) writes:
>In article <1992Dec4.070720.13056@lth.se> dag@control.lth.se (Dag Bruck) writes:
>|
>|Could someone do the net a great favour and check it?  There's a lot
>|of speculation but nobody has measured how severe the slow-down would be.
>
>People who are experienced with PCs don't have to measure this problem
>because they are well aware of the issues and the code sizes involved.

Thank youuu!

>What you ask for is essentially the same thing as "Huge" model which
>PC compilers support but *which PC programmers don't use* -- because its too
>expensive.
>Comparing an pointer inner loop, incrementing one pointer and comparing
>with another pointer within a loop.
>
>The "total ordering" approach loop executes approx 3X slower than the typical PC
>segment:offset approach.  The "total ordering" approach loop takes 28 bytes more
>code for the pointer comparison than the typical PC segment:offset
>[large model] approach.

There are a few issues that I would like someone to comment on:

   1. I assume that there is overhead in using the Huge model
 compared to the Large model, even if I never compare
 pointers.  Correct?

   2.   If the compiler was modified to generate the expensive code
 only for "operator <" in Large model, it could still generate
 the more efficient code for all other operations involving
 pointers.

 In other words, the assumption is that only the implementation
 of "int operator < (void*, void*)" need to be changed.

   3.   In a tight loop, as in the example above, the optimizer should
 be able to identify a segment address invariant.  At present
 there is no reason to do this optimization, so I'm not
 surprised that Microsoft has spent effort on other things.

   4.   The total ordering of pointers would be used in a few but
 important cases, for example, to build tables.  In these
 cases the algorithmic speed-up is more significant than
 the overhead caused by less optimal code.

Am I completely unaware of the inner workings of PCs?


   -- Dag

>>>>> On 07 Dec 92 22:22:42 GMT, jimad@microsoft.com (Jim Adcock) said:

> If you want to compare addresses, then compare addresses.  If you
> want to compare pointers, then compare pointers.  A pointer is not
> an address.  An address is one particular implementation of a pointer.
> If you want to compare addresses, the following works on all computers
> and compilers I've ever had to deal with:

> if (((long)ptr_a) > ((long)ptr_b))
>  blah();

For pointers to functions? pointers to virtual member functions?
--
     Alan Braggins, alanb@sdl.mdcbbs.com, abraggins@cix.compulink.co.uk
Shape Data - A division of EDS-Scicon Limited.   Cambridge, UK +44-223-316673
   "Any technology distinguishable from magic is insufficiently advanced."
 "My employer does not necessarily share my views - but I'm working on it."

In article <1992Dec07.225634.19943@microsoft.com> jimad@microsoft.com (Jim Adcock) writes:
>In article <1992Dec4.093044.16823@jyu.fi> sakkinen@jyu.fi (Markku Sakkinen) writes:
>|-- In the last few years there _have_ been gratuitous changes in the language
>|that have made fully standard code illegal (or perhaps worse still, legal but
>|with changed behaviour).
>
>Agreed, and in general those changes have been practical and well motivated.
>What you suggest is neither.  On the contrary, you ask to legalize your
>favorite hacks.

No, it's you who are crying for hacks:  programs that happen to work
in a certain way because of the peculiarities of a certain compiler.
Now you think it has been OK to break many "strictly conforming" programs!

> ...
>|So you say that most C++ compilers for the PC used to be more or less broken
>|(could not implement the full language), and programmers were therefore forced
>|to dirty tricks as work-arounds?
>
>No, on the contrary PC compilers implement the full language, its just that
>the full language is something different that you desire it to be.  Programmers
>made use of that langauge in legal ways that you pretend to ignore, and now
>you want to take their legal programs, declare those legal programs as "hacks"
>and require that no PC compiler be allowed to support those legal programs
>anymore.

You have been pleaded a dozen times to give an example.
Why don't you present one, so we can get this discussion on more
rational grounds!

> ...
>On the contrary C++ pointers are NOT memory pointers.  Two simple
>counterexamples are null pointers and member pointers.  You continue
>to confuse language and implementation.

'Member pointer' is a confusing misnomer;  I meant real pointers.
A null pointer is a _very_ special case (not only in C and C++).
My favourite interpretation is that every pointer type is actually
an undiscriminated union of a true pointer type and null.

> ...
>|As long as we have C++ objects, i.e. in memory, their addresses (or at least the
>|valid pointer values to access them) _must_ stay constant, because C++ has no
>|means to automatically track down and modify all pointers to an object.
>
>Wrongo.  Again you confuse language and implementation.  On the contrary,
>I've written an internal implementation of C++ that does have the means to
>automatically track down and modify all pointers to an object.  There
>are other systems that do this kind of thing too.  Such as early versions of
>Windows.

Maybe, but such a system must be terribly expensive in memory and
processor time;  and your main motivation seemed to be to save
a couple of processor cycles.

>|If the contents of some object are copied to or from the DB, that does not
>|change or complicate the situation.  On the other hand, if some C++ object is deleted
>|after having been copied to the DB, and the DB object is later restored into memory,
>|it will be a _new_ C++ object.
>
>What you suggest violates the fundamental tenents of OODBMSs -- namely that
>an object maintains its identity no matter in what medium it is stored.

-- as long as it is _in_ the database.  BTW, actually total order is
a simple thing within an OODB _because_ the identity of each object
is assured not to change.

>| ...
>|No, we don't require that the ordering should directly map into physical order,
>|it's just as fine if a pointer consists of base and segment and relocation and index
>|or whatever.  Punning would do, i.e. treating the pointer as if it were an integer value.
>|However, the ARM does not require implementations to provide an integral type
>|that is sufficient to store an arbitrary pointer.
>
>Fine, then what you ask for is what PC compilers already provide.  Its just
>that what you are asking for then is insufficient to accomplish what you
>want to do.  Because PCs already allow pointers to be "punned" to ints,
>its just that those ints are insufficient to store a pointer, and as
>such you only get a partial ordering [over the offset part] rather than a
>total ordering [over both segment:offset].

Oh dear!  I am asking to treat _a pointer_ as an integer, not
a _slice_ of a pointer;  thus those compilers don't provide what
I asked for.  Any implementation that allows the conversion
between pointers and some integral type and v.v., without loss
of information, is fine.  However, depending on such conversions
is not portable.  Some people indeed want to write portable software,
and not only for a 1970s state-of-the-art Deci (one tenth) Operating System.

>  Thus, again, as I've said
>all along, your proposed implementation is a "hack" -- that is to say, it'll
>only work on some conforming implementations, and not others.

I was not proposing an _implementation_ but an additional rule to the
language.  Of course, any new rule is inconvenient to any existing
implementation that does not already happen to obey it.

> ...
>"Pointers" have well established meaning in C/C++ -- they are not the
>same thing as memory addresses.  If you want to implement your program
>in terms of memory addresses then implement it in terms of memory addresses.
>Don't insist that pointers BE memory addresses.

I already explained that the issue was not to program in terms of
memory addresses!

----------------------------------------------------------------------
Markku Sakkinen (sakkinen@jytko.jyu.fi)
       SAKKINEN@FINJYU.bitnet (alternative network address)
Department of Computer Science and Information Systems
University of Jyvaskyla (a's with umlauts)
PL 35
SF-40351 Jyvaskyla (umlauts again)
Finland
----------------------------------------------------------------------

In article <1992Dec8.103218.27689@lth.se>, dag@seldon.control.lth.se (Dag Bruck) writes:
|> In <comp.std.c++> jimad@microsoft.com (Jim Adcock) writes:
|> >
|> >If you want to compare addresses, the following works on all computers
|> >and compilers I've ever had to deal with:
|> >
|> >if (((long)ptr_a) > ((long)ptr_b))
|> > blah();
|>
|> I would be perfectly happy with a simple work-around, like the one
|> above.  If the standard guarantees that given two pointers of the same
|> type "p" and "q",
|>
|>  p != q  <=>  long(p) > long(q)  |  long(p) < long(q)
|>
|> I assume this is not the case now, but if a trivial change in the
|> standard document would give us this guarantee, the problem is solved
|> and we need not discuss it anymore.
|>
|> If there are any problems, for example, if all significant bits of the
|> pointers will not fit into a long integer, I think we're back to
|> square one again and have to define "operator<" for pointers.  The
|> alternative is of course to dismiss the idea as not worth the trouble.
|>
|>
|>   -- Dag

I don't think that it would be a trivial change. I think Jim Adcock
raised an interesting issue, that a pointer is not the same as a
memory address. I am used to working at a low-level, so I understand
how it is easy to confuse the two. I am definitely against tying a
pointer to an explicit memory address. It is usually easy to convert
between pointers and memory addresses for a specific case, but that
conversion should be implementation dependent.

Attempting to require this for the general case becomes very
complicated. How is the null pointer handled? Is it less than all
other pointers, or is that implementation dependent, or what? How is
shared memory handled, if I have 2 pointers that are pointing to
different addresses, but are pointing to the same object, must they
compare equal? What about future hardware that will keep reference
counts, and merge/split objects as required.

I feel that pointers are pointers, not addresses. The fact that they
usually point to a unique address in memory is a helpful idea, but
should not be required.

BTW, The intel 80x86 is capable of addressing memory with a 16-bit segment
and a 32 bit offset. This is a total of 48 bits, which is larger than
the standard 32 bit longs. I believe there are several RISC chips on
the way that will have similar problems.

As an aside, you probably won't have any problems porting your code to
the intel architecture, if you are porting to 16 bit mode you will
have to typecast the pointers to longs before comparing them, if you
are porting to 32 bit mode, you probably won't have to make any
changes.

I like thing the way they are. I believe the C standard, and probably
the C++ standard clearly states that the result of comparing 2
pointers that are not pointing to the same array is undefined. If you
are going to write hacks, don't expect them to be portable.

Ralph Trickey

--
Ralph Trickey       | (513) 865-6800                  |
Mead Data Central   | x4870                           |  Disclaimer
P.O. Box 933        | ralpht@meaddata.com             |  My opinions are my own
Dayton, Ohio  45401 | ...!uunet!meaddata!ralpht       |

In article <1992Dec8.110517.28521@lth.se>, dag@seldon.control.lth.se (Dag Bruck) writes:
|> In <comp.std.c++> jimad@microsoft.com (Jim Adcock) writes:
|> >In article <1992Dec4.070720.13056@lth.se> dag@control.lth.se (Dag Bruck) writes:
|> >|
|> >|Could someone do the net a great favour and check it?  There's a lot
|> >|of speculation but nobody has measured how severe the slow-down would be.
|> >
|> >People who are experienced with PCs don't have to measure this problem
|> >because they are well aware of the issues and the code sizes involved.
|>
|> Thank youuu!
|>
|> >What you ask for is essentially the same thing as "Huge" model which
|> >PC compilers support but *which PC programmers don't use* -- because its too
|> >expensive.
|> >Comparing an pointer inner loop, incrementing one pointer and comparing
|> >with another pointer within a loop.
|> >
|> >The "total ordering" approach loop executes approx 3X slower than the typical PC
|> >segment:offset approach.  The "total ordering" approach loop takes 28 bytes more
|> >code for the pointer comparison than the typical PC segment:offset
|> >[large model] approach.
|>
|> There are a few issues that I would like someone to comment on:
|>
|>    1. I assume that there is overhead in using the Huge model
|>  compared to the Large model, even if I never compare
|>  pointers.  Correct?
|>

Yes, all increment, decrement, indexing, and probably several other
operations involving pointers would be affected.

|>    2.   If the compiler was modified to generate the expensive code
|>  only for "operator <" in Large model, it could still generate
|>  the more efficient code for all other operations involving
|>  pointers.

Yes, but you can do the same by typecasting the pointers to longs.

|>
|>  In other words, the assumption is that only the implementation
|>  of "int operator < (void*, void*)" need to be changed.
|>
|>    3.   In a tight loop, as in the example above, the optimizer should
|>  be able to identify a segment address invariant.  At present
|>  there is no reason to do this optimization, so I'm not
|>  surprised that Microsoft has spent effort on other things.
|>
|>    4.   The total ordering of pointers would be used in a few but
|>  important cases, for example, to build tables.  In these
                                                    ^^ ^^^^^
|>  cases the algorithmic speed-up is more significant than
    ^^^^^
|>  the overhead caused by less optimal code.

In these cases you may be right, I object to your dictating a
slow-down for all other cases.

|>
|> Am I completely unaware of the inner workings of PCs?

No, I think the problem is that you are hunting flies with an elephant
gun. What you want is NOT total ordering, which is very expensive, and
impractical because it would impose a penalty on all programs to make
a few easier to write. What you want is for the compiler to compare
the segment and the offset automatically, instead of requiring a
typecast to a long.

|>
|>
|>    -- Dag

I think the best idea would be to lobby your favorite PC compiler
vendor and request that they add a compile-time switch that allows
comparing  the offset and segment, or compare the offset only for
operator < on pointers. That is an idea I think everyone would
support, it would allow you to compile and run your programs, without
imposing that overhead on all programs.

--
Ralph Trickey       | (513) 865-6800                  |
Mead Data Central   | x4870                           |  Disclaimer
P.O. Box 933        | ralpht@meaddata.com             |  My opinions are my own
Dayton, Ohio  45401 | ...!uunet!meaddata!ralpht       |

dag@seldon.control.lth.se (Dag Bruck) writes:

>If there are any problems, for example, if all significant bits of the
>pointers will not fit into a long integer, I think we're back to
>square one again and have to define "operator<" for pointers.

There are machines where pointers are larger than longs.  If memory
serves, longs are 32 bits and pointers are 48 bits on the IBM AS400
for example.  (But don't quote me.)
--

Steve Clamage, TauMetric Corp, steve@taumet.com
Vice Chair, ANSI C++ Committee, X3J16

In article <ALANB.92Dec7104909@catalina.sdl.mdcbbs.com> alanb@sdl.mdcbbs.com (Alan Braggins) writes:
>>>>>> On 03 Dec 92 20:09:34 GMT, jimad@microsoft.com (Jim Adcock) said:
>
>> |  I don't think that requiring total ordering would break any existing
>> |program, but it would break quite a few existing compilers.
>
>> You think wrong.  To quote from the ANSI-C rationale, existing implementations
>> don't matter -- existing CODE does.  MUCH existing code depends on partial
>> ordering.  And NOT just on PCs.
>
>Then why have no examples been shown?
>--

 Did you miss the example I posted?

 int * far x= new int[20]; // assume each array in different segment
 int * far y= new int[20];
 int * near ye=y+20; // offset part only
 for(int * near xe=&x; xp<ye; ++xp) ...

Here the offsets only are used in the loop, so the termination test
checks if xp<ye even though x and Y are in different segments, it works,
and is much faster than comparing the full 48 bit addresses,
which would always satisfy xp<ye or xp>ye. Thus this conforming
but not strictly conforming code would go into an infinite loop
if total ordering were required.

(The 'near' keyword is of course compiler/system specific, so clearly
this code is not strictly conforming anyhow. All 80x86 systems
support these extensions because they're necessary, that doesnt make
the programs non-conforming, just not strictly conforming)


--
;----------------------------------------------------------------------
        JOHN (MAX) SKALLER,         maxtal@extro.ucc.su.oz.au
 Maxtal Pty Ltd, 6 MacKay St ASHFIELD, NSW 2131, AUSTRALIA
;--------------- SCIENTIFIC AND ENGINEERING SOFTWARE ------------------

In article <1992Dec4.093044.16823@jyu.fi> sakkinen@jyu.fi (Markku Sakkinen) writes:
also Jim Adcock and myself ..
>> ...
>>use of them.  You cannot gratuitously make changes to the base language
>>now without darned good justification -- which YOU have not established.
>
>I think the example showed extremely bad hacking style, depending critically
>on the behaviour of one specific compiler,

 Worse, it depended on one memory model of the compiler.

>while the same thing could be achieved
>in a fully standard and portable way with minimal if any performance penalty.

 I thought I did explain this statement is not correct. Unless
you are an 8086 assembler expert as I am, please take my word for it,
because I dont want to bother actually writing the 8086 code to show.
(I want to give up 8086 real mode assembler coding!)

>I don't think that the C++ community as a whole has an obligation to assure
>the continued legality of such bags of dirty tricks.

 I admitted the example I gave was silly, it was all I could think
of quickly. The point is that in the absense of prohibition, and
or specific wording 'implementation defined' it is indeterminate
which programs---hacked or not--would break.

 Here is another example: Because the 8086 is limited to
1M address space the addresses FFF0:0100 and 0000:0000 are equal.
This 'segment wraparound' property is actually used by many 8086
programmers, in fact, there is a specific operating system 'call'
that uses this fact (a hang over from CP/M actually).

 As long as data structures are aligned on 16 byte boundaries,
it is quite normal to adjust segment registers so you can scan two
arrays in parallel using a single 16 bit offset register. This
might be a hack, it is certainly machine specific, but recall
one of the design aims of C was to allow operating system design,
and a close correspondence to the hardware...even if that hardware
is 'not so good'.

 It *is* normal to try to write really fast code on the 8086,
at the expense of hacks, after all the processor itself is a hack,
but there are lots and lots of them, and non-academic programmers
have to make a living.

 If we were designing a 'from scratch' language it wouldn't be
C++, it would be Eiffel :-)

>>You still seem to be confusing the issue of conforming programs verses
>>strictly conforming programs.  A conforming PC program can use large
>> ...
>>for segment and offset variables.  Prior to these language extensions,
>>such comparisons HAD to be done by hack because their was no language
>>support for them.  Now you proprse to require C++ implementaions break
>>these existant conforming C programs.
>                          ^^^^
>
>Please don't mix up C into this, C++ _is_ a separate language.

 Not completely. C compatibility is one of the most important
issues taken into consideration. Breaking it is considered only if there
are strong arguments. Breaking prior versions of C++ is less of a problem,
there isn't a prior standard to break, after all.

>(I don't know about the drafts of the ANSI committee,
>but at least the ARM does not
>use any terminology like 'conforming' and 'strictly conforming'.)

 It doesnt have to. Jim explained what the implications are to
me, and if I have it right a strictly conforming program should
work on any compiler//machine, i.e. be portable, but a merely
conforming one might be quite system specific.

 Non-strictness is mandatory for some programs, sometimes
even non-conforming is needed. For example, no Windows program
can possibly conform to C++ specs, if only because Windows
programs have a WinMain entry and not a main entry. But there
are other reasons, one being that the C/C++ linkage/memory
model concepts are obsolete and cant cope with the requirements
of modern systems. For example, Windows supports dynamic
linkage, and to use it you have to nominate *in the language*
which functions are exported. Borland C++ therefore has
a _export keyword. Similarly, on any 80x86 system there are
various memory models and it is sometimes necessary to
nominate the type of pointer being used: _far for example.

 This is inevitable in any language purporting to
support access to the hardware on various machines.

>So you say that most C++ compilers for the PC used to be more or less broken
>(could not implement the full language), and programmers were therefore forced
>to dirty tricks as work-arounds?  Could you finally give a short concrete code example?

 This is not the point. Non-strictly conforming means that
where 'implementation defined' is specified in the manual, the programmer
has utilised a specific implementations features. Such a program
wont run on another platform, but then an embedded real time system
designed to control specific hardware wont do that anyhow.
>
>>Maintain a total ordering over a OODBMS!!??
>
>Please calm down
>(your throat will get sore if you use so many exclamation signs)
>and try not to confuse things.

 Markku, having the greatest respect for yourself and Jim I should
point out that it is part of Jim's style to use many !!??** marks.
I dont mind if he shouts sometimes, I wont go deaf listening on the net :-)

>C++ as a language does not directly support an OODBMS.

 But many people want to use it for that.

>C++ pointers are memory pointers, and object references within an OODBMS
>are a different thing (you will need a stronger and cleaner concept of object
>identity there anyway).  I'll try to explain:
>
>As long as we have C++ objects, i.e. in memory, their addresses (or at least the
>valid pointer values to access them) _must_ stay constant, because C++ has no
>means to automatically track down and modify all pointers to an object.

 It doesnt need to have. There could be a silent system
in the background doing this. For example, in Windows-real mode,
exactly this happens. The programmer is required to specifically
call a lock function on a handle to obtain a pointer, and unlock it
afterwards.

>If the contents of some object are copied to or from the DB, that does not
>change or complicate the situation.  On the other hand, if some C++ object is deleted
>after having been copied to the DB, and the DB object is later restored into memory,
>it will be a _new_ C++ object.

 Thats *your* idea. But if someone proposed some implementation
specific scheme whereby in *their* C++ implementation, a pointer
was *not* a machine address but a handle it might still be
a conforming but not strictly conforming program.

>
>>Again, seems clear to me that using a total ordering is simply a
>>un*x-memory model hack, and should be treated as such.  If *you* want
>> ...
>
>Sorry, but IMO it's you who have been furiously defending hacks, not I.

 Whats a hack is clearly relative to your point of view :-)

>Perhaps there is this misunderstanding:  you think that the requirement
>of total ordering for pointers implies a linear address model.

 No I think Jim is saying that existing software that uses
implementation defined semantics which happen not to be a total order
would be broken.

>No, we don't require that the ordering should directly map into physical order,
>it's just as fine if a pointer consists of base and segment and relocation and index
>or whatever.  Punning would do, i.e. treating the pointer as if it were an integer value.

 This is not necessarily the case. For example,
there is a phenomena called aliasing, it already causes problems for
the == and != operators. Two equal linear addresses might have several
different logical addresses. And two equal linear addresses
might be two different physical addresses .. in the same program
even at different times (virtual memory).

 On the other hand two unequal linear addresses might always
refer to the same memory. C++ already requires pointers to the same
object to compare equal, and this is a heavy constraint. A read-write
and read-only segment may be aliased, and two pointers using these
different segments to access the same object will not compare equal.
Computing the linear addresses is not possible, the user codes
are prevented from doing that.

 Furthermore, 386 selectors have a few bits in them relating
to access privileges of the requestor and nothing to do with the actual
segment requested. So even comparison for equality is problematic,
a total ordering requirement could be a bit messy to implement.

>However, the ARM does not require implementations to provide an integral type
>that is sufficient to store an arbitrary pointer.

 That is good, the 386 has 48 bit pointers but only 32 bit registers.
>
>One obvious case where a total order of pointers would be nice to depend on
>are (large) collections of pointers -- I think Andrew Koenig mentioned this
>many submissions ago.  With total order, you can organise such collections
>e.g. so that binary search can be used, requiring O(log N) time;
>otherwise you are stuck with linear search and O(N) time.

 Indeed there are good arguments for total ordering.
There are also good arguments in favour of pointers being
totally abstract entities on which no operations at all are allowed
except accessing the object to which they point.

 An operating system kernel for the 386 might well have
physical, linear, and logical addresses, and indeed one of its major
purposes might be to manage memory. Such a program would be
totally ham-strung by a total ordering requirement since memory
on modern architectures just isnt organised that way. In fact,
such a program would probably have to be non-conforming because it could
not meet the == and != requirements. Should the OS programmer
really be forced to write the OS in assembler to defeat overly
strict C++ rules based on invalid assumptions about machine
architectures?

 Summary: C and C++ are designed for writing both portable
and non-portable software. This always leads to some undesirable
tradeoffs. Lack of total ordering makes OS writing easier for
specific implementations, whereas total ordering makes portable
software easier. Who can decide which is more important?

--
;----------------------------------------------------------------------
        JOHN (MAX) SKALLER,         maxtal@extro.ucc.su.oz.au
 Maxtal Pty Ltd, 6 MacKay St ASHFIELD, NSW 2131, AUSTRALIA
;--------------- SCIENTIFIC AND ENGINEERING SOFTWARE ------------------

In article <5317@holden.lulea.trab.se> jbn@lulea.trab.se (Johan
Bengtsson) writes:

   [ discussion concerning the benefits of total ordering...]
|> However, I agree that the benefit of total ordering is not great enough
|> to impose even this small performance penalty, since there is a simple
|> technique that can be used for code that needs total pointer order:

|> inline int ptr_less( void* p1, void* p2 ) {
|>    return ( sizeof(long)==sizeof(p1) ?
|>             ((long)p1 < (long)p2) :
|>             (p1 < p2)
|>           );
|> }

|> This definitions works for the C/C++ implementations that I
|> have experience with (PC and UNIX).  I'm sure there are or will
|> be implementations for which the above function does not work,
|> but that can be handled by machine/compiler specific code.

|> Anyone know of machines/compilers for which the above function does not work?

To begin with, 80386 and 80486 in any compilation model that has long
pointers.  (The only compiler I know of at present that supports long
pointers for these processors is the one from Intel.)  In these
processors, a long (like an int) is 32 bits, but pointers are 48 bits
(16 bit segment/selector and 32 bit offset).
--
--
James Kanze                             email: kanze@us-es.sel.de
GABI Software, Sarl., 8 rue du Faisan, F-67000 Strasbourg, France
Conseils en informatique industrielle --
                   -- Beratung in industrieller Datenverarbeitung

In article <ALANB.92Dec7104909@catalina.sdl.mdcbbs.com> alanb@sdl.mdcbbs.com (Alan Braggins) writes:
|Then why have no examples been shown?

We have given examples and explanations of how conforming PC programs come
to depend on not having a total ordering.  Namely the situation easily
arises from interpreting a far pointer as an offset.  When a PC programmer
compares one offset to another -- not an infrequent task -- then
implicit in the comparison is a lack of total ordering.  If you want a
feeling for how often these kinds of assumptions are made, try taking
any significant PC progam and compile it under a variety of memory models --
small, medium, large, and huge models for example, and see how often the
program runs without error.  Your change of success is insignificant for
any "real" program when compiled for any memory model other than the original
programmer expects.

On the contrary, *you* call for examples without providing *any* examples
of where pointers must be implemented using total ordering in order to
accomplish any major programming win.  On the contrary, everything anyone
has suggested so far can easily be accomplished without requiring pointers
be implemented using total ordering.

In <comp.std.c++> ralpht@meaddata.com (Ralph W. Trickey) writes:
>In article <...>, dag@seldon.control.lth.se (Dag Bruck) writes:
>|> I would be perfectly happy with a simple work-around, like the one
>|> above.  If the standard guarantees that given two pointers of the same
>|> type "p" and "q",
>|>
>|>  p != q  <=>  long(p) > long(q)  |  long(p) < long(q)
>
>..... It is usually easy to convert
>between pointers and memory addresses for a specific case, but that
>conversion should be implementation dependent.

I repeat again: the result of the comparison may be implementation
dependent, all I want is that it exists.

>Attempting to require this for the general case becomes very
>complicated. How is the null pointer handled? Is it less than all
>other pointers, or is that implementation dependent, or what?

Yes. Implementation dependednt is fine with me.

> How is
>shared memory handled, if I have 2 pointers that are pointing to
>different addresses, but are pointing to the same object, must they
>compare equal?

As far as I can tell, C/C++ does not cater for shared memory anyway.

> What about future hardware that will keep reference
>counts, and merge/split objects as required.

That is not an issue.  If you have a C pointer to some object, the
pointer can never change because of something the hardware does to the
object.

>I like thing the way they are. I believe the C standard, and probably
>the C++ standard clearly states that the result of comparing 2
>pointers that are not pointing to the same array is undefined. If you
>are going to write hacks, don't expect them to be portable.

I argued that it should become defined, in order to facilitate the
writing of data structures in a portable way.  It is not a hack if the
standard specifies some behaviour, for example that

 p != q   <=>   p < q   |   p > q

for all pointers.  I'm not asking for a particular ordering, just an
implementation defined behaviour that meets the equivalence above.


   -- Dag

dag@seldon.control.lth.se (Dag Bruck) writes:

>In <comp.std.c++> jimad@microsoft.com (Jim Adcock) writes:
>>
>>If you want to compare addresses, the following works on all computers
>>and compilers I've ever had to deal with:
>>
>>if (((long)ptr_a) > ((long)ptr_b))
>> blah();
>
>I would be perfectly happy with a simple work-around, like the one
>above.  If the standard guarantees that given two pointers of the same
>type "p" and "q",
>
> p != q  <=>  long(p) > long(q)  |  long(p) < long(q)
>
>I assume this is not the case now, but if a trivial change in the
>standard document would give us this guarantee, the problem is solved
>and we need not discuss it anymore.
>
>If there are any problems, for example, if all significant bits of the
>pointers will not fit into a long integer, I think we're back to
>square one again and have to define "operator<" for pointers.  The
>alternative is of course to dismiss the idea as not worth the trouble.

There is exactly that problem (that pointers may not fit in long ints),
but we don't have to go back to square one.

What I propose is that we define a *standard library function* which computes
a total ordering on pointers. This would work on virtually any system
without imposing undue constraints on the implementation. Programs written
for Intel architectures would not slow down, but the template collection class
writers get their total ordering. It should make everyone happy! :-)

int compare_pointers(const void *, const void *);
    /* Returns negative, zero, or positive in the same manner as strcmp().
       Perhaps in the interests of tradition and unreadability it should
       be called ptrcmp() instead of compare_pointers() :-) */

This is basically the same as Alan Braggin's suggestion to use
int Comparable::operator < (const Comparable &), but it is important
that it be a standard library function, since it may have to be
implemented in assembly. It is hardly a burden on implementors:
for the vast majority of machines, it should be just a one-liner.

--
Fergus Henderson             fjh@munta.cs.mu.OZ.AU
This .signature virus is a self-referential statement that is true - but
you will only be able to consistently believe it if you copy it to your own
.signature file!

In <comp.std.c++> fjh@munta.cs.mu.OZ.AU (Fergus James HENDERSON) writes:
>
>What I propose is that we define a *standard library function* which computes
>a total ordering on pointers.
>
>int compare_pointers(const void *, const void *);
>    /* Returns negative, zero, or positive in the same manner as strcmp().
>       Perhaps in the interests of tradition and unreadability it should
>       be called ptrcmp() instead of compare_pointers() :-) */

Suggested semantics: for any pointers p and q:

 p == q   <=>   ptrcmp(p,q) == 0

 p != q   <=>   ptrcmp(p,q) != 0

 ptrcmp(p,q) < 0   <=>   ptrcmp(q,p) > 0

Markku Sakkinen (sakkinen@jyu.fi) wrote:
: In article <1992Dec07.225634.19943@microsoft.com> jimad@microsoft.com (Jim Adcock) writes:
: >|
: >|If the contents of some object are copied to or from the DB, that does not
: >|change or complicate the situation.  On the other hand, if some C++ object is deleted
: >|after having been copied to the DB, and the DB object is later restored into memory,
: >|it will be a _new_ C++ object.
: >
: >What you suggest violates the fundamental tenents of OODBMSs -- namely that
: >an object maintains its identity no matter in what medium it is stored.

: -- as long as it is _in_ the database.  BTW, actually total order is
: a simple thing within an OODB _because_ the identity of each object
: is assured not to change.

It would impose severe restrictions on how the virtual address space
could be used though.  The OODBMS may end up in a situation where
it can't get a persistent object into memory, not because it has used up
all virtual memory addresses, but because all unused virtual memory
adresses would violate the total ordering property.

This unnecessary address space fragmentation phenomenon (kind of) would
severely limit the capacity of OODBMSes.

--
--------------------------------------------------------------------------
| Johan Bengtsson, Telia Research AB, Aurorum 6, S-951 75 Lulea, Sweden  |
| Johan.Bengtsson@lulea.trab.se; Voice:(+46)92075471; Fax:(+46)92075490  |
--------------------------------------------------------------------------

In article <1992Dec9.133956.29659@lth.se>, dag@seldon.control.lth.se (Dag Bruck) w|>
|> Suggested semantics: for any pointers p and q:
|>
|>  p == q   <=>   ptrcmp(p,q) == 0
|>
|>  p != q   <=>   ptrcmp(p,q) != 0
|>
|>  ptrcmp(p,q) < 0   <=>   ptrcmp(q,p) > 0

And

 if p < q is defined,  ptrcmp(p,q) < 0   <=>  p < q

      -- Jerry Schwarz

In article <1992Dec8.103218.27689@lth.se> dag@seldon.control.lth.se (Dag Bruck) writes:
>type "p" and "q",
>
> p != q  <=>  long(p) > long(q)  |  long(p) < long(q)
>
>I assume this is not the case now, but if a trivial change in the
>standard document would give us this guarantee, the problem is solved
>and we need not discuss it anymore.
>
>If there are any problems, for example, if all significant bits of the
>pointers will not fit into a long integer, I think we're back to
>square one again and have to define "operator<" for pointers.  The
>alternative is of course to dismiss the idea as not worth the trouble.
>

 386: pointer is 48 bits, register is 32 bits

The standard doesnt requires a pointer to convert to a long, it says
that *if* it does, the reverse conversion gives back the same pointer.


--
;----------------------------------------------------------------------
        JOHN (MAX) SKALLER,         maxtal@extro.ucc.su.oz.au
 Maxtal Pty Ltd, 6 MacKay St ASHFIELD, NSW 2131, AUSTRALIA
;--------------- SCIENTIFIC AND ENGINEERING SOFTWARE ------------------

In article <1992Dec8.193218.13165@ucc.su.OZ.AU> maxtal@extro.ucc.su.OZ.AU (John MAX Skaller) writes:
| It doesnt have to. Jim explained what the implications are to
|me, and if I have it right a strictly conforming program should
|work on any compiler//machine, i.e. be portable, but a merely
|conforming one might be quite system specific.

To quote from the ANSI-C rationale:

EXITSTING CODE IS IMPORTANT, EXISTING IMPLEMENTATIONS ARE NOT.
A large body of C code exists of considerable commercial value...
...The Committee did not want most programmers to modify their
C programs just to have them accepted by a conforming translator...

[Note: an "existing implementation" is not just a C++ compiler, but
 also the OS the code runs on and the tools available.  The systems
 that C++ needs to run on must be able to change too -- not just the
 C++ compilers]

C CODE CAN BE PORTABLE...The Committee has attempted to specify
the language and the library as widely implementable as possible....

[Note: specifying the language in a manner that helps make programs
 portable at the expense of making the language less widely implementable
 does nothing to improve portability -- on the contrary!  We want C++ to
 be implementable on almost all CPUs and systems of the 1990s and the 2000s
 Not only Un*x machine, not only PCs, but also mainframes, vector processors,
 Lisp machines, OOArchitectures, connectionist machines, embedded processors
 inside of toaster ovens, etc]

C CODE CAN BE NON-PORTABLE.  Although it strove to give programmers the
opportunity to write truly portable programs, the Committee did not want
to FORCE programmers into writing portably, to preclude the use of C
as a "high-level assembler": the ability to write machine-specific code
is one of the strengths of C.  It is this principle which largely
motivates drawing the distinctions between STRICTLY CONFORMING PROGRAM
and CONFORMING PROGRAM.

[Note: In that C++ allows such "high level assembly" to be packaged inside
 the inner workings of a class, C++ even better supports such "high level
 assembly".  There is no reason why the inner mechanisms of one class can't
 be implemented in two different manners on two different machines.]

AVOID "QUIET CHANGES."....As much as seemed possible consistent with its
other goals, the Committee has avoided changes that quietly alter one
valid program to another with different semantics, that cause a working
program to work differently without notice....

A STANDARD IS A TREATY BETWEEN IMPLEMENTOR AND PROGRAMMER.....

KEEP THE SPIRIT OF C....
 * TRUST THE PROGRAMMMER
 * DON'T PREVENT THE PROGRAMMER FROM DOING WHAT NEEDS TO BE DONE.
 * KEEP THE LANGUAGE SMALL AND SIMPLE [okay, so we lost that one....]
 * PROVIDE ONLY ONE WAY TO DO AN OPERATION [shucks, lost that one too...]
  * MAKE IT FAST, EVEN IF IT IS NOT GUARANTEED TO BE PORTABLE.

[quotes extracted from the first couple pages of the ANSI-C RATIONALE]

In article <1992Dec9.075125.22405@lth.se> dag@bellman.control.lth.se (Dag Bruck) writes:
|>|>  p != q  <=>  long(p) > long(q)  |  long(p) < long(q)
|>
|>..... It is usually easy to convert
|>between pointers and memory addresses for a specific case, but that
|>conversion should be implementation dependent.
|
|I repeat again: the result of the comparison may be implementation
|dependent, all I want is that it exists.

It does exist in implementation dependent manners on all systems where
it could reasonably exist.  On other machines you just have to take
a different approach.

In article <1992Dec2.205330.10372@meaddata.com> ralpht@meaddata.com (Ralph W. Trickey) writes:
>newsreader. I don't understand what total ordering would achieve.

The Final Solution, I suppose.



--
 Daniel Brockman             tel 415-953-0406, fax 415-622-2892
 Bank of America, Dept 5906, 555 Calif St
 San Francisco 94104 USA    email uunet!odinba!dan dan@bofa.com

In article <9234423.15066@mulga.cs.mu.OZ.AU> fjh@munta.cs.mu.OZ.AU (Fergus James HENDERSON) writes:
>
>What I propose is that we define a *standard library function* which computes
>a total ordering on pointers. This would work on virtually any system
>without imposing undue constraints on the implementation. Programs written
>for Intel architectures would not slow down, but the template collection class
>writers get their total ordering. It should make everyone happy! :-)
>
>int compare_pointers(const void *, const void *);
>    /* Returns negative, zero, or positive in the same manner as strcmp().
>       Perhaps in the interests of tradition and unreadability it should
>       be called ptrcmp() instead of compare_pointers() :-) */
>

 This seems like an excellent suggestion. It suffers only
in those cases where we must ask whether it makes sense to
compare two pointers at all. For example a char* and a function
pointer. Might not these accidentally have the same address?

 Similarly suppose we allowed nested functions, then
pointers to them would need a pointer to a stack frame as well
as the function address (or instead of?). They would be totally
different types of objects really.

 Does anyone think this wonderful compromise solution,
ptrcmp(void*,void*) is unworkable, or will not satisfy both
parties? Any support for it?

--
;----------------------------------------------------------------------
        JOHN (MAX) SKALLER,         maxtal@extro.ucc.su.oz.au
 Maxtal Pty Ltd, 6 MacKay St ASHFIELD, NSW 2131, AUSTRALIA
;--------------- SCIENTIFIC AND ENGINEERING SOFTWARE ------------------

In article <1992Dec8.173855.18153@meaddata.com> ralpht@meaddata.com (Ralph W. Trickey) writes:
>
>Attempting to require this for the general case becomes very
>complicated. How is the null pointer handled? Is it less than all
>other pointers, or is that implementation dependent, or what? How is
>shared memory handled, if I have 2 pointers that are pointing to
>different addresses, but are pointing to the same object, must they
>compare equal?

 The answer to this particular question is YES, they must
compare equal according to the ARM. And I think this is a problem
for OS design for the 386, for example, where the memory management
kernel will just have to ignore the ARM.

 If we dropped this requirement, however, there would
be no easy way to identify objects.

--
;----------------------------------------------------------------------
        JOHN (MAX) SKALLER,         maxtal@extro.ucc.su.oz.au
 Maxtal Pty Ltd, 6 MacKay St ASHFIELD, NSW 2131, AUSTRALIA
;--------------- SCIENTIFIC AND ENGINEERING SOFTWARE ------------------

In article <5343@holden.lulea.trab.se> jbn@lulea.trab.se (Johan Bengtsson) writes:
>Markku Sakkinen (sakkinen@jyu.fi) wrote:
>: ...
>: -- as long as it is _in_ the database.  BTW, actually total order is
>: a simple thing within an OODB _because_ the identity of each object
>: is assured not to change.
>
>It would impose severe restrictions on how the virtual address space
>could be used though.  The OODBMS may end up in a situation where
>it can't get a persistent object into memory, not because it has used up
>all virtual memory addresses, but because all unused virtual memory
>adresses would violate the total ordering property.
>
>This unnecessary address space fragmentation phenomenon (kind of) would
>severely limit the capacity of OODBMSes.

You must have misunderstood the idea somehow in two ways.
First, no matter how an object identifier is represented, it can always
be interpreted as an integer or bit string for the purpose of
ordering:  "violating the total ordering property" is impossible.

Second, the _identity_ of a persistent object in the database does not
change when the object is brought (or copied) to main memory.
The ordering is not supposed to be connected with the other
semantics of the objects, nor with their location in physical or
virtual memory (except as already dictated by the existing language
rules for array elements and class members, in C++).

----------------------------------------------------------------------
Markku Sakkinen (sakkinen@jytko.jyu.fi)
       SAKKINEN@FINJYU.bitnet (alternative network address)
Department of Computer Science and Information Systems
University of Jyvaskyla (a's with umlauts)
PL 35
SF-40351 Jyvaskyla (umlauts again)
Finland
----------------------------------------------------------------------

maxtal@extro.ucc.su.OZ.AU (John MAX Skaller) writes:

> Similarly suppose we allowed nested functions, then
>pointers to them would need a pointer to a stack frame as well
>as the function address (or instead of?). They would be totally
>different types of objects really.

Actually, nested functions can be handled quite transparently.
Gnu C handles pointers to nested functions by creating a "trampoline"
function on the stack, and using the address of the trampoline
function. When the trampoline function is called, all it does is push
the pointer to the stack frame, and then jump to original nested
function. This way, the nested function does receive a hidden stack
frame parameter, but you can use pass the address of the nested
function to any function such as qsort() that just expects a normal
function pointer, since the address which will be automatically
converted to the address of a newly-created trampoline.

--
Fergus Henderson             fjh@munta.cs.mu.OZ.AU
This .signature virus is a self-referential statement that is true - but
you will only be able to consistently believe it if you copy it to your own
.signature file!

In article <1992Dec10.051649.10282@jyu.fi> sakkinen@jyu.fi (Markku Sakkinen) writes:
>In article <5343@holden.lulea.trab.se> jbn@lulea.trab.se (Johan Bengtsson) writes:
>>Markku Sakkinen (sakkinen@jyu.fi) wrote:
>
>Second, the _identity_ of a persistent object in the database does not
>change when the object is brought (or copied) to main memory.
>The ordering is not supposed to be connected with the other
>semantics of the objects, nor with their location in physical or
>virtual memory (except as already dictated by the existing language
>rules for array elements and class members, in C++).
>
So the total ordering has nothing to do with the address of anything.
(In particular, there may be several handles to the same object in
the same process at the same time).

I think it is highly unwise for databases to allow their object ids
to escape into programmers' hands.  To do so gives the databases the
same garbage collection type problems that C and C++ have, because there
can be references to objects from outside the database.  Thus the database
will have to provide a routine, say ptrcmp(Handle,Handle) to compare the
total ordering of two objects.  It could also provide ptrcmp(Handle,void *)
and ptrcmp(void *,Handle), arbitrarily deciding that all C++ objects are
less than all database objects, say.

This is much better than relying on comparison of pointers (in my opinion
today).  Database handles have to be compared differently depending on
whether it is the handle or the object that the handle points to that
is being compared.

...but the C++ language considerations never considered the requirements
of OODBMSs before.  Why start now?  :-)

Stuart
--
: Stuart MacMartin                                    email: sjm@bnr.ca      :
: Bell-Northern Research                              phone: (613) 763-5625  :
: PO Box 3511, Stn C, Ottawa, K1Y-4H7, CANADA    Standard disclaimers apply. :

In article <1992Dec8.103218.27689@lth.se> dag@seldon.control.lth.se
(Dag Bruck) writes:

|> In <comp.std.c++> jimad@microsoft.com (Jim Adcock) writes:
|> >
|> >If you want to compare addresses, the following works on all computers
|> >and compilers I've ever had to deal with:
|> >
|> >if (((long)ptr_a) > ((long)ptr_b))
|> > blah();

This won't work with the Intel 80386 C compiler, and I suppose it
won't work when they finally get a C++ compiler.

If you declare the pointers far with the Zortech C++, and compile in
extended mode, it also won't work.

In general, an 80386 pointer can be 48 bits, whereas all of the
compilers I know for the 80386 use 32 bit longs.

|> I would be perfectly happy with a simple work-around, like the one
|> above.  If the standard guarantees that given two pointers of the same
|> type "p" and "q",

|>  p != q  <=>  long(p) > long(q)  |  long(p) < long(q)

|> I assume this is not the case now, but if a trivial change in the
|> standard document would give us this guarantee, the problem is solved
|> and we need not discuss it anymore.

This is not the case now, see above.

|> If there are any problems, for example, if all significant bits of the
|> pointers will not fit into a long integer, I think we're back to
|> square one again and have to define "operator<" for pointers.  The
|> alternative is of course to dismiss the idea as not worth the trouble.

I favor the latter case.  I don't see any need for long's on a 80386
being bigger than 32 bits.  (If I need more, I'll use an extended
precision Integer package anyway, since my programs generally have to
work on several different machines, most of which *will* still have 32
bit longs.)
--
--
James Kanze                             email: kanze@us-es.sel.de
GABI Software, Sarl., 8 rue du Faisan, F-67000 Strasbourg, France
Conseils en informatique industrielle --
                   -- Beratung in industrieller Datenverarbeitung

Dag Bruck (dag@seldon.control.lth.se) wrote:
: In <comp.std.c++> fjh@munta.cs.mu.OZ.AU (Fergus James HENDERSON) writes:
: >
: >What I propose is that we define a *standard library function* which computes
: >a total ordering on pointers.
: >
: >int compare_pointers(const void *, const void *);
: >    /* Returns negative, zero, or positive in the same manner as strcmp().
: >       Perhaps in the interests of tradition and unreadability it should
: >       be called ptrcmp() instead of compare_pointers() :-) */

: Suggested semantics: for any pointers p and q:

:  p == q   <=>   ptrcmp(p,q) == 0

:  p != q   <=>   ptrcmp(p,q) != 0

:  ptrcmp(p,q) < 0   <=>   ptrcmp(q,p) > 0

I think ptrcmp() is a good way to resolve this issue.

There is only one possible remaining weakness (I think):

Any environment that relies on pointer translation (swizzling) to
transport objects between executing processes will have difficulty
maintaining a common total ordering for the pointers (IDs) of
objects within those processes (Jim Adcock pointed this out).
Examples include OODBMS and distributed systems.  Code relying
on ptrcmp() may be unportable to those environments.

Should those environments be required to (somehow) provide special
ptrcmp() functions, that look at some object ID (not memory address)?
What if a program uses more than one pointer swizzling scheme (e.g.
distributing some objects over communication channels, and storing other
objects in an OODBMS)?  Is it the users job to provide the ordering
between those different object spaces?

Anyone have a good solution for this?

--
--------------------------------------------------------------------------
| Johan Bengtsson, Telia Research AB, Aurorum 6, S-951 75 Lulea, Sweden  |
| Johan.Bengtsson@lulea.trab.se; Voice:(+46)92075471; Fax:(+46)92075490  |
--------------------------------------------------------------------------

In article <1992Dec10.121935.19315@ucc.su.OZ.AU>
maxtal@extro.ucc.su.OZ.AU (John MAX Skaller) writes:

|> In article <1992Dec8.173855.18153@meaddata.com> ralpht@meaddata.com (Ralph W. Trickey) writes:
|> >
|> >Attempting to require this for the general case becomes very
|> >complicated. How is the null pointer handled? Is it less than all
|> >other pointers, or is that implementation dependent, or what? How is
|> >shared memory handled, if I have 2 pointers that are pointing to
|> >different addresses, but are pointing to the same object, must they
|> >compare equal?

|>  The answer to this particular question is YES, they must
|> compare equal according to the ARM. And I think this is a problem
|> for OS design for the 386, for example, where the memory management
|> kernel will just have to ignore the ARM.

As it should.  The ARM (and the upcoming ANSI standard) can only
address what happens in the context of C++, not what happens to the
pointer once the OS gets its hands on it.

In a similar vein, for example, the ANSI C standard states that the
NULL pointer will not point to any object.  But all 8086 programmers
know that if you compile with 32 bit pointers, it actually points to
the interrupt vector table!  However, this is *not* an object defined
in any C program, so this is perfectly legal.  (If it wasn't, you
couldn't have C on machines without protected memory.)

In the same way, I would understand the ARM to be saying that all
pointers generated by a correct program to point to any object defined
(including a dynamic definition by new) in C++ will compare equal.  If
you give the pointer to the OS, and it gives it back to you, then any
guarantees must be made by the OS, and not the C++ language.

|>  If we dropped this requirement, however, there would
|> be no easy way to identify objects.

Once you leave the safe and easy world of your program, there is no
easy way to identify objects.  C++ doesn't address such problems as
persistance, transportability or shared memory.
--
--
James Kanze                             email: kanze@us-es.sel.de
GABI Software, Sarl., 8 rue du Faisan, F-67000 Strasbourg, France
Conseils en informatique industrielle --
                   -- Beratung in industrieller Datenverarbeitung

In article <9234423.15066@mulga.cs.mu.OZ.AU> fjh@munta.cs.mu.OZ.AU
(Fergus James HENDERSON) writes:

|> dag@seldon.control.lth.se (Dag Bruck) writes:

|> What I propose is that we define a *standard library function* which computes
|> a total ordering on pointers. This would work on virtually any system
|> without imposing undue constraints on the implementation. Programs written
|> for Intel architectures would not slow down, but the template collection class
|> writers get their total ordering. It should make everyone happy! :-)

|> int compare_pointers(const void *, const void *);
|>     /* Returns negative, zero, or positive in the same manner as strcmp().
|>        Perhaps in the interests of tradition and unreadability it should
|>        be called ptrcmp() instead of compare_pointers() :-) */

We already *have* this function.  Try the following:

 void* ptr1 ;
 void* ptr2 ;
 int cmp = memcmp( &ptr1 , &ptr2 , sizeof( void* ) ) ;

This works on all implementations I can think of.  Is it guaranteed?
(Ie: can pointers also hold undefined padding information which may
vary in a random fashion.  Note that "memcmp" is *not* guaranteed to
work on struct's.)
--
--
James Kanze                             email: kanze@us-es.sel.de
GABI Software, Sarl., 8 rue du Faisan, F-67000 Strasbourg, France
Conseils en informatique industrielle --
                   -- Beratung in industrieller Datenverarbeitung

>>>>> On Thu, 10 Dec 1992 12:12:00 GMT, maxtal@extro.ucc.su.OZ.AU (John MAX Skaller) said:

>  This seems like an excellent suggestion. It suffers only
> in those cases where we must ask whether it makes sense to
> compare two pointers at all. For example a char* and a function
> pointer. Might not these accidentally have the same address?

>  Similarly suppose we allowed nested functions, then
> pointers to them would need a pointer to a stack frame as well
> as the function address (or instead of?). They would be totally
> different types of objects really.

My understanding of the ANSI-C standard (prompted by some complaints
from lint) is that functions aren't objects, and that casting a
function pointer to void* is implementation dependent, so so is
comparing them with ptrcmp(void*, void*).

If imposing a total ordering over both objects and functions is
really desirable and possible, it could be a seperate function.
I think the function should become part of the standard C library,
and should have a name from ISO section 7.13 Future library directions.
"mem" seems the most appropriate prefix, but stdlib.h seems more
appropriate than strings.h, which means it should "begin with str
and a lowercase letter (followed by any combination...".

If possible, it should be implemented in such a way that it is no
slower than using "<" on pointers where that is a total ordering.
What's the current state of the library functions may be macros/
inline functions/inline functions with external linkage discussion?

--
     Alan Braggins, alanb@sdl.mdcbbs.com, abraggins@cix.compulink.co.uk
Shape Data - A division of EDS-Scicon Limited.   Cambridge, UK +44-223-316673
   "Any technology distinguishable from magic is insufficiently advanced."
 "My employer does not necessarily share my views - but I'm working on it."

In article <1992Dec10.121200.18889@ucc.su.OZ.AU>, maxtal@extro.ucc.su.OZ.AU (John MAX Skaller) writes:
|> >
|> >int compare_pointers(const void *, const void *);
|> >    /* Returns negative, zero, or positive in the same manner as strcmp().
|> >       Perhaps in the interests of tradition and unreadability it should
|> >       be called ptrcmp() instead of compare_pointers() :-) */
|> >
|>
|>  This seems like an excellent suggestion. It suffers only
|> in those cases where we must ask whether it makes sense to
|> compare two pointers at all. For example a char* and a function
|> pointer. Might not these accidentally have the same address?
|>
|>  Similarly suppose we allowed nested functions, then
|> pointers to them would need a pointer to a stack frame as well
|> as the function address (or instead of?). They would be totally
|> different types of objects really.

Function pointers and data pointers are differnt.  The conversions
between them are always undefined.  This would argue for a variant

  int compare_pointers(void(*)(), void(*)())

   // Jerry Schwarz

In article <KANZE.92Dec10174617@slsvdnt.us-es.sel.de>, kanze@us-es.sel.de (James Kanze) writes:
|>
|> |> int compare_pointers(const void *, const void *);
|> |>     /* Returns negative, zero, or positive in the same manner as strcmp().
|> |>        Perhaps in the interests of tradition and unreadability it should
|> |>        be called ptrcmp() instead of compare_pointers() :-) */
|>
|> We already *have* this function.  Try the following:
|>
|>  void* ptr1 ;
|>  void* ptr2 ;
|>  int cmp = memcmp( &ptr1 , &ptr2 , sizeof( void* ) ) ;
|>
|> This works on all implementations I can think of.  Is it guaranteed?
|> (Ie: can pointers also hold undefined padding information which may
|> vary in a random fashion.  Note that "memcmp" is *not* guaranteed to
|> work on struct's.)
|

It is not guaranteed. Padding is certainly allowed in a void*, and
would be common on word addressed machines. Also I vaguely remember
an implementation of C for a segmented architectures that didn't
normalize pointers unless it had to (for comparisons).

   -- Jerry Schwarz

Markku Sakkinen (sakkinen@jyu.fi) wrote:
: In article <5343@holden.lulea.trab.se> jbn@lulea.trab.se (Johan Bengtsson) writes:
: >Markku Sakkinen (sakkinen@jyu.fi) wrote:
: >: ...
: >: -- as long as it is _in_ the database.  BTW, actually total order is
: >: a simple thing within an OODB _because_ the identity of each object
: >: is assured not to change.
: >
: >It would impose severe restrictions on how the virtual address space
: >could be used though.  The OODBMS may end up in a situation where
: >it can't get a persistent object into memory, not because it has used up
: >all virtual memory addresses, but because all unused virtual memory
: >adresses would violate the total ordering property.
: >
: >This unnecessary address space fragmentation phenomenon (kind of) would
: >severely limit the capacity of OODBMSes.

: You must have misunderstood the idea somehow in two ways.
: First, no matter how an object identifier is represented, it can always
: be interpreted as an integer or bit string for the purpose of
: ordering:  "violating the total ordering property" is impossible.

No, it is you who misunderstand my understandings! (:-)

I agree; it is possible to achieve a total order for the object IDs
within a database.  I agree; it is possible to achieve a total order
for the object IDs (the pointers) within transient memory.

What is in general impractical (though sometimes possible) is to
maintain the same ordering over database object IDs and the corresponding
transient memory pointers that a programs sees when persistent objects are
mapped into memory.  Otherwise the pointer table in memory can't be
guaranteed to appear sorted according to ptrcmp().

Put differently: the database ID total order and the corresponding
transient pointer orders must be order-isomorphic (look it up, I did :-),
to ensure that the total pointer order for the addresses of
persistent objects mapped into transient memory is consistent between
different runs of the same program.

: Second, the _identity_ of a persistent object in the database does not
: change when the object is brought (or copied) to main memory.
: The ordering is not supposed to be connected with the other
: semantics of the objects, nor with their location in physical or
: virtual memory (except as already dictated by the existing language
: rules for array elements and class members, in C++).

You may be right.  OODBMS that uses ordinary memory pointers as object
handles should already have the ability to recognize void pointers that
refer to persistent objects, so they can provide a special
ptrcmp(void*,void*) function that checks the database IDs for
persistent objects.

Perhaps I should redraw my claim that this is difficult to do, and
instead say just that "there is some extra implementation cost for
OODBMS vendors".

--
--------------------------------------------------------------------------
| Johan Bengtsson, Telia Research AB, Aurorum 6, S-951 75 Lulea, Sweden  |
| Johan.Bengtsson@lulea.trab.se; Voice:(+46)92075471; Fax:(+46)92075490  |
--------------------------------------------------------------------------

I wrote some weeks ago:
> In article <1992Oct30.003946.10484@microsoft.com> jimad@microsoft.com (Jim Adcock) writes:
> >In article <1992Oct28.184135.25475@ucc.su.OZ.AU> maxtal@extro.ucc.su.OZ.AU (John MAX Skaller) writes:
> >| ...
> >|If a total ordering was required, programs utilising
> >|this requirement would be portable.
> >
> >Nope.  They would only become portable if this was the last non-portability
> >in that program -- hardly likely.
> >
> >On the converse side, tons of previously legal but not *strictly* portable
> >programs would now become illegal.
> >
> >Thus your trade-off would represent a major lose:  Lots of legal programs
> >become busted in exchange for making an unlikely few programs portable.
> > ...
>
> I would first like to return to a much more important, related problem,
> which somebody brought up here rather recently.
> Namely, there is nothing in the ARM explicitly saying that
> p == q  might not yield 1 even when p and q are pointing at two different
> objects.  This hole makes e.g. some standard idioms in Stroustrup's books
> implementation dependent.
> ...

Steve Clamage replied to this part in his usual, nice and informative manner.
Essentially, in ANSI C pointers at two different objects are required
to compare inequal, and the C++ committee may add the same rule.

> Suppose that the above problem is settled (alt. 1 or 2).
> Then, if there is no total order within pointers of the same type,
> essentially one or more of the following holds:
>
> A) '<' is not transitive, i.e. p < q and q < r does not imply p < q.
>
> B) '<' (or rather '<=') is not connective, i.e. there might be p and q
>    such that neither p = q, p < q nor q < p holds.
>
> C) All usual relationships between the different relational operators
>    need not hold (e.g. p < q does not imply q > p).
>
> I have difficulty to imagine any useful programming idioms that would
> depend on either A, B, or C (or on the exact way in which a particular
> implementation makes pointers not be totally ordered),
> but you speak about tons of legal programs that would become illegal.
> Could you give a small example?
> ...

Neither Jim Adcock nor anybody else has tried to back his claim.
Still no examples?

----------------------------------------------------------------------
Markku Sakkinen (sakkinen@jytko.jyu.fi)
       SAKKINEN@FINJYU.bitnet (alternative network address)
Department of Computer Science and Information Systems
University of Jyvaskyla (a's with umlauts)
PL 35
SF-40351 Jyvaskyla (umlauts again)
Finland
----------------------------------------------------------------------

In article <1992Nov27.091056.3895@jyu.fi> sakkinen@jyu.fi (Markku Sakkinen) writes:
>> Then, if there is no total order within pointers of the same type,
>> essentially one or more of the following holds:
>>
>> A) '<' is not transitive, i.e. p < q and q < r does not imply p < q.
>>
>> B) '<' (or rather '<=') is not connective, i.e. there might be p and q
>>    such that neither p = q, p < q nor q < p holds.
>>
>> C) All usual relationships between the different relational operators
>>    need not hold (e.g. p < q does not imply q > p).
>>
>> I have difficulty to imagine any useful programming idioms that would
>> depend on either A, B, or C (or on the exact way in which a particular
>> implementation makes pointers not be totally ordered),
>> but you speak about tons of legal programs that would become illegal.
>> Could you give a small example?
>> ...
>
>Neither Jim Adcock nor anybody else has tried to back his claim.
>Still no examples?
>

 On the 80x86 machines, with segmented architectures,
one might define == and != to comparte BOTH the offset and segment
(as required by the ARM and the extra rule you suggested ought to
have been in the ARM).

 However, the < operator might be implemented to compare
ONLY the offset part. This is legal because it is 'implementation
defined'. One could create TWO arrays in different segments,
and use < to compare relative positions of pointers into
these different arrays.

Such an implementation dependent routine would fail
if the definition of < were
changed, including if it were changed to require a total order.

This is not a very practical example, Jim can provide a better one
perhaps.
--
;----------------------------------------------------------------------
        JOHN (MAX) SKALLER,         maxtal@extro.ucc.su.oz.au
 Maxtal Pty Ltd, 6 MacKay St ASHFIELD, NSW 2131, AUSTRALIA
;--------------- SCIENTIFIC AND ENGINEERING SOFTWARE ------------------

In article <1992Nov30.195202.14370@ucc.su.OZ.AU> maxtal@extro.ucc.su.OZ.AU (John MAX Skaller) writes:
>In article <1992Nov27.091056.3895@jyu.fi> sakkinen@jyu.fi (Markku Sakkinen) writes:
>>> ...
>>> I have difficulty to imagine any useful programming idioms that would
>>> depend on either A, B, or C (or on the exact way in which a particular
>>> implementation makes pointers not be totally ordered),
>>> but you speak about tons of legal programs that would become illegal.
>>> Could you give a small example?
>>> ...
> On the 80x86 machines, with segmented architectures,
>one might define == and != to comparte BOTH the offset and segment
>(as required by the ARM and the extra rule you suggested ought to
>have been in the ARM).
>
> However, the < operator might be implemented to compare
>ONLY the offset part. This is legal because it is 'implementation
>defined'. One could create TWO arrays in different segments,
>and use < to compare relative positions of pointers into
>these different arrays.
>
>Such an implementation dependent routine would fail
>if the definition of < were
>changed, including if it were changed to require a total order.
>
>This is not a very practical example, Jim can provide a better one
>perhaps.

Is this what you mean?
 if (p == q) ... // the same object (assuming the mentioned correction
   // to the rules)
 else if (p < q) ... // in the same segment
 else if (p > q) ... // in the same segment
 else ... // the objects must be in different segments!
If some compilers really work like this (i.e. neither p==q, p<q, nor p>q holds when
p and q point to different segments, it is indeed possible to write code that would
behave differently if total order for pointers were required.

I still cannot believe Jim Adcock's claim that this would affect "tons of useful
software".  In what circumstances would one normally be interested about the segments
in which the objects lie?  The above idiom does not help to test whether the pointers
point into different _arrays_, since there can be more than one array in each segment.

----------------------------------------------------------------------
Markku Sakkinen (sakkinen@jytko.jyu.fi)
       SAKKINEN@FINJYU.bitnet (alternative network address)
Department of Computer Science and Information Systems
University of Jyvaskyla (a's with umlauts)
PL 35
SF-40351 Jyvaskyla (umlauts again)
Finland
----------------------------------------------------------------------

216z
In article <1992Dec1.072440.824@jyu.fi>, sakkinen@jyu.fi (Markku Sakkinen) writes:
|> In article <1992Nov30.195202.14370@ucc.su.OZ.AU> maxtal@extro.ucc.su.OZ.AU (John MAX Skaller) writes:
|> >In article <1992Nov27.091056.3895@jyu.fi> sakkinen@jyu.fi (Markku Sakkinen) writes:
|> >>> ...
|> >>> I have difficulty to imagine any useful programming idioms that would
|> >>> depend on either A, B, or C (or on the exact way in which a particular
|> >>> implementation makes pointers not be totally ordered),
|> >>> but you speak about tons of legal programs that would become illegal.
|> >>> Could you give a small example?
|> >>> ...
|> > On the 80x86 machines, with segmented architectures,
|> >one might define == and != to comparte BOTH the offset and segment
|> >(as required by the ARM and the extra rule you suggested ought to
|> >have been in the ARM).
|> >
|> > However, the < operator might be implemented to compare
|> >ONLY the offset part. This is legal because it is 'implementation
|> >defined'. One could create TWO arrays in different segments,
|> >and use < to compare relative positions of pointers into
|> >these different arrays.
|> >
|> >Such an implementation dependent routine would fail
|> >if the definition of < were
|> >changed, including if it were changed to require a total order.
|> >
|> >This is not a very practical example, Jim can provide a better one
|> >perhaps.
|>
|> Is this what you mean?
|>  if (p == q) ... // the same object (assuming the mentioned correction
|>    // to the rules)
|>  else if (p < q) ... // in the same segment
|>  else if (p > q) ... // in the same segment
|>  else ... // the objects must be in different segments!
|> If some compilers really work like this (i.e. neither p==q, p<q, nor p>q holds when
|> p and q point to different segments, it is indeed possible to write code that would
|> behave differently if total order for pointers were required.
|>
|> I still cannot believe Jim Adcock's claim that this would affect "tons of useful
|> software".  In what circumstances would one normally be interested about the segments
|> in which the objects lie?  The above idiom does not help to test whether the pointers
|> point into different _arrays_, since there can be more than one array in each segment.
|>

  The Intel 8086 series of chips (used in PC's) has a segmented
architecture, this consists of a 16 bit segment and a 16 bit offset.
The physical address is computed by segment << 4 + offset. Addresses
for this chip are often done using only the offset portion. This
allows access to 64K of memory, but is faster than using all 32 bits.

  I don't think that requiring total ordering would break any existing
program, but it would break quite a few existing compilers. Many DOS
compilers test for == and != using the full 32 bits to compare. This
is required since the objects might be in different segments. However,
the < and > relationships only compare the offsets, since < and > are
not defined unless the objects were declared in an array. This means
that it is possible for an object to be neither < == or > another
object if the offsets are equal, but the segments are unequal. It also
means that it is possible for an object to be <= another object, but
not < or ==. When comparing objects within an array, all standard
relationships hold. There are also methods of forcing the compiler to
examine all 32 bits of the address for < and >.

  By requiring total ordering, you would force all < and > operations
to compare both segment and offset. I commonly use a condition
like this to test for termination of a loop, it would greatly slow
down the execution of most programs written for a segmented
architecture for little benefit that I can see.

--
Ralph Trickey       | (513) 865-6800                  |
Mead Data Central   | x4870                           |  Disclaimer
P.O. Box 933        | ralpht@meaddata.com             |  My opinions are my own
Dayton, Ohio  45401 | ...!uunet!meaddata!ralpht       |

In article <1992Dec1.072440.824@jyu.fi> sakkinen@jyu.fi (Markku Sakkinen) writes:
>In article <1992Nov30.195202.14370@ucc.su.OZ.AU> maxtal@extro.ucc.su.OZ.AU (John MAX Skaller) writes:
>> On the 80x86 machines, with segmented architectures,
>>one might define == and != to comparte BOTH the offset and segment
>>(as required by the ARM and the extra rule you suggested ought to
>>have been in the ARM).
>>
>> However, the < operator might be implemented to compare
>>ONLY the offset part. This is legal because it is 'implementation
>>defined'. One could create TWO arrays in different segments,
>>and use < to compare relative positions of pointers into
>>these different arrays.
>>
>>This is not a very practical example, Jim can provide a better one
>>perhaps.
>
>Is this what you mean?
> if (p == q) ... // the same object (assuming the mentioned correction
>   // to the rules)
> else if (p < q) ... // in the same segment
> else if (p > q) ... // in the same segment
> else ... // the objects must be in different segments!
>If some compilers really work like this (i.e. neither p==q, p<q, nor p>q holds when
>p and q point to different segments, it is indeed possible to write code that would
>behave differently if total order for pointers were required.

 Here's areally contorted example.

 // p & q point to the last byte in an array, the arrays
 // are whole segments

 if(p==q) { // same array }
 else if(p<q) { // p is shorter than q !! }
 else if(p>q) { // p is longer than q !! }
 else { p is the same length as q } // neither p==q, p<q or p>q

The code is stupid and implementation dependent, but it is legal.
If the standard required a total order, the compiler vendor would
have to change the implementation of pointer comparisons to take
the segment into account, as it is the code relies on the implementation
only using the offset part.

--
;----------------------------------------------------------------------
        JOHN (MAX) SKALLER,         maxtal@extro.ucc.su.oz.au
 Maxtal Pty Ltd, 6 MacKay St ASHFIELD, NSW 2131, AUSTRALIA
;--------------- SCIENTIFIC AND ENGINEERING SOFTWARE ------------------

In article <1992Dec1.175548.16232@meaddata.com> ralpht@meaddata.com (Ralph W. Trickey) writes:
> ...
>  The Intel 8086 series of chips (used in PC's) has a segmented
>architecture, this consists of a 16 bit segment and a 16 bit offset.
>The physical address is computed by segment << 4 + offset. Addresses
>for this chip are often done using only the offset portion. This
>allows access to 64K of memory, but is faster than using all 32 bits.
>
>  I don't think that requiring total ordering would break any existing
>program, but it would break quite a few existing compilers. Many DOS
> ...

Somehow I suspected that even Jim Adcock might actually have had compilers and implementations
in mind, although he wrote about C++ programs.  Of course, any strengthening of language
requirements will affect compilers!
Thus no evidence yet for Adcock's original claim.

>  By requiring total ordering, you would force all < and > operations
>to compare both segment and offset. I commonly use a condition
>like this to test for termination of a loop, it would greatly slow
>down the execution of most programs written for a segmented
>architecture for little benefit that I can see.

On the other hands, such little irregularities in the semantics of the language
in order to allow for the quirks of some rudimentary processors and operating systems,
increase its difficulty.  Who uses 8086s any more?

----------------------------------------------------------------------
Markku Sakkinen (sakkinen@jytko.jyu.fi)
       SAKKINEN@FINJYU.bitnet (alternative network address)
Department of Computer Science and Information Systems
University of Jyvaskyla (a's with umlauts)
PL 35
SF-40351 Jyvaskyla (umlauts again)
Finland
----------------------------------------------------------------------

In article <1992Dec2.111003.23102@jyu.fi>, sakkinen@jyu.fi (Markku Sakkinen) writes:
|> In article <1992Dec1.175548.16232@meaddata.com> ralpht@meaddata.com (Ralph W. Trickey) writes:
|> > ...
|> >  The Intel 8086 series of chips (used in PC's) has a segmented
|> >architecture, this consists of a 16 bit segment and a 16 bit offset.
|> >The physical address is computed by segment << 4 + offset. Addresses
|> >for this chip are often done using only the offset portion. This
|> >allows access to 64K of memory, but is faster than using all 32 bits.
|> >
|> >  I don't think that requiring total ordering would break any existing
|> >program, but it would break quite a few existing compilers. Many DOS
|> > ...
|>
|> Somehow I suspected that even Jim Adcock might actually have had compilers and implementations
|> in mind, although he wrote about C++ programs.  Of course, any strengthening of language
|> requirements will affect compilers!
|> Thus no evidence yet for Adcock's original claim.

This language change that would slow down existing programs. Possibly
to the point where they no longer meet specifications. I consider this
breaking programs.

|>
|> >  By requiring total ordering, you would force all < and > operations
|> >to compare both segment and offset. I commonly use a condition
|> >like this to test for termination of a loop, it would greatly slow
|> >down the execution of most programs written for a segmented
|> >architecture for little benefit that I can see.
|>
|> On the other hands, such little irregularities in the semantics of the language
|> in order to allow for the quirks of some rudimentary processors and operating systems,
|> increase its difficulty.  Who uses 8086s any more?

Not just 8086's, any 80186, 286, 386, 486, ..., I limited it to the 8086
so that we wouldn't get sidetracked by other issues (selectors, etc.)
This would effect all programs written for DOS and Windows. I am sure
there are other chips in production that use a segmented architecture.
This is NOT a small portion of the programming market.

Anyway, I think that fully distributed operating systems are finally
on the way here and forcing a C++ program to abide by the rules for total
ordering would probably seriously cripple the compilers ability to partition
tasks.

BTW, how did this thread start? The beginning has scrolled out of my
newsreader. I don't understand what total ordering would achieve.

--
Ralph Trickey       | (513) 865-6800                  |
Mead Data Central   | x4870                           |  Disclaimer
P.O. Box 933        | ralpht@meaddata.com             |  My opinions are my own
Dayton, Ohio  45401 | ...!uunet!meaddata!ralpht       |

In article <1992Dec1.072440.824@jyu.fi> sakkinen@jyu.fi (Markku Sakkinen) writes:
|In article <1992Nov30.195202.14370@ucc.su.OZ.AU> maxtal@extro.ucc.su.OZ.AU (John MAX Skaller) writes:
|> On the 80x86 machines, with segmented architectures,
|>one might define == and != to comparte BOTH the offset and segment
|>(as required by the ARM and the extra rule you suggested ought to
|>have been in the ARM).

This is in fact common implementation.

|> However, the < operator might be implemented to compare
|>ONLY the offset part. This is legal because it is 'implementation
|>defined'. One could create TWO arrays in different segments,
|>and use < to compare relative positions of pointers into
|>these different arrays.

Exactly.

|>This is not a very practical example, Jim can provide a better one
|>perhaps.

Such use is not uncommon practice, and as such is a very practical example.
Again, we are not talking about breaking future programming efforts, we
are talking about NOT breaking existant programming efforts.  The argument
that "there are better ways to program these things" matters not a whit.
All that matters is that these things ARE legal and programmers DID make
use of them.  You cannot gratuitously make changes to the base language
now without darned good justification -- which YOU have not established.

|I still cannot believe Jim Adcock's claim that this would affect "tons of useful
|software".  In what circumstances would one normally be interested about the segments
|in which the objects lie?  The above idiom does not help to test whether the pointers
|point into different _arrays_, since there can be more than one array in each segment.

You still seem to be confusing the issue of conforming programs verses
strictly conforming programs.  A conforming PC program can use large
model pointers into different segments, and then make use of that fact
that pointer < > comparisons are only performed on the offset parts
in order to use those pointers as if they are offsets.  Such usages are
common because only recently have PC compilers given explicit support
for segment and offset variables.  Prior to these language extensions,
such comparisons HAD to be done by hack because their was no language
support for them.  Now you proprse to require C++ implementaions break
these existant conforming C programs.

Further, you still have not touched on the issue of C++ OODBMS and the
fact that you guys proposal of total ordering would require OODBMSs to
maintain a total ordering on objects on the database even through
a store/query/restore to memory.  Seems an unnecessary and painful restriction
on OODBMSs that a query/restore to memory cannot order the objects in
back into memory in the order the query found those objects.  Surely
you jest!?  Maintain a total ordering over a OODBMS!!??

Again, seems clear to me that using a total ordering is simply a
un*x-memory model hack, and should be treated as such.  If *you* want
to use such a hack, then use it.  Don't require everyone else in the
world to support your hack.  PCs, OODBMSs, Lisp-machine, etc, are all examples
that don't follow the un*x memory model, are still very interesting for
C++ work [with 100,000s of C++ compilers sold], and which shouldn't be
gratuitously excluded from the C++ world.  Further, you are ignoring the
emerging crop of RISC machines which are themselves segmented architectures,
of the form 16:32 and/or 32:32.

What you propose simply doesn't scale.

ralpht@meaddata.com (Ralph W. Trickey) writes:
: In article <1992Dec2.111003.23102@jyu.fi>, sakkinen@jyu.fi (Markku Sakkinen) writes:
: |> In article <1992Dec1.175548.16232@meaddata.com> ralpht@meaddata.com (Ralph W. Trickey) writes:
: |> > ...
: |> >  The Intel 8086 series of chips (used in PC's) has a segmented
: |> >architecture, this consists of a 16 bit segment and a 16 bit offset.
: |> >The physical address is computed by segment << 4 + offset. Addresses
: |> >for this chip are often done using only the offset portion. This
: |> >allows access to 64K of memory, but is faster than using all 32 bits.
: |> >
: |> >  I don't think that requiring total ordering would break any existing
: |> >program, but it would break quite a few existing compilers. Many DOS
: |> > ...
:
: This language change that would slow down existing programs. Possibly
: to the point where they no longer meet specifications. I consider this
: breaking programs.

Not being pro total ordering, allow me to point out that compilers
for segmented architectures of course would keep compatibility switches
to disable the total oredring property, gaining some speed.  Also,
customers of those programs will tend to buy faster computers over time,
so the specifications can still be met, only with more modern hardware.
I see no real problem here.

_If_ total ordering of pointers makes common programmin tasks easier,
the the very small speed penalty we are talking about would be quite
insignificant.

What tasks are made easier?

Off hand, I can only think of binary searches in sorted pointer tables.
Are there other (portable) examples?

--
--------------------------------------------------------------------------
| Johan Bengtsson, Telia Research AB, Aurorum 6, S-951 75 Lulea, Sweden  |
| Johan.Bengtsson@lulea.trab.se; Voice:(+46)92075471; Fax:(+46)92075490  |
--------------------------------------------------------------------------

In article <1992Dec2.111003.23102@jyu.fi> sakkinen@jyu.fi (Markku Sakkinen) writes:
>
>On the other hands, such little irregularities in the semantics of the language
>in order to allow for the quirks of some rudimentary processors and operating systems,
>increase its difficulty.  Who uses 8086s any more?

 More people use machines running 8086 real mode code
than any other processor, I'd reckon. Where have you been?
Why are you still using such an out of date flakey operating
system as Unix?

Same reason as people with 386 still run DOS---compatibility,
availability of software, familiarity ..... all the same reasons
people use C++ instead of a newer designed from scratch language.



--
;----------------------------------------------------------------------
        JOHN (MAX) SKALLER,         maxtal@extro.ucc.su.oz.au
 Maxtal Pty Ltd, 6 MacKay St ASHFIELD, NSW 2131, AUSTRALIA
;--------------- SCIENTIFIC AND ENGINEERING SOFTWARE ------------------

In article <1992Dec2.111003.23102@jyu.fi> sakkinen@jyu.fi (Markku Sakkinen) writes:
|On the other hands, such little irregularities in the semantics of the language
|in order to allow for the quirks of some rudimentary processors and operating systems,
|increase its difficulty.  Who uses 8086s any more?

If I remember right, last time I researched this  there was something
like 50,000,000 - 100,000,000 PCs worldwide, most of which are used in
8086 mode most of the time.  Further, there are several hundred thousand
C++ compilers sold for the PC.

The ignorance of this audience is showing.

In article <1992Dec1.175548.16232@meaddata.com> ralpht@meaddata.com (Ralph W. Trickey) writes:
|  The Intel 8086 series of chips (used in PC's) has a segmented
|architecture, this consists of a 16 bit segment and a 16 bit offset.
|The physical address is computed by segment << 4 + offset. Addresses
|for this chip are often done using only the offset portion. This
|allows access to 64K of memory, but is faster than using all 32 bits.

This statement is simply incorrect for any of the recent 80x86 chips
and for any of the recent OS's designed to use these chips.  Get and
read an 80486 manual for instance, which describes the various virtual memory
models available.

|  I don't think that requiring total ordering would break any existing
|program, but it would break quite a few existing compilers.

You think wrong.  To quote from the ANSI-C rationale, existing implementations
don't matter -- existing CODE does.  MUCH existing code depends on partial
ordering.  And NOT just on PCs.

|  By requiring total ordering, you would force all < and > operations
|to compare both segment and offset. I commonly use a condition
|like this to test for termination of a loop, it would greatly slow
|down the execution of most programs written for a segmented
|architecture for little benefit that I can see.

Agreed.  For those people who happen to currently program on architectures
and OS's that present a particularly simple [and unscalable] linear
memory model, who want to restrict their coding efforts to that particular
memory model, then go ahead.  But don't try to force the rest of the world into
your restrictions.

In <comp.std.c++> ralpht@meaddata.com (Ralph W. Trickey) writes:
>|> >
>|> >  I don't think that requiring total ordering would break any existing
>|> >program, but it would break quite a few existing compilers.
>
>This language change that would slow down existing programs. Possibly
>to the point where they no longer meet specifications. I consider this
>breaking programs.

Could someone do the net a great favour and check it?  There's a lot
of speculation but nobody has measured how severe the slow-down would be.

>BTW, how did this thread start? The beginning has scrolled out of my
>newsreader. I don't understand what total ordering would achieve.

A total ordering would make it easier to build some common data
structures.  For example, a binary search tree needs some sort of
comparison function.  If you are only interested in finding a
particular object in the tree (i.e., the actual ordering is
irrelevant), comparing the addresses would work nicely.

What you need in the search tree example is a total ordering for the
duration of the program execution; it does not matter if the ordering
is different the next time the program is executed.

Note that some types of objects do not have a comparison function, and
any existing comparison function may be expensive.

I think the absense of a total ordering is a much greater problem in
C++ than in C, because general purpose data structures are becoming
much more common in the shape of templates.

    -- Dag
--
Department of Automatic Control  E-mail: dag@control.lth.se
Lund Institute of Technology
P. O. Box 118    Phone: +46 46-104287
S-221 00 Lund, SWEDEN   Fax:    +46 46-138118

>>>>> On Fri, 4 Dec 1992 07:07:20 GMT, dag@control.lth.se (Dag Bruck) said:

> A total ordering would make it easier to build some common data
> structures.  For example, a binary search tree needs some sort of
> comparison function.  If you are only interested in finding a
> particular object in the tree (i.e., the actual ordering is
> irrelevant), comparing the addresses would work nicely.

> What you need in the search tree example is a total ordering for the
> duration of the program execution; it does not matter if the ordering
> is different the next time the program is executed.

> Note that some types of objects do not have a comparison function, and
> any existing comparison function may be expensive.

> I think the absense of a total ordering is a much greater problem in
> C++ than in C, because general purpose data structures are becoming
> much more common in the shape of templates.

>     -- Dag

Comparable::operator<(Comparable &arg)
{
#ifdef POINTER_TOTAL_ORDER
    return ((void*)this < (void*)(&arg));
#else
    return pointer_comparison((void*)this, (void*)(&arg));
    // Written in assembly if necessary - if there isn't *some*
    // way of getting a total ordering on this machine, that is
    // a pretty good reason for not requiring one...
#endif
}
--
     Alan Braggins, alanb@sdl.mdcbbs.com, abraggins@cix.compulink.co.uk
Shape Data - A division of EDS-Scicon Limited.   Cambridge, UK +44-223-316673
   "Any technology distinguishable from magic is insufficiently advanced."
 "My employer does not necessarily share my views - but I'm working on it."

In article <1992Dec02.212336.26703@microsoft.com> jimad@microsoft.com (Jim Adcock) writes:
>In article <1992Dec1.072440.824@jyu.fi> sakkinen@jyu.fi (Markku Sakkinen) writes:
>|In article <1992Nov30.195202.14370@ucc.su.OZ.AU> maxtal@extro.ucc.su.OZ.AU (John MAX Skaller) writes:
>|> ...
>Such use is not uncommon practice, and as such is a very practical example.
> ...
>use of them.  You cannot gratuitously make changes to the base language
>now without darned good justification -- which YOU have not established.

I think the example showed extremely bad hacking style, depending critically
on the behaviour of one specific compiler, while the same thing could be achieved
in a fully standard and portable way with minimal if any performance penalty.
I don't think that the C++ community as a whole has an obligation to assure
the continued legality of such bags of dirty tricks.
-- In the last few years there _have_ been gratuitous changes in the language
that have made fully standard code illegal (or perhaps worse still, legal but
with changed behaviour).  An example is the change of the meaning of 'protected'.

>| ...
>You still seem to be confusing the issue of conforming programs verses
>strictly conforming programs.  A conforming PC program can use large
> ...
>for segment and offset variables.  Prior to these language extensions,
>such comparisons HAD to be done by hack because their was no language
>support for them.  Now you proprse to require C++ implementaions break
>these existant conforming C programs.
                          ^^^^

Please don't mix up C into this, C++ _is_ a separate language.
(I don't know about the drafts of the ANSI committee, but at least the ARM does not
use any terminology like 'conforming' and 'strictly conforming'.)
So you say that most C++ compilers for the PC used to be more or less broken
(could not implement the full language), and programmers were therefore forced
to dirty tricks as work-arounds?  Could you finally give a short concrete code example?

>Further, you still have not touched on the issue of C++ OODBMS and the
>fact that you guys proposal of total ordering would require OODBMSs to
>maintain a total ordering on objects on the database even through
>a store/query/restore to memory.  Seems an unnecessary and painful restriction
>on OODBMSs that a query/restore to memory cannot order the objects in
>back into memory in the order the query found those objects.  Surely
>you jest!?  Maintain a total ordering over a OODBMS!!??

Please calm down (your throat will get sore if you use so many exclamation signs)
and try not to confuse things.  C++ as a language does not directly support
an OODBMS.  C++ pointers are memory pointers, and object references within an OODBMS
are a different thing (you will need a stronger and cleaner concept of object
identity there anyway).  I'll try to explain:

As long as we have C++ objects, i.e. in memory, their addresses (or at least the
valid pointer values to access them) _must_ stay constant, because C++ has no
means to automatically track down and modify all pointers to an object.
If the contents of some object are copied to or from the DB, that does not
change or complicate the situation.  On the other hand, if some C++ object is deleted
after having been copied to the DB, and the DB object is later restored into memory,
it will be a _new_ C++ object.  Nobody in this thread has required that its address
should have any defined relationship to the address of the deleted object.

>Again, seems clear to me that using a total ordering is simply a
>un*x-memory model hack, and should be treated as such.  If *you* want
> ...

Sorry, but IMO it's you who have been furiously defending hacks, not I.
Perhaps there is this misunderstanding:  you think that the requirement
of total ordering for pointers implies a linear address model.
No, we don't require that the ordering should directly map into physical order,
it's just as fine if a pointer consists of base and segment and relocation and index
or whatever.  Punning would do, i.e. treating the pointer as if it were an integer value.
However, the ARM does not require implementations to provide an integral type
that is sufficient to store an arbitrary pointer.

One obvious case where a total order of pointers would be nice to depend on
are (large) collections of pointers -- I think Andrew Koenig mentioned this
many submissions ago.  With total order, you can organise such collections
e.g. so that binary search can be used, requiring O(log N) time;
otherwise you are stuck with linear search and O(N) time.

----------------------------------------------------------------------
Markku Sakkinen (sakkinen@jytko.jyu.fi)
       SAKKINEN@FINJYU.bitnet (alternative network address)
Department of Computer Science and Information Systems
University of Jyvaskyla (a's with umlauts)
PL 35
SF-40351 Jyvaskyla (umlauts again)
Finland
----------------------------------------------------------------------

In article <5305@holden.lulea.trab.se> jbn@lulea.trab.se (Johan Bengtsson) writes:
|Not being pro total ordering, allow me to point out that compilers
|for segmented architectures of course would keep compatibility switches
|to disable the total oredring property, gaining some speed.  Also,
|customers of those programs will tend to buy faster computers over time,
|so the specifications can still be met, only with more modern hardware.
|I see no real problem here.

Actually it would be such a big lose on PC architectures that I would
suspect that compilers for such would ship with total ordering off
by default, and with total ordering only enabled in strict compatibility mode.

Thus in practice forcing PCs to implement it wouldn't help you because
you couldn't or wouldn't in practice use it anyway.

In article <5305@holden.lulea.trab.se> jbn@lulea.trab.se (Johan Bengtsson) writes:
>_If_ total ordering of pointers makes common programmin tasks easier,
>the the very small speed penalty we are talking about would be quite
>insignificant.

 On 8086 class machines the speed penalty could be huge.
Instead of a single instruction comparing a register to memory,
the problem of where to put the segment part arises. There is
only one spare segment register (ES) in most memory models,
and if one of the pointers lives in an extra segment referenced
by ES then it cannot be used. Thus an a additional instruction
is required to load the segment part into a register, whose
previous contents wil have to be pushed, the comparison done
in two halves with several branches floating about,
then the register value popped back again.

 Furthermore, the segment:register pairs on the 8086 will have
to be normalised ... both of them. Of course the unnormalised
parts will have to be preserved in case there is a requirement
for this ... I think we have at least one decimal order of magnitude
slower here.

 CMP AX,PTR ; no total order

as opposed to

 ; no  no no I'm not going to do this
 ; it would take hours to figure out how to do it!

>
>What tasks are made easier?
>
>Off hand, I can only think of binary searches in sorted pointer tables.
>Are there other (portable) examples?
>

 This is whole class of examples, including all ordered
aggregates of pointers---lists, trees, etc etc.

 Another example might be where memory is allocated
on a stack, pointer comparisons could be useful unwinding the stack,
checking for dangling references in GC, implementing a
mark and release scheme, etc.

(Of course, NOT having a total order might also be important in such
schemes if they were machine specific).

--
;----------------------------------------------------------------------
        JOHN (MAX) SKALLER,         maxtal@extro.ucc.su.oz.au
 Maxtal Pty Ltd, 6 MacKay St ASHFIELD, NSW 2131, AUSTRALIA
;--------------- SCIENTIFIC AND ENGINEERING SOFTWARE ------------------

jimad@microsoft.com (Jim Adcock) writes:
: In article <5305@holden.lulea.trab.se> jbn@lulea.trab.se (Johan Bengtsson) writes:
: |Not being pro total ordering, allow me to point out that compilers
: |for segmented architectures of course would keep compatibility switches
: |to disable the total ordering property, gaining some speed.  Also,
: |customers of those programs will tend to buy faster computers over time,
: |so the specifications can still be met, only with more modern hardware.
: |I see no real problem here.
:
: Actually it would be such a big lose on PC architectures that I would
: suspect that compilers for such would ship with total ordering off
: by default, and with total ordering only enabled in strict compatibility
: mode.

That would make new customers who have read about the standard kind of
unhappy when their programs mysteriously crash.  Anyway, I made a simple
test, running a pointer through char arrays of size 1000 a large number
of times, using

ptr1 < ptr2
and
(long)ptr1 < (long)ptr2

which happens to be the way to get a total ordering with Microsoft C 6.00,
with 286 code generation.  Total ordering made the program take about 33%
longer.  I would suspect that a compiler that generates 386 code would
have zero overhead for total ordering (anyone confirm?).

This is what I did (I don't have the complete program handy):

char* ptr, start, stop;
//...
ptr = start;
stop = start + 1000;
while ( ptr < stop ) {  // or (long)ptr < (long)stop
   ++ptr;
}

I would excpect such tight loops to be rare in programs, and
a #pragma(no_total_order), or a compiler switch  could be provided
to get speed in those hot spots.

However, I agree that the benefit of total ordering is not great enough
to impose even this small performance penalty, since there is a simple
technique that can be used for code that needs total pointer order:

inline int ptr_less( void* p1, void* p2 ) {
   return ( sizeof(long)==sizeof(p1) ?
            ((long)p1 < (long)p2) :
            (p1 < p2)
          );
}

This definitions works for the C/C++ implementations that I
have experience with (PC and UNIX).  I'm sure there are or will
be implementations for which the above function does not work,
but that can be handled by machine/compiler specific code.

Anyone know of machines/compilers for which the above function does not work?

--
--------------------------------------------------------------------------
| Johan Bengtsson, Telia Research AB, Aurorum 6, S-951 75 Lulea, Sweden  |
| Johan.Bengtsson@lulea.trab.se; Voice:(+46)92075471; Fax:(+46)92075490  |
--------------------------------------------------------------------------

>>>>> On 03 Dec 92 20:09:34 GMT, jimad@microsoft.com (Jim Adcock) said:

> |  I don't think that requiring total ordering would break any existing
> |program, but it would break quite a few existing compilers.

> You think wrong.  To quote from the ANSI-C rationale, existing implementations
> don't matter -- existing CODE does.  MUCH existing code depends on partial
> ordering.  And NOT just on PCs.

Then why have no examples been shown?
--
     Alan Braggins, alanb@sdl.mdcbbs.com, abraggins@cix.compulink.co.uk
Shape Data - A division of EDS-Scicon Limited.   Cambridge, UK +44-223-316673
   "Any technology distinguishable from magic is insufficiently advanced."
 "My employer does not necessarily share my views - but I'm working on it."

In article <1992Dec4.070720.13056@lth.se> dag@control.lth.se (Dag Bruck) writes:
|In <comp.std.c++> ralpht@meaddata.com (Ralph W. Trickey) writes:
|>|> >
|>|> >  I don't think that requiring total ordering would break any existing
|>|> >program, but it would break quite a few existing compilers.
|>
|>This language change that would slow down existing programs. Possibly
|>to the point where they no longer meet specifications. I consider this
|>breaking programs.
|
|Could someone do the net a great favour and check it?  There's a lot
|of speculation but nobody has measured how severe the slow-down would be.

People who are experienced with PCs don't have to measure this problem
because they are well aware of the issues and the code sizes involved.
What you ask for is essentially the same thing as "Huge" model which
PC compilers support but *which PC programmers don't use* -- because its too
expensive.  Note however, that if you insisted on using total ordering
*you* could compile *your* program under Huge model and then *you* would be
paying the penalty.  Rather than insisting all PC programmers pay the
penalty always.

But, since *you* request the numbers, here's a simple example:

Compaq Deskpro 386/20
C7 compiler all optimizations.

Comparing an pointer inner loop, incrementing one pointer and comparing
with another pointer within a loop.

The "total ordering" approach loop executes approx 3X slower than the typical PC
segment:offset approach.  The "total ordering" approach loop takes 28 bytes more
code for the pointer comparison than the typical PC segment:offset
[large model] approach.

======

Again, PC compilers already support what you ask for.  Its just that programmers
can't afford to use it.  Or perhaps more accurately stated its plenty expensive
enough that PC programmers only want to pay for it when they're *really*
using it!

|A total ordering would make it easier to build some common data
|structures.  For example, a binary search tree needs some sort of
|comparison function.  If you are only interested in finding a
|particular object in the tree (i.e., the actual ordering is
|irrelevant), comparing the addresses would work nicely.

If you want to compare addresses, then compare addresses.  If you
want to compare pointers, then compare pointers.  A pointer is not
an address.  An address is one particular implementation of a pointer.
If you want to compare addresses, the following works on all computers
and compilers I've ever had to deal with:

if (((long)ptr_a) > ((long)ptr_b))
 blah();

|I think the absense of a total ordering is a much greater problem in
|C++ than in C, because general purpose data structures are becoming
|much more common in the shape of templates.

The problem is no worse than in C because in practice in both languages a
programmer can make a total ordering if and where the programmer nee
ds it.  Further, the problem is *less* in C++ because classes and
overloaded operators allow class implementors to encapsulate their
implementation of total ordering if and where needed.  If the programmer
can do it, then there is no need for the language definition to require it.
On the contrary, the language definition should stick to things fundamental,
and should leave the implementation to the compiler and operating system
implementers.

In article <1992Oct30.003946.10484@microsoft.com> jimad@microsoft.com (Jim Adcock) writes:
>In article <1992Oct28.184135.25475@ucc.su.OZ.AU> maxtal@extro.ucc.su.OZ.AU (John MAX Skaller) writes:
>
>| I dont understand. For a start, there is NO requirement
>|that I can see that < is a partial order. Have I missed something?
>
>What you have missed is the implication of this statement.  *No requirement*
>is equivalent to a *Permission* for compiler vendors and programmers to
>write compilers and programs making use of that *Permission.*  Such compilers
>and programs are perfectly legal and valid C and C++ compilers/programs.
>They are *conforming* -- they're just not *strictly conforming* programs.

 Yes, I see. You are saying that by upgrading the requirements
to a total order existing confrming programs which are not strictly
conforming suddenly become non-conforming and are thus broken.
>
>| As I understand it the rules are:
>|
>| 1) pointers to the same object compare ==
>| 2) within an array, < is a total order
>| 3) In other cases < is implementation defined.
>
> 4) Don't gratuitously change C++ from C so as to break existing
> legal C programs.

 Yes, I understand now I think. Leaving things 'implementation
defined' is then a complete barrier to ever upgrading those things
to be defined by the language without possibly breaking existing programs.

>
>|Any program relying on some implementation defined order (3) cannot
>|be portable.
>
>*It doesn't have to be portable to be legal!*

[]

>|If a total ordering was required, programs utilising
>|this requirement would be portable.
>
>Nope.  They would only become portable if this was the last non-portability
>in that program -- hardly likely.

 It might be the case if the class used < for the purpose
Andrew mentioned, and was otherwise a general purpose class.
This makes the class (rather than the program) the thing that we want
to make portable, i.e. the unit of reusability.
>
>On the converse side, tons of previously legal but not *strictly* portable
>programs would now become illegal.
>Besides, total ordering would require non-flat model programs to become
>bigger and slower.  But you guys already know that.  Now how about cutting
>out the game playing -- this issue has already been fought out in the
>ANSI C committees.  Why reopen old ground?
>

 I have not had access to these proceedings so know nothing
about previous battles. This sort of thing happens all the time here,
it would be good if there were better access to the proceedings,
as I'm sure you'll agree :-)



--
;----------------------------------------------------------------------
        JOHN (MAX) SKALLER,         maxtal@extro.ucc.su.oz.au
 Maxtal Pty Ltd, 6 MacKay St ASHFIELD, NSW 2131, AUSTRALIA
;--------------- SCIENTIFIC AND ENGINEERING SOFTWARE ------------------

In article <1992Oct30.003946.10484@microsoft.com> jimad@microsoft.com (Jim Adcock) writes:
>In article <1992Oct28.184135.25475@ucc.su.OZ.AU> maxtal@extro.ucc.su.OZ.AU (John MAX Skaller) writes:
>| ...
>|If a total ordering was required, programs utilising
>|this requirement would be portable.
>
>Nope.  They would only become portable if this was the last non-portability
>in that program -- hardly likely.
>
>On the converse side, tons of previously legal but not *strictly* portable
>programs would now become illegal.
>
>Thus your trade-off would represent a major lose:  Lots of legal programs
>become busted in exchange for making an unlikely few programs portable.
> ...

I would first like to return to a much more important, related problem,
which somebody brought up here rather recently.
Namely, there is nothing in the ARM explicitly saying that
p == q  might not yield 1 even when p and q are pointing at two different
objects.  This hole makes e.g. some standard idioms in Stroustrup's books
implementation dependent.

(If p has type A* and q has type B*, where B is derived from A,
then p==q, wherever allowed by access control, will and should of course
yield 1 if q points at a subobject of *p.)

So far, no representative of the ANSI committee has replied
(or I have missed such a posting)!
I am waiting for one of three alternatives:

1) The above picture is wrong:  it can be reasoned from such and such
   paragraphs of the ARM that p==q should imply that *p and *q are the
   same object.

2) The committee is fixing the hole.

3) The situation is indeed as described, and the committee is not planning
   to do anything about it.

Alternative 3 would certainly need some strong arguments,
which I am incapable to imagine.


Suppose that the above problem is settled (alt. 1 or 2).
Then, if there is no total order within pointers of the same type,
essentially one or more of the following holds:

A) '<' is not transitive, i.e. p < q and q < r does not imply p < q.

B) '<' (or rather '<=') is not connective, i.e. there might be p and q
   such that neither p = q, p < q nor q < p holds.

C) All usual relationships between the different relational operators
   need not hold (e.g. p < q does not imply q > p).

I have difficulty to imagine any useful programming idioms that would
depend on either A, B, or C (or on the exact way in which a particular
implementation makes pointers not be totally ordered),
but you speak about tons of legal programs that would become illegal.
Could you give a small example?

BTW, arguments about ANSI C are not always convincing.
C is very much a block-structured assembler, while C++ aspires
to be an object-oriented language, and has much more complex semantics.
Tradeoffs appropriate for C simply need not be wise for C++.
The umbilical cord should finally be cut.

----------------------------------------------------------------------
Markku Sakkinen (sakkinen@jytko.jyu.fi)
       SAKKINEN@FINJYU.bitnet (alternative network address)
Department of Computer Science and Information Systems
University of Jyvaskyla (a's with umlauts)
PL 35
SF-40351 Jyvaskyla (umlauts again)
Finland
----------------------------------------------------------------------

In article <1992Nov4.071814.10880@ucc.su.OZ.AU> maxtal@extro.ucc.su.OZ.AU (John MAX Skaller) writes:
| Yes, I see. You are saying that by upgrading the requirements
|to a total order existing confrming programs which are not strictly
|conforming suddenly become non-conforming and are thus broken.

Yes, exactly.

| Yes, I understand now I think. Leaving things 'implementation
|defined' is then a complete barrier to ever upgrading those things
|to be defined by the language without possibly breaking existing programs.

Yes, except the word is not "possibly" but rather "probably" because
the vast majority of programs written are written in non-portable manner
by programmers who neither understand nor care about portability.  Unfortunate,
but true.

I'm not saying that you can't ever change an "implementation defined" to
a "language defined" -- it just that you need to understand that such changes
are *major* changes to the language -- not *minor* changes, and you better
be darned sure that everyone buys into the associated cost.  Because a
lot of programs are going to be suddenly busted, and a lot of compiler
vendors are going to be solidly cursed by 100s or 1000s of customers for
"gratuitously" changing their compilers in ways that suddenly "bust" programs
that use to be "correct."  And such customers are right --  their programs
were "correct" -- just not strictly conforming.

| It might be the case if the class used < for the purpose
|Andrew mentioned, and was otherwise a general purpose class.
|This makes the class (rather than the program) the thing that we want
|to make portable, i.e. the unit of reusability.

Agreed.  But note that requiring strict ordering would also make this
class non-portable non-reusable on systems using C++ OODBMSs -- because
you can't reasonably maintain a total ordering over a DB over a series of
complete or partial passivations/activations.  Also merging/splitting DBs
accross several computer systems becomes problematic if one assumes a total
ordering.

| I have not had access to these proceedings so know nothing
|about previous battles. This sort of thing happens all the time here,
|it would be good if there were better access to the proceedings,
|as I'm sure you'll agree :-)

I agree, but the battles I was referring to happened even more moons ago
in the ANSI-C committee.  The ANSI-C committee was pretty smart.  Things
left implementation-defined were hard-won compromises between two or more
groups that couldn't agree and so agreed to not agree.  Unfortunately, such
has also got to be true of the ANSI/ISO-C++ effort.  You can only standardize
what people widely agree to.  Everything else has to remain implementation
defined.  If one faction or the other was truly "correct" in their strongly
held position, then one can only assume their compilers will ultimately win
in the marketplace -- and maybe could be agreed upon at the C+n standardization
effort ;-)

In article <1992Nov4.080805.13496@jyu.fi> sakkinen@jyu.fi (Markku Sakkinen) writes:
...
>I would first like to return to a much more important, related problem,
>which somebody brought up here rather recently.
>Namely, there is nothing in the ARM explicitly saying that
>p == q  might not yield 1 even when p and q are pointing at two different
>objects.  This hole makes e.g. some standard idioms in Stroustrup's books
>implementation dependent.

I'd like to ask a related question.

Given code like:

char* start = new char [10];
char* end   = start+10;
char* p     = start;

assert ((p >= start) && (p <= end));  // this is gauranteed by ANSI-C
p += 10;
assert ((p >= start) && (p <= end));  // this is gauranteed by ANSI-C
p = start;
p--;
assert (! ((p >= start) && (p <= end))); // ???????

Is the last assertion portable? ARM/ANSI-C References?


    LeWiS.



--
Reading peoples signatures is a real waste of time.

lewis@sophists.com                                  (Lewis Gordon Pringle, Jr.)

In article <1992Nov10.185247.14128@sophists.com> lewis@sophists.com (Lewis G. Pringle) writes:
>In article <1992Nov4.080805.13496@jyu.fi> sakkinen@jyu.fi (Markku Sakkinen) writes:
>...
>>I would first like to return to a much more important, related problem,
>>which somebody brought up here rather recently.
>> ...

I am still waiting for an answer to that question.
Nobody got a clue?

>I'd like to ask a related question.
>
>Given code like:
>
>char* start = new char [10];
>char* end   = start+10;
>char* p     = start;
> ...
>p = start;
>p--;
>assert (! ((p >= start) && (p <= end))); // ???????
>
>Is the last assertion portable? ARM/ANSI-C References?

Certainly not portable.  The ARM (o. 72 - 73) says that 'p--' above
is undefined;  I would suppose that an implementation is allowed
even to abort the programme at that point.  Or, 'p > start' and
'p < start' might both yield true, and 'p >= start' and 'p <= start'
both false.

----------------------------------------------------------------------
Markku Sakkinen (sakkinen@jytko.jyu.fi)
       SAKKINEN@FINJYU.bitnet (alternative network address)
Department of Computer Science and Information Systems
University of Jyvaskyla (a's with umlauts)
PL 35
SF-40351 Jyvaskyla (umlauts again)
Finland
----------------------------------------------------------------------

lewis@sophists.com (Lewis G. Pringle) writes:

|In article <1992Nov4.080805.13496@jyu.fi> sakkinen@jyu.fi (Markku Sakkinen) writes:
|...
|>I would first like to return to a much more important, related problem,
|>which somebody brought up here rather recently.
|>Namely, there is nothing in the ARM explicitly saying that
|>p == q  might not yield 1 even when p and q are pointing at two different
|>objects.  This hole makes e.g. some standard idioms in Stroustrup's books
|>implementation dependent.

There is language in the C standard (ANSI 3.3.9, Equality Operators)
which requires that pointers which compare equal point to the same
object (plus some weasel wording).  This is missing from 5.10 of the
ARM and (so far) from the C++ Committee Working Paper.  This issue
should probably be addressed.

|Given code like:

|char* start = new char [10];
|char* end   = start+10;
|char* p     = start;

|assert ((p >= start) && (p <= end)); // 1. this is gauranteed by ANSI-C
|p += 10;
|assert ((p >= start) && (p <= end)); // 2. this is gauranteed by ANSI-C
|p = start;
|p--;
|assert (! ((p >= start) && (p <= end))); // 3. ???????

|Is the last assertion portable? ARM/ANSI-C References?

The first two are also guaranteed by 5.9 in the ARM.

The third example does not have defined behavior in Standard C or C++.
You are allowed to create an address one unit past the end of an array,
but you are not necessarily allowed to create an address ahead of the
array.  The expression "p--" is not necessarily valid, and the following
comparison has no defined semantics.  See ANSI C 3.3.8 and ARM 5.9.
--

Steve Clamage, TauMetric Corp, steve@taumet.com
Vice Chair, ANSI C++ Committee, X3J16

In article <1992Oct22.180951.24111@jyu.fi> sakkinen@jyu.fi (Markku Sakkinen) writes:

> Thus, while Jim Adcock, in the posting to which you had originally replied,
> was quite happy with the situation as is, you would be in favour of a change
> in the standard to make pointer types totally ordered?

Yes, I would.  Of course, my preference may not count for all that much,
given the number of machines out there with segmented architectures.
It would be nice if someone with access to real data could do a
cost/benefit analysis.
--
    --Andrew Koenig
      ark@europa.att.com

In article <23978@alice.att.com> ark@alice.UUCP () writes:
>In article <1992Oct22.180951.24111@jyu.fi> sakkinen@jyu.fi (Markku Sakkinen) writes:
>
>> Thus, while Jim Adcock, in the posting to which you had originally replied,
>> was quite happy with the situation as is, you would be in favour of a change
>> in the standard to make pointer types totally ordered?
>
>Yes, I would.  Of course, my preference may not count for all that much,
>given the number of machines out there with segmented architectures.
>It would be nice if someone with access to real data could do a
>cost/benefit analysis.

I dont understand how the segmented architectures have anything to do with it.
It is only necessary that there be *an* total order, it makes
no difference what that order is. Certainly there is no problem
on any of the 80x86 machines in obtaining an arbitrary total order
on pointers. On the 486 in 32 bit protected mode pointers are
48 bits and can just be compared bitwise just as on a linear
address machine.

The problems that exist on such machines are not so much with <
but with == and !=. In principle on the 486 two machine
pointers---different bit patterns---can point to the same
object in such a way that it is NOT possible to compare them
for equality without invoking the operating system.

(This will occur if two segments are overlaid, for example,
one being read only and the other read/write. It can also
occur on a linear address machine (or the 486) if the virtual
memory systemn allows remapping of the linear address space.
Here two different linear addresses might point to the same object)

Without placing constraints on architectures the best that can be said
is that if the bit patterns of two pointers are equal, they
point to the same object. If they are not equal, nothing further
is known. Even *this* is not true if the pointers are from
two different tasks.


--
;----------------------------------------------------------------------
        JOHN (MAX) SKALLER,         maxtal@extro.ucc.su.oz.au
 Maxtal Pty Ltd, 6 MacKay St ASHFIELD, NSW 2131, AUSTRALIA
;--------------- SCIENTIFIC AND ENGINEERING SOFTWARE ------------------

In article <1992Oct23.064817.2648@ucc.su.OZ.AU> maxtal@extro.ucc.su.OZ.AU (John MAX Skaller) writes:

> I dont understand how the segmented architectures have anything to do with it.
> It is only necessary that there be *an* total order, it makes
> no difference what that order is.

Consider a machine where addresses are (segment, offset) with the actual
address being determined by adding the segment and the offset.
If the compiler adopts the convention that all pointers to elements
of the same array will have the same segment pointer, then it can
do < > <= >= comparisons (which are valid only for pointers to
elements of the same array) by comparing the offsets and ignoring the
segments.  This is not a legitimate ordering, because it might be that
for elements of two different arrays with the same offset, all three
of < > == would return false.
--
    --Andrew Koenig
      ark@europa.att.com

In article <1992Oct23.064817.2648@ucc.su.OZ.AU>
 maxtal@extro.ucc.su.OZ.AU (John MAX Skaller) writes:

>(This will occur if two segments are overlaid, for example,
>one being read only and the other read/write. It can also
>occur on a linear address machine (or the 486) if the virtual
>memory systemn allows remapping of the linear address space.
>Here two different linear addresses might point to the same object)

I don't think this is a concern for either C or C++.  While it is possible
to set up several aliases for the same data, I can think of no reason for
a language implementation to provide multiple aliases for the same data
when only standard language facilities are used.

For example, an 80386 may choose to map the stack and data segments so
there is partial overlap, but any reference to the stack via the data
segment (or to the static data via the stack segment) would be via
non-portable constructions like casting an integer to a pointer.  Any
object would have a fixed segment associated with it even though it might
be possible to access it via a different segment.

Any means of accessing the same object through different segments (which
would be an extension to the language) could be handled by defining a "far
pointer" class without changing the meaning of "==" for ordinary pointers.

--
    John Carr (jfc@athena.mit.edu)

In article <1992Oct21.153904.13965@ucc.su.OZ.AU> maxtal@extro.ucc.su.OZ.AU (John MAX Skaller) writes:
| The requirement that two pointers to the same object compare
|equal is a bit stiff. The bit paterns on a 486 might not compare equal,
|indeed it may not be *possible* to implement this requirement.
|(The reason is it would require access to the LDT or GDT to
|calculate the linear addresses, and/or access to the virtual memory
|index tables for the same reason)
|
| Does this requirement really preclude memory mapping
|techniques?

There is nothing unique to the 80x86 architecture in this
argument.  Lots of architectures have virtual memory capabilities that
allow multiple pages to be mapped at the OS level to the same physical
page.  By such an argument none of these machines could implement the
object comparison requirements.  The issue is NOT that OS level
routines CAN be written that violate this requirement.  The issue is
whether or not reasonable compiler and required libraries can be
written that implement the requirement, which in turn allow programmers
to write strictly portable programs that use the requirement.  If
a programmer chooses to use non-conforming features of some environment
in a way that violates the assumptions of a particular compiler
implementation, this in no way invalidates that particular compiler
implementation -- it in no way says that compiler approach "can't
be done."  It merely says that that programmer has written a non-conforming
program -- let alone a strictly conforming program!

Please note however, that if C++ diverged from C in requiring a total
ordering, such a change would break many good, legal, conforming C/C++
programs, because it is currently NOT *illegal* in C to make use of the C and
C++ definition of partial ordering -- such usages are merely *implementation
defined*.  Thus a switch at this late date to total ordering would
represent a very large gratuitous change breaking many existing
conforming programs.

This would be a big step in the wrong direction of tying C/C++ to one
particularly simple and naive memory model, rather than allowing C/C++ to
be reasonably ported to all of today, yesterday's and tomorrow's computer
architectures.  IMHO.  32-bit flat architectures are simply one stop on
the way to the future.  There are lots of interesting CPU architectures
that aren't 0:32.  At the very least, 16:32 and 32:32 architectures are
becoming commonplace, as is multiprocessing.  Would people force all machines
now and in the future into the 0:32 straight-jacket?  This would be very
short-sighted IMHO.

On the contrary, let's head in the opposite direction, and make the
cast from ptr to int and back again strictly implementation defined,
thus opening C++ up to architectures with moveable objects, and opening
the door to reasonable compacting memory management schemes.

In article <1992Oct26.170404.1904@microsoft.com> jimad@microsoft.com (Jim Adcock) writes:
>Please note however, that if C++ diverged from C in requiring a total
>ordering, such a change would break many good, legal, conforming C/C++
>programs, because it is currently NOT *illegal* in C to make use of the C and
>C++ definition of partial ordering -- such usages are merely *implementation
>defined*.  Thus a switch at this late date to total ordering would
>represent a very large gratuitous change breaking many existing
>conforming programs.

 I dont understand. For a start, there is NO requirement
that I can see that < is a partial order. Have I missed something?

 As I understand it the rules are:

 1) pointers to the same object compare ==
 2) within an array, < is a total order
 3) In other cases < is implementation defined.

In particular, in case 3 a compiler could just return TRUE for
all comparisons, so we do not have a partial order here.

Any program relying on some implementation defined order (3) cannot
be portable. If a total ordering was required, programs utilising
this requirement would be portable. Existing non-portable programs
might even suddenly become portable. Surely very few implementation
defined orderings would not be total orders anyhow, so very few
existing programs would be broken if the rules changed?


--
;----------------------------------------------------------------------
        JOHN (MAX) SKALLER,         maxtal@extro.ucc.su.oz.au
 Maxtal Pty Ltd, 6 MacKay St ASHFIELD, NSW 2131, AUSTRALIA
;--------------- SCIENTIFIC AND ENGINEERING SOFTWARE ------------------

In article <1992Oct24.044422.28435@athena.mit.edu> jfc@athena.mit.edu (John F Carr) writes:
[On two pointers comparing equal on segmented machines]

>I don't think this is a concern for either C or C++.  While it is possible
>to set up several aliases for the same data, I can think of no reason for
>a language implementation to provide multiple aliases for the same data
>when only standard language facilities are used.

 I can. Suppose the language implementation decided to
protect 'const' objects by aliasing all pointers to const, so that
a violation caused a hardware fault. Thus

 const char *x=new char[100];
 char *y=(char*)x; // cast away const

Now access through x is physically protected (for unknown reasons,
perhaps to preserve 'const' in machine code routines) but access
is allowed through y. But now x!=y unless special care is taken.
This is illegal at the moment because we have two different
pointers to the same object.
>
>For example, an 80386 may choose to map the stack and data segments so
>there is partial overlap, but any reference to the stack via the data
>segment (or to the static data via the stack segment) would be via
>non-portable constructions like casting an integer to a pointer.  Any
>object would have a fixed segment associated with it even though it might
>be possible to access it via a different segment.
>

 For foreign interfacing there are many issues not addressed
by the language. The language conceives a single task with a single
address space. Yet C++ is *used* in other circumstances. One cannot
write an OODBMS server or GUI app without violating  this concept. But
arguments from implementers of such things in favour of downcasting
for example are considered to have some merit.

 I call the native single address space type program
a "domestic" program (not invented by me though). Unfortunately,
it does not serve well for many applications. One must 'trick'
the language---often.


--
;----------------------------------------------------------------------
        JOHN (MAX) SKALLER,         maxtal@extro.ucc.su.oz.au
 Maxtal Pty Ltd, 6 MacKay St ASHFIELD, NSW 2131, AUSTRALIA
;--------------- SCIENTIFIC AND ENGINEERING SOFTWARE ------------------

In article <1992Oct26.170404.1904@microsoft.com> jimad@microsoft.com (Jim Adcock) writes:

[< on pointers .. total ordering]

>This would be a big step in the wrong direction of tying C/C++ to one
>particularly simple and naive memory model, rather than allowing C/C++ to
>be reasonably ported to all of today, yesterday's and tomorrow's computer
>architectures.  IMHO.  32-bit flat architectures are simply one stop on
>the way to the future.  There are lots of interesting CPU architectures
>that aren't 0:32.  At the very least, 16:32 and 32:32 architectures are
>becoming commonplace, as is multiprocessing.  Would people force all machines
>now and in the future into the 0:32 straight-jacket?  This would be very
>short-sighted IMHO.

 I agree but I dont see what this has to do with the issue
of whether < is required to be a total order. If all pointers on
a machine are the same length, and alisaing is not allowed,
then a bitwise comparison yields a total order. That ordering
is meaningless in itself, but as Andrew Koenig pointed out it
is useful for putting pointers in data structures requiring
a type T with a total order.
>
>On the contrary, let's head in the opposite direction, and make the
>cast from ptr to int and back again strictly implementation defined,
>thus opening C++ up to architectures with moveable objects, and opening
>the door to reasonable compacting memory management schemes.

 I'm not sure whether casting to/from int is relevant here,
except that *if* you can do it at all, you get a total order.
If you made it implementation defined (i.e. the casts were REQUIRED
to work) then you would either no longer have a total order
or you would have to have quite big 'int' values.

--
;----------------------------------------------------------------------
        JOHN (MAX) SKALLER,         maxtal@extro.ucc.su.oz.au
 Maxtal Pty Ltd, 6 MacKay St ASHFIELD, NSW 2131, AUSTRALIA
;--------------- SCIENTIFIC AND ENGINEERING SOFTWARE ------------------

In article <23986@alice.att.com> ark@alice.UUCP () writes:
>In article <1992Oct23.064817.2648@ucc.su.OZ.AU> maxtal@extro.ucc.su.OZ.AU (John MAX Skaller) writes:
>
>> I dont understand how the segmented architectures have anything to do with it.
>> It is only necessary that there be *an* total order, it makes
>> no difference what that order is.
>
>Consider a machine where addresses are (segment, offset) with the actual
>address being determined by adding the segment and the offset.
>If the compiler adopts the convention that all pointers to elements
>of the same array will have the same segment pointer, then it can
>do < > <= >= comparisons (which are valid only for pointers to
>elements of the same array) by comparing the offsets and ignoring the
>segments.  This is not a legitimate ordering, because it might be that
>for elements of two different arrays with the same offset, all three
>of < > == would return false.

 Yes, but IF the language required a total ordering the
compiler would be REQUIRED to normalise the pointers, which is
precisely what Borland C++ does for real mode 8086 code anyhow
in many circumstances.

 Any comments on the harder issue of

 "two pointers to the same object compare equal" (p74)


--
;----------------------------------------------------------------------
        JOHN (MAX) SKALLER,         maxtal@extro.ucc.su.oz.au
 Maxtal Pty Ltd, 6 MacKay St ASHFIELD, NSW 2131, AUSTRALIA
;--------------- SCIENTIFIC AND ENGINEERING SOFTWARE ------------------

In article <1992Oct28.180039.20655@ucc.su.OZ.AU> maxtal@extro.ucc.su.OZ.AU (John MAX Skaller) writes:
| Yes, but IF the language required a total ordering the
|compiler would be REQUIRED to normalise the pointers

Not true.  The compiler can be written in such a manner that no strictly
conforming program can legally result in a denormalized pointer.  Then
the compiler has no requirement to perform normalization -- because such
could only be a result of a not strictly conforming program.

In article <1992Oct28.184135.25475@ucc.su.OZ.AU> maxtal@extro.ucc.su.OZ.AU (John MAX Skaller) writes:

| I dont understand. For a start, there is NO requirement
|that I can see that < is a partial order. Have I missed something?

What you have missed is the implication of this statement.  *No requirement*
is equivalent to a *Permission* for compiler vendors and programmers to
write compilers and programs making use of that *Permission.*  Such compilers
and programs are perfectly legal and valid C and C++ compilers/programs.
They are *conforming* -- they're just not *strictly conforming* programs.

| As I understand it the rules are:
|
| 1) pointers to the same object compare ==
| 2) within an array, < is a total order
| 3) In other cases < is implementation defined.

 4) Don't gratuitously change C++ from C so as to break existing
 legal C programs.

|Any program relying on some implementation defined order (3) cannot
|be portable.

*It doesn't have to be portable to be legal!*  It is quite legitimate to
write legal programs that aren't portable -- in fact obviously 99.9% of
the interesting C/C++ programs *aren't* strictly portable!  "Portability"
then is the wrong measure when it comes to standards.  Instead, the issue
is legality.  You cannot gratuitously take a large class of programs and
make them all illegal.  Such destroys the compatibility that C++ is justly
famous for.

|If a total ordering was required, programs utilising
|this requirement would be portable.

Nope.  They would only become portable if this was the last non-portability
in that program -- hardly likely.

On the converse side, tons of previously legal but not *strictly* portable
programs would now become illegal.

Thus your trade-off would represent a major lose:  Lots of legal programs
become busted in exchange for making an unlikely few programs portable.

|Surely very few implementation
|defined orderings would not be total orders anyhow, so very few
|existing programs would be broken if the rules changed?

Segment hacks in programs for x86 systems are EXTREMELY common.  If
you were to require a total ordering on pointers a HUGE amount of currently
conforming C/C++ programs would suddenly become illegal.  This is clearly
not acceptable, and not well thought out.  My off-the-top-of-my-head
estimate for the number of C++ programmers that would fall in this
category would be several hundred thousand.  [Based on C++ compiler sales
numbers]  The number of C programmers affected would probably be even larger --
unless you expect C/C++ compilers to implement total ordering on C++
programs but partial orderings on C programs?  Wrong.

Besides, total ordering would require non-flat model programs to become
bigger and slower.  But you guys already know that.  Now how about cutting
out the game playing -- this issue has already been fought out in the
ANSI C committees.  Why reopen old ground?

In article <1992Sep10.094957.23588@jyu.fi> sakkinen@jyu.fi (Markku Sakkinen) writes:
|My opinion:  the idiom is sensible, in many cases even necessary.
|It is the pertinent part in the language definition that is broken,
|obviously (as explained by Johan above) in order to facilitate
|efficient implementation on obsolescent machine architectures.
|Was it William Wulf who wrote approximately: "More sins in programming
|are committed in the name of efficiency than all other reasons combined,
|including sheer stupidity"?

Note that many of the newest RISC machines also feature segmented architectures,
and are typically run with their compilers in a mode where pointer comparsions
are not done on the segment part.

But in any case, at least my PC compiler (Large Model)
performs == and != comparisons based both on the segment and offset parts.
Its the ordered comparisons > < >= <= where only the offset part is compared.
Thus == != work for all ptrs.  > < >= <= only work within an array.

Which is as it should be.

I think the standard should define == != to always work on ptrs of comparable
types -- assuming those ptr are pointing at legitimate objects or one past
the end of a legitimate array.  > < >= <= to be only defined within an array
or one past its end.

In article <1992Oct16.234851.28948@microsoft.com> jimad@microsoft.com (Jim Adcock) writes:

> But in any case, at least my PC compiler (Large Model)
> performs == and != comparisons based both on the segment and offset parts.
> Its the ordered comparisons > < >= <= where only the offset part is compared.
> Thus == != work for all ptrs.  > < >= <= only work within an array.

> Which is as it should be.

This is far from clear.

For example, if a type T has a < operator defined that is actually a strong
total order relation, that makes it possible to store T objects efficiently
in a variety of order-based data structures such as M,N-trees, etc.
There are many applications for such structures.  For example, one might make
the constructor and destructor for class T use such a structure to keep
track of all the T objects in the universe, and so on.
--
    --Andrew Koenig
      ark@europa.att.com

In article <23915@alice.att.com> ark@alice.UUCP () writes:
>In article <1992Oct16.234851.28948@microsoft.com> jimad@microsoft.com (Jim Adcock) writes:
>
>> But in any case, at least my PC compiler (Large Model)
>> performs == and != comparisons based both on the segment and offset parts.
>> Its the ordered comparisons > < >= <= where only the offset part is compared.
>> Thus == != work for all ptrs.  > < >= <= only work within an array.
>
>> Which is as it should be.
>
>This is far from clear.
>
>For example, if a type T has a < operator defined that is actually a strong
>total order relation, that makes it possible to store T objects efficiently
>in a variety of order-based data structures such as M,N-trees, etc.
>There are many applications for such structures.  For example, one might make
>the constructor and destructor for class T use such a structure to keep
>track of all the T objects in the universe, and so on.

Sorry, there is a misunderstanding here.
The discussion in this thread (see subject line) has been about _pointer_
comparisons all the time.  Comparison of object values is another story
altogether.

Another aspect of the original problem:
Given two pointer values (of the same type), it is acceptable that
their ordered comparison is not always sensible (or it is implementation
dependent).  However, there does not even exist any standard way to test
_whether_ the comparison is valid (i.e., if the pointers point at elements
of the same array or at members of the same object).
That is a defect.

While we are at it, I would like to hear if the standardisation committee
has completed the requirement of the ARM (p. 74): "Two pointers to the
same object compare equal." with "Two pointers of the same type to different
objects compare inequal." or something similar.
(The qualification 'of the same type' is necessary because of base class
vs. derived class pointers.)

----------------------------------------------------------------------
Markku Sakkinen (sakkinen@jytko.jyu.fi)
       SAKKINEN@FINJYU.bitnet (alternative network address)
Department of Computer Science and Information Systems
University of Jyvaskyla (a's with umlauts)
PL 35
SF-40351 Jyvaskyla (umlauts again)
Finland
----------------------------------------------------------------------

In <comp.std.c++> sakkinen@jyu.fi (Markku Sakkinen) writes:
>In article <23915@alice.att.com> ark@alice.UUCP () writes:
>>For example, if a type T has a < operator defined that is actually a strong
>>total order relation, that makes it possible to store T objects efficiently
>>in a variety of order-based data structures such as M,N-trees, etc.
>
>Sorry, there is a misunderstanding here.
>The discussion in this thread (see subject line) has been about _pointer_
>comparisons all the time.  Comparison of object values is another story
>altogether.

A strong ordering of pointers makes much sense in many data
structures, even if the ordering of the object values is not well
defined.  I believe the most common data type in trees, hash tables,
etc. is indeed "pointer to T".

The ordering of pointers may be implementation defined, and I don't
even think it would have to be equal between runs of the same program.

Dag

In article <23915@alice.att.com> ark@alice.UUCP () writes:
|In article <1992Oct16.234851.28948@microsoft.com> jimad@microsoft.com (Jim Adcock) writes:
|
|> But in any case, at least my PC compiler (Large Model)
|> performs == and != comparisons based both on the segment and offset parts.
|> Its the ordered comparisons > < >= <= where only the offset part is compared.
|> Thus == != work for all ptrs.  > < >= <= only work within an array.
|
|> Which is as it should be.
|
|This is far from clear.
|
|For example, if a type T has a < operator defined that is actually a strong
|total order relation, that makes it possible to store T objects efficiently
|in a variety of order-based data structures such as M,N-trees, etc.
|There are many applications for such structures.  For example, one might make
|the constructor and destructor for class T use such a structure to keep
|track of all the T objects in the universe, and so on.

Are you talking about overloadable comparison operators?  I am talking
about built-in ptr comparison operators as defined by C/C++

dag@control.lth.se (Dag Bruck) writes:

...
>A strong ordering of pointers makes much sense in many data
>structures, even if the ordering of the object values is not well
>defined.  I believe the most common data type in trees, hash tables,
>etc. is indeed "pointer to T".

>The ordering of pointers may be implementation defined, and I don't
>even think it would have to be equal between runs of the same program.

C only defines pointer comparison if the pointers point to objects in
the _same_array_. The ordering between two pointers that do not point in
the same array is undefined. That means you cannot rely on any
property. For example, it might lead to a run-time error, and if it
doesn't, the ordering of two pointers might change _during_ the run of
the program. On a segmented machine, an implementation could implement
pointer comparison based on the actual address. If two segments are
swapped out and reloaded, their order might change. Any pointers
within the same segment would still retain their ordering, but the
order between two pointers in different segments could change at any
time. I have seen a lot of C programs that would fail on a machine
like this.

C++ didn't try to change the pointer/array structure of C which, if I
recall rightly, was called 'fatally flawed'. IMHO the unrestricted
pointer juggling is one of the weakest points of C (and C++), but
given C, it would be nearly impossible to correct this in C++.

-------------------------------------------------------------------------------
Niels T. Ferguson          | #include <stddisclaimer.h>
CWI                        |
Amsterdam, The Netherlands | ... of shoes and ships and sealing-wax, of
tel: +31 20 5924103        | cabbages and kings. And why the sea is boiling
e-mail: niels@cwi.nl       | hot, and whether pigs have wings.


--
-------------------------------------------------------------------------------
Niels T. Ferguson          | #include <stddisclaimer.h>
CWI                        |
Amsterdam, The Netherlands | ... of shoes and ships and sealing-wax, of

In article <1992Oct19.055511.18826@jyu.fi> sakkinen@jyu.fi (Markku Sakkinen) writes:

> In article <23915@alice.att.com> ark@alice.UUCP () writes:

> >For example, if a type T has a < operator defined that is actually a strong
> >total order relation, that makes it possible to store T objects efficiently
> >in a variety of order-based data structures such as M,N-trees, etc.

> Sorry, there is a misunderstanding here.
> The discussion in this thread (see subject line) has been about _pointer_
> comparisons all the time.  Comparison of object values is another story
> altogether.

No misunderstanding.

I made a general statement about potentially useful properties of arbitrary
types.  That statement still holds true when those types happen to be pointer
types.  That is, if < were defined as a strong total ordering on pointers,
I could use these data structures to keep track of sets of pointers.
--
    --Andrew Koenig
      ark@europa.att.com

In article <1992Oct19.152004.8350@lth.se> dag@control.lth.se (Dag Bruck) writes:
|The ordering of pointers may be implementation defined, and I don't
|even think it would have to be equal between runs of the same program.

Under many if not most OS's the ordering of pointers resulting from heap
allocations would be implementation defined, and needn't be equal between
runs of the same program.  One can usually figure out some system dependent
hack to force an ordering on allocations, but program and/or system performance
will frequently suffer.  Thus I would suggest that strong ordering constraints
should remain implementation dependent, as in the C standard.  IE speed
should never be sacrificed up front in order to address secondary concerns.

In article <1992Oct19.055511.18826@jyu.fi> sakkinen@jyu.fi (Markku Sakkinen) writes:
>In article <23915@alice.att.com> ark@alice.UUCP () writes:
>>In article <1992Oct16.234851.28948@microsoft.com> jimad@microsoft.com (Jim Adcock) writes:
>>
>>> But in any case, at least my PC compiler (Large Model)
>>> performs == and != comparisons based both on the segment and offset parts.
>>> Its the ordered comparisons > < >= <= where only the offset part is compared.
>>> Thus == != work for all ptrs.  > < >= <= only work within an array.
>>
>>> Which is as it should be.
>>
>>This is far from clear.
>>
>>For example, if a type T has a < operator defined that is actually a strong
>>total order relation, that makes it possible to store T objects efficiently
>>in a variety of order-based data structures such as M,N-trees, etc.
>>There are many applications for such structures.  For example, one might make
>>the constructor and destructor for class T use such a structure to keep
>>track of all the T objects in the universe, and so on.
>
>Sorry, there is a misunderstanding here.
>The discussion in this thread (see subject line) has been about _pointer_
>comparisons all the time.  Comparison of object values is another story
>altogether.

 In "template<class T> ...... T t1, t2; ... t1<t2"
T might well be a pointer.
>
>Another aspect of the original problem:
>Given two pointer values (of the same type), it is acceptable that
>their ordered comparison is not always sensible (or it is implementation
>dependent).  However, there does not even exist any standard way to test
>_whether_ the comparison is valid (i.e., if the pointers point at elements
>of the same array or at members of the same object).
>That is a defect.

 For the example Andrew gave it matters only that

 a) the comparison doesnt crash the machine
 b) it gives the same results if done twice
 c) the operation is transitive and antisymmetric

(i.e. there is a well defined linear order)
>
>While we are at it, I would like to hear if the standardisation committee
>has completed the requirement of the ARM (p. 74): "Two pointers to the
>same object compare equal." with "Two pointers of the same type to different
>objects compare inequal." or something similar.

 You would also need to say a<b implies !(a>b) and other
things.

 The requirement that two pointers to the same object compare
equal is a bit stiff. The bit paterns on a 486 might not compare equal,
indeed it may not be *possible* to implement this requirement.
(The reason is it would require access to the LDT or GDT to
calculate the linear addresses, and/or access to the virtual memory
index tables for the same reason)

 Does this requirement really preclude memory mapping
techniques?

--
;----------------------------------------------------------------------
        JOHN (MAX) SKALLER,         maxtal@extro.ucc.su.oz.au
 Maxtal Pty Ltd, 6 MacKay St ASHFIELD, NSW 2131, AUSTRALIA
;--------------- SCIENTIFIC AND ENGINEERING SOFTWARE ------------------

In article <7724@charon.cwi.nl> niels@cwi.nl (Niels Ferguson) writes:
>dag@control.lth.se (Dag Bruck) writes:
>
>...
>>A strong ordering of pointers makes much sense in many data
>>structures, even if the ordering of the object values is not well
>>defined.  I believe the most common data type in trees, hash tables,
>>etc. is indeed "pointer to T".
>
>>The ordering of pointers may be implementation defined, and I don't
>>even think it would have to be equal between runs of the same program.
>
>C only defines pointer comparison if the pointers point to objects in
>the _same_array_. The ordering between two pointers that do not point in
>the same array is undefined. That means you cannot rely on any
>property. For example, it might lead to a run-time error, and if it
>doesn't, the ordering of two pointers might change _during_ the run of
>the program. On a segmented machine, an implementation could implement
>pointer comparison based on the actual address. If two segments are
>swapped out and reloaded, their order might change. Any pointers
>within the same segment would still retain their ordering, but the
>order between two pointers in different segments could change at any
>time. I have seen a lot of C programs that would fail on a machine
>like this.

 I dont think this can happen. The LINEAR address changes
but the linear addresses are not what is being compared. At least
on the 486 comparison of segmented addresses will always give
the same results, irrespective of the linear or virtual
addresses they map to. If this were not the case programs
could not store pointers and expect them to remain valid.
>
>C++ didn't try to change the pointer/array structure of C which, if I
>recall rightly, was called 'fatally flawed'. IMHO the unrestricted
>pointer juggling is one of the weakest points of C (and C++), but
>given C, it would be nearly impossible to correct this in C++.

 Its not impossible surely. For example, we could have
a declaration

 int array[6] x;

meaning a REAL array of 6 ints. With bounds checking and
restrictions on pointers. For example if we allowed

 int array[6]* p;
 p++;

the p++ could be checked. Given that this sort of thing
can be done (albiet clumbsily) with templates the question is whether
it is really a good idea to add a proper array mechanism
in addition to the C-array mechanism we already have.

--
;----------------------------------------------------------------------
        JOHN (MAX) SKALLER,         maxtal@extro.ucc.su.oz.au
 Maxtal Pty Ltd, 6 MacKay St ASHFIELD, NSW 2131, AUSTRALIA
;--------------- SCIENTIFIC AND ENGINEERING SOFTWARE ------------------

In article <23937@alice.att.com> ark@alice.UUCP () writes:
>In article <1992Oct19.055511.18826@jyu.fi> sakkinen@jyu.fi (Markku Sakkinen) writes:
>
>> In article <23915@alice.att.com> ark@alice.UUCP () writes:
>
>> >For example, if a type T has a < operator defined that is actually a strong
>> >total order relation, that makes it possible to store T objects efficiently
>> >in a variety of order-based data structures such as M,N-trees, etc.
>
>> Sorry, there is a misunderstanding here.
>> The discussion in this thread (see subject line) has been about _pointer_
>> comparisons all the time.  Comparison of object values is another story
>> altogether.
>
>No misunderstanding.
>
>I made a general statement about potentially useful properties of arbitrary
>types.  That statement still holds true when those types happen to be pointer
>types.  That is, if < were defined as a strong total ordering on pointers,
>I could use these data structures to keep track of sets of pointers.

Thus, while Jim Adcock, in the posting to which you had originally replied,
was quite happy with the situation as is, you would be in favour of a change
in the standard to make pointer types totally ordered?

Above, you omitted exactly that part of your earlier posting
that was mixing things up (immediately following the first quote):

>> >There are many applications for such structures.  For example, one might make
>> >the constructor and destructor for class T use such a structure to keep
>> >track of all the T objects in the universe, and so on.

Pointer types are not classes, and they cannot have constructors or
destructors.

----------------------------------------------------------------------
Markku Sakkinen (sakkinen@jytko.jyu.fi)
       SAKKINEN@FINJYU.bitnet (alternative network address)
Department of Computer Science and Information Systems
University of Jyvaskyla (a's with umlauts)
PL 35
SF-40351 Jyvaskyla (umlauts again)
Finland
----------------------------------------------------------------------

jbn@lulea.trab.se (Johan Bengtsson) writes:

|pete@genghis.borland.com (Pete Becker) writes:

|:  0x0000:0x0010
|:  0x0001:0x0000
|:
|: These two addresses refer to the same memory location.  Converting them to
|: longs in the most obvious way produces these two values:
|:
|:  0x00000010
|:  0x00010000

|But can this really happen, if the rule "pointer arithmetic only
|within an array" is adhered to?  Shouldn't all pointers within an
|array be based on the same segment?


If you do non-normalized pointer arithmetic, the offset portion could
be greater than 15 and still point within the array.  This causes no
problems for the hardware, which doesn't care whether pointers are
normalized.  The compiler must still arrange for pointer comparisons
to come out right, such as by normalizing them first.
--

Steve Clamage, TauMetric Corp, steve@taumet.com
Vice Chair, ANSI C++ Committee, X3J16

First, a question for comp.std.c:
is the following a legal (strictly conforming) program?

 struct S { unsigned:0; }
 int main() { return sizeof(S); }

Secondly, some comments about C++.
In ANSI C, pointer comparisons between pointers to unrelated objects (ie.
objects that are not both members of the same aggregate) cause undefined
behavior, I believe. For example, the following program
 #include <assert.h>
 int main() {
  int x,y;
  assert(&x != &y);
 }
should cause undefined behavior. [Is this correct?]

Now the C++ reference manual (5.9) says basically the same thing, with the
further constraints that comparisons with pointers to static members are
undefined, as are comparisons between pointers to members whose declarations
are separated by an access-class specifier (public/protected/private).

Section 5.9 says that "Two pointers to the same object compare equal",
but it does NOT say that "pointers to distinct objects compare unequal" -
instead it says "... Other pointer comparisons are implementation dependent."

Given that this is the case, it seems contradictory that repeated calls to
operator new(0) are required to return pointers to "distinct objects".
How could a conforming program possibly detect whether this requirement
was actually met? Surely the following program
 #include <assert.h>
 int main() {
  assert(operator new(0) != operator new(0));
 }
is not strictly conforming, is it?

--
Fergus Henderson             fjh@munta.cs.mu.OZ.AU
This .signature virus is a self-referential statement that is true - but
you will only be able to consistently believe it if you copy it to your own
.signature file!

fjh@munta.cs.mu.OZ.AU (Fergus James HENDERSON) writes:

>is the following a legal (strictly conforming) program?
>
> struct S { unsigned:0; }
> int main() { return sizeof(S); }

It is not a legal C program, but not due to any particular ANSI
constraints.  It has syntax errors.  Perhaps you meant:

 struct S { unsigned:0; };
 int main() { return sizeof(struct S); }

--
Murray

fjh@munta.cs.mu.OZ.AU (Fergus James HENDERSON) writes:
:
: Secondly, some comments about C++.
: In ANSI C, pointer comparisons between pointers to unrelated objects (ie.
: objects that are not both members of the same aggregate) cause undefined
: behavior,

Small clarifications:

The ARM is explicit about the relational operators (<,>,<=,>=),
and then goes on to say the equality operators are "exactly analogous".
Anyway, comparison with pointers to members of the same aggregate are only
defined if they belong to the same access zone (simplified).  Also,
pointer comparison within the same array is supported.

:I believe. For example, the following program
:  #include <assert.h>
:  int main() {
:   int x,y;
:   assert(&x != &y);
:  }
: should cause undefined behavior. [Is this correct?]

I'd say yes.  On a segmented architecture (can you say 'PC'?)
pointer comparison need not use the full 32 bits for pointer comparison,
instead a 16 bit offset may be used (note that this limits arrays to 64 KB).

I wonder if the 'PC' segmented architecture will reappear in the
first 64 bit processors (representing pointers as 32 bit offsets within
up to 2^32 segments)?  Does anyone have any info on this?

Anyway, the current rules do seem to cause trouble for the common (?)
idiom for operator =:

const T& operator = ( const T& t )
{
 if ( &t == this ) return; // avoid self-assignment
 // ...
}

Is the above idiom broken?
Should the current rules be changed (inflicting a small performance penalty
on some machines)?

: Given that this is the case, it seems contradictory that repeated calls to
: operator new(0) are required to return pointers to "distinct objects".
: How could a conforming program possibly detect whether this requirement
: was actually met? Surely the following program
:  #include <assert.h>
:  int main() {
:   assert(operator new(0) != operator new(0));
:  }

If sizeof(long) >= sizeof(void*), then you should be able to
test like this:

assert( (long)p1 != (long)p2 );

since a pointer stored in an integer variable must keep all information
needed to restore the pointer (if the integer type is large enough).

--
--------------------------------------------------------------------------
| Johan Bengtsson, Telia Research AB, Aurorum 6, S-951 75 Lulea, Sweden  |
| Johan.Bengtsson@lulea.trab.se; Voice:(+46)92075471; Fax:(+46)92075490  |
--------------------------------------------------------------------------

jbn@lulea.trab.se (Johan Bengtsson) writes:

>If sizeof(long) >= sizeof(void*), then you should be able to
>test like this:
>
>assert( (long)p1 != (long)p2 );
>
>since a pointer stored in an integer variable must keep all information
>needed to restore the pointer (if the integer type is large enough).

I don't think that this is the case.

If the integer variable is *larger* than the pointer, then some of the
bits in the integer need not be used when converting from integer to pointer.
I do not see any restriction in the reference manual that would require
the opposite conversion to initialize those bits.
This would then mean that (long) p1 != (long) p2 might return true even
when p1 == p2, because the uninitialized padding bits might be different.

[This means that ((long) p1) may behave "non-deterministically", although
((void *)(long)p1) is guaranteed to evaluate to p1 provided that "long"
is sufficiently large.]

Is that all correct?

--
Fergus Henderson             fjh@munta.cs.mu.OZ.AU
This .signature virus is a self-referential statement that is true - but
you will only be able to consistently believe it if you copy it to your own
.signature file!

In article <4945@holden.lulea.trab.se> jbn@lulea.trab.se (Johan Bengtsson) writes:
>fjh@munta.cs.mu.OZ.AU (Fergus James HENDERSON) writes:
>:  [ ... ]
>  [ ... ]
>:I believe. For example, the following program
>:  #include <assert.h>
>:  int main() {
>:   int x,y;
>:   assert(&x != &y);
>:  }
>: should cause undefined behavior. [Is this correct?]
>
>I'd say yes.  On a segmented architecture (can you say 'PC'?)
>pointer comparison need not use the full 32 bits for pointer comparison,
>instead a 16 bit offset may be used (note that this limits arrays to 64 KB).
>  [ ... ]
>Anyway, the current rules do seem to cause trouble for the common (?)
>idiom for operator =:
>
>const T& operator = ( const T& t )
>{
> if ( &t == this ) return; // avoid self-assignment
> // ...
>}
>
>Is the above idiom broken?
>Should the current rules be changed (inflicting a small performance penalty
>on some machines)?

Oh dear, why have I not noted this _horrible_ defect in the language
definition before?  Probably because it was too bad to be suspected.
The above idiom is certainly common, and it is used in Stroustrup's
own books.  The first example I could found now in "The C++ P. L." (2. ed.)
is in 8.3.3 (p. 266).  In one member function of the list class there is
code like this:
 slink* f = last->next;
 if (f == last)
  last = 0;
 else
  last->next = f->next;

I can see no warning in the vicinity telling that the meaning of this code
is implementation dependent or undefined!

My opinion:  the idiom is sensible, in many cases even necessary.
It is the pertinent part in the language definition that is broken,
obviously (as explained by Johan above) in order to facilitate
efficient implementation on obsolescent machine architectures.
Was it William Wulf who wrote approximately: "More sins in programming
are committed in the name of efficiency than all other reasons combined,
including sheer stupidity"?

----------------------------------------------------------------------
Markku Sakkinen (sakkinen@jytko.jyu.fi)
       SAKKINEN@FINJYU.bitnet (alternative network address)
Department of Computer Science and Information Systems
University of Jyvaskyla (a's with umlauts)
PL 35
SF-40351 Jyvaskyla (umlauts again)
Finland
----------------------------------------------------------------------

In article <1992Sep10.094957.23588@jyu.fi> sakkinen@jyu.fi (Markku Sakkinen) writes:
| In article <4945@holden.lulea.trab.se> jbn@lulea.trab.se (Johan Bengtsson) writes:
| >
| >const T& operator = ( const T& t )
| >{
| > if ( &t == this ) return; // avoid self-assignment
| > // ...
| >}
| >
| >Is the above idiom broken?
|
| Oh dear, why have I not noted this _horrible_ defect in the language
| definition before?  Probably because it was too bad to be suspected.
| The above idiom is certainly common, and it is used in Stroustrup's
| own books.  The first example I could found now in "The C++ P. L." (2. ed.)
| is in 8.3.3 (p. 266).

The idiom is clearly older than that.  Stroustrup uses it in the FIRST
edition of his book, section 6.6, p. 179:

    void String::operator=(String& a)
    {
        if (this == &a) return;  // beware of s=s;
        ...

It would certainly cause grief to many a program if this were to suddenly
be found to be unportable.

Scott

-------------------------------------------------------------------------------
What do you say to a convicted felon in Providence?  "Hello, Mr. Mayor."

In article <4945@holden.lulea.trab.se> jbn@lulea.trab.se (Johan Bengtsson) writes:
>
>If sizeof(long) >= sizeof(void*), then you should be able to
>test like this:
>
>assert( (long)p1 != (long)p2 );
>
>since a pointer stored in an integer variable must keep all information
>needed to restore the pointer (if the integer type is large enough).
>

 Not necessarily. The requirement is only that the original pointers can
be restored, not that their representations as longs be identical.  For
example:

 0x0000:0x0010
 0x0001:0x0000

These two addresses refer to the same memory location.  Converting them to
longs in the most obvious way produces these two values:

 0x00000010
 0x00010000

The trick on segmented architectures is to always normalize the pointers before
comparing. The first pointer above isn't normalized, because it has an offset
greater than 15.  The second one is normalized. Comparisons between normalized
pointers are always valid.
 -- Pete

Hi! I had posted this earlier but due to no suitable response I am posting it
again. I would gratefully acknowledge a reply in this matter.

I am working on developing classes for simulation of finite element meshes
using the object-oriented language c++. I would be grateful if anyone could
send me any programs in c++ which would help me in my work. Also has anyone
developed a class for the simulation of a FEM for any particular structure.
You can mail them to me at my e-mail address and then I will summarize in
the net. Also are there any ftp sites from where I could get any useful
information. Thanx in advance.
                         Zoher.( oherb@jhunix.hcf.jhu.edu )

pete@genghis.borland.com (Pete Becker) writes:
: In article <4945@holden.lulea.trab.se> jbn@lulea.trab.se (Johan Bengtsson) writes:
: >
: >If sizeof(long) >= sizeof(void*), then you should be able to
: >test like this:
: >
: >assert( (long)p1 != (long)p2 );
: >
: >since a pointer stored in an integer variable must keep all information
: >needed to restore the pointer (if the integer type is large enough).
:
:  Not necessarily. The requirement is only that the original pointers can
: be restored, not that their representations as longs be identical.  For
: example:
:
:  0x0000:0x0010
:  0x0001:0x0000
:
: These two addresses refer to the same memory location.  Converting them to
: longs in the most obvious way produces these two values:
:
:  0x00000010
:  0x00010000

But can this really happen, if the rule "pointer arithmetic only
within an array" is adhered to?  Shouldn't all pointers within an
array be based on the same segment?

And for memory models that do not have this requirement (the s.c.
"huge" model), pointer comparison should be smart enough anyway, no?

--
--------------------------------------------------------------------------
| Johan Bengtsson, Telia Research AB, Aurorum 6, S-951 75 Lulea, Sweden  |
| Johan.Bengtsson@lulea.trab.se; Voice:(+46)92075471; Fax:(+46)92075490  |
--------------------------------------------------------------------------