NICE Language Committee: arrays
From swissoft.h.provi.de!eiffel@Hannover.POP.DE Fri Oct 20 10:50:33 1995
Date: 20 Oct 1995 18:38:00 +0200
To: bertrand@eiffel.com
Cc: tynor@atlanta.twr.com
Subject: Re: VIP - some questions
X-Mailer: XP v3.02 R/C4131
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 8bit
Content-Length: 1174
Status: RO
X-Lines: 28
Dear Steve, dear Bertrand
Steve wrote:
> and 2) I cannot think of a reasonable way to implement
> resizable arrays in the face of possible sharing of the 'area'. Do we
> really want a user to be able to indirectly trash some other array
> handle mearly by resizing a different array handle that happens to share
> a common 'area'?
Oh boy! Your're right. Sorry. Even if the two objects which share the
same area don't modify (resize) it there remains a problem (in our
implementation): If one of the two dies, the area will be reclaimed
by the GC because one basic assumption about arrays is that two
different array objects do not share data areas (same with strings).
Actually, in Eiffel/S, an array (or string) has a reference to a
'special' object which in turn has a pointer to the actual storage
area - but that doesn't change the problem: The area is 'untagged'
i.e. the GC cannot mark it and therefore the GC will kill it as
soon as the unique special object to which it belongs dies.
With best regards,
Michael
SwisSoft, Michael Schweitzer Geismar Landstr. 16 D-37083 Goettingen
Fax : +49 551 770 35 44 email : eiffel@swissoft.h.provi.de
From swissoft.h.provi.de!eiffel@Hannover.POP.DE Fri Oct 20 14:30:06 1995
Date: 20 Oct 1995 22:16:00 +0200
To: bertrand@eiffel.com
Cc: tynor@atlanta.twr.com
Subject: Re: VIP - ...
X-Mailer: XP v3.02 R/C4131
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 8bit
Content-Length: 1174
Status: RO
X-Lines: 28
Dear Steve, dear Bertrand
Steve wrote:
> and 2) I cannot think of a reasonable way to implement
> resizable arrays in the face of possible sharing of the 'area'. Do we
> really want a user to be able to indirectly trash some other array
> handle mearly by resizing a different array handle that happens to share
> a common 'area'?
Oh boy! Your're right. Sorry. Even if the two objects which share the
same area don't modify (resize) it there remains a problem (in our
implementation): If one of the two dies, the area will be reclaimed
by the GC because one basic assumption about arrays is that two
different array objects do not share data areas (same with strings).
Actually, in Eiffel/S, an array (or string) has a reference to a
'special' object which in turn has a pointer to the actual storage
area - but that doesn't change the problem: The area is 'untagged'
i.e. the GC cannot mark it and therefore the GC will kill it as
soon as the unique special object to which it belongs dies.
With best regards,
Michael
SwisSoft, Michael Schweitzer Geismar Landstr. 16 D-37083 Goettingen
Fax : +49 551 770 35 44 email : eiffel@swissoft.h.provi.de
From tynor@atlanta.twr.com Fri Oct 20 08:56:22 1995
Date: Fri, 20 Oct 95 11:40:48 EDT
To: eiffel@swissoft.h.provi.de (Michael Schweitzer)
Cc: bertrand@eiffel.com, jcm@mstr.hgc.edu (Jim McKim)
Subject: Re: VIP - some questions
References: <5w8GnNJELdB@swissoft.h.provi.de>
Content-Length: 1418
Status: RO
X-Lines: 30
Michael wrote:
| True, it's artificial and I must admit that I don't have a better
| example. The point is that it's no more difficult to guarantee a
| little bit more. Since probably all implementations actually im-
| plement the rule I proposed it would be strange to say 'yes, they
| have consecutive values but you may not rely on this fact'.
I acquiesce. In fact, our implementation does implement in this way, and
I cannot think of a reason why future rewrites would have trouble
continuing to guarantee this.
| 'make_from_array':
|
| I think it should be possible to have both semantics: shared and
| non-shared. I feel that I'd probably use the non-shared version
I have no problem with supporting both from a conceptual point of view
-- there were two points to my message: 1) the semantics should be
unambiguous and 2) I cannot think of a reasonable way to implement
resizable arrays in the face of possible sharing of the 'area'. Do we
really want a user to be able to indirectly trash some other array
handle mearly by resizing a different array handle that happens to share
a common 'area'? Bertrand: How does the current ISE implementation
handle this? Or is this just a dangerous feature that users are
warned to not abuse (that is, "Once you call `make_from_array', never
`resize' either the original or the new array.").
Steve
(Back in Atlanta, but heading out the door for Savannah shortly)
From tynor@atlanta.twr.com Mon Oct 23 06:31:42 1995
Date: Mon, 23 Oct 95 08:53:00 EDT
To: eiffel@swissoft.h.provi.de (Michael Schweitzer)
Subject: Resizing `shared' arrays
References: <5wCGu13ELdB@swissoft.h.provi.de>
Cc: bertrand@eiffel.com, jcm@mstr.hgc.edu (Jim McKim)
Content-Length: 2866
Status: RO
X-Lines: 50
Michael wrote:
| > and 2) I cannot think of a reasonable way to implement
| > resizable arrays in the face of possible sharing of the 'area'. Do we
| > really want a user to be able to indirectly trash some other array
| > handle mearly by resizing a different array handle that happens to share
| > a common 'area'?
|
| Oh boy! Your're right. Sorry. Even if the two objects which share the
| same area don't modify (resize) it there remains a problem (in our
| implementation): If one of the two dies, the area will be reclaimed
| by the GC because one basic assumption about arrays is that two
| different array objects do not share data areas (same with strings).
|
| Actually, in Eiffel/S, an array (or string) has a reference to a
| 'special' object which in turn has a pointer to the actual storage
| area - but that doesn't change the problem: The area is 'untagged'
| i.e. the GC cannot mark it and therefore the GC will kill it as
| soon as the unique special object to which it belongs dies.
Resizing which results in a new object (i.e. the area could not be grown
but a new object had to be allocated and then copied) is probably the
worst case, but even less severe cases cause problems: Assume that we
resized such that the area _could_ be grown. So the base references to
the area are unchanged -- both ARRAY objects still point to the same
area. But say the resizing changed the lower bound. The elements in the
area are shifted up to accommodate the new elements. One ARRAY handle
knows this and can adjust whatever attributes it uses to keep track of
the "real" lower bound of the array. The other doesn't. It still thinks
the lower bound is the old lower bound. If I write to item 'n' from one
array, I'll be writing to a different element in the area than if I
write to the same 'n' from the other array.
The only ways I can see to possibly implement this are to 1) put all the
lower/upper bound information on the area object itself or 2) add a
collection of "clients" of the SPECIAL (or fellow sharers of the ARRAY)
so that dangerous modifications to the shared special can be
communicated to the other arrays sharing the special (and new features
for updating those clients ("area_resized (new_area: SPECIAL[T];
new_lower_bound : INTEGER; new_upper_bound: INTEGER)" ??? -- but these
are not how our ARRAY's have been traditionally implementated (the
`area' is a simple area of memory that knows little more than its
length), it's not how I understand Eiffel/S's implementation to be, and
it's not even how I understood the ISE implementation to be. So
Bertrand, please reveal your implementation strategy for "shared" areas
for ARRAY's. I note that your STRING class used to have some sort of
"share" feature (which we never implemented for all the above reasons),
so I assume you have some clever workaround for this quandry...
Steve
From jcm@mstr.hgc.edu Wed Sep 27 07:49:48 1995
Date: Wed, 27 Sep 1995 10:47:56 -0400
To: bertrand@eiffel.com
Subject: ARRAY spec
Cc: jcm@mstr.hgc.edu
X-Sun-Charset: US-ASCII
Content-Length: 3191
Status: RO
X-Lines: 86
Dear Bertrand,
You've been pretty quiet for the last few days wrt the ARRAY spec.
I'm sorry to keep bothering you on this issue, but I think at the moment
you hold the key to continuing progress. (I really am sorry. I can only
imagine how busy you are!)
In particular I need to
know your current feelings wrt 'valid_index'. Here's the discussion
I'd like to see you respond to. It's from my mail to the group on 9/20.
--------------------------------------------------------
>
> 4. Postcondition of `valid_index'
>
> Should not use equality, since this removes any flexibility for descendants
> to redefine the function.
>
> Should use `implies' rather than `='.
>
> See also point 8 below.
I'm assuming you mean the postcondition should read
stronger_valid_index: Result implies (lower <= i) and (i <= upper)
in which case, this is a serious concern that I'll address in point 8.
On the off chance you meant
weaker_valid_index: ((lower <= i) and (i <= upper)) implies Result
then I have no problem. Reinstating 'valid_index' as a precondition to
appropriate features is a cosmetic change, and you can skip all my ranting
below.
[...]
>
> 8. Preconditions on access and element change operations (item, put etc.)
>
> The ELKS says `valid_index (i)'. We don't see any need to spell
> out this property; it is more abstract and more flexible (see
> point 4 above) than the proposed replacement.
Hmm... Would you agree that it is imperative for clients to know which
indices are valid and which are not in order to correctly use 'put', 'item',
etc.? I only see three ways that clients can obtain such information.
1) From the short form of ARRAY.
2) From the long form of ARRAY (i.e the code).
3) By experimentation.
Both (2) and (3) seem undesirable and you seem to be ruling out (1). Am
I missing some fourth way?
I understand the need to maintain flexible preconditions (and other assertions)
so that descendants can redefine these appropriately, and I use this technique
myself, albeit mostly in deferred classes. But here it seems to me we are working
with a _very_ concrete class and surely direct clients of ARRAY will outnumber
folks who want to strengthen valid_index by thousands to one, if, indeed, there
are any of the latter at all.
OTOH, you certainly have a broader perspective on these issues than I, so
if you are not overwhelmed by the brilliance ;-) of my argument (in
particular if you have users that are actually strengthening valid_index
in descendants of ARRAY) let me propose a compromise. It's a bit awkward,
but it does serve the needs of both direct clients and descendants.
valid_index (i: INTEGER): BOOLEAN
-- Is i within the bounds of the array?
ensure
-- Implemented here as Result = (lower <= i) and (i <= upper)
-- May be redefined in descendants.
What do you think?
-----------------------------------
There are other open issues in that mail message as well, but this is
the one I see as critical. If you respond to any of these others I'll
consider it a bonus :-), but please, if at all possible, let's resolve
the 'valid_index' issue.
Best regards and thanks in advance,
-- Jim
From jcm@mstr.hgc.edu Wed Oct 11 09:06:42 1995
Date: Wed, 11 Oct 1995 12:04:35 -0400
To: bertrand@eiffel.com, fhart@atlanta.twr.com, tynor@atlanta.twr.com,
eiffel@swissoft.h.provi.de, eiffelgroup@eiffel.com
Subject: ARRAY
Cc: jcm@mstr.hgc.edu
Content-Type: X-sun-attachment
Status: RO
X-Lines: 351
Content-Length: 12676
----------
X-Sun-Data-Type: text
X-Sun-Data-Description: text
X-Sun-Data-Name: text
X-Sun-Charset: us-ascii
X-Sun-Content-Lines: 9
X-Sun-Content-Length: 171
Dear friends,
Attached is the latest version of the ARRAY class, based mainly on feedback from
Bertrand and Michael.
See most of you at OOPSLA next week!
Best,
-- Jim
----------
X-Sun-Data-Type: default
X-Sun-Data-Name: array.bertrand_and_fred.2
X-Sun-Charset: us-ascii
X-Sun-Content-Lines: 329
X-Sun-Content-Length: 12190
Preferred version of ARRAY. -- array.bertrand_and_fred.1 updated to
include further comments from Bertrand and Michael Schweitzer. In
particular, based on their comments, I have resolved some changes
and concerns in the previous version, and add some others.
Note: If you can see the name of this file in your mail reader, it is bertrand_and_fred.2. This is because the original message was sent only to
them. This is the second updating of that original.
I will be pestering all of you that I see next week at OOPSLA for your
opinions on this version. So be ready :-)! I'll also want to run some
preliminary ideas about STRING past you, if I can do so without trying
your patience too much.
One serious concern in the previous version was the definition
of 'valid_index', which just about everyone agreed should be the precondition
to 'enter', 'item' and such like. Bertrand and ISE felt that this feature
should be left unspecified to give flexibility to descendants, while Michael
and I felt that we needed to let clients
know _precisely_ when it was OK to enter new items, etc. I suggested a
compromise which Bertrand has accepted. It's included in this version.
See what you think. Also, please check that I've included 'valid_index'
in every precondition where it's appropriate.
A second serious concern was the definition of 'resize'. I've added a
second version of 'resize' that I believe satisfies both Bertrand and
Michael. There was some unresolved discussion about the names of
these features. See what you think of the ones I've chosen.
The third serious concern is the type of 'to_c'. I would like to decouple
the rest of the proposal from this issue as it seems to me to be something
you implementers must hash out. I'd hate to see the whole specification
held up because of disagreement about this one feature.
Specific areas of remaining concern can be found quickly by searching
for CONCERN. Changes made based on Michael's and Bertrand's latest
comments can be found by searching for CHANGE.
I still need desparately to hear from Steve and/or Fred on the proposal as
a whole.
Note: The only changes between this version and what was intended
in PELKS vintage95 is a new version of the 'make' routine and the
splitting of 'resize' into two features. Otherwise, all I'm proposing here
is a rigorous specification of the features in (I hope) a readable and
forthright way.
Class ARRAY
indexing
description: "Sequences of values, all of the same type or of a conforming
one, accessible through integer indices in a contiguous interval"
class interface
ARRAY [G]
-- Basic specification set: lower, upper, item
-- Auxiliary specification set: is_equal, valid_index
creation
make (min_index, max_index: INTEGER)
-- Allocate array; set index interval to
-- min_index .. max_index; set all values to default.
require
valid_indices: min_index <= max_index + 1
ensure
lower_initialized : lower = min_index
upper_initialized: upper = max_index
items_initialized: -- for_all i, lower..upper (item(i) = Void or else item(i) = item(i).default)
make_from_array (a: ARRAY [G])
-- Initialize from the items of `a', possibly sharing their representation.
-- (Useful in proper descendants of class ARRAY,
-- to initialize an array-like object from a manifest array.)
require
a_not_void: a /= Void
ensure
lower_initialized : lower = a.lower
upper_initialized: upper = a.upper
items_initialized: -- for_all i, lower..upper (item(i) = a.item(i))
CHANGE: In the header comment suggested by Eric and Bertrand, approved by
Michael.
feature -- Initialization
make (min_index, max_index: INTEGER)
-- Allocate array; set index interval to
-- min_index .. max_index; set all values to default.
require
valid_indices: min_index <= max_index + 1
ensure
lower_initialized : lower = min_index
upper_initialized: upper = max_index
items_initialized: -- for_all i, lower..upper (item(i) = Void or else item(i) = item(i).default)
make_from_array (a: ARRAY [G])
-- Initialize from the items of `a', possibly sharing their representation.
-- (Useful in proper descendants of class ARRAY,
-- to initialize an array-like object from a manifest array.)
require
a_not_void: a /= Void
ensure
lower_initialized : lower = a.lower
upper_initialized: upper = a.upper
items_initialized: -- for_all i, lower..upper (item(i) = a.item(i))
CHANGE: In the header comment suggested by Eric and Bertrand, approved by
Michael.
feature -- Access
entry (i: INTEGER): G
-- Entry at index i.
-- (Redefinable synonym for item and infix "@".)
require
valid_index: valid_index( i )
CHANGE: Precondition changed as promised in the intro. Header comment changed
slightly (Michael's suggestion) so as not to be redundant with the
precondition.
frozen item (i: INTEGER): G
-- Entry at index i.
require
valid_index: valid_index( i )
CHANGE: Precondition changed as promised in the intro. Header comment changed
slightly (Michael's suggestion) so as not to be redundant with the
precondition.
frozen infix "@" (i: INTEGER): G
-- Entry at index i.
require
valid_index: valid_index( i )
ensure
definition: Result = item( i )
CHANGE: Precondition changed as promised in the intro. Header comment changed
slightly (Michael's suggestion) so as not to be redundant with the
precondition.
feature -- Measurement
count: INTEGER
-- Number of available indices
ensure
definition: Result = upper - lower + 1
CONCERN: ISE sees no need for the postcondition, as the same info is
available in the invariant. For reasons detailed in an earlier
mail message, I feel it's important to keep the assertion here, even
if in some implementations it becomes a comment. Michael has agreed that
parameterless queries do sometimes need asseritons, but I don't think
he's blessed this particular instance. Steve feels that some repetition
between the routine contracts and the invariant is defensible, but also
has not blessed this particular case.
I do feel strongly that the spec should not be influenced by implementation
details such as the choice of implementing 'count' as a function or a
variable.
lower: INTEGER
-- Minimum index
upper: INTEGER
-- Maximum index
feature -- Comparison
is_equal (other: like Current): BOOLEAN
-- Is array made of the same items as other?
-- (Redefined from GENERAL.)
require else -- from GENERAL
other_not_void: other /= Void
ensure
definition: Result = (lower = other.lower) and (upper = other.upper) --and for_all i, lower..upper (item( i ) = other.item( i ))
ensure then -- from GENERAL
consistent: standard_is_equal (other) implies Result;
same_type: Result implies same_type (other);
symmetric: Result implies other.is_equal (Current)
feature -- Status report
valid_index (i: INTEGER): BOOLEAN
-- Is i within the bounds of the array?
ensure
-- Defined here as Result = (lower <= i) and (i <= upper)
-- May be redefined in descendants.
CHANGE: As noted above, this is the compromise suggested by me and approved
by Bertrand. What do the rest of you think?
feature -- Element change
enter (v: like item; i: INTEGER)
-- Replace i-th entry, if in index interval, by v.
-- (Redefinable synonym for put.)
require
valid_index: valid_index( i )
ensure
stable_lower: lower = old lower
stable_upper: upper = old upper
new_item: item(i) = v
stable_before_i: -- for_all n, lower..(i-1) (item(n) = old item(n))
stable_after_i: -- for_all n, (i+1)..upper (item(n) = old item(n))
CHANGE: Precondition changed as promised in the intro.
CHANGE: ISE proposed the type of the first argument be 'like item' and Michael
agreed. Further comments?
force (v: like item; i: INTEGER)
-- Assign item v to i-th entry.
-- Always applicable: resize the array if i falls out of
-- currently defined bounds; preserve existing items.
ensure
new_item: item (i) = v;
new_lower: lower = i.min( old lower )
new_upper: upper = i.max( old upper )
new_low_items: -- for_all n, (i+1)..(old lower-1) (item(n) = Void or else item(n) = item(n).default)
new_high_items: -- for_all n, (old upper+1)..(i-1) (item(n) = Void or else item(n) = item(n).default)
in_between: -- for_all n, old lower..old upper (i = n or else item(n) = old item(n))
frozen put (v: like item; i: INTEGER)
-- Replace i-th entry, if in index interval, by v.
require
valid_index: valid_index( i )
ensure
stable_lower: lower = old lower
stable_upper: upper = old upper
new_item: item(i) = v
stable_before_i: -- for_all n, lower..(i-1) (item(n) = old item(n))
stable_after_i: -- for_all n, (i+1)..upper (item(n) = old item(n))
feature -- Resizing
accommodate (min_index, max_index: INTEGER)
-- Rearrange array so that it can accommodate
-- indices down to min_index and up to max_index.
-- Do not lose any previously entered item.
require
valid_indices: min_index <= maxindex
ensure
new_lower: lower = min_index.min(old lower)
new_upper: upper = max_index.max(old upper)
stable_items: -- for_all i, (old lower)..(old upper) (item(i) = old item(i))
new_low_items: -- for_all i, lower..(old lower - 1) (item(i) = Void or else item(i) = item(i).default)
new_high_items: -- for_all i, (old upper + 1)..upper (item(i) = Void or else item(i) = item(i).default)
CHANGE: This is ISE's version of 'resize' renamed as suggested by Bertrand.
CONCERN: The precondition is unnecessary, should we dump it?
size(min_index, max_index: INTEGER)
-- Resize the array to the given indices. Do not lose
-- any item that is in the intersection of the closed
-- intervals [lower, upper] and [minindex, maxindex].
require
valid_indices: min_index <= maxindex
ensure
new_lower: lower = minindex
new_upper: upper = maxindex
stable_items: -- for_all i, lower..upper
((old lower <= i and i <= old upper) implies item( i ) = old item( i ))
new_items: -- for_all i, lower..upper
(i < old lower or i > old_upper) implies
(item( i ) = Void or else item( i ) = item(i).default))
CHANGE: This is Michael's and (I believe Tower's) version of 'resize' renamed.
When 'size' is used as a verb it means "to make a particular size; to
bring to a proper or suitable size." If we only renamed one of these the
other implementers' customers would be driven to distraction.
CONCERN: Since we allow empty arrays, should we weaken the precondition to
min_index <= max_index + 1?
NOTE: Once a rigorous specification for 'resize' became available it was
immediately clear that different implementers had been interpreting it
differently. In addition, it was easy to accommodate (so to speak)
both versions. Similar benefits were obtained in homing in on the definition
of 'make' in discussions with Roger Browne. I feel good!
feature -- Conversion
to_c: POINTER
-- Address of actual sequence of values,
-- for passing to external (non-Eiffel) routines.
CONCERN: ISE would like the type of this feature to be ANY. Again,
let me plead for moving the rest of the spec forward, even if this
issue cannot be resolved in the immediate future.
feature -- Duplication
copy (other: like Current)
-- Reinitialize by copying all the items of other.
-- (This is also used by clone.)
-- (From GENERAL.)
require else --from GENERAL
other_not_void: other /= Void
ensure then -- from GENERAL
is_equal: is_equal (other)
invariant
consistent_size: count = upper - lower + 1;
nonnegative_count: count >= 0
valid_bounds: lower <= upper + 1
item_equals_at: -- for_all i, lower..upper (item( i ) = Current @ i)
CHANGE: I've removed the assertion labeled 'valid_indices'.
end
From jcm@mstr.hgc.edu Mon Oct 23 08:34:17 1995
Date: Mon, 23 Oct 1995 11:32:10 -0400
To: eiffel@swissoft.h.provi.de, tynor@atlanta.twr.com
Subject: Re: Resizing `shared' arrays
Cc: bertrand@eiffel.com, jcm@mstr.hgc.edu
X-Sun-Charset: US-ASCII
Content-Length: 1510
Status: RO
X-Lines: 38
> From tynor@atlanta.twr.com Mon Oct 23 09:29:11 1995
> To: eiffel@swissoft.h.provi.de (Michael Schweitzer)
> Subject: Resizing `shared' arrays
> Cc: bertrand@eiffel.com, jcm@mstr.hgc.edu (Jim McKim)
> Content-Length: 2866
> X-Lines: 50
>
[.. Steve and Michael discuss the pitfalls of having 'make_from_array'
share the underlying area of the array, especially wrt resizing ..]
A couple/three quick comments. I'll have more to say later in the week
when I can snag an hour or two to assimilate my discussions with Steve
and Bertrand at OOPSLA. (Thank you both for spending so much time with me,
BTW. Much appreciated.)
1) I only seem to be getting about every third message in this thread :-(.
2) We do need to hear from Bertrand as to whether the 'sharing' version is
important to ISE.
3) One point Bertrand made at OOPSLA is that this feature (as the comment
implies) is specifically for making an array object from a manifest array
(not sure why the part about descendants is important). In this case there
seems to be no _problem_ sharing 'area', but I don't know whether it's
somehow _important_ to share the 'area'. I would _prefer_ to settle this
with a rigorous spec you're all happy with, before we go to Committee, but
one kludgy possibility is to include a comment to the effect that this
feature is designed to be used with manifest arrays and that unpredictable
behavior (e.g. sharing of underlying representation) may result otherwise.
>
> Steve
>
Best,
-- Jim
|
