ocaml-lib-devel — Developer's mailing list

Re: [Ocaml-lib-devel] Request polymorphic set and map

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

> > > What about:
> > >
> > > let s1 = ExtSet.make cmp1 in
> > > let s2 = ExtSet.make cmp2 in
> > > ...
> > > let s = ExtSet.union s1 s2
> >
> > Should raise something like "exception Comparator_differs" if not
physical
> > equality between s1.cmp and s2.cmp.
>
> Physical equality of functions can be tricky. Example:

Of course, we cannot ensure the logicial equality of functions, but I'm
pretty sure that most of the cases, comparators are globaly defined ,
because you want to have a specific comparaison behavior , different from
the "Pervasives.compare" default one.

> > in functor approach, you cannot actually do it since the comparator is
bound
> > to a type/module so errors are detected at compilation time and not at
> > runtime.
>
> Well, I have to admit that I like the compile-time check a lot more.

Then use functors :-) We will not force you to use ExtSet !

> > But that's a small tradeoff compared to the ability to define sets
> > without having to define a module for every type you need.
>
> Defining module isn't as painful :-) It can be in fact done in single
> line:
>
> module Iset = Set.Make(struct type t = int let compare = compare end)

The problem with functors is more that your Iset is not compatible with
others users (localy defined) Iset , since they're different modules. Then
when you have for example two libraries using both integer sets, you have to
manage the two types dinstincly and eventualy write convertion functions
from one to the other, which is somehow stupid :-)

Nicolas Cannasse

Re: [Ocaml-lib-devel] Request polymorphic set and map

[Michal M. <mal...@pl...>]

On Tue, Jun 17, 2003 at 04:41:58PM +0900, Nicolas Cannasse wrote:
> > What about:
> >
> > let s1 = ExtSet.make cmp1 in
> > let s2 = ExtSet.make cmp2 in
> > ...
> > let s = ExtSet.union s1 s2
> 
> Should raise something like "exception Comparator_differs" if not physical
> equality between s1.cmp and s2.cmp.

Physical equality of functions can be tricky. Example:

# let g () = fun x -> x;;
val g : unit -> 'a -> 'a = <fun>
# g () == g ();;
- : bool = false

It is possible that you define comparator function to be local (but not
to depend on environment), and your runtime check will fail.

let f () =
  let cmp a b = a.x - b.x in
  let s = ExtSet.make cmp in
  ...
  s

> in functor approach, you cannot actually do it since the comparator is bound
> to a type/module so errors are detected at compilation time and not at
> runtime. 

Well, I have to admit that I like the compile-time check a lot more.

> But that's a small tradeoff compared to the ability to define sets
> without having to define a module for every type you need.

Defining module isn't as painful :-) It can be in fact done in single
line:

module Iset = Set.Make(struct type t = int let compare = compare end)

-- 
: Michal Moskal :: http://www.kernel.pl/~malekith : GCS {C,UL}++++$ a? !tv
: When in doubt, use brute force. -- Ken Thompson : {E-,w}-- {b++,e}>+++ h

Re: [Ocaml-lib-devel] Request polymorphic set and map

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

> > People keep saying that they can cut and paste the
> > Functor based Set and Map to get a polymorphic version
> > using the builtin-compare, so that:
> >
> > let s = ExtSet.empty in
> > let s = Ext.set add_element s 0
> >
> > for example, works (the type is deduced like for a list
> > or Hashtble, rather than being manually instantiated.)
> >
> > Is there a plan to put these into Extlib?
> > Another option would be
> >
> > let s = ExtSet.make cmp in ..
> >
> > where cmp is suitable comparator.
>
> What about:
>
> let s1 = ExtSet.make cmp1 in
> let s2 = ExtSet.make cmp2 in
> ...
> let s = ExtSet.union s1 s2

Should raise something like "exception Comparator_differs" if not physical
equality between s1.cmp and s2.cmp.
in functor approach, you cannot actually do it since the comparator is bound
to a type/module so errors are detected at compilation time and not at
runtime. But that's a small tradeoff compared to the ability to define sets
without having to define a module for every type you need.

Nicolas Cannasse

Re: [Ocaml-lib-devel] Request polymorphic set and map

[Michal M. <mal...@pl...>]

On Tue, Jun 17, 2003 at 01:12:32PM +1000, John Max Skaller wrote:
> People keep saying that they can cut and paste the
> Functor based Set and Map to get a polymorphic version
> using the builtin-compare, so that:
> 
> 	let s = ExtSet.empty in
> 	let s = Ext.set add_element s 0
> 
> for example, works (the type is deduced like for a list
> or Hashtble, rather than being manually instantiated.)
> 
> Is there a plan to put these into Extlib?
> Another option would be
> 
> 	let s = ExtSet.make cmp in ..
> 
> where cmp is suitable comparator.

What about:

let s1 = ExtSet.make cmp1 in
let s2 = ExtSet.make cmp2 in
...
let s = ExtSet.union s1 s2

?

-- 
: Michal Moskal :: http://www.kernel.pl/~malekith : GCS {C,UL}++++$ a? !tv
: When in doubt, use brute force. -- Ken Thompson : {E-,w}-- {b++,e}>+++ h

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

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

> > Ok, so let's provide them a "list only" version of fold_right (
ExtList.fold
> > ? ) that will do the job in a tail-rec way using internals set_cdr to
> > construct the list in the user-wanted way. This of course does not cover
all
> > the cases, but should be enough to preserve speed where it is needed
(btw
> > enums should be even better for this kind of things ^^;) . The
difference of
> > this fold is that we are iterating from left_to_right but I don't think
that
> > a lot of users actually wants to do so.
>
> Well, we already have List.map to convert a 'a list to a 'b list and keep
> the order the same.

List.map is not the same as List.fold !
- with fold, you can "skip" elements in a list, doing then a filter_map
- you can access the accumulator , and this is useful in many cases (no
duplicates for example)

I suggest having something like :

let fold f l =
    let x = [ Obj.magic () ] in
    let rec loop dst = function
        | [] -> ()
        | h :: t ->
            let r = [ f h (List.tl x) ] in
            Obj.set_field (Obj.repr dst) 1 (Obj.repr r);
            loop r t
    in
    loop x;
    List.tl x

Nicolas Cannasse

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

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

Brian Hurt wrote:

> On Tue, 17 Jun 2003, John Max Skaller wrote:
>
> Loop overhead is negligable.  Especially with today's imbalance between 
> processor and memory speeds, I'd be way more concerned about thrashing L1 
> code cache.  Especially for short lists which are probably in cache 
> anyways.  On a P4, a *single* cache miss can cost over 300 clock cycles.  
> I can do an awful lot of loops in 300 clock cycles.


That's true.


> With fold_right, it's impossible - 

On the contrary. A fold right has to recurse all down the list,
which is nasty, but after that it could be cache efficient in
the extreme: we have a linear array of the data on the stack now,
which the cache should handle with very high efficiency both
because it only requires sequential memory access and also because
if the system has any smarts, it knows the stack is a good candidate
for sequential-predictive caching. So it's possible the right fold, after
linearising the list, is actually FASTER than a left fold since
the whole of the operation can sometimes be done without a single
cache-miss if the predictive memory loading is optimised appropriately.
[Linear memory fetches can take 0 real time if they're spaced out
enough -- the memory itself can sometime cache linear chunks]

Basically: the tail chasing is efficient because while it
looks all over memory for the list nodes, the code
to do that is a tight loop in the cache. Then the user
fold operation can be loaded into the cache, and operate
directly on in-cache data in the case of integers,
or with one access for pointers.

The left fold, on the other hand, mixes the code
for the list access and folding, which may spill the
instruction cache, and there is no opportunity
for sequential-prediction (only invariant prediction
for the fold result). The additional code for the
left fold atom may also force a register spill
which doesn't happen in the right_fold (the fold accumulator)
and of course registers (L0 cache :-) are even faster
than the L1 cache.

Well, I'm totally unsure of any of this, but don't
be TOO fast to assume fold_right is always a dog :-)

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

Re: [Ocaml-lib-devel] Request polymorphic set and map

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

> People keep saying that they can cut and paste the
> Functor based Set and Map to get a polymorphic version
> using the builtin-compare, so that:
>
> let s = ExtSet.empty in
> let s = Ext.set add_element s 0
>
> for example, works (the type is deduced like for a list
> or Hashtble, rather than being manually instantiated.)
>
> Is there a plan to put these into Extlib?
> Another option would be
>
> let s = ExtSet.make cmp in ..
>
> where cmp is suitable comparator.

Yes, we would actually need this one , in a ploymorphic defunctorized way.
That was my point when I sent the BinTree module, but it's not so good
actually. Instead of using Set I would prefer being able to "shade" elements
just like Hashtable is doing so one can simply shift to/from Hashtable/
"ExtSet" with only replacing the module name . This way we need to have a
compatible interface and behavior.

Nicolas Cannasse

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

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

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

I might have solve the problem with a better implementation :

let max = 1000

let fold_right f l init =
    let rec tail_loop acc = function
       | [] -> acc
       | h :: t -> tail_loop (f h acc) t
    in
    let rec loop n = function
        | [] -> init
        | h :: t ->
            if n < max then
                f h (loop (n+1) t)
            else
                f h (tail_loop init (List.rev t))
    in
    loop 0 l

This way for short list you're only doing some extra count, and for long
list you're ending doing a rev , but only on the remaining part of the list.

Nicolas Cannasse

[Ocaml-lib-devel] Request polymorphic set and map

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

People keep saying that they can cut and paste the
Functor based Set and Map to get a polymorphic version
using the builtin-compare, so that:

	let s = ExtSet.empty in
	let s = Ext.set add_element s 0

for example, works (the type is deduced like for a list
or Hashtble, rather than being manually instantiated.)

Is there a plan to put these into Extlib?
Another option would be

	let s = ExtSet.make cmp in ..

where cmp is suitable comparator.

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

[Ocaml-lib-devel] Array interface

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

I finally managed to get hold of the archive.
If you want to make me a developer I can contribute to the documentation.

Comments. DynArray.make size null: makes an array of length zero,
with size element slots initialised by null.

Can't you initialise the empty slots with Obj.magic(0)?
I don't want to put an element here. I may not have a
convenient default, and even if I do it is going
to kill performance compared to an integer, since
there will be a bogus pointer for the collector to
chase down.

Also, I haven't checked the collector header,
but isn't there a count field that can be
used for the count without compromising the
allocator's knowledge of the length of a block?
[The size may be needed for disposal and/or movement
on compaction] If there is, the store can be
totally uninitialised, which is even more efficient.

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

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

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

Brian Hurt wrote:

> On Mon, 16 Jun 2003, Nicolas Cannasse wrote:



>I'm treading dangerously close to saying "if 
> you're using fold_right, you're screwing up.  One of List.map, Enum.map, 
> or List.fold_left is what you really want to be using."


It depends on context. Generally I use whatever is easiest to
read and write, becaise generally I am dealing with lists
of 0-10 elements, with 0-3 being 99% of the cases
(number of parameters a function has in a typical program, number
of components in a product type)

Sometimes I have slightly longer lists, for example:
list of all tokens in the program: that's typically in the
1000's. Vyper actually did something like 10 sub-folds over
the input token stream, mainly to get it into a shape that
could be LALR-parsed. Still, matching on the list was
probably more of an issue than tail recursion for the optimising
compiler: the bytecode compiler crashed out of stack space when
one of my iterations wasn't tail rec, but consuming 10 Meg of stack
isn't a big deal for a binary on a single user machine with 64Meg real.

Now, appending one elements to the end of the token list, on the other
hand, would be a disaster. I dun mind a constant number of O(n) operations,
but n log n where n is in the 1000s is a much bigger number .. a resize array
would be much faster.

Ocaml doesn't have one. Nor mutable doubly-linked lists or other
simple data structures that would sometimed be very convenient,
but a pain to define and then redefine in the next project ..

BTW: lost the web site. Please put web site address
in the signature.



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

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

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

In article <Pin...@ea...>, Brian Hurt wrote:
> On Mon, 16 Jun 2003, Alan Post wrote:
>> 
>> Why not simply provide "fold" which does a fold_left, and put in a
>> comment that the user should reverse the list arg if she really wants
>> a fold_right?  As you said, it isn't possible to walk a list
>> backwards, so why pretend?
> 
> The short answer is that the standard library provides a fold_right, 
> rightly or wrongly.  If we're angling to replace the standard libraries, 
> we need to not break any code that depends on them.  Adding functions is 
> OK, deleting functions I'd approach with great trepidation.

That sounds sensible to me.  How about doing the compatible thing,
then, using the stack-gobbling approach the existing library uses, and
putting in a comment that the user should avoid this function.

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

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

On Mon, 16 Jun 2003, Alan Post wrote:

> In article <Pin...@ea...>, Brian Hurt wrote:
> > 
> > With fold_right, it's impossible - so the question becomes which version
> > do people want- slow and broken for long lists, or glacial and correct for
> > all lists?  Or some tricky version which picks between them?  I've come to 
> > dislike my tricky version for reasons quite apart from performance.
> 
> Why not simply provide "fold" which does a fold_left, and put in a
> comment that the user should reverse the list arg if she really wants
> a fold_right?  As you said, it isn't possible to walk a list
> backwards, so why pretend?
> 

The short answer is that the standard library provides a fold_right, 
rightly or wrongly.  If we're angling to replace the standard libraries, 
we need to not break any code that depends on them.  Adding functions is 
OK, deleting functions I'd approach with great trepidation.

Brian

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

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

In article <Pin...@ea...>, Brian Hurt wrote:
> 
> With fold_right, it's impossible - so the question becomes which version
> do people want- slow and broken for long lists, or glacial and correct for
> all lists?  Or some tricky version which picks between them?  I've come to 
> dislike my tricky version for reasons quite apart from performance.

Why not simply provide "fold" which does a fold_left, and put in a
comment that the user should reverse the list arg if she really wants
a fold_right?  As you said, it isn't possible to walk a list
backwards, so why pretend?

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

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

On Tue, 17 Jun 2003, John Max Skaller wrote:

> Nothing is cheap inside an inner loop :-) The count could cost as much
> as a fold, particularly as a count IS in fact a fold. So you might
> double my computation time,

Not all folds are equal.  This is a fold right, which is going to be more 
expensive than a fold left no matter what we do.  My advice is, in that 
tight inner loop, you call fold left instead.

Come to think of it, in all cases I think I'd recommend calling fold_left 
instead of fold_right.

> 
> if I have a heavily nested fold on a small list. I may even know the
> list is always small, and hope the compiler may speed things up by
> unrolling the fold :-)

Loop overhead is negligable.  Especially with today's imbalance between 
processor and memory speeds, I'd be way more concerned about thrashing L1 
code cache.  Especially for short lists which are probably in cache 
anyways.  On a P4, a *single* cache miss can cost over 300 clock cycles.  
I can do an awful lot of loops in 300 clock cycles.

So the trick is to make it a loop.  Preferably without having to duplicate
the entire list.  This is trivial with fold_left- in fact, the naive
implementation of fold_left is this way.  

With fold_right, it's impossible - so the question becomes which version
do people want- slow and broken for long lists, or glacial and correct for
all lists?  Or some tricky version which picks between them?  I've come to 
dislike my tricky version for reasons quite apart from performance.

Brian

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

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

Brian Hurt wrote:

> On Sat, 14 Jun 2003, John Max Skaller wrote:
> 
> 
>>i don't want you counting my lists :-)
>>
> 
> What is so evil about doing a List.length?  Especially in this case, where 
> I hard cap the computational cost- as all I need to answer is if the 
> length less than some constant.  So, for short lists (for some suitably 
> wimbly definition of short) doing a list length is cheap.  

Nothing is cheap inside an inner loop :-)
The count could cost as much as a fold,

particularly as a count IS in fact a fold.


So you might double my computation time,

if I have a heavily nested fold on a small list.
I may even know the list is always small,
and hope the compiler may speed things up by
unrolling the fold :-)

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

Re: [Ocaml-lib-devel] ExtList set_field

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

On Mon, 16 Jun 2003, Nicolas Cannasse wrote:

> Recently, after the talks of Xavier Leroy on the main ocaml list, it appear
> that Obj.set_field is not working so good. Jacques Garrigue looked at the
> generated native code and he noticed that the Obj.set_field is doing
> additional (useless) operation by testing the block tag for
> Double_array_tag. Not only the code is bigger, but there is a (very) little
> speed issue , compared to using a mutable structure like :
> type 'a mutlist = { h : 'a ; mutable tl : 'a mutlist; }
> I might then modify ExtList soon to clean theses things.
> ( please note that we still Obj.magic to convert from/to 'a list.

We're already dependent upon the structure of the list object already.  
This is probably a good idea.  If you don't want to do it, I'll do it.

> 
> Another problem might come from the "trick" :
> let x = [ Obj.magic () ] in
> ....
> List.tl x
> who might get outlined by the compiler and thus will be shared by several
> calls (which is not what we want since we're muting the tail !). A
> workaround is not to use unit but one of the arguments of the function to
> prevent to compiler to mark the block as constant.

My preference would be to special case the first element.  Picking a 
resonably difficult example of how this would work, we'd have:

type 'a mut_list = {hd: 'a; mutable tl: 'a list}
external inj : 'a mut_list -> 'a list = "%identity"

let filter_map f l =
    let rec loop2 dst = function
        | [] -> ()
        | h :: t ->
            match f h with
                | None -> loop2 dst t
                | Some x -> 
                    let r = { hd = x; tl = [] } in
                    dst.tl <- inj r;
                    loop2 r t
    in
    let rec loop1 = function
        | [] -> []
        | h :: t ->
            match f h with
                | None -> loop1 t
                | Some x ->
                    let r = { hd = x; tl = [] } in
                    loop2 r t;
                    inj r
    in
    loop1 l

The code is a little bit more complicated, I agree.  But we don't have to 
worry about magic values.  Generally, the less magic we depend upon, the 
happier I am.

Brian

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

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

On Mon, 16 Jun 2003, Nicolas Cannasse wrote:

> But even like this i'm not very satisfied...

Neither am I.

> 
> Actually , here's the problem : why do people need fold_right ? ( means :
> why don't they use fold_left ? )
> Answer : because most of the time they want to build a list in the same
> order as the input list.

Um, isn't that what List.map and Enum.map are for?  Any time you're 
building up another data structure, whatever the data structure, Enum is 
probably a better answer.

Basically, the problem with fold_right is the implicit assumption that 
lists can be traversed backwards.  They can't, and fold_right is the only 
routine that assumes that.  I'm treading dangerously close to saying "if 
you're using fold_right, you're screwing up.  One of List.map, Enum.map, 
or List.fold_left is what you really want to be using."

Minor nit: can we add a List.fold defined like:
let fold = fold_left
into extlib?  This has bit me more than once, forgetting that List doesn't 
have a fold, it has a fold_left and a fold_right.



> 
> Ok, so let's provide them a "list only" version of fold_right ( ExtList.fold
> ? ) that will do the job in a tail-rec way using internals set_cdr to
> construct the list in the user-wanted way. This of course does not cover all
> the cases, but should be enough to preserve speed where it is needed (btw
> enums should be even better for this kind of things ^^;) . The difference of
> this fold is that we are iterating from left_to_right but I don't think that
> a lot of users actually wants to do so.

Well, we already have List.map to convert a 'a list to a 'b list and keep 
the order the same.  We have List.rev to convert a 'a list to a 'a list in 
reverse order.  If we added a List.rev_map, which combined the two, I 
don't see what other possibilities are needed.  More complex stuff you do 
with Enums.

let rev_map f lst =
    let rec loop curr accum =
        match curr with
            | [] -> accum
            | h :: t -> loop t ( ( f h ) :: accum )
    in
    loop lst []

This has the advantages of being a) obvious, b) efficient, and c) simple.

Hmm.  While I'm thinking about it, maybe an Enum.rev as well.  This would 
have to create an intermediate list, but would look something like:

let rev e =
    let lst = ref [] in
    let rec loop () =
        lst := (e.next ()) :: (!lst);
        loop ()
    in
    try
        loop ()
    with
        No_more_elements -> List.enum (!lst)

Jumping back to fold_right, I now think we have three choices for extlib:

- Supply the non-tail recursive version, and go "that's what the function 
is defined like- don't use it on long lists.  In fact, probably don't use 
it at all."

- Supply the list reversing version, and go "works on all lists, but uses 
a bunch of heap space.  You probably don't want to use this."

- Don't supply it at all.  Declare it fundamentally broken.

Brian

[Ocaml-lib-devel] ExtList set_field

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

Recently, after the talks of Xavier Leroy on the main ocaml list, it appear
that Obj.set_field is not working so good. Jacques Garrigue looked at the
generated native code and he noticed that the Obj.set_field is doing
additional (useless) operation by testing the block tag for
Double_array_tag. Not only the code is bigger, but there is a (very) little
speed issue , compared to using a mutable structure like :
type 'a mutlist = { h : 'a ; mutable tl : 'a mutlist; }
I might then modify ExtList soon to clean theses things.
( please note that we still Obj.magic to convert from/to 'a list.

Another problem might come from the "trick" :
let x = [ Obj.magic () ] in
....
List.tl x
who might get outlined by the compiler and thus will be shared by several
calls (which is not what we want since we're muting the tail !). A
workaround is not to use unit but one of the arguments of the function to
prevent to compiler to mark the block as constant.

Nicolas Cannasse

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

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

> 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:
[...]
> Thoughts?  Comments?  Benchmarks?

The problem here is that the "good number" will be good for some
applications but not good for other ones.
For example if one of my program have a bunch of *exactly* 1000 elements
list, then I'm spending a lot of time in counting elements... for nothing.
One possibility is to have that counter really be dynamic , se when we
return false we divide the counter by two, and when true we it multiply by
1.5 or something with of course reasonable bounds. Looks a little like TCP
:-)
But even like this i'm not very satisfied...

Actually , here's the problem : why do people need fold_right ? ( means :
why don't they use fold_left ? )
Answer : because most of the time they want to build a list in the same
order as the input list.

Ok, so let's provide them a "list only" version of fold_right ( ExtList.fold
? ) that will do the job in a tail-rec way using internals set_cdr to
construct the list in the user-wanted way. This of course does not cover all
the cases, but should be enough to preserve speed where it is needed (btw
enums should be even better for this kind of things ^^;) . The difference of
this fold is that we are iterating from left_to_right but I don't think that
a lot of users actually wants to do so.

Nicolas Cannasse

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

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

On Sat, 14 Jun 2003, John Max Skaller wrote:

> i don't want you counting my lists :-)

What is so evil about doing a List.length?  Especially in this case, where 
I hard cap the computational cost- as all I need to answer is if the 
length less than some constant.  So, for short lists (for some suitably 
wimbly definition of short) doing a list length is cheap.  For long lists, 
the length function short circuits out without doing a full count.  Maybe 
I should have made max smaller- 100 say, instead of 1000.  *Especially* 
since we're about to do an O(N) fold_right on the list anyways.

Now, mind you, there *are* reasons why my code may not be the most 
optimum.  Including:

- at some arbitrary point the algorithm trades off heap space for stack 
space, meaning it's hard to estimate how much of each you'll need.

- there is some performance benefit to be gained if you already know what 
the right routine to call is.

> 
> I know which routine I need from context often.
> So provide:
> 
> 	fold_right
> 	rev_fold_right

Or possibly even three- recursive, reversing, and sense-selecting.  

Brian

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

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

> 
> 
> My opinion: version 1.0 should be a source tarbar.  If we wait until we're
> all things to all people, we'll never release.  A lot of the packaging
> should be done external to the build process anyways.
> 
> Now, to a more relevent question: what's left that needs to be documented?
> 
> Brian

    Hi all,

    I made a couple additions to the in-code Ocamldoc documentation.  The biggies
that are left are: RefList and anything to do with Enum's.  There are bits and
pieces missing here and there...

    When I get the chance, I'll put the new htdocs on the webpage.

    -Amit

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

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

Brian Hurt wrote:

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

i don't want you counting my lists :-)

I know which routine I need from context often.
So provide:

	fold_right
	rev_fold_right

The fact is, I'll often chose rev_fold_right
because I WANT the list reversed.

I suspect the way to handle a dynamic trade off is:

	fold_right_dynamic estimate f lst init

where 'estimate' is provided by the client.
you don't count the list and decide, you decide based
on the client's estimate. The client can then:

	a) count the list, or otherwise create
	an estimate

	b) curry the function on the estimate

Example: in my Felix compiler I have lists of function
parameters. Well, I know they're short, i don't have to
count them, and if someone writs a function with
2000 parameters, well, I just don't care if there's
a minor slow down :-)

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

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

My opinion: version 1.0 should be a source tarbar.  If we wait until we're
all things to all people, we'll never release.  A lot of the packaging
should be done external to the build process anyways.

Now, to a more relevent question: what's left that needs to be documented?

Brian

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

[Michal M. <mal...@pl...>]

On Thu, Jun 12, 2003 at 02:54:45PM +0900, Nicolas Cannasse wrote:
> > 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.

When designing such tool, take into account that lots of ocaml users out
there is using rpms and debs with ocaml related stuff. Installing
packages from sources, and managing it using specialized tools is often
not an option.

So please separate software installation from querying compiler options
for given package and the like. For example create few conceptually
simple tools, one can be pkgconfig look-alike, other rpm (package
manager that can handle package installation and removal) with limited
functionality, and yet another apt-get (tool to automagically fetch deps
for given package) with recompilation support.

As a side-note: I really regret pkgconfig didn't come out earlier, since
it allows to get rid of all (or almost all) autoconfig stuff, but only
if your required packages support it.

Anyhow:

[malekith@roke ~]$ ls /usr/lib/pkgconfig|wc -l
     79
[malekith@roke ~]$ 
     
It got quite popular, not only for gnome-related stuff. I believe
one of sources of its success was conceptual simplicity. All you need to
support pkgconfig, is to put simple foo.pc file in /usr/lib/pkgconfig.

Example:

#v+
prefix=/usr
exec_prefix=/usr
libdir=/usr/lib
includedir=/usr/include/alsa

Name: alsa
Description: Advanced Linux Sound Architecture (ALSA) - Library
Version: 0.9.3
Requires: 
Libs: -L${libdir} -lasound -lm -ldl -lpthread
Cflags: -I${includedir}
#v-

Of course for ocaml we would need somewhat different lines, but you get
the idea.

And yes, there is findlib already. But it's far too complex for my
taste -- it tries to handle too much.

-- 
: Michal Moskal :: http://www.kernel.pl/~malekith : GCS {C,UL}++++$ a? !tv
: PLD Linux ::::::::: Wroclaw University, CS Dept : {E-,w}-- {b++,e}>+++ h