Objective Caml release 3.08.2

Objective Caml release 3.08.2

[Damien Doligez]

Greetings,

We have the pleasure of announcing the release of

              Objective Caml version 3.08.2

This is a bug-fix release; see below for the list of changes.
Upgrading is not urgent unless you have problems with one of
the bugs listed below.

Only the source is available at the moment.  We will provide some
binaries in the near future.

It is available at http://caml.inria.fr/ocaml/distrib.html

-- Damien Doligez for the Caml Team


Objective Caml 3.08.2:
----------------------

Bug fixes:
- runtime: memory leak when unmarshalling big data structures (PR#3247)
- camlp4: incorrect line numbers in errors (PR#3188)
- emacs: xemacs-specific code, wrong call to "sit-for"
- ocamldoc: "Lexing: empty token" (PR#3173)
- unix: problem with close_process_* (PR#3191)
- unix: possible coredumps (PR#3252)
- stdlib: wrong order in Set.fold (PR#3161)
- ocamlcp: array out of bounds in profiled programs (PR#3267)
- yacc: problem with polymorphic variant types for grammar entries 
(PR#3033)

Misc:
- export <caml/printexc.h> for caml_format_exception (PR#3080)
- clean up caml_search_exe_in_path (maybe PR#3079)
- camlp4: new function "make_lexer" for new-style locations
- unix: added missing #includes (PR#3088)

Re: [Caml-list] Objective Caml release 3.08.2

[Frédéric Gava]

----- Original Message -----
From: "Damien Doligez" <damien.doligez@inria.fr>
To: "caml announce" <caml-announce@inria.fr>
Sent: Wednesday, November 24, 2004 2:06 PM
Subject: [Caml-list] Objective Caml release 3.08.2


> - stdlib: wrong order in Set.fold (PR#3161)

Why an order for the fold operator ? The fold operator is used in many
parallel applications and in these cases, the order is not specified (it is
done in parallel). Peraps add a new operator to the interface (scan ? or
async_fold ?) where the order is unspecified (another set's operators like
choose do not specified the order). In this case, it would be possible to
write a true parallel implementation of fold (every process "folds" a part
of the set and them they "fold" there tempory results) .

Frédéric Gava.

Re: [Caml-list] Objective Caml release 3.08.2

[skaller]

On Fri, 2004-11-26 at 01:47, Frédéric Gava wrote:

> 
> > - stdlib: wrong order in Set.fold (PR#3161)
> 
> Why an order for the fold operator ?

Because Set.t is an ordered container,
and order matters for folds if the operator being folded
isn't associative.

These functions are deterministic and depend on order:

Set.min_elt, Set.max_elt, Set.elements, Set.fold, Set.iter

Set.choose, however, chooses at random, and Set.for_all
doesn't appear to be ordered either (is that a bug
in the doc or deliberate?)

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net

Re: [Caml-list] Objective Caml release 3.08.2

[Frédéric Gava]

> > Why an order for the fold operator ?
>
> Because Set.t is an ordered container,
Ok, but it is an abstract type : you do not know (except when you used
ocamlbrowser) how it works
and you do not need it (you do not want to know how really work the Thread
for example (simple user point of view) ).

> and order matters for folds if the operator being folded
> isn't associative.
Ok. That's right. This is why I thinks, another fold is necessary for
associative operators (and thus for possible optimizations of this fold) and
thus wihtout side-effects.

> These functions are deterministic and depend on order:
> Set.min_elt, Set.max_elt, Set.elements, Set.fold, Set.iter

Ok, for Set.iter  but Set.elements could also give the elements of the set
in any order: you need to specify to the SGBD that you want an ordered table
in SQL, why here it is necessary. You can  sort your list if you need
(peraps it takes more time but two functions could be give to the users:
Set.elements and Set.order_elements). A Set.elements without ordering the
elements would be more efficient.

 > Set.choose, however, chooses at random, and Set.for_all
> doesn't appear to be ordered either (is that a bug
> in the doc or deliberate?)
What would be the interest of sorting all the times the elements ?

Frédéric Gava

Re: [Caml-list] Objective Caml release 3.08.2

[Christophe TROESTLER]

On Thu, 25 Nov 2004, Frédéric Gava <frederic.gava@wanadoo.fr> wrote:
> 
> > > Why an order for the fold operator ?
> >
> > Because Set.t is an ordered container,
> Ok, but it is an abstract type : you do not know how it works and
> you do not need it

As  was said,  since Set.Make  takes an  ordered structure,  there are
cases  where you  may  care to  process  your elements  in an  ordered
fashion -- it is good that  the Set module makes this promise.  If you
do not like it, ignore it.

> A Set.elements without ordering the elements would be more efficient.

Show us!

My 2¢,
ChriS

Re: [Caml-list] Objective Caml release 3.08.2

[Frédéric Gava]

> > A Set.elements without ordering the elements would be more efficient.
>
> Show us!
Depending of your implementation of Set. In the case of balanced tree, ok,
the time will be the same but this is a special case:

>----- Original Message -----
>From: "skaller" <skaller@users.sourceforge.net>
>So I would tend to think it may well be worthwhile adding
>an unordered set to Ocaml. I guess some operations may
>change from O(log N) to O(1), or from O(N log N) to just O(N),
>eg fold.
----- Original Message -----
From: "Jon Harrop" <jon@jdh30.plus.com>
>Other useful set implementations which do not present elements in-order are
>possible, most notably a hashed set because it has significantly better
>average-case performance.

In the case of associative operator for the fold, the cost would be O(N/p)
in an parallel implementation of Set where p is the number of processors. I
would tend to think it may well be worthwhile.

Re: [Caml-list] Objective Caml release 3.08.2

[Jon Harrop]

On Thursday 25 November 2004 18:05, Frédéric Gava wrote:
> > > Why an order for the fold operator ?
> > Because Set.t is an ordered container,
>
> Ok, but it is an abstract type : you do not know (except when you used
> ocamlbrowser) how it works...

The ability to fold over the elements of a set in order can be very useful. 
Consequently, when implementing a set data structure, the mathematical notion 
of a set is often supplemented with the added assurances that many functions 
over the set will operate in-order. This is typically achieved by 
implementing the set as a red-black balanced binary tree.

Other useful set implementations which do not present elements in-order are 
possible, most notably a hashed set because it has significantly better 
average-case performance.

Cheers,
Jon.

Re: [Caml-list] Objective Caml release 3.08.2

[skaller]

On Fri, 2004-11-26 at 05:05, Frédéric Gava wrote:

> > and order matters for folds if the operator being folded
> > isn't associative.
> Ok. That's right. This is why I thinks, another fold is necessary for
> associative operators (and thus for possible optimizations of this fold) and
> thus wihtout side-effects.

Perhaps that should be a question: are there optimisations
which can be performed if the ordering constraint is dropped?

This probably has two parts:

(a) Is Set.min_elt as fast as Set.choose?
(b) Are there any other optimisations (eg deforestation) 
which would benefit?

I don't know the answer to either question in the particular
case of Set.

Perhaps there would be some benefit for a Set' data type,
which was unordered.

ISO C++ STL has an ordered Set type (which typically does use
a red black tree), and in Technical Report 1 (TR1), there
is an unordered set type, intended to be implemented with
a hash table.

So I would tend to think it may well be worthwhile adding
an unordered set to Ocaml. I guess some operations may
change from O(log N) to O(1), or from O(N log N) to just O(N),
eg fold.


-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net

Re: [Caml-list] Objective Caml release 3.08.2

[Frédéric Gava]

> So I would tend to think it may well be worthwhile adding
> an unordered set to Ocaml. I guess some operations may
> change from O(log N) to O(1), or from O(N log N) to just O(N),
> eg fold.
Good Idea. In this case, with the same interface (but not the same
specification), it would be easier to optimize
some functions (in my case, I thinks about parallel implementation)

Frédéric Gava

Re: [Caml-list] Objective Caml release 3.08.2

[Aleksey Nogin]

On 24.11.2004 05:06, Damien Doligez wrote:

> Greetings,
> 
> We have the pleasure of announcing the release of
> 
>              Objective Caml version 3.08.2
> 
> This is a bug-fix release; see below for the list of changes.
> Upgrading is not urgent unless you have problems with one of
> the bugs listed below.
> 
> Only the source is available at the moment.  We will provide some
> binaries in the near future.

Binary and source RPMs for Red Hat Linux 8.0, 9, Fedora Core Release 1, 
2, 3, and Mandrake 10.0 are available at http://rpm.nogin.org/ocaml.html

-- 
Aleksey Nogin

Home Page: http://nogin.org/
E-Mail: nogin@cs.caltech.edu (office), aleksey@nogin.org (personal)
Office: Jorgensen 70, tel: (626) 395-2907