ocaml-lib-devel — Developer's mailing list

Re: [Ocaml-lib-devel] Enum API change: export next

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

> Blech.  I just realized that many (most?) of you are in France- like 6-7 
> hours ahead of me.  And that by the time I submitted anything on Friday 
> you had all gone home for the weekend.  My apologies- I'll unroll the 
> changes.

That's even worst than you think, since I'm in Kyoto for few months now !
that's GMT +9  I think.

Nicolas Cannasse

Re: [Ocaml-lib-devel] Enum API change: export next

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

By the way, I've commited a new version of enum.ml[i] which removes the 
exported next.  And a new version of extList.ml which stops using the no 
longer exported next, and instead uses Obj.magic.  I haven't inlined 
_setcdr yet.

Brian

[Ocaml-lib-devel] Names for xarray: I propose dynarray

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

According to the NIST, what I've implemented is a dynamic array:
http://www.nist.gov/dads/HTML/dynamicarray.html

I hereby propose we rename it dynarray then.  I'm not worried about losing 
revision control history- if I hadn't checked it in, we wouldn't have had 
any to lose :-).

Brian

Re: [Ocaml-lib-devel] ExtList: using _setcdr instead of Obj.magic

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

On Mon, 21 Apr 2003, Nicolas Cannasse wrote:

> > Went through and changed all the inlined _setcdr calls to normal _setcdr
> > calls.
> 
> Uh ! it took me some time to inlined them :'(

Then I wish you had asked me before doing so.  As I'm opposed to it.

> 
> > a) If we never call the function, why define it?
> 
> It is called , it should actually be called when call - complexity is lower
> than O(n) since the overhead is not big.

Which is never in list functions, that I know about.

> 
> > b) function calls aren't that expensive.  And _setcdr is probably inlined
> > in most cases anyways.
> 
> In native code, there is no problem with it.
> In bytecode, the speedups are around 20% and since we're working an on
> Standard library, it would be good to provide efficient code to the
> community, don't you think ? That's why after lots of benchs and differents
> versions I ended up inlining the calls.

Hmm.  I'm less concerned about performance with bytecode.  Bluntly, if you 
want speed, go native.  If you're going bytecode, you're giving up a lot 
of speed anyways.  But I'm still surprised it's not inlined in the 
bytecode case as well.  Just to check- you did use -inline, right?

> 
> > c) In the future, when we have to change the magic incantation to make it
> > work, we only have to change it once, in _setcdr, and not all over.
> 
> We will never have to do so.

I've yet to hear this in a case where it turned out to be so.  And I 
notice the changes are sneaking out of ExtList- I note that Enum has an 
Obj.magic call which is effectively _setcdr.  On my to-do list was to take 
a long hard look at Enum.force to see if I could move that _setcdr back 
into ExtList where it belongs.

Brian

Re: [Ocaml-lib-devel] Enum API change: export next

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

Blech.  I just realized that many (most?) of you are in France- like 6-7 
hours ahead of me.  And that by the time I submitted anything on Friday 
you had all gone home for the weekend.  My apologies- I'll unroll the 
changes.

On Mon, 21 Apr 2003, Nicolas Cannasse wrote:

> > We're already exporting count, export next as well.  Why I want this will
> > be clear in a moment...
> 
> Ok, but I don't agree :
> 
> I do understand that you want to remove 'magic' calls from the ExtList, but
> actualy, the problem is that we are already doing magic calls in setcdr, so
> why would we need to add a primitive to Enum for that ? But that's not the
> main problem... The problem is that WE SHOULD NOT export next since :
> 
> 1) its semantic it is not really defined, and Enum.next does not make sense
> since 99.9999% of the time you're applying the same function to all elements
> of the Enum.

The other 0.0001% of the time, you're screwed?  And I think it's more like 
99.9%/0.1% of the time- the difference is important, it's rare but it 
happens.  As for the semantic being not really defined, a) I thought it 
was obvious, and b) this is a problem.  If I, joe ocaml programmer, don't 
know what the semantics of next is, then I can't define a new Enum.  Which 
means I can't define a new Enum of my new data structure.  Personally, I 
don't think the semantics of next are *that* complicated, and should be 
that hard to define.

> 2) I don't want beginners start programming using  while Enum.has_more e do
> let x = Enum.next .... done because it's really a BAD WAY ( Java like ) of
> working with enumerations (and it's involving a call to count each time ! )

a) I actually had an idea for this: have Enum.make take three functions- 
next, count, and has_next.  This cleans up a lot.  Especially a lot of 
places where we need to catch exceptions to detect the end of the list.  
This at least gets rid of calling count each time we call has_next.  As it 
stands, has_next is nigh unto useless.

b) So, being Java like in calling extensible arrays Vectors is good, but 
allowing Java like Iterator code is bad?   Of the two, I'll take the 
iterator code.

> 3) There is big problems of exception scoping !! that's the major fact why I
> hided Enum.next :
>     for example an user could do Enum.map with a function that is using
> Enum.next, and then call for example Enum.iter on it... if the user-defined
> map function raises No_more_elements ( because the user didn't check
> properly for it, or because he simply wants to catch the exception at an
> upper lever ) then this exception will be catched by Enum.iter which will
> simply ignore it and stop.... Serious problem here for debugging big piece
> of codes !

Having an efficient has_next allows us to move away from using exceptions 
to detect the end of the list.  So, Enum.iter could then be defined as:

let iter f e =
    while (has_more e) do
        f (next e)
    done
;;

Now, the exception really does mean an exceptional event has happened- 
either has_more lied to us, or we have some sort of race condition and 
some other thread read the last element between our calling of has_more 
and our calling of next.  Both rare occurances.  And should, for whatever 
stupid reason, f raises No_more_elements the exception gets passed along.

But I'm not too worried about f raising No_more_elements.  I find that 
unlikely.

> Sorry not to have talked about theses points before, but please revert the
> changes since I'm feeling really about this addin' :)

I will.  I'm not giving up the debate however! :-)

Brian

Re: [Ocaml-lib-devel] PSQueue and XArray committed

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

> Threw the sources into CVS.
>
> Brian

Brian, could we end the talks about XArray naming before committing ( too
late this time ). Before since we need to rename it that will be a remove /
add. My thoughts are still strong about Vector ( I know you don't like it ,
but that's the most appropriate name ) please propose another of if you have
better idea.

Nicolas Cannasse

Re: [Ocaml-lib-devel] ExtList: using _setcdr instead of Obj.magic

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

> Went through and changed all the inlined _setcdr calls to normal _setcdr
> calls.

Uh ! it took me some time to inlined them :'(

> a) If we never call the function, why define it?

It is called , it should actually be called when call - complexity is lower
than O(n) since the overhead is not big.

> b) function calls aren't that expensive.  And _setcdr is probably inlined
> in most cases anyways.

In native code, there is no problem with it.
In bytecode, the speedups are around 20% and since we're working an on
Standard library, it would be good to provide efficient code to the
community, don't you think ? That's why after lots of benchs and differents
versions I ended up inlining the calls.

> c) In the future, when we have to change the magic incantation to make it
> work, we only have to change it once, in _setcdr, and not all over.

We will never have to do so.
And if we do, I volunteer to make the changes.

Nicolas Cannasse

Re: [Ocaml-lib-devel] Enum API change: export next

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

> We're already exporting count, export next as well.  Why I want this will
> be clear in a moment...

Ok, but I don't agree :

I do understand that you want to remove 'magic' calls from the ExtList, but
actualy, the problem is that we are already doing magic calls in setcdr, so
why would we need to add a primitive to Enum for that ? But that's not the
main problem... The problem is that WE SHOULD NOT export next since :

1) its semantic it is not really defined, and Enum.next does not make sense
since 99.9999% of the time you're applying the same function to all elements
of the Enum.
2) I don't want beginners start programming using  while Enum.has_more e do
let x = Enum.next .... done because it's really a BAD WAY ( Java like ) of
working with enumerations (and it's involving a call to count each time ! )
3) There is big problems of exception scoping !! that's the major fact why I
hided Enum.next :
    for example an user could do Enum.map with a function that is using
Enum.next, and then call for example Enum.iter on it... if the user-defined
map function raises No_more_elements ( because the user didn't check
properly for it, or because he simply wants to catch the exception at an
upper lever ) then this exception will be catched by Enum.iter which will
simply ignore it and stop.... Serious problem here for debugging big piece
of codes !
    So that's why I did wrote some comment about No_more_elements :  (*
raised by 'next' functions, does NOT goes outside the API *) so the user can
NEVER make it raised ( only by doing raise Enum.No_more_elements by hand in
to_enum implementations ).

Sorry not to have talked about theses points before, but please revert the
changes since I'm feeling really about this addin' :)

Nicolas Cannasse

[Ocaml-lib-devel] More additions to Enum API

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

It's a cold, rainy, sunday afternoon and I'm bored- so I added the
following functions to the Enum API: iter2, iter2i, foldi, fold2, fold2i,
map2, map2i.

The *i functions pass an index counter which counts from 0 to n through 
the enumeration.  The 2 functions take two enumerations.  Note that I'm 
not doing a lot of checking at the moment to make sure the two 
enumerations are the same length.  The iterations stop when one interation 
runs out of elements.  I took a swipe at adding pedantic checking- while 
it's possible, it's not pretty.  Although most of the unprettiness came 
from handling unknown-length enumerations (this might be an argument 
against them)- I am more inclined that pedantic assertions that the two 
enumerations be the same length simply isn't that important.

Brian

[Ocaml-lib-devel] Grr- a reason not use tabs

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

So you get an error from ocamlc like (names changed to protect the 
guilty):

File "foo.ml", line 127, characters 22-26:
This expression has type int but is here used with type int -> 'a

Normally, in vim you can go 127G22| and bounce directly to what it's 
having a typing problem with.  Unfortunately, ocamlc counts tabs as single 
characters, vim counts tabs as however many charaters a tabstop is.  So 
you bounce to the incorrect place in the line.  This can have you run down 
a blind alley thinking that variable bar was the problem, when it was 
actually variable baz.

Spaces do not get misinterpreted like that.

Brian

[Ocaml-lib-devel] Xarray change: use iteri instead of fold

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

In Xarray in several places I was (ab) using fold to implement iteri.  
Just switch over to using Enum.iteri instead.

Brian

[Ocaml-lib-devel] ExtList change went in

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

Quashed the use of Obj.magic in of_enum to use Enum.next instead.

Brian

[Ocaml-lib-devel] Enum api additions

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

Hearing no dissent, I commited the next() API addition to Enum.  In 
addition, I added iteri and mapi functions.  The new mapi is lazy and O(1) 
like map is.

Brian

Re: [Ocaml-lib-devel] unknown length, user defined enumerations?

[Dmitry B. <db...@ma...>]

"Nicolas Cannasse" <war...@fr...> writes:

> Yes, the Enum module is quite more "abstract" then the Stream one, and has
> differents goals.
> BTW, about your "count" problem you HAVE TO return the lines count, because
> for exemple Array.of_enum will require it to create the array before putting
> elements inside. The solution is quite easy to do : when "count" is called
> the first time, you're reading all remaining files and then have to modify
> your Enum.t which will now iter on the builded list. This is almost what the
> "Enum.force" is doing, but I modified its behavior so it can be used this
> way.
>
> The problem is that you can't right now do a "force" in a count function
> since you're have not yet any Enum.t to work on, but ok let's try :
> Here's the code :
>
> let lines_enum ch =
>     let dummy = ref None in
>     let e = Enum.make
>         ~next:(fun () -> try input_line ch with End_of_file -> raise
> Enum.No_more_elements)
>         ~count:(fun () -> match !dummy with None -> assert false | Some e ->
> Enum.force e; Enum.count e)
>     in
>     dummy := e;
>     e

It's OK for regular files, but what if you're reading something like socket
or pipe that is endless by its nature? You usually look into the returned
line and decide if it's enough. So maybe to parameterize your line_enum
fuction the way like this:

let lines_enum ?(is_eof=(fun s -> false)) ch =
    let dummy = ref None in
    let e = Enum.make
        ~next:(fun () ->
		 try
		   let line = input_line ch in
		     if is_eof line then raise Enum.No_more_elements else line
		 with
		     End_of_file -> raise Enum.No_more_elements)
        ~count:(fun () -> match !dummy with None -> assert false | Some e ->
Enum.force e; Enum.count e)
    in
    dummy := e;
    e

Just an idea ...

- Dmitry Bely

[Ocaml-lib-devel] Bag O' Changes to xarray.ml(i)

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

I forgot to add in a bunch of changes suggested by members of this list-
all the ones I remember are now in there.

Brian

[Ocaml-lib-devel] PSQueue and XArray committed

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

Threw the sources into CVS.

Brian

[Ocaml-lib-devel] Obj.magic-less of_enum

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

In my ongoing quest to remove all but one Obj.magic calls from ExtList, I 
propose the following implementation for ExtList.of_enum:

let of_enum e =
    try
        let h = [ Enum.next e ] in
        let _ = Enum.fold (fun x acc ->
            let r = [ x ] in
            _setcdr acc r;
            r) h e in
        h
    with Enum.No_more_elements -> []

(I have tabstop set to 4 currently.  That's a different argument.)

This depends upon the exported Enum.next patch.  Basically, if the enum is 
empty creating the head element throws a caught exception and returns [], 
otherwise we go on to the classic fold implementation.

Brian

[Ocaml-lib-devel] Enum API change: export next

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

We're already exporting count, export next as well.  Why I want this will 
be clear in a moment...

Unlike the _setcdr change, I thought about it before checking this change 
in.  So that people can comment before I commit.

Brian

[Ocaml-lib-devel] ExtList: using _setcdr instead of Obj.magic

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

Went through and changed all the inlined _setcdr calls to normal _setcdr 
calls.

a) If we never call the function, why define it?

b) function calls aren't that expensive.  And _setcdr is probably inlined 
in most cases anyways.

c) In the future, when we have to change the magic incantation to make it 
work, we only have to change it once, in _setcdr, and not all over.

Brian

Re: [Ocaml-lib-devel] unknown length, user defined enumerations?

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

On Fri, 18 Apr 2003, Nicolas Cannasse wrote:

> BTW, about your "count" problem you HAVE TO return the lines count, because
> for exemple Array.of_enum will require it to create the array before putting
> elements inside. The solution is quite easy to do : when "count" is called
> the first time, you're reading all remaining files and then have to modify
> your Enum.t which will now iter on the builded list. This is almost what the
> "Enum.force" is doing, but I modified its behavior so it can be used this
> way.

This is suboptimal in cases- like Xarray and list- where they don't really 
need the count.  Xarray is a very good example.  Count isn't *needed*, but 
it is handy.

Instead, I'd implement Array.of_enum like:

let rec of_enum enum =
    let c = Enum.count enum in
    if (c < 0) then
        (* Convert the enum to a list, then create the array from the
           list *)
        of_enum (List.enum_of (List.of_enum enum))
    else
        Array.init c (fun _ -> Enum.next enum)
;;

This basically does the same thing your example does- it recreates the 
enum as a list, and then enumerates that.

The only of_enum function I can think of that *needs* a count is 
Array.of_enum.  I can think of a lot of enumerations where I don't know, 
at the start, how many elements are in the enumeration.

Brian

Re: [Ocaml-lib-devel] Include usage

[Remi V. <van...@la...>]

"Nicolas Cannasse" <war...@fr...> writes:

> Hi list !
>
> I think it would be better to reduce the size of the code and not to
> duplicate Ocaml Stdlib source code to simply use the "include" keyword.
> So for example our extHashtbl.ml file would looks like :
>
> module Hashtbl = struct
>     include Hashtbl (* the OCaml std lib one *)
>     (**  add new functions **)
> end
>
> This way we can even override the OCaml StdLib functions by redefining them
> after the include statement.
> I think it would be nice to reduce this way the extList.ml code to only
> modified/new functions, that would make things a lot clearer and results a
> lower code size.
>
> What do you think of it ?

Seem a good Idea.


-- 
Rémi Vanicat
va...@la...
http://dept-info.labri.u-bordeaux.fr/~vanicat

Re: [Ocaml-lib-devel] XML Light

[Olivier A. <ol...@us...>]

Hi,

 Nicolas Cannasse [Friday 18 April 2003] :
 > I'm currently rewriting my Xml-Light library which is a minimal Xml
 > parser/printer and adding DTD support to it. It's almost done (all parsing
 > is ok, now I still have to do some testing and DTD proving) but before
 > releasing it, since I would like it to be part of the ExtLib, I'm calling
 > for features / comments. Here's joined the current MLI for Xml and Dtd - not
 > yet finalized. The implementation code is quite small, there is a lexer and
 > a small parser for DTD elements expressions.

You're using `parser' as an identifier for a type : it clashes with
camlp4 where `parser' is a keyword introducing stream matching. Maybe
it should be named something else.

-- 
   Olivier

[Ocaml-lib-devel] Include usage

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

Hi list !

I think it would be better to reduce the size of the code and not to
duplicate Ocaml Stdlib source code to simply use the "include" keyword.
So for example our extHashtbl.ml file would looks like :

module Hashtbl = struct
    include Hashtbl (* the OCaml std lib one *)
    (**  add new functions **)
end

This way we can even override the OCaml StdLib functions by redefining them
after the include statement.
I think it would be nice to reduce this way the extList.ml code to only
modified/new functions, that would make things a lot clearer and results a
lower code size.

What do you think of it ?

Nicolas Cannasse

[Ocaml-lib-devel] XML Light

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

Hi list !

I'm currently rewriting my Xml-Light library which is a minimal Xml
parser/printer and adding DTD support to it. It's almost done (all parsing
is ok, now I still have to do some testing and DTD proving) but before
releasing it, since I would like it to be part of the ExtLib, I'm calling
for features / comments. Here's joined the current MLI for Xml and Dtd - not
yet finalized. The implementation code is quite small, there is a lexer and
a small parser for DTD elements expressions.

Any comments are welcomed !

Nicolas Cannasse

Re: [Ocaml-lib-devel] unknown length, user defined enumerations?

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

> The problem is that you can't right now do a "force" in a count function
> since you're have not yet any Enum.t to work on, but ok let's try :
> Here's the code :
...

BTW, If you look at implementation of Enum.filter, that's what it is doing,
since you cannot know the elements count before actually having filtered
them.

Nicolas Cannasse