Map.fold behavior changed

Map.fold behavior changed

[EEK Cooper]

Hi all,

My team just noticed that the behavior of Map.fold changed in OCaml 
version 3.08.4.

I'm concerned that the OCaml team would change the behavior of a 
library function so late in its life. I understand that it was thought 
to be "wrong" <http://caml.inria.fr/mantis/view.php?id=3607>, but 
changing the behavior of an existing function breaks existing apps and 
shouldn't be done lightly. Such changes should, of course, be carefully 
highlighted in a change log as *incompatible* changes, requring updates 
to existing programs--this one was buried under "bug fixes." The old 
behavior was apparently longstanding since 1995 
<http://camlcvs.inria.fr/cgi-bin/cvsweb/ocaml/stdlib/map.ml?annotate=1.15;f=h> 
versus 
<http://camlcvs.inria.fr/cgi-bin/cvsweb/ocaml/stdlib/map.ml?annotate=1.15.4.1;f=h>. If OCaml is meant to be a practical programming language, it should provide consistency for its users from version to 
version.

That said, we're now in the position where we need to compile different 
code depending on the version of OCaml. What's the best way to do 
conditional compilation in OCaml? Should we use cpp and #ifdef, or is 
there a more OCaml-savvy solution?

Thanks in advance,
Ezra

Re: [Caml-list] Map.fold behavior changed

[Jean-Christophe Filliatre]

EEK Cooper writes:
 > 
 > My team just noticed that the behavior of Map.fold changed in OCaml 
 > version 3.08.4.
 > 
 > I'm concerned that the OCaml team would change the behavior of a 
 > library function so late in its life. I understand that it was thought 
 > to be "wrong" <http://caml.inria.fr/mantis/view.php?id=3607>, but 
 > changing the behavior of an existing function breaks existing apps and 
 > shouldn't be done lightly. 

I must agree  with you since we also  got a similar bug in  one of our
apps due to this Map.fold _implementation_ change.

However, we must also admit  that we were using an unspecified feature
of the  standard library. If  I remember correctly,  the documentation
was saying that  the traversal order was left  _unspecified_.  The new
version   of  Map.fold   simply  has   a  stronger,   but  consistent,
specification.  From this point of view, the Ocaml team thus cannot be
blamed.

You (and I) were using  the _implementation_ as a specification, which
is bad :-)

-- 
Jean-Christophe Filliâtre (http://www.lri.fr/~filliatr)

Re: [Caml-list] Map.fold behavior changed

[EEK Cooper]

I'm glad to hear that others are facing this problem as well. Those of 
you who are: how are you dealing with it? Are you simply requiring your 
users to use a particular version of the compiler? Or switching on 
Sys.ocaml_version?

Quoting Jean-Christophe Filliatre <filliatr@lri.fr>:

> EEK Cooper writes:
>
>  > My team just noticed that the behavior of Map.fold changed in OCaml
>  > version 3.08.4.
>  >
>  > I'm concerned that the OCaml team would change the behavior of a
>  > library function so late in its life. I understand that it was thought
>  > to be "wrong" <http://caml.inria.fr/mantis/view.php?id=3607>, but
>  > changing the behavior of an existing function breaks existing apps and
>  > shouldn't be done lightly.
>
> I must agree  with you since we also  got a similar bug in  one of our
> apps due to this Map.fold _implementation_ change.
>
> However, we must also admit  that we were using an unspecified feature
> of the  standard library. If  I remember correctly,  the documentation
> was saying that  the traversal order was left  _unspecified_.

For the record, I don't think this is true. My copy of map.mli, as part 
of OCaml 3.08.3, says:

     val fold: (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b
     (** [fold f m a] computes [(f kN dN ... (f k1 d1 a)...)],
        where [k1 ... kN] are the keys of all bindings in [m]
        (in increasing order), and [d1 ... dN] are the associated data. *)

specifying the same ordering as the current version. Also the original 
bug ticket <http://caml.inria.fr/mantis/view.php?id=3607> about the 
issue asserts that it should behave according to the documentation.

Since the behavior was NOT unspecified, it was reasonable to assume 
that the documentation suffered from a simple typo, and to expect the 
behavior not to change. I believe the documentation should have been 
fixed rather than the behavior.

Ezra

Re: [Caml-list] Map.fold behavior changed

[Jean-Christophe Filliatre]

EEK Cooper writes:
 > I'm glad to hear that others are facing this problem as well. Those of 
 > you who are: how are you dealing with it? Are you simply requiring your 
 > users to use a particular version of the compiler? Or switching on 
 > Sys.ocaml_version?

When we discovered the bug, we first used a test of ocaml's version at
configuration time and a  preprocessing using camlp4's pa_ifdef module
to select the  right order relation according to  ocaml's version (our
initial  order relation  or  the  inverse relation,  to  get the  same
behavior as before with the new Map.fold).

But this was not very satisfactory, and we finally rewrote our code to
be independent  of Map.fold implementation  (and we got rid  of camlp4
preprocessing, which simplified our Makefile).

-- 
Jean-Christophe Filliâtre (http://www.lri.fr/~filliatr)

Re: [Caml-list] Map.fold behavior changed

[Damien Doligez]

On Feb 24, 2006, at 14:29, EEK Cooper wrote:

> Since the behavior was NOT unspecified, it was reasonable to assume  
> that the
> documentation suffered from a simple typo, and to expect the  
> behavior not to
> change.

"It is documented to do something else, so we will assume that it's  
intended
to do what it does, instead of what the documentation says."

I don't think this is very reasonable.

-- Damien

Re: [Caml-list] Map.fold behavior changed

[Brian Hurt]

On Fri, 24 Feb 2006, EEK Cooper wrote:

> Hi all,
>
> My team just noticed that the behavior of Map.fold changed in OCaml version 
> 3.08.4.

OK, Stupid question on my part: what was the change in behavior?

Brian

Re: [Caml-list] Map.fold behavior changed

[Brian Hurt]

On Fri, 24 Feb 2006, Damien Doligez wrote:

> On Feb 24, 2006, at 14:29, EEK Cooper wrote:
>
>> Since the behavior was NOT unspecified, it was reasonable to assume that 
>> the
>> documentation suffered from a simple typo, and to expect the behavior not 
>> to
>> change.
>
> "It is documented to do something else, so we will assume that it's intended
> to do what it does, instead of what the documentation says."
>
> I don't think this is very reasonable.

OK, My stupid question was already answered.

There are times, however, when a specified traversal ordering is required. 
Since a map is defined as an ordered tree, having a fold_left and 
fold_right functions would not be hard to do:

let rec fold_left f init = function
 	| Empty -> init
 	| Node(l, v, d, r, _) ->
 		fold_left f (f (fold_left f init l) v d) r

let rec fold_right  f node init =
 	match node with
 		| Empty -> init
 		| Node(l, v, d, r, _) ->
 			fold_right f l (f v d (fold_right f r init))

These aren't checked to see if they even compile, but they're close.

I may take this opportunity to offer a red-black tree implementation of 
Map as a replacement, if people are interested.  The advantage a 
red-black tree is that it uses one less word of memory per element in a 
map.

Brian

Re: [Caml-list] Map.fold behavior changed

[Joaquin Cuenca Abela]

--- Damien Doligez <damien.doligez@inria.fr> wrote:

> On Feb 24, 2006, at 14:29, EEK Cooper wrote:
> 
> > Since the behavior was NOT unspecified, it was
> reasonable to assume  
> > that the
> > documentation suffered from a simple typo, and to
> expect the  
> > behavior not to
> > change.
> 
> "It is documented to do something else, so we will
> assume that it's  
> intended
> to do what it does, instead of what the
> documentation says."
> 
> I don't think this is very reasonable.

Expecting the documentation to be beyond flaws or
making it right "by definition" also exposes you to
problems when it just doesn't follow the intent of the
writers.

The fact that the documentation is written in english
and not in a computer language doesn't make it any
less vulnerable to bugs.

If the implementation and documentation diverge, and
both behaviours are equally logic, sound, consistent,
etc. the fact that changing the documentation doesn't
create any regression problems should easily tip the
balance against any change in the implementation.

Regards,


Joaquin Cuenca Abela
e98cuenc at yahoo dot com

__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around 
http://mail.yahoo.com 

Re: [Caml-list] Map.fold behavior changed

[Jean-Christophe Filliatre]

Brian Hurt writes:
 > 
 > I may take this opportunity to offer a red-black tree implementation of 
 > Map as a replacement, if people are interested.  The advantage a 
 > red-black tree is that it uses one less word of memory per element in a 
 > map.

For  information, I  wrote an  implementation of  Set  using red-black
trees a long time ago. It is available here:

  http://www.lri.fr/~filliatr/software.en.html

Note:  this  code was  even  formally  proved  correct using  a  proof
assistant. Getting Map from Set is rather straightforward.

I also did some benchmarks  to compare red-black trees, patricia trees
and  Ocaml AVLs  and, as  time is  concerned, the  AVLs  were (almost)
always the most efficient.

-- 
Jean-Christophe Filliâtre (http://www.lri.fr/~filliatr)

Re: [Caml-list] Map.fold behavior changed

[Damien Doligez]

On Feb 24, 2006, at 17:01, Joaquin Cuenca Abela wrote:

> Expecting the documentation to be beyond flaws or
> making it right "by definition" also exposes you to
> problems when it just doesn't follow the intent of the
> writers.

Of course, but when you find a discrepancy, you should file a bug
report, not assume that the documentation is wrong.

-- Damien

Re: [Caml-list] Map.fold behavior changed

[Nathaniel Gray]

On 2/24/06, EEK Cooper <s0567141@sms.ed.ac.uk> wrote:
> Hi all,
>
> My team just noticed that the behavior of Map.fold changed in OCaml
> version 3.08.4.
>
[snip

> That said, we're now in the position where we need to compile different
> code depending on the version of OCaml. What's the best way to do
> conditional compilation in OCaml? Should we use cpp and #ifdef, or is
> there a more OCaml-savvy solution?

Copy/paste.  Take the implementation you like, copy it, call it MyMap,
and use a sed script to change Map to MyMap in your code.  Quick? 
Yes.  Effective?  Yes.  Elegant?  Not so much.

BTW, cpp won't work because of the lexical differences between ocaml
and C.  OTOH, I think there may be a camlp4 module that implements
cpp-like ifdefs.

Cheers,
-n8

--
>>>-- Nathaniel Gray -- Caltech Computer Science ------>
>>>-- Mojave Project -- http://mojave.cs.caltech.edu -->

Re: [Caml-list] Map.fold behavior changed

[Nicolas Pouillard]

On 3/1/06, Nathaniel Gray <n8gray@gmail.com> wrote:
> On 2/24/06, EEK Cooper <s0567141@sms.ed.ac.uk> wrote:
> > Hi all,
> >
> > My team just noticed that the behavior of Map.fold changed in OCaml
> > version 3.08.4.
> >

[...]

> BTW, cpp won't work because of the lexical differences between ocaml
> and C.  OTOH, I think there may be a camlp4 module that implements
> cpp-like ifdefs.
>

The pa_macro module does that.

Cheers,

--
Nicolas Pouillard aka Ertai  <ertai@feydakins.org>
http://uttk.org      Uttk -- Unified Test Tool Kit

Re: [Caml-list] Map.fold behavior changed

[Ezra Cooper]

Damien Doligez wrote:

>
> On Feb 24, 2006, at 17:01, Joaquin Cuenca Abela wrote:
>
>> Expecting the documentation to be beyond flaws or
>> making it right "by definition" also exposes you to
>> problems when it just doesn't follow the intent of the
>> writers.
>
>
> Of course, but when you find a discrepancy, you should file a bug
> report, not assume that the documentation is wrong.


But you see, in this case a member of my team was reading the latest
documentation, and using the latest version. So everything looked
correct to him, but he didn't realize that he was making our code
incompatible with the last ~10 years of OCaml.

In any case, we have worked around it by testing Sys.ocaml_version.
Thanks to everyone who replied for their suggestions.

Is there any reason why Sys.ocaml_version is a string, by the way?
Shouldn't it be some kind of numerical representation to make it easy to
do ordered comparisons?

Thanks all,
Ezra

Re: [Caml-list] Map.fold behavior changed

[N. Owen Gunden]

On Thu, Mar 02, 2006 at 01:57:53PM +0000, Ezra Cooper wrote:
> Is there any reason why Sys.ocaml_version is a string, by the way?
> Shouldn't it be some kind of numerical representation to make it easy to
> do ordered comparisons?

Actually ordered comparisons work very nicely on string version numbers.

Re: [Caml-list] Map.fold behavior changed

[Florian Hars]

N. Owen Gunden wrote:
> Actually ordered comparisons work very nicely on string version numbers.

This reminds me of an episode on another mailing list some years ago, where
someone complained: "The documentation for package A says that it requires at
least version 1.13 of package B, I used version 1.9 of Package B, and it still
doesn't work."

Yours, Florian.

Re: [Caml-list] Map.fold behavior changed

[Damien Doligez]

On Mar 9, 2006, at 08:14, Florian Hars wrote:

> This reminds me of an episode on another mailing list some years  
> ago, where
> someone complained: "The documentation for package A says that it  
> requires at
> least version 1.13 of package B, I used version 1.9 of Package B,  
> and it still
> doesn't work."

OCaml version numbers won't have this problem until version 10,  
which, at the
current release rate, shouldn't happen before the year 2048.

At that time I will push for using letters for major relase numbers,  
in order
to get another 300 years of nicely-comparable version numbers.

-- Damien

Re: [Caml-list] Map.fold behavior changed

[Florian Hars]

Damien Doligez wrote:
> OCaml version numbers won't have this problem until version 10,  which, 
> at the current release rate, shouldn't happen before the year 2048.

OCaml version numbers won't have this problem until version 3.10,  which,
at the current release rate, shouldn't happen before the year 2006.

Yours, Florian.

Re: [Caml-list] Map.fold behavior changed

[Jon Harrop]

On Wednesday 15 March 2006 07:27, Florian Hars wrote:
> Damien Doligez wrote:
> > OCaml version numbers won't have this problem until version 10,  which,
> > at the current release rate, shouldn't happen before the year 2048.
>
> OCaml version numbers won't have this problem until version 3.10,  which,
> at the current release rate, shouldn't happen before the year 2006.

But the current version number is 3.09.1?

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists

Re: [Caml-list] Map.fold behavior changed

[Alain Frisch]

Florian Hars wrote:
> Damien Doligez wrote:
> 
>> OCaml version numbers won't have this problem until version 10,  
>> which, at the current release rate, shouldn't happen before the year 
>> 2048.
> 
> 
> OCaml version numbers won't have this problem until version 3.10,  which,
> at the current release rate, shouldn't happen before the year 2006.

Hint:

# "3.09.1" < "3.10";;
- : bool = true

Cheers,

Alain

Re: [Caml-list] Map.fold behavior changed

[Florian Hars]

Alain Frisch wrote:
  > # "3.09.1" < "3.10";;

Ugh. I hate leading zeroes. And I will get another coffee right now.

Yours, Florian.

Re: [Caml-list] Map.fold behavior changed

[Christophe Raffalli]

Florian Hars a écrit :
> Alain Frisch wrote:
>  > # "3.09.1" < "3.10";;
>
may be next version of ocaml will be 4.0 ;-)