ocaml-lib-devel — Developer's mailing list

Re: [Ocaml-lib-devel] About iterators and enums

[Bardur A. <oca...@sc...>]

On Sun, May 02, 2004 at 12:20:16PM +0200, Nicolas Cannasse wrote:

> > On Fri, Apr 30, 2004 at 09:16:44AM +0200, Nicolas Cannasse wrote:
> > > > Stay tuned; my missinglib for OCaml will support Python-style
> > > > interpolation very shortly....   This should render it fully
> compatible
> > > > with Python's SafeConfigParser, and give it some extra features to
> boot.
> > > > That is, OCaml's library can parse files generated by Python's save(),
> > > > and vice-versa, and get the same results out of them.
> > > >
> > > > -- John
> > >
> > > Could you interface it with IO ? so one can read and write config files.
> > > What is exactly "interpolation" ?
> >
> > It currently works with standard channels, but yes, I could do that.
> > (I wouldn't feel comfortable doing it until IO is in a released Extlib,
> > though).
> >
> > Interpolation means inserting sprintf-like statements in the config file
> > to refer to other values in the file or to values in a hash table
> > supplied by the programmer.  For instance:
> >
> > [DEFAULTS]
> > photos = /home/foo/photos
> >
> > [album1]
> > path = %(photos)s/firstalbum
> > copyright = $(copyright)s
> >
> > In this instance, path will expand to /home/foo/photos/firstalbum and
> > copyright will expand to some value that the programmer passes in to
> > ConfigParser in a Hashtable (with key "copyright").  Or, if the
> > programmer doesn't do that, it will cause an error.
> >
> > This interpolation is compatible with Python's SafeConfigParser and will
> > be optional.
> 
> Thank you for the information.
> 
> Here's my opinion about ConfigParser : it's nice to
> provide some config data file format handling, it's also
> nice to provide Python compatibility. But I'm confused
> about what's the goal of this library : if this file
> format is supposed to store app config data then I don't
> see the point of having compatibility with Python. Since
> the config data is app-specific, the only case that could
> be interesting to have compatibility is to have a big
> application, some parts written in OCaml and some other
> parts in Python, with both accessing the same
> configuration data : that's not general case !

I don't what his reasons are for wanting Python
compatibility; but mine are very simple:

- The format works!
- Users don't want to have to learn a different format.
- There is *no* good reason *NOT* to have compatibility.

> 
> Now if you want to get compatibility, that's maybe
> because you don't only want this file to store "config"
> data but data only.
>
> And for this purpose I think XML is a far better
> description format since it allows recursivity, proving
> using a DTD or Schema, and is widely used and available
> in a lot more langages than Ocaml and Python.

XML is overkill for almost everything people like to put
into XML these days -- it's also much much harder to parse
(even if you have a relatively simple DTD I've found that
one tends to gets bogged down by detail; but maybe that's
just because of the XML parsers I've tried (yes, that
includes PXP)).

... not that I'm saying that storing actual app. data (as
opposed to app. configuration data) in .ini is a good idea
either. But that is beside the point as I don't think
anyone is suggesting that.

> Now if your goal is really to store app config data then
> I don't undestand why to keep Python compatibility, and
> why actually not to represent the data into XML ?
> The .INI file format is far from being the best around.

Granted, but you're overlooking its usefulness in
situations where you don't NEED any more features than
.INI has. XML is utter overkill for something so simple as
configuration data which is not hierarchical in nature.
And even *if* your configuration data is hierarchical, XML
has many drawbacks:

- Contrary to popular belief, XML is not user-editable in
the same way that any sane configuration format is
user-editable:

    - XML is incredibly verbose; take a look
    a typical XML config versus e.g. the sshd config file.
    Then come back and suggest XML as a configuration file
    format. It's very hard to seperate the wheat from the
    chaff in your typical XML file. This makes it hard to
    edit.

    - There are special rules for symbols like "&", "<"
    and ">", "&", etc. Users do not want to have to use
    special "escaped" entities when they are not actually
    necessary.
    
    (see also next section)
    
- XML is way more complex than it needs to be: Take a look
at YAML (http://www.yaml.org/). It does the same thing
everybody seems to want XML for and does it in a much
simpler, neater *and* more user-friendly way.

(more, but I can't bothered to list all of it...)

> The average user, either knows XML and will be able to
> edit by-hand or will not even try to edit and modify your
> config file, unless you provide him a nice GUI.
> 

Nonsense. To be able to edit *YOUR* XML the user must know
at least two very non-obvious things:

1) Proper nesting rules for *your* DTD. (Which of course
varies from app to app, so you can't hide behind the
"everbody knows XML" bit). That means that they need to
know how to read DTDs, or that you have to provide a layman's
explanation of the format -- more work for you (for no
good reason since .ini/yaml is much easier for both you *and*
your users).

2) Allowable attribute values (which cannot usually be
specified in the DTD anyway -- so the DTD model fails
here)

A .ini is trivially learned by comparison. Even if you sat
a complete beginner down in front of a computer, they
would be able to change the settings (given a text editor
:)).

Another counter-point: Not all apps have GUIs, but want
users to be able to set configuration settings without
having to understand XML. What are you going to then?

(I could go on and on about the failings of XML, but
you'll probably get tired of reading it, so I'll just stop
here...)

-- 
Bardur Arantsson
<ba...@im...>
<ba...@sc...>

- With this weapon I can expose fictional characters and bring
about sweeping reforms!
                                        Zippy | Zippy the Pinhead

Re: [Ocaml-lib-devel] Re: What is SF-ExtLib exactly?

[Nicolas C. <war...@fr...>]

> This is now updated , the only files remaining under plain LGPL are
OcamlDBI
> ones. I'm waiting for the answer of its author in order to make the
licence
> changes.

Changed confirmed, files commited.

NC

Re: [Ocaml-lib-devel] Re: What is SF-ExtLib exactly?

[Nicolas C. <war...@fr...>]

> > If someone could tell what exactly to put into the files in order to =
be
> > consistent with the wanted licence, I'll do the changes before the
upcoming
> > release.
>
> In every file, change
>
>   * version 2.1 of the License, or (at your option) any later version.
>
> to
>
>   * version 2.1 of the License, or (at your option) any later version,
>   * with the special exception on linking described in file <filename>.
>
> and make sure that you only do this on files you have written yourself,=
 or
> where you have a written statement by the original author authorizing t=
he
> change. Look at the ocaml distribution for inspiration about how to fil=
l
> "filename".
>
> Tsch=FCss, Florian Hars.

Thanks,
This is now updated , the only files remaining under plain LGPL are Ocaml=
DBI
ones. I'm waiting for the answer of its author in order to make the licen=
ce
changes. Other changes were made without contacting other contributors,
since only the headers were wrong, everybody agreed to release under the
same licence as Ocaml stdlib when the extlib starts.

Regards,
Nicolas Cannasse

Re: [Ocaml-lib-devel] About iterators and enums

[Nicolas C. <war...@fr...>]

> On Fri, Apr 30, 2004 at 09:16:44AM +0200, Nicolas Cannasse wrote:
> > > Stay tuned; my missinglib for OCaml will support Python-style
> > > interpolation very shortly....   This should render it fully
compatible
> > > with Python's SafeConfigParser, and give it some extra features to
boot.
> > > That is, OCaml's library can parse files generated by Python's save(),
> > > and vice-versa, and get the same results out of them.
> > >
> > > -- John
> >
> > Could you interface it with IO ? so one can read and write config files.
> > What is exactly "interpolation" ?
>
> It currently works with standard channels, but yes, I could do that.
> (I wouldn't feel comfortable doing it until IO is in a released Extlib,
> though).
>
> Interpolation means inserting sprintf-like statements in the config file
> to refer to other values in the file or to values in a hash table
> supplied by the programmer.  For instance:
>
> [DEFAULTS]
> photos = /home/foo/photos
>
> [album1]
> path = %(photos)s/firstalbum
> copyright = $(copyright)s
>
> In this instance, path will expand to /home/foo/photos/firstalbum and
> copyright will expand to some value that the programmer passes in to
> ConfigParser in a Hashtable (with key "copyright").  Or, if the
> programmer doesn't do that, it will cause an error.
>
> This interpolation is compatible with Python's SafeConfigParser and will
> be optional.

Thank you for the information.

Here's my opinion about ConfigParser : it's nice to provide some config data
file format handling, it's also nice to provide Python compatibility. But
I'm confused about what's the goal of this library : if this file format is
supposed to store app config data then I don't see the point of having
compatibility with Python. Since the config data is app-specific, the only
case that could be interesting to have compatibility is to have a big
application, some parts written in OCaml and some other parts in Python,
with both accessing the same configuration data : that's not general case !

Now if you want to get compatibility, that's maybe because you don't only
want this file to store "config" data but data only. And for this purpose I
think XML is a far better description format since it allows recursivity,
proving using a DTD or Schema, and is widely used and available in a lot
more langages than Ocaml and Python. Now if your goal is really to store app
config data then I don't undestand why to keep Python compatibility, and why
actually not to represent the data into XML ? The .INI file format is far
from being the best around. The average user, either knows XML and will be
able to edit by-hand or will not even try to edit and modify your config
file, unless you provide him a nice GUI.

Regards,
Nicolas Cannasse

Re: [Ocaml-lib-devel] properties of symbols

[Brian H. <bh...@sp...>]

On Wed, 28 Apr 2004, Nicolas Cannasse wrote:

> > On Sun, 25 Apr 2004, Henri DF wrote:
> >
> > > thanks for the pointer. i (naively) thought that anything which "takes
> > > away
> > > polymorphism" could only improve efficiency, and that this would extend
> to
> > > functors.
> > >
> > > [OT] i wonder when there is ever a case for functors then..
> > >
> [...]
> > On my wish list: int, bool, float, and char modules.  These would take a
> > lot of the pain out of using functors.
> 
> You forgot :
> (int * int)
> (string * int list)
> (int * char * bool)
> ...
> ...
> ...
> Since there is so much (infinity) core-types, we can't declare module types
> for all of them, so set is broken :'(
> 

This is a slipery slope argument, which is false if there is a clear break 
point, a point where taking the next step does *not* automatically follow 
from the previous steps.  In terms of proof by induction, if is a point 
where step n+1 is not necessarily true simply because step n is true, the 
proof doesn't work.

Now, there is a break point between int and int*int.  A tuple is a data
structure, along with a list, an array, and a tree.  When you say the data
structure outloud, you say the word "of"- it's a tuple *OF* an int and an
int.  The types I listed are "simple" types, not comprised of other types.  
You don't use the word "of" in describing them.  

Well, string is a gray area by this definition.  The phrase "string of
char" makes some sense.  But I note that the standard lib already provides
it for us- the String module works.  Try it:
Module StringSet = Set.Make(String);;

So that's my disproof.  Simply because we provide int, float, char, and 
bool modules, this doesn't imply that we should provide list, array, or 
tuple modules.

-- 
"Usenet is like a herd of performing elephants with diarrhea -- massive,
difficult to redirect, awe-inspiring, entertaining, and a source of
mind-boggling amounts of excrement when you least expect it."
                                - Gene Spafford 
Brian

Re: [Ocaml-lib-devel] About iterators and enums

[Bardur A. <oca...@sc...>]

On Fri, Apr 30, 2004 at 02:06:46PM +0200, Nicolas Cannasse wrote:

> > > > 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.
> > > 
> > > This already exists :)
> > 
> > Heh, well, almost...
> > 
> > > Simply call Enum.force() in order to fully evaluate your enumeration,
> > > without actually loosing elements.
> > > 
> > 
> > But wouldn't that build an actual "list" (and thus also
> > require memory for all the enumeration elements),
> > something which could *possibly* be avoided by letting the
> > ADT create the "safe" enumeration...? (And obviously, it
> > would also cause all lazy values in the enumeration to be
> > evaluated, something which may not be desirable...)
> 
> The good and more general way to create a "safe" enumeration is :
> a) to duplicate your mutable data structure 
> b) to call enum on it :)

If your data structure is not clonable (e.g. a Dbm
database), but _could_ be iterated through safely (one
possibility is to just create a copy of the list of keys
and ignore any missing entries), then you *cannot* clone
the data structure, yet you *cannot* assume that Enum will
return a "safe" enumeration either (because of the changed
"specification").

This makes enum less useful in my eyes.

> Having two implementatioons of  to_enum function is not desirable.

Um... you wouldn't need to if you where to go with what I
called solution 3. Modules could **optionally** provide a
safe_enum function which creates a "safe" enum. (Of
course, these should be added to all the ExtLib ADTs where
practical).

-- 
Bardur Arantsson
<ba...@im...>
<ba...@sc...>

- So... humans have easily-injured knees. My race will find this
information very useful indeed!
                                                 Morbo | Futurama

Re: [Ocaml-lib-devel] About iterators and enums

[Bardur A. <oca...@sc...>]

On Fri, Apr 30, 2004 at 08:25:15PM +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.
> >
> >
> > You're wrong.
> > If it's part of Enums specs then of course you're supposed to know this.
> 
> I thought that the advantage of enums was that you don't have to worry
> about the underlying data type.
> 

You still don't. You simply cannot EVER assume that it
will work to enumerate some data structure while modifying
it.

-- 
Bardur Arantsson
<ba...@im...>
<ba...@sc...>

Knowledge shared is power lost.
                                                 Alistair Crowley

Re: [Ocaml-lib-devel] Re: What is SF-ExtLib exactly?

[Florian H. <ha...@bi...>]

John Goerzen wrote:
> I don't really understand how OCaml is different from statically-linking
> in C.  This is not a new problem.

OK, the I stand partially corrected: the linker is a bit more liberal than my 
subjective impression was after chasing too many chains of "File B and A make 
inconsistent assumptions over interface A" and then the same with C and B and 
so on... You can make some changes to the library and still relink, so 
technically you can in fact comply with the cited section from the LGPL.

But there is a large class of changes to a library that keep the interface in 
the definitions files (as of LGPL 6.a, last sentence) unchanged and still make 
relinking impossible, so you might still be in violation of the LGPL if you 
don't distribute the source, depending on how much money the opposite side can 
pay for a lawyer.

Here is a trivial example, first we compile a library and a program that uses it:

$ cat foobar.mli
val print_foobar: unit -> unit
$ cat foobar.ml
let print_foobar x = print_endline "foobar"
$ cat use.ml
let _ = Foobar.print_foobar ()
$ ocamlopt -a foobar.mli foobar.ml -o foobar.cmxa
$ ocamlopt  foobar.cmxa use.ml -o run
$ ./run
foobar

Now we change the library slightly by factoring some functionality into a 
helper function without changing the visible interface and relink with the cmx 
of the application:

$ cat foobar.ml
let foobar x = "foobar"
let print_foobar x = print_endline (foobar x)
$ ocamlopt -a foobar.mli foobar.ml -o foobar.cmxa
$ ocamlopt  foobar.cmxa use.cmx -o run
Files use.cmx and foobar.cmxa
make inconsistent assumptions over implementation Foobar

This is different form C, since the C linker does not care about additional 
symbols in the library, and a fortiori not about symbols that are not visible 
in the library. This behaviour of the C linker is written into the LGPL and it 
is disputable whether the ocaml linker has the required properties to allow 
releasing a work that uses a library without source. If you want to be safe, 
you cannot rely on it (look at the IBM policy: never ever use LGPL code that is 
statically linked, just to be safe). Copyright law is ugly.

Yours, Florian.

Re: [Ocaml-lib-devel] Re: What is SF-ExtLib exactly?

[Florian H. <ha...@bi...>]

Nicolas Cannasse wrote:
> If someone could tell what exactly to put into the files in order to be
> consistent with the wanted licence, I'll do the changes before the upco=
ming
> release.

In every file, change

  * version 2.1 of the License, or (at your option) any later version.

to

  * version 2.1 of the License, or (at your option) any later version,
  * with the special exception on linking described in file <filename>.

and make sure that you only do this on files you have written yourself, o=
r=20
where you have a written statement by the original author authorizing the=
=20
change. Look at the ocaml distribution for inspiration about how to fill=20
"filename".

Tsch=FCss, Florian Hars.

Re: [Ocaml-lib-devel] About iterators and enums

[John G. <jgo...@co...>]

On Fri, Apr 30, 2004 at 09:16:44AM +0200, Nicolas Cannasse wrote:
> > Stay tuned; my missinglib for OCaml will support Python-style
> > interpolation very shortly....   This should render it fully compatible
> > with Python's SafeConfigParser, and give it some extra features to boot.
> > That is, OCaml's library can parse files generated by Python's save(),
> > and vice-versa, and get the same results out of them.
> > 
> > -- John
> 
> Could you interface it with IO ? so one can read and write config files.
> What is exactly "interpolation" ?

It currently works with standard channels, but yes, I could do that.
(I wouldn't feel comfortable doing it until IO is in a released Extlib,
though).

Interpolation means inserting sprintf-like statements in the config file
to refer to other values in the file or to values in a hash table
supplied by the programmer.  For instance:

[DEFAULTS]
photos = /home/foo/photos

[album1]
path = %(photos)s/firstalbum
copyright = $(copyright)s

In this instance, path will expand to /home/foo/photos/firstalbum and
copyright will expand to some value that the programmer passes in to
ConfigParser in a Hashtable (with key "copyright").  Or, if the
programmer doesn't do that, it will cause an error.

This interpolation is compatible with Python's SafeConfigParser and will
be optional.

-- John

Re: [Ocaml-lib-devel] About iterators and enums

[Martin J. <mar...@em...>]

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.
>
>
> You're wrong.
> If it's part of Enums specs then of course you're supposed to know this.

I thought that the advantage of enums was that you don't have to worry
about the underlying data type.


Martin (still waiting for any kind of code using enums)

Re: [Ocaml-lib-devel] About iterators and enums

[Nicolas C. <war...@fr...>]

> > > 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.
> > 
> > This already exists :)
> 
> Heh, well, almost...
> 
> > Simply call Enum.force() in order to fully evaluate your enumeration,
> > without actually loosing elements.
> > 
> 
> But wouldn't that build an actual "list" (and thus also
> require memory for all the enumeration elements),
> something which could *possibly* be avoided by letting the
> ADT create the "safe" enumeration...? (And obviously, it
> would also cause all lazy values in the enumeration to be
> evaluated, something which may not be desirable...)

The good and more general way to create a "safe" enumeration is :
a) to duplicate your mutable data structure 
b) to call enum on it :)
Having two implementatioons of  to_enum function is not desirable.

Regards,
Nicolas Cannasse

Re: [Ocaml-lib-devel] About iterators and enums

[Bardur A. <oca...@sc...>]

On Fri, Apr 30, 2004 at 01:41:22PM +0200, Nicolas Cannasse wrote:

> > 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.
> 
> This already exists :)

Heh, well, almost...

> Simply call Enum.force() in order to fully evaluate your enumeration,
> without actually loosing elements.
> 

But wouldn't that build an actual "list" (and thus also
require memory for all the enumeration elements),
something which could *possibly* be avoided by letting the
ADT create the "safe" enumeration...? (And obviously, it
would also cause all lazy values in the enumeration to be
evaluated, something which may not be desirable...)

-- 
Bardur Arantsson
<ba...@im...>
<ba...@sc...>

- There's nothing quite like a shorn scrotum. It's breathtaking,
really. I suggest you try it yourself.
                           Dr. Evil | Austin Powers In Goldmember

Re: [Ocaml-lib-devel] About iterators and enums

[Nicolas C. <war...@fr...>]

> 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.

This already exists :)
Simply call Enum.force() in order to fully evaluate your enumeration,
without actually loosing elements.

NC

Re: [Ocaml-lib-devel] About iterators and enums

[Bardur A. <oca...@sc...>]

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
<ba...@im...>
<ba...@sc...>

- Strange women lying in ponds distributing swords is no basis
for a system of government.
                         Dennis | Monty Python and the Holy Grail

Re: [Ocaml-lib-devel] About iterators and enums

[Nicolas C. <war...@fr...>]

> > 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.


You're wrong.
If it's part of Enums specs then of course you're supposed to know this.

Nicolas Cannasse

Re: [Ocaml-lib-devel] About iterators and enums

[Martin J. <mar...@em...>]

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
  ...


Martin

Re: [Ocaml-lib-devel] About iterators and enums

[Nicolas C. <war...@fr...>]

> More precisely: we can record a reference to the index of the current
> bucket and to the tail of the current bucket. But if the table is
> resized during the iteration, the result will be problematic.
> This problem already exists since you should not modify the table from
> inside the Hashtbl.fold process.
> Probably I have a bad perception of enums, but my intuition tells me that
> you should be able to safely iterate over the elements of the enumeration
> without any specific knowledge of the actual container. Or in other words,
> if a function takes an enum as an argument, it should be able to know what
> is possible to do exactly. This is different from manipulating the
> container directly and apply the specific fold function that comes with
> specific restrictions.
> If enums could make the containers read-only, why not, but I cannot
> imagine how this could be done in an elegant manner.

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".

Nicolas Cannnasse

Re: [Ocaml-lib-devel] About iterators and enums

[Martin J. <mar...@em...>]

On Fri, 30 Apr 2004, Martin Jambon wrote:

> On Fri, 30 Apr 2004, Bardur Arantsson wrote:
>
> > I (and others, apparently :)) think it's easier to just
> > use Enums and not have to even think about such things. As
> > an application developer, not having to care about
> > implementation details of the language is IMHO always a
> > good sign that you've found a worthwhile abstraction.
>
> Great, but it is not possible to provide enums for every data structure.
> I would like to hear your opinion on how to define and implement enums
> over OCaml's hash tables.

More precisely: we can record a reference to the index of the current
bucket and to the tail of the current bucket. But if the table is
resized during the iteration, the result will be problematic.
This problem already exists since you should not modify the table from
inside the Hashtbl.fold process.
Probably I have a bad perception of enums, but my intuition tells me that
you should be able to safely iterate over the elements of the enumeration
without any specific knowledge of the actual container. Or in other words,
if a function takes an enum as an argument, it should be able to know what
is possible to do exactly. This is different from manipulating the
container directly and apply the specific fold function that comes with
specific restrictions.
If enums could make the containers read-only, why not, but I cannot
imagine how this could be done in an elegant manner.


Martin

Re: [Ocaml-lib-devel] About iterators and enums

[Martin J. <mar...@em...>]

On Fri, 30 Apr 2004, Bardur Arantsson wrote:

> I (and others, apparently :)) think it's easier to just
> use Enums and not have to even think about such things. As
> an application developer, not having to care about
> implementation details of the language is IMHO always a
> good sign that you've found a worthwhile abstraction.

Great, but it is not possible to provide enums for every data structure.
I would like to hear your opinion on how to define and implement enums
over OCaml's hash tables.


Martin

Re: [Ocaml-lib-devel] About iterators and enums

[Bardur A. <oca...@sc...>]

On Fri, Apr 30, 2004 at 04:26:17PM +0800, Martin Jambon wrote:

> On Fri, 30 Apr 2004, Bardur Arantsson wrote:
> 
> > On Fri, Apr 30, 2004 at 04:14:48PM +0800, Martin Jambon wrote:
> >
> > > On Thu, 29 Apr 2004, Nicolas Cannasse wrote:
> > >
> > [--snip--]
> > > > > Please give us some examples.
> > > >
> > > > The rational of Enums is the following :
> > > > - we have increasing numbers of containers (list, arrays, dynarrays,
> > > > hashtbl, pmap, .... )
> > > > - all theses containers need to implement all the functionnal ops : map,
> > > > iter, fold...
> > > > - conversions between each of the containers is a O(n^2).
> > >
> > > Usually it is O(n) or O(n log n).
> >
> > I think he meant the *number* of conversion functions is
> > O(n^2), not that their complexity is O(n^2).
> 
> Right. Sorry.
> But usually people just use from/to list conversion, or directly fold.

I guess so, but as mentioned, converting to list as an
intermediate representation is inefficient (memory-wise),
and folding has to be implemented tail-recursively by the
ADT-maker for it to be efficient and avoid stack overflow
on long "lists".

I (and others, apparently :)) think it's easier to just
use Enums and not have to even think about such things. As
an application developer, not having to care about
implementation details of the language is IMHO always a
good sign that you've found a worthwhile abstraction.

Cheers,

-- 
Bardur Arantsson
<ba...@im...>
<ba...@sc...>

On the positive side it made him easier to find, but on the
negative side it made him easier to find. The success of
Dibbler's commercial strategy hinged on being able to find his
customers, not the other way around.
                                     Terry Pratchett | Soul Music

Re: [Ocaml-lib-devel] About iterators and enums

[Martin J. <mar...@em...>]

On Fri, 30 Apr 2004, Martin Jambon wrote:

> let fold_while f test s init =
>   let result = ref init in
>   try
>     fold
>       (fun accu x  ->
> 	 if test x then f x accu
> 	 else (result := accu;
> 	       raise Exit))
>       [] s
>   with Exit -> !result

Hum, I meant:

let fold_while f test s init =
  let result = ref init in
  try
    fold
      (fun x accu ->
	 if test x then f x accu
	 else (result := accu;
	       raise Exit))
      s init
  with Exit -> !result


Martin

Re: [Ocaml-lib-devel] About iterators and enums

[Martin J. <mar...@em...>]

On Fri, 30 Apr 2004, Bardur Arantsson wrote:

> On Fri, Apr 30, 2004 at 04:14:48PM +0800, Martin Jambon wrote:
>
> > On Thu, 29 Apr 2004, Nicolas Cannasse wrote:
> >
> [--snip--]
> > > > Please give us some examples.
> > >
> > > The rational of Enums is the following :
> > > - we have increasing numbers of containers (list, arrays, dynarrays,
> > > hashtbl, pmap, .... )
> > > - all theses containers need to implement all the functionnal ops : map,
> > > iter, fold...
> > > - conversions between each of the containers is a O(n^2).
> >
> > Usually it is O(n) or O(n log n).
>
> I think he meant the *number* of conversion functions is
> O(n^2), not that their complexity is O(n^2).

Right. Sorry.
But usually people just use from/to list conversion, or directly fold.


Martin

Re: [Ocaml-lib-devel] About iterators and enums

[Bardur A. <oca...@sc...>]

On Fri, Apr 30, 2004 at 04:14:48PM +0800, Martin Jambon wrote:

> On Thu, 29 Apr 2004, Nicolas Cannasse wrote:
> 
[--snip--]
> > > Please give us some examples.
> >
> > The rational of Enums is the following :
> > - we have increasing numbers of containers (list, arrays, dynarrays,
> > hashtbl, pmap, .... )
> > - all theses containers need to implement all the functionnal ops : map,
> > iter, fold...
> > - conversions between each of the containers is a O(n^2).
> 
> Usually it is O(n) or O(n log n).

I think he meant the *number* of conversion functions is
O(n^2), not that their complexity is O(n^2).

> 
> > - enums are here to provide an easy way to convert between different
> > containers, and to abstract them at the same time when using functionnal
> > ops.
> > There is nice side effects about their lazyness :
> > - you never need to allocate intermediate data structure when filtering /
> > mapping
> > - you can work with a large collection of elements without any problem.
> >
> > For example, let's take a 1 M elements list.
> > Each map will duplicate it into a brand new 1 M elements list.
> > With enums you can stack several maps and filters, and then at the end, when
> > you iter or fold, each readed element will go through your functionnal
> > stack, be mapped or filtered by it, and eventually reach the output.
> 
> Here is a simple example:
> 
> let l2 = List.map f1 l1 in
> let l3 = List.filter f2 l2 in
> let l4 = List.map f3 l3 in
> ...
> 
> You can replace it by:
> 
> let l4 = List.fold_left (fun accu x ->
>                             let y = f1 x in
>                             if f2 y then f3 y :: accu
>                             else accu) l1 in
> ...
> 
> In both cases, the memory is kept constant (2 * n) during the process but
> in the second version, less memory is allocated/deallocated.
> Of course List may be replaced by any other module.
> 
> If you don't want to iterate until the end, just raise an exception:
> 
> let fold_while f test s init =
>   let result = ref init in
>   try
>     fold
>       (fun accu x ->
> 	 if test x then f x accu
> 	 else (result := accu;
> 	       raise Exit))
>       [] s
>   with Exit -> !result
> 

Well, duh! "Anything written in OCaml can be replaced with
other OCaml code which does the same thing! News at 11".

The point is that with Enums that code is written for you
and automagically works with any data structure which can
be enum'd.

-- 
Bardur Arantsson
<ba...@im...>
<ba...@sc...>

- Me? The 13th Duke of Wimbourne? In a student nurse's hall of
residence at three in the morning? With my reputation? ... Bingo!
                       The 13th Duke of Wimbourne | The Fast Show

Re: [Ocaml-lib-devel] About iterators and enums

[Martin J. <mar...@em...>]

On Thu, 29 Apr 2004, Nicolas Cannasse wrote:

> > I am still curious to see in what kind of situations you would use them.
> > Please give us some examples.
>
> The rational of Enums is the following :
> - we have increasing numbers of containers (list, arrays, dynarrays,
> hashtbl, pmap, .... )
> - all theses containers need to implement all the functionnal ops : map,
> iter, fold...
> - conversions between each of the containers is a O(n^2).

Usually it is O(n) or O(n log n).

> - enums are here to provide an easy way to convert between different
> containers, and to abstract them at the same time when using functionnal
> ops.
> There is nice side effects about their lazyness :
> - you never need to allocate intermediate data structure when filtering /
> mapping
> - you can work with a large collection of elements without any problem.
>
> For example, let's take a 1 M elements list.
> Each map will duplicate it into a brand new 1 M elements list.
> With enums you can stack several maps and filters, and then at the end, when
> you iter or fold, each readed element will go through your functionnal
> stack, be mapped or filtered by it, and eventually reach the output.

Here is a simple example:

let l2 = List.map f1 l1 in
let l3 = List.filter f2 l2 in
let l4 = List.map f3 l3 in
...

You can replace it by:

let l4 = List.fold_left (fun accu x ->
                            let y = f1 x in
                            if f2 y then f3 y :: accu
                            else accu) l1 in
...

In both cases, the memory is kept constant (2 * n) during the process but
in the second version, less memory is allocated/deallocated.
Of course List may be replaced by any other module.

If you don't want to iterate until the end, just raise an exception:

let fold_while f test s init =
  let result = ref init in
  try
    fold
      (fun accu x ->
	 if test x then f x accu
	 else (result := accu;
	       raise Exit))
      [] s
  with Exit -> !result





> Better : you can input to your algorithm some data coming from a list, a
> socket, an array, a file, or the container you need. Write once, use N
> times, where N is the number of "sources" for your data.
> If you're not convinced by this I don't know what I can add...

Some real code!


> > I can give several examples for the Hashtbl stuff that I already posted,
> > and I don't expect it to be at the core of the future "standard" library
> > for the Objective Caml language.
>
> Samples are not enough. I personaly prefer rationals.

ROTFL


> > I don't know what you plan to do about Int, Float and Bool additional
> > modules, or with tables of properties, as recently proposed by other
> > posters.
>
> Int , Float and Bool are useful with functors. ExtLib is functor-free and
> happy with it.

Functors exist and will continue to be used!


> Functors were already discussed and dismissed before : please
> watch the archives.

Please give a clear reference.


> The tables of properties are nice but IMHO are requiring more typing.

I don't understand your sentence.


> > And why don't you merge the project with the other ExtLib?
>
> This is out-of-question. Other ExtLib use C code and ExtLib is pure OCaml.

The current standard lib uses C code too.
Try first to remove all the "include" from modules of the standard
library, and see if you can rewrite the missing parts in pure OCaml.


> > If you don't trust other people's work, the result will be that someone
> > else will decide to start one more general library project.
>
> I do trust, when there is some strong arguments in favor of an addition to
> the ExtLib : if I let everything end up into the ExtLib without some
> filtering and previous discussions over the usabality and general use of the
> stuff then it will grow like the Java library : big and unusable. Small and
> consistent is better.

The current standard library is perfect then.

Bye,

Martin