On Fri, Apr 30, 2004 at 06:18:11PM +0800, Martin Jambon wrote:
> On Fri, 30 Apr 2004, Nicolas Cannasse wrote:
>
> > This is indeed interesting problem :
> > 1) The current implementation trade complexity to get safety : the first
> > call to next() is duplicating one the array so further modifications of the
> > Hashtbl will not cause any problem since we're working on a duplicate one.
> > That's expected behavior for an Enum.
> > 2) Other solution is to only iterate over the Hashtbl, incrementing the
> > index and throwing No_more_elements when we're out of the bounds of the
> > array. Then we need to add to the specs (as it's actually the case for many
> > languages) "results of iterating while modifying a mutable underlying data
> > structure are unspecified".
>
> But the client code that uses enums is not supposed to know this.
> Maybe a compromise would be to add one or several flags to the enum in
> order to test what is possible to do with this enum, and provide
> conversion functions to an enum such as a list enum, that would not have
> the same restrictions.
>
> let f hashtable =
> let e = Hashtbl.enum hashtable in (* solution 2) *)
> let e' =
> if Enum.is_mutable e then
> Enum.make_not_mutable e (* solution 1) *)
> else e in
> ...
>
(I'm not sure that "mutable" should be the default here,
but anyway...)
I'll use "safe" instead of "mutable" and "unsafe" instead
of immutable/not mutable since I think it more accurately
describes a property of the enumeration (rather than of
the underlying data structure).
Depending on whether you want run-time exceptions or
compile-time errors:
Solution 3:
let e'' =
Hashtbl.safe_enum e
let e''' =
Hashtbl.enum e
(the first one returning an enum which can handle
removal, but possibly taking more than O(1) to create)
If the underlying ADT doesn't support safe_enum you, of
course, just get compile-time errors.
If the underlying ADT can support safe_enum easily, you
can just provide safe_enum and let
ADT.enum=ADT.safe_enum (which obviously allowed as long
as ADT.safe_enum is O(1)).
Solution 4:
Add an "Enum.make_safe e" function which can
make the enumerator safe to use even if the
underlying ADT changes.
Of course, it would be necessary to add a
"make_safe" closure parameter to Enum.make, but this
could possibly be optional, allowing the ADT to
just provide one if possible and have Enum.make_safe
raise an Exception if no "make_safe" closure was
specified.
This moves potential errors to run-time which
may or may not be a good thing, depending on whether
you want the enum behavior to be run-time selectable.
(If only it were possible to implement some sort of
automatic copy-on-write semantics for values in O'Caml...
That would make a real solution sooo much easier. :))
I would prefer (3), but if there is a reluctance towards
adding any of this, I think the behavior of an enumeration
should just be left unspecified if the underlying data
structure changes. As long as it is apparent from the Enum
API documentation that this is the case, I don't think
that this is a real problem -- after all most languages
behave this way.
--
Bardur Arantsson
<bardur@xxxxxxxxxxxx>
<bardur@xxxxxxxxxxxxxxx>
- Strange women lying in ponds distributing swords is no basis
for a system of government.
Dennis | Monty Python and the Holy Grail
-------------------------------------------------------
This SF.Net email is sponsored by: Oracle 10g
Get certified on the hottest thing ever to hit the market... Oracle 10g.
Take an Oracle 10g class now, and we'll give you the exam FREE.
http://ads.osdn.com/?ad_id=3149&alloc_id=8166&op=click
|
