ocaml-lib-devel — Developer's mailing list

[Ocaml-lib-devel] Idea with ExtList.fold_right

[Brian H. <bri...@ql...>]

Just had an idea for ExtList.fold_right.  Ok, there are basically two 
different possible implementations: the non-tail-recursive version:

let rec fold_right f lst init =
    match lst with
        | [] -> init
        | h :: t -> f h (fold_right f t init)

And the tail-recursive, list reversing version:

let fold_right f lst init =
    let rec loop l accu =
        match l with 
            [] -> accu
            | h :: t -> loop t (f h accu)
    in
    loop (List.rev lst) init
    

The first one is faster for short lists, but stack overflows on long 
lists.  The second one never overflows, but is slower for short lists.

So do a length of the list and pick the "right" algorithm for the job.  
The length should be limited- once we know the list is too long, we can 
exit (we don't need the full length).  This gives rise to the following 
code:

let fold_right f lst init =
    let max = 1000 in
    let rec toolong len = function
        | [] -> false
        | h :: t -> if len >= max then true else toolong (len + 1) t
    and revloop accu = function
        | [] -> accu
        | h :: t -> revloop (f h accu) t
    and ntrloop = function
        | [] -> init
        | h :: t -> f h (ntrloop t)
    in
    if toolong 0 lst then
        revloop init (List.rev lst)
    else
        ntrloop lst

Thoughts?  Comments?  Benchmarks?

Brian

[Ocaml-lib-devel] Psqueue API change

[Brian H. <bri...@ql...>]

Psqueue.query (imprecise) should return 'a option.  Instead of the current
kludge.

Checkin in a few minutes.

Brian

Re: [Ocaml-lib-devel] Version 1.0?

[Blair Z. <bl...@or...>]

John Max Skaller wrote:
> 
> Blair Zajac wrote:
> 
> > Instead of reinventing the wheel here, how about using pkg-config.  It
> > handles this kind of stuff and used by a large number of packages:
> >
> > % ls /usr/lib/pkgconfig/
> 
> Wow. I got a /usr/lib/pkgconfig directory on my box.
> Never heard of it before.
> Unfortunately, I don't seem to have the tool itself.
> 
> So someone (like me) that wanted to use Felix would not
> 
> only have to download Python, Interscript, and Ocaml,
> but also ExtLib and pkgconfig ..

Which OS are you using?

Best,
Blair

-- 
Blair Zajac <bl...@or...>
Plots of your system's performance - http://www.orcaware.com/orca/

Re: [Ocaml-lib-devel] Version 1.0?

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

> I tried to do that once and users hated it :-)
> They wanted a plain old tarball. Still, software like Internet
> Explorer and Redhat Linux use this idea, but I suspect
> it would be more useful if it could update multiple packages,
> not just Extlib.
[...]
> You can make an executable which is put in, say
[...]
> extlib --help --version --test

This is directly putting us back into the COAN thread.
Multiple packages, dependencies, patches, install , compile , link , update.
A lot of things to do , in a portable way.

Right now some people from the Caml team and around have been talking about
such a tool. I might start implementing such a thing quite soon, based on
the statement they made and on several long talks I already have about it
with Jacques Garrigue. I'll keep informed people on this list of further
advances.

Nicolas Cannasse

Re: [Ocaml-lib-devel] Version 1.0?

[John M. S. <sk...@oz...>]

Blair Zajac wrote:

> Instead of reinventing the wheel here, how about using pkg-config.  It
> handles this kind of stuff and used by a large number of packages:
> 
> % ls /usr/lib/pkgconfig/


Wow. I got a /usr/lib/pkgconfig directory on my box.
Never heard of it before.
Unfortunately, I don't seem to have the tool itself.

So someone (like me) that wanted to use Felix would not

only have to download Python, Interscript, and Ocaml,
but also ExtLib and pkgconfig ..

Hmmm ..


-- 
John Max Skaller, mailto:sk...@oz...
snail:10/1 Toxteth Rd, Glebe, NSW 2037, Australia.
voice:61-2-9660-0850

Re: [Ocaml-lib-devel] Re: OCamlMakefile

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

> > OCamlMakefile is doing less then ocamake, and in an non portable way.
> > If you read the README , you will see : "get and install Ocamake from
> > http://tech.motion-twin.com"
> 
> Nicolas,
> 
>   Any chance you could change ocamake to exit with a non-zero status
>   when it fails to build something?  In the "failed to build
>   dependencies" mode, for me at least, it exits with zero status.

Funny , I actually added this yesterday in my local version.
I'll update the online version asap.

Nicolas Cannasse

[Ocaml-lib-devel] Re: OCamlMakefile

[Alan P. <ap...@re...>]

In article <00d301c33088$3e580ff0$2713f9ca@WARP>, Nicolas Cannasse wrote:
> 
> OCamlMakefile is doing less then ocamake, and in an non portable way.
> If you read the README , you will see : "get and install Ocamake from
> http://tech.motion-twin.com"

Nicolas,

  Any chance you could change ocamake to exit with a non-zero status
  when it fails to build something?  In the "failed to build
  dependencies" mode, for me at least, it exits with zero status.

    Alan

Re: [Ocaml-lib-devel] OCamlMakefile

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

>     I don't have the ocamake utility, so I couldn't build
> anything ;)  I noticed on the list someone suggested a move
> to OCamlMakefile.  I hope no one minds, but I've made this
> change.  I've also added a few tidbits of ocamldoc comments.
> Is it OK if I commit these changes?

About documentation, yes fell free to commit of course !
As for OCamlMakefile , please don't !
OCamlMakefile is doing less then ocamake, and in an non portable way.
If you read the README , you will see : "get and install Ocamake from
http://tech.motion-twin.com"

Nicolas Cannasse

Re: [Ocaml-lib-devel] Version 1.0?

[Blair Z. <bl...@or...>]

John Max Skaller wrote:
> 
> Nicolas Cannasse wrote:
> 
> > I agree on this one . Modern software development and Internet are enabling
> > a quick bug reporting/fix and then users only have to update their version.
> > About this "update" and installation-made-easy of the ExtLib, I was thinking
> > writing a small and simple OCaml program that will check and download the
> > last extlib version , compile using ocamake (I think perhaps we should then
> > put ocamake in the ExtLib) and install it in  'ocamlc -where'/extlib .
> 
> I tried to do that once and users hated it :-)
> They wanted a plain old tarball. Still, software like Internet
> Explorer and Redhat Linux use this idea, but I suspect
> it would be more useful if it could update multiple packages,
> not just Extlib.

I agree a tarball release should be available.

> > I would like to have some comments from Unix users to know how we can make the
> > user being able to choose the install directory and still have a nice and
> > portable way of retreiving the install dir (needed by Makefile of program
> > using ExtLib at linking time).
> 
> You can make an executable which is put in, say
> 
>         /usr/local/bin
> 
> or
> 
>         ~/bin
> 
> extlib
> 
> which prints the install dir so people can write:
> 
>         ocamlc -I`extlib`
> 
> and add some options:
> 
>         extlib --help --version --test
> 
> it would also be tricky to have
> 
>         man extlib
> 
> tell where the installation went.

Instead of reinventing the wheel here, how about using pkg-config.  It
handles this kind of stuff and used by a large number of packages:

% ls /usr/lib/pkgconfig/
fontconfig.pc           gnome-python-2.0.pc*    libxml-2.0.pc
gconfgtk.pc             gobject-2.0.pc          libxml.pc
gconf.pc                gthread-2.0.pc          libxslt.pc
gdk.pc                  gthread.pc              openssl.pc*
glib-2.0.pc             gtk+.pc                 ORBit.pc
glib.pc                 libIDL.pc               xcursor.pc
gmodule-2.0.pc          libmetacity-private.pc  xft.pc
gmodule.pc              libnautilus.pc
gnome-mime-data-2.0.pc  libpng12.pc

You can query arbitrary settings for your package:

% pkg-config --help
Usage: pkg-config [OPTION...]
  --version                                      output version of pkg-config
  --modversion                                   output version for package
  --atleast-pkgconfig-version=VERSION            require given version of
                                                 pkg-config
  --libs                                         output all linker flags
  --libs-only-l                                  output -l flags
  --libs-only-L                                  output -L flags
  --cflags                                       output all pre-processor and
                                                 compiler flags
  --cflags-only-I                                output -I flags
  --variable=VARIABLENAME                        get the value of a variable
  --define-variable=VARIABLENAME=VARIABLEVALUE   set the value of a variable
  --exists                                       return 0 if the module(s)
                                                 exist
  --uninstalled                                  return 0 if the uninstalled
                                                 version of one or more
                                                 module(s) or their
                                                 dependencies will be used
  --atleast-version=VERSION                      return 0 if the module is at
                                                 least version VERSION
  --exact-version=VERSION                        return 0 if the module is at
                                                 exactly version VERSION
  --max-version=VERSION                          return 0 if the module is at
                                                 no newer than version VERSION
  --list-all                                     list all known packages
  --debug                                        show verbose debug information
  --print-errors                                 show verbose information
                                                 about missing or conflicting
                                                 packages
  --silence-errors                               show verbose information
                                                 about missing or conflicting
                                                 packages
  --errors-to-stdout                             print errors from
                                                 --print-errors to stdout not
                                                 stderr

Help options
  -?, --help                                     Show this help message
  --usage                                        Display brief usage message

Best,
Blair

-- 
Blair Zajac <bl...@or...>
Plots of your system's performance - http://www.orcaware.com/orca/

[Ocaml-lib-devel] OCamlMakefile

[Amit D. <ad...@Co...>]

    Hi everyone,

    I must apologize for not (yet) submitting any code, as
I've been a bit busy.  I did, however, just do an update with
the intention of adding more documentation (as this was
recommended as an important goal of reaching 1.0 quickly ;)

    I don't have the ocamake utility, so I couldn't build
anything ;)  I noticed on the list someone suggested a move
to OCamlMakefile.  I hope no one minds, but I've made this
change.  I've also added a few tidbits of ocamldoc comments.
Is it OK if I commit these changes?

    -Amit

Re: [Ocaml-lib-devel] Version 1.0?

[John M. S. <sk...@oz...>]

Nicolas Cannasse wrote:


> I agree on this one . Modern software development and Internet are enabling
> a quick bug reporting/fix and then users only have to update their version.
> About this "update" and installation-made-easy of the ExtLib, I was thinking
> writing a small and simple OCaml program that will check and download the
> last extlib version , compile using ocamake (I think perhaps we should then
> put ocamake in the ExtLib) and install it in  'ocamlc -where'/extlib . 


I tried to do that once and users hated it :-)
They wanted a plain old tarball. Still, software like Internet
Explorer and Redhat Linux use this idea, but I suspect
it would be more useful if it could update multiple packages,
not just Extlib.

> I would like to have some comments from Unix users to know how we can make the
> user being able to choose the install directory and still have a nice and
> portable way of retreiving the install dir (needed by Makefile of program
> using ExtLib at linking time).


You can make an executable which is put in, say


	/usr/local/bin

or

	~/bin

extlib

which prints the install dir so people can write:

	ocamlc -I`extlib`

and add some options:

	extlib --help --version --test

it would also be tricky to have

	man extlib

tell where the installation went.

 
> Releasing with bugs is one point : theses can be fixed later.
> But releasing without any correct documentation IS a mistake.


	I agree.


-- 
John Max Skaller, mailto:sk...@oz...
snail:10/1 Toxteth Rd, Glebe, NSW 2037, Australia.
voice:61-2-9660-0850

Re: [Ocaml-lib-devel] Version 1.0?

[John M. S. <sk...@oz...>]

Brian Hurt wrote:

> On Wed, 11 Jun 2003, John Max Skaller wrote:


> I only know of one API question at this point: things that might change
> (go away): and that's precise/imprecise actions in psqueue.  Currently
> there are two sets of operations: find, adjust, add, and remove, which
> throw an exception on "unexpected" conditions (adding a key that already
> exists, removing a key which doesn't, etc), and query, update, insert, and
> delete, which do something "intelligent" in those costs (adding a key that
> already exists becomes an update, removing a key that doesn't exist does
> nothing, etc).  Now, my preference would be to pick one of the two sets
> and run with it- but I don't know which one.  Feedback would be
> appreciated here.


I'm afraid my comments won't help much .. but I'll make them anyhow.


I use Hashtbl, and until recently only the basic functions.
Now, sometimes, it does more than I want, for example, I've never use
the pushdown stack of entries feature. So for me, the 'add' function
is actually a pain, since I have to first check if a key is present
to avoid duplicates. Similarly, sometimes I just want to either
add or replace, and I had to write code to do that.

Since I found 'replace' was added, I'm using that now.
Its equivalent to 'add if not present otherwise update',
which is easy enough to code, but I get a feeling the built-in
update is more efficient, and I can check its semantics in the manual,
rather than search my own code.

So .. I wouldn't do without the raw primitives: they're the routines
which form a basis, and which are expected to be fast. But some
of the composite routines are also useful and perhaps more likely
to be what is needed in many cases.

So I'd probably include *both* the axioms and the theorems,
without going overboard: include the extra stuff if it's likely to
be heavily used OR allows for more efficient processing OR
would be hard to code. Hmmm .. meaning: enrich the basic
interface but not *too* much. You can always add in the extra
routines later if someone complains, but you want the interface
to be ready to use without needing a whole lot of client
written auxilliaries.

Which I think leaves you just as uncertain as before :-)

-- 
John Max Skaller, mailto:sk...@oz...
snail:10/1 Toxteth Rd, Glebe, NSW 2037, Australia.
voice:61-2-9660-0850

Re: [Ocaml-lib-devel] Version 1.0?

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

> And plenty of problems with Ocaml itself.
> And there are many that you won't even find yourself:
> you need users to help you both find problems,
> and also to prioritorise them.

I agree on this one . Modern software development and Internet are enabling
a quick bug reporting/fix and then users only have to update their version.
About this "update" and installation-made-easy of the ExtLib, I was thinking
writing a small and simple OCaml program that will check and download the
last extlib version , compile using ocamake (I think perhaps we should then
put ocamake in the ExtLib) and install it in  'ocamlc -where'/extlib . I
would like to have some comments from Unix users to know how we can make the
user being able to choose the install directory and still have a nice and
portable way of retreiving the install dir (needed by Makefile of program
using ExtLib at linking time).

> RELEASE ExtLib within one week no matter what.
>
> I want to use it! I don't CARE if its bugged,
>
> or if the interfaces aren't right yet.

Releasing with bugs is one point : theses can be fixed later.
But releasing without any correct documentation IS a mistake.
If users don't understand what's inside / how to use the version 1 , they'll
not get "ext-addicted" :-) and will simply don't use it. If you want a quick
release of ExtLib, please help with writing the documentation of existing
modules !

Nicolas Cannasse

Re: [Ocaml-lib-devel] Version 1.0?

[Brian H. <bri...@ql...>]

On Wed, 11 Jun 2003, John Max Skaller wrote:

> One thing Guido van Rossum, the inventor of Python,
> once said to me was that all that really mattered was
> users. (Meaning, your product is good if it attracts
> a lot of users).

This I seriously agree with.  A 1.0 release would help adoption.  
Especially as it seems we do have users, or at least potiential users.

> Well, its easier for a group.
> So I vote:
> 
> RELEASE ExtLib within one week no matter what.
> 
> I want to use it! I don't CARE if its bugged,
> 
> or if the interfaces aren't right yet.

I only know of one API question at this point: things that might change
(go away): and that's precise/imprecise actions in psqueue.  Currently
there are two sets of operations: find, adjust, add, and remove, which
throw an exception on "unexpected" conditions (adding a key that already
exists, removing a key which doesn't, etc), and query, update, insert, and
delete, which do something "intelligent" in those costs (adding a key that
already exists becomes an update, removing a key that doesn't exist does
nothing, etc).  Now, my preference would be to pick one of the two sets
and run with it- but I don't know which one.  Feedback would be
appreciated here.

There are a number of functions I'd like to add (psqueue.enum for
example).  But adding functions isn't a problem (for compatibility)- it's
removing or altering existing functions.

Brian

Re: [Ocaml-lib-devel] Version 1.0?

[John M. S. <sk...@oz...>]

Diego Olivier Fernandez Pons wrote:

>     Bonjour,
> 
> 
>>It is necessary to provide on-site documentation to what is
>>*officially* working properly, and to include that in any release.
>>
> 
> Not stating clearly what does work and what doesn't is a mistake I
> have done in Baire. I really think Jonh Max Skaller is right in this
> point and OCaml-lib should avoid doing the same mistake I did.
> 
> 
>>If you do that, it doesn't matter if the other half of the library
>>isn't ready. Release it anyhow.
>>
>>	release early, release often
>>
> 
> One of the problems is the stability of interfaces. I have broken and
> rewritten from scratch Baire several times, and I will continue doing
> so until I get it right.


I am the same with Felix. It's been around for 3-4 years, and never 

announced. But really, I think it is necessary to credit the initial
users of a package with a willingness to rewrite the code that uses
your package as you change it.

Unless of course, you are lucky, and get 100K users on the first
day :-)


> It is important to be able to do such things when you are not an
> experimented developer in the concerned field (and Baire surely is my
> first data structure library).
 
> I don't know how the Caml-lib team feels it, but I first though
> 'initial' Baire would be the only one and I realized much later there
> were a lot of wrong things in it.


So? There are a lot of things wrong with C++ too.

And plenty of problems with Ocaml itself.
And there are many that you won't even find yourself:
you need users to help you both find problems,
and also to prioritorise them.

One thing Guido van Rossum, the inventor of Python,
once said to me was that all that really mattered was
users. (Meaning, your product is good if it attracts
a lot of users).

I don't entirely agree, but he has a point.
And you won't have any users if you don't release :-)

Be willing to be caught out making a mistake.

[Arggg .. I can't release Felix yet .. its incomplete ..
its got bugs ..]

Yeah, its really hard to do, especially for an individual.

Well, its easier for a group.
So I vote:

RELEASE ExtLib within one week no matter what.

I want to use it! I don't CARE if its bugged,

or if the interfaces aren't right yet.

Thing is, I don't have any idea yet, because I haven't
tried using it, and I CANNOT make my package depend
on a CVS archive or my own private copy of the code.
[indeed, there is a licencing issue: Felix is FFAU]

-- 
John Max Skaller, mailto:sk...@oz...
snail:10/1 Toxteth Rd, Glebe, NSW 2037, Australia.
voice:61-2-9660-0850

Re: [Ocaml-lib-devel] Proposal : BinTree

[Brian H. <bri...@ql...>]

On Tue, 10 Jun 2003, Nicolas Cannasse wrote:

> > > Here's a module proposal for adding to the ExtLib.
> > > This is a binary search tree ( module BinTree ).
> > > Operations  add, remove, find are done in Log(n) when the tree is
> optimized.
> > > This is a mutable version of the data structure.
> > >
> >
> > Is there a reason you did this as a mutable tree and not the "standard"
> > applicative version?
> 
> That's a good question. Actually is there a standard ?

"Classic" might have been a better word than Standard.

Basically,

type 'a tree_t = Void | Node of 'a tree_t * 'a * 'a tree_t
(* or whatever *)

val add : 'a tree_t -> 'a -> 'a tree_t

etc.

> List are of course applicative, Array are of course mutables, but if Sets
> are applicative , Hashtables and Stack are mutable...
> Should we provide both mutable and applicative version of every data
> structure ?

I'd say no.  We should provide the "natural" or "usefull" version.  
Defining what I mean by natural or usefull gets tricky.

The only reason I can see for stacks to be mutable in the standard library
is because the applicative version is *so* trivial to implement.  I mean:

type 'a stack = 'a list

let push s e = e :: s

let top s = List.hd s

let pop s = List.tl s

Maps are applicative, and are based upon applicative trees.  Same with
sets- also based on applicative trees.  Hashtables I could see being
mutable because they are conceptually based upon arrays- which are also
mutable.  Strings are mutable, and buffers are as well as they're
conceptually based upon strings (which are conceptually based upon arrays
of chars).  Personally, I'd have preferred nonmutable strings, but neither
here nor there.  Queues are mutable because I don't know of any sane way
to implement them applicatively.

> 
> Actually it's good sometimes to have applicative structures, it fits well
> with the functional style where you can write :
>     let l = List.map f l in
>     let l = List.filter f2 l in
>     last_call  (List.filter f3 l)
> 
> The main advandage here is being able to pass a modified data structure as
> argument to another, without actually modifiying it.
> But most of the time, the thing you want to really do is :
> 
> let l = last_call (List.filter f3 l)
> 
> Please note that here I took "filter" as sample function, because map is
> always applicative since it can change the type (BTW, we could add in-place
> map to MList) , same for fold.
> 
> IMHO, there is only few cases when people are actually using the
> "immutable" feature of a data structure, and then if you're providing
> a "copy" operation (Enum can do it for you :-) you have the same
> expression power, with shorter syntax since you don't have to rebind
> the same variable ever and ever.

There is explicitly using applicative features, and implicitly using it.  
Consider:

let foo lst =
    (* pick out just those items I want *)
    let mylst = List.filter f3 lst in 
    (* a bunch of code that uses mylst and not lst *)

Now here, from the function's perspective, lst might as well go away after 
the call to filter.  But the code calling this function might be depending 
upon lst to not be modified by foo.  So I think the applicative/functional 
aspect of Ocaml is used a lot more often than it might look it.

All of which has nothing to do with wether the tree library should be
applicative or mutable.  If the library is created mutable, then in using
it you may have side-effects.  Just like several other libraries/data
structures.

Brian

Re: [Ocaml-lib-devel] Proposal : BinTree

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

> > Here's a module proposal for adding to the ExtLib.
> > This is a binary search tree ( module BinTree ).
> > Operations  add, remove, find are done in Log(n) when the tree is
optimized.
> > This is a mutable version of the data structure.
> >
>
> Is there a reason you did this as a mutable tree and not the "standard"
> applicative version?

That's a good question. Actually is there a standard ?
List are of course applicative, Array are of course mutables, but if Sets
are applicative , Hashtables and Stack are mutable...
Should we provide both mutable and applicative version of every data
structure ?

Actually it's good sometimes to have applicative structures, it fits well
with the functional style where you can write :
    let l = List.map f l in
    let l = List.filter f2 l in
    last_call  (List.filter f3 l)

The main advandage here is being able to pass a modified data structure as
argument to another, without actually modifiying it.
But most of the time, the thing you want to really do is :

let l = last_call (List.filter f3 l)

Please note that here I took "filter" as sample function, because map is
always applicative since it can change the type (BTW, we could add in-place
map to MList) , same for fold.

IMHO, there is only few cases when people are actually using the "immutable"
feature of a data structure, and then if you're providing a "copy" operation
(Enum can do it for you :-) you have the same expression power, with shorter
syntax since you don't have to rebind the same variable ever and ever.

Nicolas Cannasse

Re: [Ocaml-lib-devel] Version 1.0?

[Diego O. F. P. <Die...@et...>]

    Bonjour,

> It is necessary to provide on-site documentation to what is
> *officially* working properly, and to include that in any release.

Not stating clearly what does work and what doesn't is a mistake I
have done in Baire. I really think Jonh Max Skaller is right in this
point and OCaml-lib should avoid doing the same mistake I did.

> If you do that, it doesn't matter if the other half of the library
> isn't ready. Release it anyhow.
>
> 	release early, release often

One of the problems is the stability of interfaces. I have broken and
rewritten from scratch Baire several times, and I will continue doing
so until I get it right.

It is important to be able to do such things when you are not an
experimented developer in the concerned field (and Baire surely is my
first data structure library).

I don't know how the Caml-lib team feels it, but I first though
'initial' Baire would be the only one and I realized much later there
were a lot of wrong things in it.


        Diego Olivier

Re: [Ocaml-lib-devel] Re: [PATCH] updated enum: now concat uses t.fast

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

> > I'll try to review theses patch when I have some time.
> > I think it's good idea to remove the try..catch blocks when we have a
"fast"
> > count in concat and append, because they occur in each call to next .
But
> > for fold / iter , I'm not sure, mainly because a fast count can still be
> > O(N) and cost more than having one try...catch block setuped. Could you
do
> > some benchs using ExtList.enum instead of Enum.init ? The "fast" count
is
> > O(N) here in this case ( but is computed only once ). With big lists (
"when
> > we need speed" ) I'm pretty sure it will be better not to call count.
>
> I was operating under the assumption that "fast" would be set only for
> data structures that had their count readily available -- for
> instance, dynarray and init.

To get this behavior, it would mean that the user have to specify if it's
count() function is "fast" or not when constructing an Enum . Then it's
getting quite difficult for an new user to understand how to create Enums
and we're loosing the simplicity of them . "fast" should remain an internal
optimisation to distinguish the cases when we are calling "force" or not
when counting elements ( the minor speed improvement does not worth having a
more complex interface ).

Nicolas Cannasse

[Ocaml-lib-devel] Re: [PATCH] updated enum: now concat uses t.fast

[Alan P. <ap...@re...>]

In article <01b201c32e41$ce0853b0$2413f9ca@WARP>, Nicolas Cannasse wrote:
>
> I'll try to review theses patch when I have some time.
> I think it's good idea to remove the try..catch blocks when we have a "fast"
> count in concat and append, because they occur in each call to next . But
> for fold / iter , I'm not sure, mainly because a fast count can still be
> O(N) and cost more than having one try...catch block setuped. Could you do
> some benchs using ExtList.enum instead of Enum.init ? The "fast" count is
> O(N) here in this case ( but is computed only once ). With big lists ( "when
> we need speed" ) I'm pretty sure it will be better not to call count.

I was operating under the assumption that "fast" would be set only for
data structures that had their count readily available -- for
instance, dynarray and init.

Re: [Ocaml-lib-devel] [PATCH] updated enum: now concat uses t.fast

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

> Here's an updated version of my patch to enum.ml, including using fast
> in Enum.concat.  A try block on every call to next() was quite
> expensive.  I wasn't able to think of anything useful to do with
> t.count (as opposed to tn.count) in concat, though.
>
> If it's more convenient, I've also posted my modified enum.ml at:
>
>   http://recalcitrant.org/~apost/enum.ml

Thanks Alan.
I'll try to review theses patch when I have some time.
I think it's good idea to remove the try..catch blocks when we have a "fast"
count in concat and append, because they occur in each call to next . But
for fold / iter , I'm not sure, mainly because a fast count can still be
O(N) and cost more than having one try...catch block setuped. Could you do
some benchs using ExtList.enum instead of Enum.init ? The "fast" count is
O(N) here in this case ( but is computed only once ). With big lists ( "when
we need speed" ) I'm pretty sure it will be better not to call count.

Nicolas Cannasse

[Ocaml-lib-devel] [PATCH] updated enum: now concat uses t.fast

[Alan P. <ap...@re...>]

Here's an updated version of my patch to enum.ml, including using fast
in Enum.concat.  A try block on every call to next() was quite
expensive.  I wasn't able to think of anything useful to do with
t.count (as opposed to tn.count) in concat, though.

If it's more convenient, I've also posted my modified enum.ml at:

  http://recalcitrant.org/~apost/enum.ml



--- /usr/local/src/ocaml-extlib/extlib-dev/enum.ml	Tue Jun  3 19:21:46 2003
+++ ./enum.ml	Sun Jun  8 19:20:07 2003
@@ -24,7 +24,7 @@
 	mutable fast : bool;
 }
 
-(* raised by 'next' functions, should NOT goes outside the API *)
+(* raised by 'next' functions, should NOT go outside the API *)
 exception No_more_elements
 
 let _dummy () = assert false
@@ -50,7 +50,7 @@
 				f (n - 1 - !count));
 		clone = (fun () -> init !count f);
 		fast = true;
-	}			
+	}
 
 let force t =
 	let rec clone enum count =
@@ -158,90 +158,153 @@
 	t.clone()
 
 let iter f t =
-	let rec loop () =
-		f (t.next());
-		loop();
-	in
-	try
-		loop();
-	with
-		No_more_elements -> ()
+	if t.fast then
+		(* 10% faster than the exception-based implementation.
+		 * A tail-recursive approach was slower than the for loop.
+		 * Unfortunately, "for _ =" is not allowed.
+		 *)
+		for idx = 1 to t.count () do
+			f (t.next ())
+		done
+	else
+		let rec loop () =
+			f (t.next());
+			loop();
+		in
+		try
+			loop();
+		with
+			No_more_elements -> ()
 
 let iteri f t =
-	let rec loop idx =
-		f idx (t.next());
-		loop (idx+1);
-	in
-	try
-		loop 0;
-	with
-		No_more_elements -> ()
+	if t.fast then
+		for idx = 0 to (t.count ()) - 1 do
+		       	f idx (t.next ())
+		done
+	else
+		let rec loop idx =
+			f idx (t.next());
+			loop (idx+1);
+		in
+		try
+			loop 0;
+		with
+			No_more_elements -> ()
 
 let iter2 f t u =
-	let rec loop () =
-		f (t.next()) (u.next());
-		loop ()
-	in
-	try
-		loop ()
-	with
-		No_more_elements -> ()
+	if t.fast then
+		for idx = 1 to min (t.count ()) (u.count ()) do
+			f (t.next ()) (u.next ())
+		done
+	else
+		let rec loop () =
+			f (t.next()) (u.next());
+			loop ()
+		in
+		try
+			loop ()
+		with
+			No_more_elements -> ()
 
 let iter2i f t u =
-	let rec loop idx =
-		f idx (t.next()) (u.next());
-		loop (idx + 1)
-	in
-	try
-		loop 0
-	with
-		No_more_elements -> ()
+	if t.fast then
+		for idx = 0 to (min (t.count ()) (u.count ())) - 1 do
+			f idx (t.next ()) (u.next ())
+		done
+	else
+		let rec loop idx =
+			f idx (t.next()) (u.next());
+			loop (idx + 1)
+		in
+		try
+			loop 0
+		with
+			No_more_elements -> ()
 
 let fold f init t =
-	let acc = ref init in
-	let rec loop() =
-		acc := f (t.next()) !acc;
-		loop()
-	in
-	try
-		loop()
-	with
-		No_more_elements -> !acc
+	if t.fast then begin
+		(* Runs in 61% of the time required by the exception-based
+		 *   implementation.
+		 * A tail-recursive approach was 5% slower than the for loop.
+		 *)
+		let acc = ref init in
+		for idx = 1 to (t.count ()) do
+			acc := f (t.next ()) !acc
+		done;
+		!acc
+	end
+	else
+		let acc = ref init in
+		let rec loop() =
+			acc := f (t.next()) !acc;
+			loop()
+		in
+		try
+			loop()
+		with
+			No_more_elements -> !acc
 
 let foldi f init t =
-	let acc = ref init in
-	let rec loop idx =
-		acc := f idx (t.next()) !acc;
-		loop (idx + 1)
-	in
-	try
-		loop 0
-	with
-		No_more_elements -> !acc
+	if t.fast then begin
+		let acc = ref init in
+		for idx = 0 to (t.count ()) - 1 do
+			acc := f idx (t.next ()) !acc
+		done;
+		!acc
+	end
+	else
+		let acc = ref init in
+		let rec loop idx =
+			acc := f idx (t.next()) !acc;
+			loop (idx + 1)
+		in
+		try
+			loop 0
+		with
+			No_more_elements -> !acc
 
 let fold2 f init t u =
-	let acc = ref init in
-	let rec loop() =
-		acc := f (t.next()) (u.next()) !acc;
-		loop()
-	in
-	try
-		loop()
-	with
-		No_more_elements -> !acc
+	if t.fast then begin
+		let acc = ref init in
+		for idx = 0 to (min (t.count ()) (u.count ())) - 1 do
+			acc := f (t.next ()) (u.next ()) !acc
+		done;
+		!acc
+	end
+	else
+		let acc = ref init in
+		let rec loop() =
+			acc := f (t.next()) (u.next()) !acc;
+			loop()
+		in
+		try
+			loop()
+		with
+			No_more_elements -> !acc
 
 let fold2i f init t u =
-	let acc = ref init in
-	let rec loop idx =
-		acc := f idx (t.next()) (u.next()) !acc;
-		loop (idx + 1)
-	in
-	try
-		loop 0
-	with
-		No_more_elements -> !acc
+	if t.fast then begin
+		let acc = ref init in
+		for idx = 0 to (min (t.count ()) (u.count ())) - 1 do
+			acc := f idx (t.next ()) (u.next ()) !acc
+		done;
+		!acc
+	end
+	else
+		let acc = ref init in
+		let rec loop idx =
+			acc := f idx (t.next()) (u.next()) !acc;
+			loop (idx + 1)
+		in
+		try
+			loop 0
+		with
+			No_more_elements -> !acc
 
 let find f t =
+	(* Using count is slower on long enums, and only 5-10% faster on very
+	 *   short ones, so don't bother.
+	 *)
 	let rec loop () =
 		let x = t.next() in
 		if f x then x else loop()
@@ -293,40 +356,73 @@
 	from2 next (fun () -> filter f (t.clone()))
 
 let rec filter_map f t =
-    let rec next () =
-        match f (t.next()) with
-        | None -> next()
-        | Some x -> x
-    in
+	let rec next () =
+		match f (t.next()) with
+		| None -> next()
+		| Some x -> x
+	in
 	from2 next (fun () -> filter_map f (t.clone()))
 
+(*
+ * Note that e.next can change, but only from false to true.
+ *
+ * TODO:  given that ta.count is called O(N) times, perhaps its result should be
+ *        cached locally instead.  This could be significant in the case where
+ *        ta is a deeply nested append.
+ *)
 let rec append ta tb = 
-	let append_next = ref _dummy in
-	append_next := (fun () ->
-		try
-			ta.next()
-		with
-			No_more_elements ->
-				append_next := tb.next;
-				!append_next ());
-	{
-		count = (fun () -> ta.count() + tb.count());
-		next = (fun () -> !append_next ());
-		clone = (fun () -> append (ta.clone()) (tb.clone()));
+	let e = {
+		count = _dummy;
+		next = _dummy;
+		clone = _dummy;
 		fast = ta.fast && tb.fast;
 	}
+	and append_count = ref (fun () -> (ta.count ()) + (tb.count ()))
+	and append_clone = ref (fun () -> append (ta.clone ()) (tb.clone ()))
+	and append_next  = ref _dummy in
+        let ta_done () =
+		append_count := tb.count;
+		append_clone := tb.clone;
+		append_next  := tb.next;
+		e.fast       <- tb.fast;
+		!append_next ()
+	in
+	append_next :=
+		if ta.fast then
+			(fun () ->
+				match ta.count () with
+				| 0 -> ta_done ()
+				| _ -> ta.next ())
+		else
+			(fun () ->
+				try
+					ta.next()
+				with
+					No_more_elements -> ta_done ());
+	e.count <- (fun () -> !append_count ());
+	e.next  <- (fun () -> !append_next  ());
+	e.clone <- (fun () -> !append_clone ());
+	e
 
 let rec concat t =
 	let concat_ref = ref _dummy in
-	let rec concat_next() =
-		let tn = t.next() in
-		concat_ref := (fun () ->
-			try
-				tn.next()
-			with
-				No_more_elements ->
-					concat_next());
+	let rec concat_next () =
+		let tn = t.next () in
+		concat_ref := 
+			if tn.fast then
+			    	(fun () ->
+					match tn.count () with
+					| 0 -> concat_next ()
+					| _ -> tn.next ())
+			else
+				(fun () ->
+					try
+						tn.next ()
+					with
+						No_more_elements ->
+							concat_next ());
 		!concat_ref ()
 	in
 	concat_ref := concat_next;
-	from2 (fun () -> !concat_ref ()) (fun () -> concat (t.clone()))
\ No newline at end of file
+	from2 (fun () -> !concat_ref ()) (fun () -> concat (t.clone ()))
+

Re: [Ocaml-lib-devel] Version 1.0?

[John M. S. <sk...@oz...>]

Brian Hurt wrote:

> Here's an interesting debate point- what does a 1.0 release of ExtLib look 
> like?  How close are we?
> 
> Starting this discussion is tantaumont to saying "I think it's ready now", 
> which I'm not.  I'm just thinking of maybe getting a rough sketch of what 
> people want/are working on.
> 
> Here's my short list in approximate order of priority:
> - fix the bug in psqueue
> - unit tests at least some
> - generic red-black tree library
> - doubly linked list library
> - bit fields/bit sets
> 
> Comments?

It is necessary to provide on-site documentation
to what is *officially* working properly, and to
include that in any release.

If you do that, it doesn't matter if the other
half of the library isn't ready. Release it anyhow.

	release early, release often

is often quoted (though I don't know who said it).

What would be important to me, if I found I wanted
to use some functions from it, is that it can be
EASILY USED BY DUMB PROGRAMMERS WHO NEVER WRITE OCAML.

By which I mean, it should be trivial for them to
download the library, build it, do some rudimentary
testing, install it .. and then it is available
for building the *actual* ocaml product they really
want.

On a Unix system an important requirement is to have
a standard default place for it to live, so I can
write scripts to build my ocaml software which happens
to use ExtLib *as if* it were part of the standard
distribution (after its been installed).

I do hate the idea of polluting the offical
distribution directories with third party software,
since it is sometimes nice to rm -rf the whole official
distribution installation and rebuild it (and if
ExtLib lived inside, it too would have to be rebuilt).
OTOH, even Python provides a 'site-packages' directory ..
.. which is a subdirectory of the main library directory :(


-- 
John Max Skaller, mailto:sk...@oz...
snail:10/1 Toxteth Rd, Glebe, NSW 2037, Australia.
voice:61-2-9660-0850

Re: [Ocaml-lib-devel] Unit tests

[John M. S. <sk...@oz...>]

Brian Hurt wrote:


> This is what I was talking about when I mentioned "makefile hacks".  
> Unfortunately, I know enough about the build environment of Windows 
> (despite several years busily repressing memories) that I am wary of doing 
> and scripting hacks.  The only scripting language I am sure exists is 
> Ocaml.


Then use it. Only, please get rid of primary makefiles.

Make is a very stupid, ugly, unworkable tool.
Its use should be avoided at all costs.
It offers only one advantage: familiarity for uses to
say

	make

to build something. I don't know if this can be done
but a simple makefile:

all:
	ocaml xlmake <arguments>

which simply invokes the ocaml program
xlmake with the arguments to the command
make, would even solve that problem.

Otherwise I'm happy to read the doce enough
to learn I have to type

	xlmake

or
	ocaml xlmake.ml

to do a make.

You may note that to do this efficiently would
require some kind of topological dependency sorting:
well, ExtLib has a data structure for that doesn't it? :-)

-- 
John Max Skaller, mailto:sk...@oz...
snail:10/1 Toxteth Rd, Glebe, NSW 2037, Australia.
voice:61-2-9660-0850

[Ocaml-lib-devel] [PATCH] minor cleanup

[Alan P. <ap...@re...>]

Here's a little patch cleaning up Enum.append slightly from the
previous one.

--- enum.ml	2003/06/08 10:09:07	1.4
+++ enum.ml	2003/06/08 10:49:45
@@ -379,30 +379,26 @@
 	}
 	and append_count = ref (fun () -> ta.count() + tb.count())
 	and append_clone = ref (fun () -> append (ta.clone()) (tb.clone()))
-	and append_next  = ref _dummy
+	and append_next  = ref _dummy in
+        let ta_done () =
+		append_count := tb.count;
+		append_clone := tb.clone;
+		append_next := tb.next;
+		e.fast <- tb.fast;
+		!append_next ()
 	in
 	append_next := begin
 		if ta.fast then
 			(fun () ->
 				match ta.count () with
-				| 0 ->
-					append_count := tb.count;
-					append_clone := tb.clone;
-					append_next := tb.next;
-					e.fast <- tb.fast;
-					!append_next ()
+				| 0 -> ta_done ()
 				| _ -> ta.next ())
 		else
 			(fun () ->
 				try
 					ta.next()
 				with
-					No_more_elements ->
-						append_count := tb.count;
-						append_next := tb.next;
-						append_clone := tb.clone;
-						e.fast <- tb.fast;
-						!append_next ())
+					No_more_elements -> ta_done ())
 	end;
 	e.count <- (fun () -> !append_count ());
 	e.next  <- (fun () -> !append_next  ());