From: ········@bayou.uh.edu
Subject: Re: C++ briar patch (Was: Object IDs are bad)
Date:
Message-ID: <5lkokt$2ak$1@Masala.CC.UH.EDU>
Andy Czerwonka (·········@zebra.net) wrote:
: In article <············@Masala.CC.UH.EDU>, ········@Bayou.UH.EDU says...
: > Henry Baker (······@netcom.com) wrote:
[Snip]
: > : (Those who don't understand this comment should first learn about Algol-68,
: > : Simula, Smalltalk and Lisp, before replying.)
: >
: > Or any one of the above for that matter. For those who think that C++'s
: > OO hack is actually good, look at Smalltalk and CLOS. You will see
: > just why C++'s "object orientation" is a joke, and a very unfunny one
: > at that.
[Snip]
: If you're a good OO programmer and understand how things are done, C++
: allows you to do more things because of its power of addresses. Take it
: from a Smalltalker.
These are the three things I know of that you'd need to use addresses
(pointers) for in C++:
1) Memory Allocation -- unnecessary in languages with GC
2) Creation of Recursive Data Types -- unnecessary in languages
with dynamic data types
3) Remotely Accessing Other Variables -- unnecessary and bad
period.
4) Achieving Polymorphism -- this is a weakness specific to C++
Of course if there is something that I'm missing that makes this
low level construct a necessity for a high level concept (OO) then
I would appreciate it if you would enlighten me.
: --
: Cheers,
: Andy
--
Cya,
Ahmed
From: Fergus Henderson
Subject: Re: C++ briar patch (Was: Object IDs are bad)
Date:
Message-ID: <5lm7sj$l1v@mulga.cs.mu.OZ.AU>
········@Bayou.UH.EDU (········@bayou.uh.edu) writes:
>These are the three things I know of that you'd need to use addresses
>(pointers) for in C++:
> 1) Memory Allocation -- unnecessary in languages with GC
> 2) Creation of Recursive Data Types -- unnecessary in languages
> with dynamic data types
> 3) Remotely Accessing Other Variables -- unnecessary and bad
> period.
> 4) Achieving Polymorphism -- this is a weakness specific to C++
>
>Of course if there is something that I'm missing that makes this
>low level construct a necessity for a high level concept (OO) then
>I would appreciate it if you would enlighten me.
As has been discussed in detail in this thread, the high-level concept
that pointers are useful for modelling is object identity.
Pointers are also useful for representing cyclic data structures.
--
Fergus Henderson <···@cs.mu.oz.au> | "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh> | of excellence is a lethal habit"
PGP: finger ···@128.250.37.3 | -- the last words of T. S. Garp.
From: Jeffrey Mark Siskind
Subject: Re: C++ briar patch (Was: Object IDs are bad)
Date:
Message-ID: <xohoha7161p.fsf@ai.emba.uvm.edu>
···@mundook.cs.mu.OZ.AU (Fergus Henderson) writes:
> As has been discussed in detail in this thread, the high-level concept
> that pointers are useful for modelling is object identity.
There is another use for pointers. And this use requires order comparison
between pointer, not just equality. Suppose you have two sets of objects.
Represented as two lists of pointers to those objects. And you want to know
whether the two sets are equal (i.e. have the same members). This takes O(n^2)
if you don't have any way of ordering the objects:
(define (set=? x y)
(and (every (lambda (xe) (memq xe y)) x)
(every (lambda (ye) (memq ye x)) y)))
But it takes O(n*lg n) if you can compare the ordinality of addresses of
objects:
(define (set=? x y) (every eq? (sort x < address-of) (sort y < address-of)))
Jeff (home page http://www.emba.uvm.edu/~qobi)
From: Joe English
Subject: Re: C++ briar patch (Was: Object IDs are bad)
Date:
Message-ID: <5lr391$4hf@crl2.crl.com>
Jeffrey Mark Siskind <····@ai.emba.uvm.edu> wrote:
>
>There is another use for pointers. And this use requires order comparison
>between pointer, not just equality. Suppose you have two sets of objects.
>Represented as two lists of pointers to those objects. And you want to know
>whether the two sets are equal (i.e. have the same members). This takes O(n^2)
>if you don't have any way of ordering the objects [...]
>But it takes O(n*lg n) if you can compare the ordinality of addresses of
>objects [...]
Yes, this might be useful, but it won't work in C or C++.
('<=' on pointers is not necessarily transitive -- indeed, is
not even defined! -- unless both pointers point into the same
object.)
It also assumes that equality of addresses is the same thing
as equality of values for the objects in question, which is not
always the case. (For example, consider comparing two sets
of sets of objects ...)
--Joe English
········@crl.com
From: Fergus Henderson
Subject: Re: C++ briar patch (Was: Object IDs are bad)
Date:
Message-ID: <5lrak2$453@mulga.cs.mu.OZ.AU>
········@crl.com (Joe English) writes:
>Jeffrey Mark Siskind <····@ai.emba.uvm.edu> wrote:
>>
>>There is another use for pointers. And this use requires order comparison
>>between pointer, not just equality. Suppose you have two sets of objects.
>>Represented as two lists of pointers to those objects. And you want to know
>>whether the two sets are equal (i.e. have the same members). This takes O(n^2)
>>if you don't have any way of ordering the objects [...]
>>But it takes O(n*lg n) if you can compare the ordinality of addresses of
>>objects [...]
>
>Yes, this might be useful, but it won't work in C or C++.
>
>('<=' on pointers is not necessarily transitive -- indeed, is
>not even defined! -- unless both pointers point into the same
>object.)
You're right that `<=' can't be used for this purpose in C++, but
the C++ draft working paper also provides a template class specialization
`less<T*>' for comparing pointers in the standard library that _is_
guaranteed to be defined for all pointers and that is guaranteed to be
transitive; this class is used by the standard library class template `set'.
--
Fergus Henderson <···@cs.mu.oz.au> | "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh> | of excellence is a lethal habit"
PGP: finger ···@128.250.37.3 | -- the last words of T. S. Garp.
From: John R. "Bob" Bane
Subject: Re: C++ briar patch (Was: Object IDs are bad)
Date:
Message-ID: <5ls7ce$6sj@tove.cs.umd.edu>
In article <··········@crl2.crl.com> ········@crl.com (Joe English) writes:
>
>Jeffrey Mark Siskind <····@ai.emba.uvm.edu> wrote:
>>
>>There is another use for pointers. And this use requires order comparison
>>between pointer, not just equality. Suppose you have two sets of objects.
>> [... snip ...]
>
>Yes, this might be useful, but it won't work in C or C++.
And, it won't work in any system which has a GC that can move objects.
I believe this includes every commerical Common Lisp system these days.
Don't know about the Schemes.
Just to pad this out so the posting system won't complain: I'm digging
up some data to add to the "bloated apps would be more/less bloated in Lisp"
thread. I need to resurrect an old QIC cartridge dump to get real numbers
(not *real* data! *gasp*) on source and object code sizes.
--
Internet: ····@tove.cs.umd.edu
Voice: 301-352-5617
From: Fergus Henderson
Subject: Re: C++ briar patch (Was: Object IDs are bad)
Date:
Message-ID: <5ls9o1$q3r@mulga.cs.mu.OZ.AU>
····@cs.umd.edu (John R. "Bob" Bane) writes:
>········@crl.com (Joe English) writes:
>>
>>Jeffrey Mark Siskind <····@ai.emba.uvm.edu> wrote:
>>>
>>>There is another use for pointers. And this use requires order comparison
>>>between pointer, not just equality. Suppose you have two sets of objects.
>>> [... snip ...]
>>
>>Yes, this might be useful, but it won't work in C or C++.
Not true of C++, as I pointed out in another post.
>And, it won't work in any system which has a GC that can move objects.
Not true either. Allowing pointer ordering comparisons certainly does
constrain the GC implementation, but there are some garbage collectors
that move objects that will satisfy those constraints (i.e. that
preserve the relative ordering of pointers). For example, I think most
Prolog garbage collectors fall into this category, because of the need
to preserve the relative ordering of variables so that the results of
Prolog's ·@<' operator are consistent.
(Which is not to say that allowing pointer ordering comparisons is
necessarily a good idea: the constraints it imposes on the GC can
certainly make things harder for the GC implementor.)
--
Fergus Henderson <···@cs.mu.oz.au> | "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh> | of excellence is a lethal habit"
PGP: finger ···@128.250.37.3 | -- the last words of T. S. Garp.
From: Alan MacDonald
Subject: Re: C++ briar patch (Was: Object IDs are bad)
Date:
Message-ID: <5luk68$a08@mimas.brunel.ac.uk>
In article <··········@tove.cs.umd.edu> John R., ····@cs.umd.edu writes:
>In article <··········@crl2.crl.com> ········@crl.com (Joe English)
writes:
>>
>>Jeffrey Mark Siskind <····@ai.emba.uvm.edu> wrote:
>>>
>>>There is another use for pointers. And this use requires order
comparison
>>>between pointer, not just equality. Suppose you have two sets of
objects.
>>> [... snip ...]
>>
>>Yes, this might be useful, but it won't work in C or C++.
>
>And, it won't work in any system which has a GC that can move objects.
>I believe this includes every commerical Common Lisp system these days.
>Don't know about the Schemes.
This claim is too strong - it _will_ work in any system where the GC
preserves
object order. It's no problem to write a copying GC which does so,
although
generational GC might be out. Thus , equality type and non-determinism
issues
aside, it's no problem to write (say) an SML compiler with efficient sets
and
maps that do not require an explicit order parameter to be provided - one
does a structure comparison on immutable objects & pointer comparison
on refs - just as the built in equality predicate does.
In article <··········@mimas.brunel.ac.uk>,
Alan MacDonald <··············@brunel.ac.uk> wrote:
>In article <··········@tove.cs.umd.edu> John R., ····@cs.umd.edu writes:
> >In article <··········@crl2.crl.com> ········@crl.com (Joe English)
>writes:
> >>
> >>Jeffrey Mark Siskind <····@ai.emba.uvm.edu> wrote:
> >>>There is another use for pointers. And this use requires order
>comparison
> >>>between pointer, not just equality. Suppose you have two sets of
>objects.
> >>> [... snip ...]
> >>Yes, this might be useful, but it won't work in C or C++.
> >And, it won't work in any system which has a GC that can move objects.
> >I believe this includes every commerical Common Lisp system these days.
> >Don't know about the Schemes.
I think this is probably true of most or all commercial Common Lisp
systems.
It's definitely not true of all Schemes. There are several Schemes
that use mark-sweep, and RScheme uses a treadmillish fake-copying
real-time generational GC.
>This claim is too strong - it _will_ work in any system where the GC
>preserves
>object order. It's no problem to write a copying GC which does so,
>although
>generational GC might be out.
It depends on what you mean by "copying." The classic "copying"
GC's use a single-pass traversal of the reachable data that copies
objects as it goes. This kind of GC generally can't preserve
"genetic order", i.e., allocation ordering.
A mark-compact GC generally can. In this kind of GC, you do a marking
traversal of the reachable data, and then move the marked stuff into
a contiguous area of memory (typically by "sliding" compaction, where
successive objects in memory order are slid as far as possible toward
one end of memory, "squeezing out" the space between objects).
There was a paper on "genetic-order preserving" GC's in the last
IWMM '95 proceedings.
Relying on such a GC strategy definitely restricts the language
implementors' choices, not just in the area of GC, but also
in the area of persistent object stores that use pointer swizzling
so that they can address more data than will fit in the hardware
virtual address space.
(For example, RScheme uses a GC that doesn't normally relocate objects,
but has a persistent store that does.)
>Thus , equality type and non-determinism
>issues
>aside, it's no problem to write (say) an SML compiler with efficient sets
>and
>maps that do not require an explicit order parameter to be provided - one
>does a structure comparison on immutable objects & pointer comparison
>on refs - just as the built in equality predicate does.
How fast are structure comparisons in ML? This seems like a serious
performance issue in some cases. In general, I'd think that
structure comparisons could be expensive, and a lot of the time
you'd prefer simple pointer equivalence for efficiency.
--
| Paul R. Wilson, Comp. Sci. Dept., U of Texas @ Austin (······@cs.utexas.edu)
| Papers on memory allocators, garbage collection, memory hierarchies,
| persistence and Scheme interpreters and compilers available via ftp from
| ftp.cs.utexas.edu, in pub/garbage (or http://www.cs.utexas.edu/users/wilson/)
From: Bernhard Pfahringer
Subject: Re: C++ briar patch (Was: Object IDs are bad)
Date:
Message-ID: <5lr0lt$bf@borg.cs.waikato.ac.nz>
In article <···············@ai.emba.uvm.edu>,
Jeffrey Mark Siskind <····@ai.emba.uvm.edu> wrote:
>
>There is another use for pointers. And this use requires order comparison
>between pointer, not just equality. Suppose you have two sets of objects.
>Represented as two lists of pointers to those objects. And you want to know
>whether the two sets are equal (i.e. have the same members). This takes O(n^2)
>if you don't have any way of ordering the objects:
>
>(define (set=? x y)
> (and (every (lambda (xe) (memq xe y)) x)
> (every (lambda (ye) (memq ye x)) y)))
>
>But it takes O(n*lg n) if you can compare the ordinality of addresses of
>objects:
>
>(define (set=? x y) (every eq? (sort x < address-of) (sort y < address-of)))
>
But if efficiency is important, who might like to design your objects
in a way such that they are "markable" and then use the following
O(n) algorithm instead (no order comparison between pointers needed here):
(defun set=? (x y)
(loop with mark = (unique-mark)
for xe in x do (mark! xe mark)
finally (return (loop for ye in y
always (marked? ye mark)))))
--
Bernhard Pfahringer
···············@cs.waikato.ac.nz http://www.ai.univie.ac.at/~bernhard
From: Michael Greenwald
Subject: Are pointers useful? [Was: C++ briar patch (Was: Object IDs are bad)]
Date:
Message-ID: <michaelg.864256945@CS.Stanford.EDU>
Jeffrey Mark Siskind <····@ai.emba.uvm.edu> writes:
>···@mundook.cs.mu.OZ.AU (Fergus Henderson) writes:
>> As has been discussed in detail in this thread, the high-level concept
>> that pointers are useful for modelling is object identity.
>There is another use for pointers. And this use requires order comparison
>between pointer, not just equality.
Why use pointers for this? This seems dangerous in a language where
you can't depend upon the address of an object remaining constant.
Consider a compacting GC between the two SORTs in your example. Much
trouble. For this application (and EQ hashing etc.) I've always
defined my own INDEX or KEY accessor. Sometimes it is structured, but
often it's just storing and incrementing a per-class UID at object
creation.
If address is guaranteed invariant, you can of course use it as an
optimization.
From: Erik Naggum
Subject: Re: C++ briar patch (Was: Object IDs are bad)
Date:
Message-ID: <3072944679077944@naggum.no>
* ········@Bayou.UH.EDU
| Of course if there is something that I'm missing that makes this
| low level construct a necessity for a high level concept (OO) then
| I would appreciate it if you would enlighten me.
pointers are useful in many ways for many reasons, but the crucial question
is whether you should be able to do more than obtain and dereference them.
the view that the pointer is an arithmetic type is the culprit.
#\Erik
--
if we work harder, will obsolescence be farther ahead or closer?