[Caml-list] [Ann] Zarith

[Caml-list] [Ann] Zarith

[Xavier Leroy]

Dear list,

It is my pleasure to announce release 1.0 of Zarith, a new OCaml
library for exact, arbitrary-precision arithmetic on integers and
rationals.  Zarith was written by Antoine Miné with a little help from
me and feedback from Pascal Cuoq.

To download:  http://forge.ocamlcore.org/projects/zarith/

The implementation uses GMP (the GNU Multiple Precision arithmetic
library) to compute over big integers.  However, small integers are
represented as unboxed Caml integers, to save space and improve
performance. Big integers are allocated in the Caml heap, bypassing
GMP's memory management and achieving better GC behavior than e.g.
the MLGMP library.  Computations on small integers use a special,
faster path (coded in assembly for some platforms and functions)
eschewing calls to GMP, while computations on large intergers use the
low-level MPN functions from GMP.  As a consequence, Zarith is much
faster and more space-efficient than the Big_int module from OCaml's
standard distribution.

Additional niceties of Zarith include:
- short function names and infix operators, allowing one to write e.g.
    Z.(~$2 + ~$5 * x)
- polymorphic comparisons (=, <, >, etc) work correctly on Zarith's
  big integers, provided OCaml 3.12.1 or later is used.

Feedback is welcome, preferably through the bug tracker at
http://forge.ocamlcore.org/projects/zarith/

Enjoy,

- Xavier Leroy

Re: [Caml-list] [Ann] Zarith

[rixed]

> - polymorphic comparisons (=, <, >, etc) work correctly on Zarith's
>   big integers, provided OCaml 3.12.1 or later is used.

Is there anything special in 3.12.1 to help library authors define
specialized comparison operators ?

Re: [Caml-list] [Ann] Zarith

[Gerd Stolpmann]

Am Donnerstag, den 18.08.2011, 10:02 +0200 schrieb
rixed@happyleptic.org:
> > - polymorphic comparisons (=, <, >, etc) work correctly on Zarith's
> >   big integers, provided OCaml 3.12.1 or later is used.
> 
> Is there anything special in 3.12.1 to help library authors define
> specialized comparison operators ?

You can define such operators for abstract values only (i.e. on the C
side of bindings), and this is available for a long time. There is no
such feature for data structures entirely programmed in OCaml (which is
a bit self-discriminating, IMHO).

I guess the problem is that any addition of comparison operators
requires another level of indirection, and it would feel strange to
program and use. This means one could imagine with minimal modifications
of the current runtime to support something like

type 'a wrapped_value
val wrap_value : 'a comparison_operators -> 'a -> 'a wrapped_value
val unwrap_value : 'a wrapped_value -> 'a

In the machine representation, a wrapped_value would have a special tag
to signal the runtime that it carries comparison operators. Because of
this indirection, it is inconvenient to use, as the programmer of a data
structure would need to wrap and unwrap values just to override the
comparisons (basically like it is possible in C today). One idea to
improve this could be a special kind of functor that is able to add
wrap/unwrap calls to a given argument module, so the programmer would
not have to program this explicitly.

Gerd
-- 
------------------------------------------------------------
Gerd Stolpmann, Darmstadt, Germany    gerd@gerd-stolpmann.de
Creator of GODI and camlcity.org.
Contact details:        http://www.camlcity.org/contact.html
Company homepage:       http://www.gerd-stolpmann.de
*** Searching for new projects! Need consulting for system
*** programming in Ocaml? Gerd Stolpmann can help you.
------------------------------------------------------------

Re: [Caml-list] [Ann] Zarith

[Gabriel Scherer]

[-- Attachment #1: Type: text/plain, Size: 1034 bytes --]

On Thu, Aug 18, 2011 at 10:02 AM, <rixed@happyleptic.org> wrote:

> Is there anything special in 3.12.1 to help library authors define
> specialized comparison operators ?
>

Yes, from the 3.12.1 changelog:

> - Added new operation 'compare_ext' to custom blocks, called when
>  comparing a custom block value with an unboxed integer.
>

The  following fix is also possibly relevant:

> - Hardened generic comparison in the case where two custom blocks
>  are compared and have different sets of custom operations.


I believe the comparison hardening was made desirable by the expected use of
first-class modules to encode existential datatypes: with existential
datatypes you may try to use the polymorphic comparison operators on two
values of the same (existential) datatype having different internal
representations. The problem didn't happen with the previous encoding of
existential types using first-class polymorphism, as it implies packing the
value inside closures, so the polymorphic comparison operators were not
usable.

[-- Attachment #2: Type: text/html, Size: 1659 bytes --]

Re: [Caml-list] [Ann] Zarith

[Alain Frisch]

On 08/18/2011 10:58 AM, Gabriel Scherer wrote:
> I believe the comparison hardening was made desirable by the expected
> use of first-class modules to encode existential datatypes: with
> existential datatypes you may try to use the polymorphic comparison
> operators on two values of the same (existential) datatype having
> different internal representations. The problem didn't happen with the
> previous encoding of existential types using first-class polymorphism,
> as it implies packing the value inside closures, so the polymorphic
> comparison operators were not usable.

The problem existed before, because of exceptions. When two exception 
values having constructors with the same name are compared with the 
polymorphic equality, their arguments are compared structurally even if 
they don't have the same type.  (One way to address this would be to 
have a special tag on exception values to force physical comparison of 
the constructors.)


-- Alain