ocaml-lib-devel Mailing List for OCaml ExtLib (Page 89)

SourceForge Headquarters 1320 Columbia Street Suite 310 San Diego, CA 92101 +1 (858) 422-6466

At work, our cvs is set up to email notices out to a mailing list when 
commits happen.  Any chance of setting up our cvs server to do that?

BTW, I inlined setcdr, as discussed.

Brian

Hi,

I just noticed there is already a web page setuped at :
http://ocaml-lib.sourceforge.net/
But it's quite out dated.
It there some good willed people around who would like to take care of it ?

Thanks,
Nicolas Cannasse

> 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 ?

Done for ExtList.

Nicolas Cannasse

On Tue, 22 Apr 2003, Nicolas Cannasse wrote:

> > > 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.
> 
> I was talking about complexity in term of numbers of calls to _setcdr.
> BTW, you're right, I'm not sure there is functions with only one call to
> _setcdr

So was I.  I can't think of a function that calls _setcdr that doesn't 
call it O(n) times.  Which means we never called _setcdr- I remember 
grepping for it and not finding it.

> 
> > I've yet to hear this in a case where it turned out to be so.
> 
> This will need a very major changes in the entire Ocaml sources since it
> will involve modifying the current memory representation, and I'm pretty
> sure it won't happen before few years.

Yeah, this does strike me as being an unlikely change.  How many different 
formats are there for an immutable linked list are there?  2?  data then 
next, or next then data.  They chose the first one.  And I don't see any 
advantage to them switching.

> 
> > 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.
> 
> From my point of view, the setcdr is a trick which should of course not be
> put in the interface extList.mli ( we agreed on that before ). And so if you
> want to use it in Enum, you have to rewrite it. This is a performance trick,
> since we could always build the list in the other way and then rev it, and a
> safe trick since we could instead use a non tail-rec call.
> As a performance trick , it should be inlined.
> As a safe trick, it shouldn't be shown to the user, and a _setcdr function
> shouldn't even exists :)
> 

OK.  You talked me into it.  _setcdr goes away, and I'll replace 
everything with Obj.magic calls.

Brian

> > 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.

I was talking about complexity in term of numbers of calls to _setcdr.
BTW, you're right, I'm not sure there is functions with only one call to
_setcdr

> I've yet to hear this in a case where it turned out to be so.

This will need a very major changes in the entire Ocaml sources since it
will involve modifying the current memory representation, and I'm pretty
sure it won't happen before few years.

> 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.

From my point of view, the setcdr is a trick which should of course not be
put in the interface extList.mli ( we agreed on that before ). And so if you
want to use it in Enum, you have to rewrite it. This is a performance trick,
since we could always build the list in the other way and then rev it, and a
safe trick since we could instead use a non tail-rec call.
As a performance trick , it should be inlined.
As a safe trick, it shouldn't be shown to the user, and a _setcdr function
shouldn't even exists :)

Nicolas Cannasse

> 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 :-).

It would be perhaps nice to have then then same name-prefix for both
"mutable" list and "mutable" array.
RefList / RefArray ( this one make sense since the type Xarray.t contains a
mutable 'array field )
or
DynList / DynArray

Nicolas Cannasse

> 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

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

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

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

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

> 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

> 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

> 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

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

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

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

Brian

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

Brian

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

"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

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

Threw the sources into CVS.

Brian

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

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

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

2003	Jan	Feb (81)	Mar (97)	Apr (88)	May (80)	Jun (170)	Jul (9)	Aug	Sep (18)	Oct (58)	Nov (19)	Dec (7)
2004	Jan (22)	Feb (9)	Mar (28)	Apr (164)	May (186)	Jun (101)	Jul (143)	Aug (387)	Sep (69)	Oct (14)	Nov (8)	Dec (99)
2005	Jan (10)	Feb (34)	Mar (24)	Apr (7)	May (41)	Jun (20)	Jul (3)	Aug (23)	Sep (2)	Oct (26)	Nov (41)	Dec (7)
2006	Jan (6)	Feb (3)	Mar (11)	Apr	May	Jun (5)	Jul (8)	Aug (20)	Sep	Oct (6)	Nov (5)	Dec
2007	Jan	Feb (1)	Mar	Apr (3)	May (2)	Jun	Jul	Aug (1)	Sep (7)	Oct (6)	Nov (19)	Dec (11)
2008	Jan	Feb (7)	Mar (9)	Apr (21)	May (42)	Jun (27)	Jul (28)	Aug (26)	Sep (16)	Oct (32)	Nov (49)	Dec (65)
2009	Jan (35)	Feb (20)	Mar (36)	Apr (42)	May (111)	Jun (99)	Jul (70)	Aug (25)	Sep (15)	Oct (29)	Nov (3)	Dec (18)
2010	Jan (10)	Feb (4)	Mar (57)	Apr (63)	May (71)	Jun (64)	Jul (30)	Aug (49)	Sep (11)	Oct (4)	Nov (2)	Dec (3)
2011	Jan (1)	Feb (1)	Mar	Apr	May	Jun (1)	Jul (1)	Aug (2)	Sep	Oct	Nov	Dec (1)
2012	Jan	Feb	Mar	Apr	May	Jun	Jul	Aug (1)	Sep	Oct	Nov	Dec
2013	Jan	Feb (1)	Mar	Apr	May	Jun	Jul	Aug	Sep	Oct	Nov	Dec
2014	Jan	Feb	Mar	Apr	May	Jun (2)	Jul	Aug	Sep (1)	Oct	Nov (1)	Dec
2015	Jan	Feb	Mar	Apr	May	Jun	Jul	Aug (1)	Sep	Oct	Nov	Dec
2021	Jan	Feb	Mar	Apr	May	Jun	Jul	Aug	Sep (1)	Oct	Nov	Dec
2022	Jan	Feb (1)	Mar	Apr	May	Jun	Jul	Aug	Sep	Oct	Nov	Dec
2023	Jan	Feb	Mar	Apr	May	Jun	Jul	Aug	Sep (1)	Oct	Nov	Dec (1)
2024	Jan (1)	Feb (3)	Mar (6)	Apr (2)	May	Jun	Jul	Aug	Sep	Oct	Nov	Dec (1)
2025	Jan (2)	Feb	Mar	Apr	May	Jun	Jul (1)	Aug (1)	Sep (5)	Oct	Nov	Dec

ocaml-lib-devel Mailing List for OCaml ExtLib (Page 89)

ocaml-lib-devel — Developer's mailing list