ocaml-lib-devel — Developer's mailing list

[Ocaml-lib-devel] [BUG] read_i32 produces incorrect results

[Nuutti K. <na...@ik...>]

I think I found a bug in IO.read_i32 implementation. The current
implementation is (roughly):

,----[ IO.ml ]
| let read_i32 ch =
|   let ch1 = read_byte ch in
|   let ch2 = read_byte ch in
|   let ch3 = read_byte ch in
|   let ch4 = read_byte ch in
|     if ch4 land 64 <> 0 then raise (Overflow "read_i32");
|     if ch4 land 128 <> 0 then
|       ch1 lor ch2 lsl 8 lor ch3 lsl 16 lor ((ch4 land 63) lor 64) lsl 24
|     else
|       ch1 lor ch2 lsl 8 lor ch3 lsl 16 lor ch4 lsl 24
`----

I believe it should be something like this:

,----[ IO.ml ]
| let read_i32 ch =
|   let ch1 = read_byte ch in
|   let ch2 = read_byte ch in
|   let ch3 = read_byte ch in
|   let ch4 = read_byte ch in
|     if ch4 land 128 <> 0 then (
|       if ch4 land 64 == 0 then raise (Overflow "read_i32");
|       ch1 lor ch2 lsl 8 lor ch3 lsl 16 lor ((ch4 land 63) lor 64) lsl 24
|     ) else (
|       if ch4 land 64 <> 0 then raise (Overflow "read_i32");
|       ch1 lor ch2 lsl 8 lor ch3 lsl 16 lor ch4 lsl 24
|     )
`----

Otherwise it will give incorrect results for numbers that are over 1
gig negative and superflusly complain Overflow for numbers over half a
gig negative (roughly, obviously).

I didn't produce a patch, since the change is trivial and I am not
savvy with the library coding style.

I am not subscribed to the list, so I would appreciate CCing me in
case any questions are raised.

-- Naked

[Ocaml-lib-devel] Exceptions

[skaller <sk...@us...>]

On Tue, 2004-08-31 at 05:26, Bardur Arantsson wrote:

> It seems there is no function to read exactly n characters
> into a string (ie. IO.nread just without automatically
> shortening the string if EOF is hit while reading). Since
> at least one person needs it (me :)) I thought I would add
> this:
> 
>    let really_nread i n =
>         if n < 0 then raise (Invalid_argument "IO.really_nread");
>         if n = 0 then


Seeing the exception being raised here suggests to
me Ocaml needs a better mechanism for errors.

The exception being raised conforms to the "Same way as 
Ocaml std lib" policy.

It exhibits these problems:

(1) It doesn't say which argument
(2) It doesn't say what the problem was
(3) There's no reference to the file/line position of the raise

>This will cause an infinite loop on non-blocking IO (r = 0).
>You might want to raise Sys_blocked_io in this case.

Weird. You raise Sys_blocked_io when in fact the problem
is that it *isn't* blocked??


-- 
John Skaller, mailto:sk...@us...
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net

Re: [Ocaml-lib-devel] IO.really_nread

[Bardur A. <oca...@sc...>]

On Mon, Aug 30, 2004 at 10:35:51PM +0200, Nicolas Cannasse wrote:

> > Hi all,
> > 
> > It seems there is no function to read exactly n characters
> > into a string (ie. IO.nread just without automatically
> > shortening the string if EOF is hit while reading). Since
> > at least one person needs it (me :)) I thought I would add
> > this:
> > 
> >    let really_nread i n =
> >         if n < 0 then raise (Invalid_argument "IO.really_nread");
> >         if n = 0 then
> >                 ""
> >         else
> >         let s = String.create n in
> >         let l = ref n in
> >         let p = ref 0 in
> >         while !l > 0 do
> >                 let r = i.in_input s !p !l in
> >                 p := !p + r;
> >                 l := !l - r;
> >         done;
> >         s
> > 
> > which is exactly the same code as IO.nread, except it
> > doesn't try to catch the No_more_input exception.
> > 
> > Any objections to adding this?
> 
> This will cause an infinite loop on non-blocking IO (r = 0).
> You might want to raise Sys_blocked_io in this case.
> 

Hmm... the channel adapter uses Pervasives.input to read.
This in turn uses Pervasives.unsafe_input, which uses
caml_ml_input(), which uses caml_do_read() which will
actually raise Sys_blocked_io itself when the read()
function returns the appropriate error code. So unless I'm
missing something it should actually work correctly for
non-blocking IO...

-- 
Bardur Arantsson
<ba...@im...>
<ba...@sc...>

Hard work often pays off after time. But laziness always pays off
now.
                                      http://www.demotivators.com

Re: [Ocaml-lib-devel] IO.really_nread

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

> Hi all,
> 
> It seems there is no function to read exactly n characters
> into a string (ie. IO.nread just without automatically
> shortening the string if EOF is hit while reading). Since
> at least one person needs it (me :)) I thought I would add
> this:
> 
>    let really_nread i n =
>         if n < 0 then raise (Invalid_argument "IO.really_nread");
>         if n = 0 then
>                 ""
>         else
>         let s = String.create n in
>         let l = ref n in
>         let p = ref 0 in
>         while !l > 0 do
>                 let r = i.in_input s !p !l in
>                 p := !p + r;
>                 l := !l - r;
>         done;
>         s
> 
> which is exactly the same code as IO.nread, except it
> doesn't try to catch the No_more_input exception.
> 
> Any objections to adding this?

This will cause an infinite loop on non-blocking IO (r = 0).
You might want to raise Sys_blocked_io in this case.

Nicolas Cannasse

[Ocaml-lib-devel] IO.really_nread

[Bardur A. <oca...@sc...>]

Hi all,

It seems there is no function to read exactly n characters
into a string (ie. IO.nread just without automatically
shortening the string if EOF is hit while reading). Since
at least one person needs it (me :)) I thought I would add
this:

   let really_nread i n =
        if n < 0 then raise (Invalid_argument "IO.really_nread");
        if n = 0 then
                ""
        else
        let s = String.create n in
        let l = ref n in
        let p = ref 0 in
        while !l > 0 do
                let r = i.in_input s !p !l in
                p := !p + r;
                l := !l - r;
        done;
        s

which is exactly the same code as IO.nread, except it
doesn't try to catch the No_more_input exception.

Any objections to adding this?

-- 
Bardur Arantsson
<ba...@im...>
<ba...@sc...>

- You've got mail! Hope you don't have stocks.
                         Robin Williams | Live on Broadway (2002)

[Ocaml-lib-devel] Re: Re: new dllist (yet again)

[Jesse G. <je...@wi...>]

Nicolas Cannasse wrote:

>> 1.) I probably need to write the following functions:
>>
>>     rev_iter
>>     rev_map
>>     rev_to_list
>>     rev_of_list
> 
> That's exactly what enums are good for, you should provide only one :
> 
> val rev_enum : 'a t -> 'a Enum.t
> 
> and then everybody can apply iter, map, fold, to_list, to_array..... (all
> functional operations).

It's not as efficient as distinct special purpose
functions, but it should prove to be just as scalable,
right? O(1) rev_enum + O(N) Enum.iter

Are there any major objections to this?

-- 
Jesse Guardiani, Systems Administrator
WingNET Internet Services,
P.O. Box 2605 // Cleveland, TN 37320-2605
423-559-LINK (v)  423-559-5145 (f)
http://www.wingnet.net

[Ocaml-lib-devel] Re: Re: new dllist (yet again)

[Jesse G. <je...@wi...>]

Bardur Arantsson wrote:

> On Sun, Aug 29, 2004 at 11:58:25AM -0400, Jesse D. Guardiani wrote:
> 
> [--snip--]>
>> I *would* like to discuss implementation details a bit before we commit
>> the code though. You can
>> download the source and view the current docs here for reference:
>>    http://www.wingnet.net/~jesse/ocaml/dllist/
>> 
>> Things that I think warrant discussion:
> [--snip--]
> 
>> 3.) I'd like some comments on the drop and rev_drop functions. Do we
>> need the remove function? Is
>>     drop a good name? etc....
> 
> Just a couple of tiny suggestions regarding naming:
> 
> - "skip" might be a more appropriate name for "jump".
> 
> - I'm not so crazy about the name "merge" since it's one
> of those quite overloaded terms... How about "splice" to
> distinguish it from a regular list merge (which is usually
> not the same as list concatenation)?

So jump becomes skip and merge becomes splice.

Is everyone in agreement here?

-- 
Jesse Guardiani, Systems Administrator
WingNET Internet Services,
P.O. Box 2605 // Cleveland, TN 37320-2605
423-559-LINK (v)  423-559-5145 (f)
http://www.wingnet.net

Re: [Ocaml-lib-devel] Re: new dllist (yet again)

[Bardur A. <oca...@sc...>]

On Sun, Aug 29, 2004 at 11:58:25AM -0400, Jesse D. Guardiani wrote:

[--snip--]> 
> I *would* like to discuss implementation details a bit before we commit 
> the code though. You can
> download the source and view the current docs here for reference:
>    http://www.wingnet.net/~jesse/ocaml/dllist/
> 
> Things that I think warrant discussion:
[--snip--]

> 3.) I'd like some comments on the drop and rev_drop functions. Do we 
> need the remove function? Is
>     drop a good name? etc....

Just a couple of tiny suggestions regarding naming: 

- "skip" might be a more appropriate name for "jump".

- I'm not so crazy about the name "merge" since it's one
of those quite overloaded terms... How about "splice" to
distinguish it from a regular list merge (which is usually
not the same as list concatenation)? 

-- 
Bardur Arantsson
<ba...@im...>
<ba...@sc...>

- Baldrick, belive me, eternity in the company of Beelzebub, and
all his helish instruments of death, would be a picnic compared
with five minutes with me and this pencil.
                               Edmund Blackadder | Blackadder III

Re: [Ocaml-lib-devel] Re: new dllist (yet again)

[skaller <sk...@us...>]

On Mon, 2004-08-30 at 01:58, Jesse D. Guardiani wrote:

> 1.) I probably need to write the following functions:
> 
>     rev_iter
>     rev_map
>     rev_to_list
>     rev_of_list
> 
>     Is everyone OK with so many rev_ functions? 

Yes. Don't use a flag. The distinction in direction
with the rev_ functions is static as it should be.

-- 
John Skaller, mailto:sk...@us...
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net

Re: [Ocaml-lib-devel] Re: new dllist (yet again)

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

> 1.) I probably need to write the following functions:
>
>     rev_iter
>     rev_map
>     rev_to_list
>     rev_of_list

That's exactly what enums are good for, you should provide only one :

val rev_enum : 'a t -> 'a Enum.t

and then everybody can apply iter, map, fold, to_list, to_array..... (all
functional operations).

Nicolas

Re: [Ocaml-lib-devel] Re: new dllist (yet again)

[Bardur A. <oca...@sc...>]

On Sun, Aug 29, 2004 at 11:58:25AM -0400, Jesse D. Guardiani wrote:

[--snip--]
> Well, Brian, do you want it? I don't mind either way.
> 
> I *would* like to discuss implementation details a bit before we commit 
> the code though. You can
> download the source and view the current docs here for reference:
>    http://www.wingnet.net/~jesse/ocaml/dllist/
> 
> Things that I think warrant discussion:
> 
> 1.) I probably need to write the following functions:
> 
>    rev_iter
>    rev_map
>    rev_to_list
>    rev_of_list
> 
>    Is everyone OK with so many rev_ functions? The
> advantage is that they're identical to the normal
> functions as far as performance is concerned, they just
> work in the opposite direction. Can anyone think of a
> better way to do it? Perhaps a boolean options argument? 
> i.e. ?(rev=false) This adds overhead to each function
> though, as we'd need to use the next and prev functions
> internally instead of node.next and node.prev.

I think ?(direction=[`Forward | `Reverse]) looks slightly
nicer, albeit more verbose...

Anyway, I hardly think the overhead of unified traversal
algorithms is going to kill anyone's performance.

-- 
Bardur Arantsson
<ba...@im...>
<ba...@sc...>

I only posted as Anonymous Coward because I knew I was going to
be offtopic and rude. I got very scared, the name Coward seemed
suitable.
                           Anonymous Coward | http://slashdot.org

Re: [Ocaml-lib-devel] Re: new dllist (yet again)

[Jesse D. G. <je...@wi...>]

Nicolas Cannasse wrote:

>>>type opcode
>>>type code =
>>>    | Op of opcode
>>>    | Array of code array
>>>type key = array * int (* pointer in the tree *)
>>>      
>>>
>>Yeah I've thought of that, but:
>>
>>The problem is it makes pattern detection hard.
>>For example to detect the sequence A B with a slist
>>you just recursively seek
>>
>>A :: (B :: _ ) as tail -> ..
>>    
>>
>
>That's true. You might want to keep some parts of your geneate code flat but
>that's something you can anticipate. First apply as much as possible of
>rewriting rules, then flatten, then loop using you reach a fixpoint. You can
>also minimize the number of allocations by implementing a two-steps flatten
>algorithm : first recursivly calculate the size of the array needed then
>alloc it and recursively fill it.
>
>%Jesse:
>Back to the subject I have thought a little by myself and I think now that
>DLList could be added to ExtLib, if it replaces the RefList module. I think
>almost nobody use it, so why not replace the ref-list by a mutable list, and
>why not a double linked list, that is my thinking. Which of Jesse or Brian
>will take over the DLList maintenance in ExtLib ? If Brian then you can
>commit it (as well as IndexedTree as discussed before) , if Jesse then
>please send me your SF account so I can add you to the developers list.
>  
>

Well, Brian, do you want it? I don't mind either way.

I *would* like to discuss implementation details a bit before we commit 
the code though. You can
download the source and view the current docs here for reference:
    http://www.wingnet.net/~jesse/ocaml/dllist/

Things that I think warrant discussion:

1.) I probably need to write the following functions:

    rev_iter
    rev_map
    rev_to_list
    rev_of_list

    Is everyone OK with so many rev_ functions? The advantage is that 
they're identical to the normal
    functions as far as performance is concerned, they just work in the 
opposite direction. Can anyone
    think of a better way to do it? Perhaps a boolean options argument? 
i.e. ?(rev=false) This adds
    overhead to each function though, as we'd need to use the next and 
prev functions internally instead
    of node.next and node.prev.

2.) Someone needs to rework the currently commented out enum code. If 
someone can explain to me
    the general idea behind enums then maybe I can tackle this, but 
Brian is probably better suited.

3.) I'd like some comments on the drop and rev_drop functions. Do we 
need the remove function? Is
     drop a good name? etc....

4.)  Does everyone like the merge function? It serves a dual purpose:
    a.) O(1) node/list concatenation if used on two nodes from discrete 
lists
    b.) O(1) multi-node removal (creating two discrete lists from one) 
if used on two nodes in the same list.

    I can't decide if the dual nature of the merge function is an 
advantage or a liability. It makes it possible
    to apply nodes from two discrete lists by accident when you intended 
to apply nodes from the same
    list, thus introducing bugs. The problem is that there is no way to 
determine at compile time which list
    a given node is attached to, otherwise we could break this function 
into two functions: merge and cut

5.) Can anyone think of other useful functions?

Thanks!

--
Jesse Guardiani, Systems Administrator
WingNET Internet Services,
P.O. Box 2605 // Cleveland, TN 37320-2605
423-559-LINK (v)  423-559-5145 (f)
http://www.wingnet.net

Re: [Ocaml-lib-devel] Re: new dllist (yet again)

[Bardur A. <oca...@sc...>]

On Sat, Aug 28, 2004 at 08:53:01PM +0200, Nicolas Cannasse wrote:

> > > %Jesse:
> > > Back to the subject I have thought a little by myself and I think now
> that
> > > DLList could be added to ExtLib, if it replaces the RefList module. I
> think
> >
> > OptParse uses RefList.
> 
> YAMTD
> 
> Yet Another Modification To Do :)
> 

Well, maybe... I was just pointing out that it might be a
bad idea to remove RefList *now*.

-- 
Bardur Arantsson
<ba...@im...>
<ba...@sc...>

- All humans are vermin in the eyes of Morbo!
                                                 Morbo | Futurama

Re: [Ocaml-lib-devel] Re: new dllist (yet again)

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

> > %Jesse:
> > Back to the subject I have thought a little by myself and I think now
that
> > DLList could be added to ExtLib, if it replaces the RefList module. I
think
>
> OptParse uses RefList.

YAMTD

Yet Another Modification To Do :)

Nicolas

Re: [Ocaml-lib-devel] Re: new dllist (yet again)

[Bardur A. <oca...@sc...>]

On Sat, Aug 28, 2004 at 08:28:05PM +0200, Nicolas Cannasse wrote:

> > > type opcode
> > > type code =
> > >     | Op of opcode
> > >     | Array of code array
> > > type key = array * int (* pointer in the tree *)
> >
> > Yeah I've thought of that, but:
> >
> > The problem is it makes pattern detection hard.
> > For example to detect the sequence A B with a slist
> > you just recursively seek
> >
> > A :: (B :: _ ) as tail -> ..
> 
> That's true. You might want to keep some parts of your geneate code flat but
> that's something you can anticipate. First apply as much as possible of
> rewriting rules, then flatten, then loop using you reach a fixpoint. You can
> also minimize the number of allocations by implementing a two-steps flatten
> algorithm : first recursivly calculate the size of the array needed then
> alloc it and recursively fill it.
> 
> %Jesse:
> Back to the subject I have thought a little by myself and I think now that
> DLList could be added to ExtLib, if it replaces the RefList module. I think

OptParse uses RefList.

-- 
Bardur Arantsson
<ba...@im...>
<ba...@sc...>

Sufficiently advanced magic is indistinguishable from technology.
                       Terry Pratchett | The Science of Discworld

Re: [Ocaml-lib-devel] Re: new dllist (yet again)

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

> > type opcode
> > type code =
> >     | Op of opcode
> >     | Array of code array
> > type key = array * int (* pointer in the tree *)
>
> Yeah I've thought of that, but:
>
> The problem is it makes pattern detection hard.
> For example to detect the sequence A B with a slist
> you just recursively seek
>
> A :: (B :: _ ) as tail -> ..

That's true. You might want to keep some parts of your geneate code flat but
that's something you can anticipate. First apply as much as possible of
rewriting rules, then flatten, then loop using you reach a fixpoint. You can
also minimize the number of allocations by implementing a two-steps flatten
algorithm : first recursivly calculate the size of the array needed then
alloc it and recursively fill it.

%Jesse:
Back to the subject I have thought a little by myself and I think now that
DLList could be added to ExtLib, if it replaces the RefList module. I think
almost nobody use it, so why not replace the ref-list by a mutable list, and
why not a double linked list, that is my thinking. Which of Jesse or Brian
will take over the DLList maintenance in ExtLib ? If Brian then you can
commit it (as well as IndexedTree as discussed before) , if Jesse then
please send me your SF account so I can add you to the developers list.

Nicolas

Re: [Ocaml-lib-devel] Re: new dllist (yet again)

[skaller <sk...@us...>]

On Sun, 2004-08-29 at 02:29, Nicolas Cannasse wrote:

> type opcode
> type code = opcode array
> type key = int (* index in the array *)
> 
> use :
> 
> type opcode
> type code =
>     | Op of opcode
>     | Array of code array
> type key = array * int (* pointer in the tree *)

Yeah I've thought of that, but:

The problem is it makes pattern detection hard.
For example to detect the sequence A B with a slist
you just recursively seek

	A :: (B :: _ ) as tail -> .. 

If two instructions could be next to each other
OR one is Op A and the second the first element
of Array [| Op B; .. |] or perhaps Array [| Array [| ..
so I'd need to flatten this to do that kind of check,
and then I'd lose the location even if I did find
the pattern.. 

However for some things like control flow this kind of
representation might be useful (where you are looking
for entry an exit points, and sequential code isn't
interesting) .. except then I think you need a graph :)

> you can then translate any part of your code into not only a single opcode
> but into an array of opcodes, and they will remain correctly ordered. You
> need a tree structure to perform rewriting rules correctly and efficiently ,

yes but the problem is that the tree you need for each rule
is different :)

In particular rewriting isn't always one-to-many.
In fact the only description I can think of is that
its spagetti to spagetti :)

However what you suggest is potentially more stable than
a singly linked list (eg replacing an instruction with
many leaves labels in the same position).

The actual instruction set is currently:

and bexe_t =
  [
  | `BEXE_label of range_srcref * string
  | `BEXE_comment of range_srcref * string 
  | `BEXE_goto of range_srcref * string  
  | `BEXE_ifgoto of range_srcref * tbexpr_t * string  
  | `BEXE_ifnotgoto of range_srcref * tbexpr_t * string 
  | `BEXE_call of range_srcref * tbexpr_t * tbexpr_t 
  | `BEXE_call_direct of range_srcref * bid_t * btypecode_t list *
tbexpr_t 
  | `BEXE_call_stack of range_srcref * bid_t * btypecode_t list *
tbexpr_t 
  | `BEXE_call_prim of range_srcref * bid_t * btypecode_t list *
tbexpr_t 
  | `BEXE_jump of range_srcref * tbexpr_t * tbexpr_t 
  | `BEXE_loop of range_srcref * int * tbexpr_t 
  | `BEXE_read of range_srcref * bid_t
  | `BEXE_fun_return of range_srcref * tbexpr_t
  | `BEXE_proc_return of range_srcref   
  | `BEXE_nop of range_srcref * string
  | `BEXE_code of range_srcref * string
  | `BEXE_assign of range_srcref * tbexpr_t * tbexpr_t 
  | `BEXE_init of range_srcref * bid_t * tbexpr_t 
  | `BEXE_regmatch of range_srcref * tbexpr_t * regular_args_t
  | `BEXE_reglex of range_srcref * tbexpr_t * tbexpr_t * regular_args_t
  ]

range_srcref is a section of original source to print
when there's an error. tbexpr is a typed, bound, expression term.
bid_t is just an int, which is used to find a procedure in a hashtable.
regular_args_t specifies a finite state machine.

The representation of labels as strings requires lookup
every time which sucks.

-- 
John Skaller, mailto:sk...@us...
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net

Re: [Ocaml-lib-devel] Re: new dllist (yet again)

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

> > Taken apart advantages of keys, you get only bidrectional iteration,
which
> > is IMHO not interesting enough to justify adding a new data structure to
> > ExtLib.
[snip on arrays]

I think you should look at Brian proposal of IndexedTree (functionnal
array). It provides exactly that : a low cost insertion at any part of the
array. But any insertion/deletion will of course invalid the keys of some
parts of the array items. That's not exactly what you need here...

[snip on felix compilation]

I understand correctly your problem, because I got same when writing
compilers. It's often that you need several passes in order to optimize some
code or simply for example when writing a forward jump of N instructions
into a forward jump to address XX.
But I don't think dllist are the best solution here. As you said, you need
some rewriting rules, so what about :

instead of :

type opcode
type code = opcode array
type key = int (* index in the array *)

use :

type opcode
type code =
    | Op of opcode
    | Array of code array
type key = array * int (* pointer in the tree *)

you can then translate any part of your code into not only a single opcode
but into an array of opcodes, and they will remain correctly ordered. You
need a tree structure to perform rewriting rules correctly and efficiently ,
a dllist for this kind of problem is just an inconvenient way of handling
flat trees in a mutable fashion.

Nicolas

Re: [Ocaml-lib-devel] Re: new dllist (yet again)

[skaller <sk...@us...>]

On Sat, 2004-08-28 at 20:39, Nicolas Cannasse wrote:
> > I did add some other things in reply to your query which you
> > haven't quoted.
> >
> > Dlists have the following properties:
> >
> > (1) bidirectional iteration
> > (2) keys stable under all mutations
> > (3) keys are zero cost
> > (4) keys are generated by the data structure to support
> > any user defined ordering.
> 
> I don't agree with your definition of a node being a key to the item.

Its a definition, your agreement is not required :)

> - nodes are not ordered,

Yes they are. The ordering isn't total over node soup.
However for two nodes in a single linear list ordering
is total. For a circular list, you can say a node is
between two others in a given direction.

> - node adresses are not stable since they can be moved by the GC.

Irrelevant -- by address I didn't mean machine address.
That was just a way to distingush, in C++ terminology,
the node itself and a pointer to it.

Such a pointer is perfectly stable, even with GC compaction:
the difficulty expressing this for Ocaml is that a node
'pointer' is represented in Ocaml by the Ocaml term for
the node -- since Ocaml automatically boxes things.

> Taken apart advantages of keys, you get only bidrectional iteration, which
> is IMHO not interesting enough to justify adding a new data structure to
> ExtLib.

You are simply not understanding the way I expressed the
property in terms of keys. I'm sorry its my fault not
expressing this well, but the property I am trying
to explain actually exists.

If you have some set of values V, and you wish to
*impose* an ordering on them, you can do that by
storing them in an array, for example. You can then
lookup the values and get the index, and compare
the indexes.

I'm sure you understand that. The location in the
array is a key. It isn't represented *explicitly*
in the array.

In fact the location in the array can be represented
by a pointer to the array plus an integer OR a pointer
to the array plus a pointer to the element. As you know
in C:

	a[i] = *(a + i)

expresses this idea [a+i is a pointer to an element]

However for arrays, you can't modify the ordering
in a flexible way in O(1) -- and you can't do it 
at all, without modifying some pointesr/indexes
into the array -- if you blit elements after
position n down, to insert a new element,
every single index j >=n needs to have 1 added
to it to continue to refer to the same element.

I'm sure you agree, all this is obvious and well
known properties of arrays (even if I'm not expressing it well).

The key thing about dlists is that you can do the insertions
and deletions into the ordering relation WITHOUT modifying
any external cursors -- nothing moves when you add or
delete an element, they're just relinked.

That's what I mean by stable. Iterators, pointers,
cursors, or keys -- whatever you want to call them --
into dlists are stable under ordering modifications.

I used the word key to create an analogy with 
keyed data structures like Map. Using the 
functions (which don't actually exist
in Ocaml, but that's not important):

	get_next_key      data_structure   key
	get_previous_key  data_structure   key

you have stable keys and bidirectional
iteration. But there is a problem -- to do insertion,
you need to create a key between two others -- and that
isn't always possible. It depends on the keys. 

If you use an Ocaml Map with the above functions,
you can always do it with a string, since you can
just add an extra character to the end if you
run out of space -- I'm assuming the usual lexicographical
comparison.

But this is very expensive. For dlists, you can't and don't
need to create your own keys -- when you insert between
adjacent nodes n1 and n2 you automatically get returned
a node n3 in between them -- and the cost is O(1)
(and also VERY fast).

By the way -- using Ocaml Map with the above
next/previous functions is SUPERIOR in many ways to 
using a dlist.

That data structure allows persistence/functional 
behaviour -- insertions create a new map without
changing the old one.

However, the operations are O(log N) and you need
a lot more storage since you have to represent the
keys and also the technique requires that the user
choose and manage the keys to define the desired
ordering between values.

Simply defining the ordering by linking adjacent
elements is much faster and more efficient --
at the cost of losing functional/persistent
behaviour.
----------------------------------------------------
In my application -- lists of instructions --
the simple singly linked lists are quite clumbsy and
hard to manage sometimes. you simply cannot afford
to scan and rebuild the list multiple times to 
make a modification, and then do it all again
to do the next one. To avoid this I try to 
do multiple modifications in each pass.

Unfortunately the modifications are coupled...

anyhow, it is possible that dlist would be better
in this kind of case, where you can make a change
and backtrack a bit, rescan to ensure some invariant,
possibly making another change .. then proceed:
it may be tricky, but with a functional technique
it could be almost impossible to do efficiently.

I know I'm not describing this well, but you can
look at the Felix optimiser source code if you want
to see the kind of thing I'm doing.

Here's an example. To inline a procedure
I replace a "call f" instruction with
the body of f.

If f has arguments, I have to create a new variable,
assign the argument to it, and replace every use
of the parameter in the body with a reference
to the variable.

I also have to replace every 'return' instruction
with a 'goto end_f' instruction, and then make
sure to insert the label 'end_f' at the end.

Having done all that, I have inlined the procedure 
BUT there is at least one possible inefficiency:
a return at the end of the function will be
replaced by a 'goto end_f' followed by 
the label 'end_f'.

Ok, so I can delete the goto in that case.

But we're not finished. If that was the 
only return statement in the function,
then the end label isn't needed either,
so we can delete that too.

There is a similar issue with tail-rec
optimisation. I add a label at the start
of the function to jump to -- before I know
if there are actually any tail-rec calls.
[I have to do that to avoid yet another
functional pass over the list]

Its even worse: when I inline a function,
that function might contain a tail
call to its caller. This call is tail-rec,
but I can't optimise it immediately because
you can't 'goto' out of a function.

But after inlining -- THEN I can do the optimisation.
So I have to rescan the inlined code looking
for possible tail-rec optimisations.

I have to do that BEFORE the function I'm inlining
into is itself inlined into another function,
otherwise the call will just go to the original
function -- once a function body is inlined
into another its identity is lost.

Oh yeah -- this is just the coupling
between two optimistions (inlining + tail-rec
elimination). Of course I assumed i could
detect a tail call easily -- but it isn't
that easy. My instructions allow nops 
and comments. This is a tail call:

fred:
	return;

	call f a;// **** tail call
	// a comment
	goto fred;

so even detecting a tail call is non-trivial:
in fact I even take conditional branches into
account.

Now I would *much* prefer a couple of simple
functional passes to do all the work. I might
be able to do that IF I had a nice clean mathematically
simple representation and rewrite rules, perhaps
similar to lambda calculus style term rewriting..
but I don't have such a simple representation
and I'm implementing 'ad hoc' optimisations.

So -- do i need dlists for these lists of
instructions? I don't know. Actually I need
to find labels fast, and identify sequential
blocks, and a few other things, so I probably
could use something even more sophisticated.

So the argument for dlists here is -- unless they're
available I can't even try them out. Like you,
I'm inclined to avoid mutable data structures.
I just don't know what I should use -- but at the
moment slists are the only viable choice.

-- 
John Skaller, mailto:sk...@us...
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net

Re: [Ocaml-lib-devel] Re: new dllist (yet again)

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

> I did add some other things in reply to your query which you
> haven't quoted.
>
> Dlists have the following properties:
>
> (1) bidirectional iteration
> (2) keys stable under all mutations
> (3) keys are zero cost
> (4) keys are generated by the data structure to support
> any user defined ordering.

I don't agree with your definition of a node being a key to the item.
Several reasons for that :
- a node does not describe any interesting property of the item, it is just
a pointer to the item. You cannot by any way produce a node by your own
means, and only a node returned by add is valid for a given dllist.
- nodes are not ordered, comparing them will just blow the stack since
they're recursive. You can check for equality with == and != operators but
nothing else.
- node adresses are not stable since they can be moved by the GC.
Taken apart advantages of keys, you get only bidrectional iteration, which
is IMHO not interesting enough to justify adding a new data structure to
ExtLib.

Nicolas

Re: [Ocaml-lib-devel] Re: Re: new dllist (yet again)

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

> > Well I might be a dictator but I don't have alone CVS write access, so I
> > might be fired if I perform badly in my dictator job ;) 
> 
> Ah no -- I *do* have CVS write access. You can fire me
> because you're the sole administrator. I can't fire you :)

Aaaar
That was my trump card, I've been uncovered 
No I have no other choice but to eliminate you John, sorry ;)

Nicolas

Re: [Ocaml-lib-devel] Getopt/OptParse (the saga continues...)

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

> > Since "replace" is an ExtLib functionality, I think it's ok to agree to
> > break our own implementation . Since I also think that replace should be
on
> > strings, and the current replace should be renamed as replace_chars then
I
> > vote for breakage.
> > My proposal for String.replace is the following :
> >
> > val replace : str:string -> by:string -> bool
> >
>
> This won't work. There are three string parameters:
> The original string, the string to replace and the string
> to replace it with. It would also have to return the new
> string.

True , forgot something  :)

val replace : str:string -> sub:string -> by:string -> bool

> But anyway... I was just wondering if the patch was
> forgotten? It hasn't shown up in CVS yet... I just tried
> committing it to SF CVS (mainly to see if I could ;)), but
> got some sort of permission denied -- which is fine, I
> really don't care all that much about having write access
> to more things than I already do :). But it might be a
> good idea to apply the patch as posted, i.e. just adding
> ExtString.splice and keeping everything else within
> OptParse. Things can be moved around later if it turns out
> to be a good idea.

I was thinking you would apply the patch. For that, you need to checkout the
SF CVS while login with your SF Account. You are developer of ExtLib so you
should get write access to the CVS.

Nicolas

Re: [Ocaml-lib-devel] Re: Re: new dllist (yet again)

[skaller <sk...@us...>]

On Sat, 2004-08-28 at 09:10, Brian Hurt wrote:
> On Fri, 27 Aug 2004, Richard Jones wrote:

> In defense of dllist, we currently don't have a way to do an ordered
> lookup table

> The best functional solution I can come up with to do it functionally is a 
> double map solution- a ('key, int * 'data) map to do key lookups, and an
> (int, 'key * 'data) map to do insertion order lookups.  When the insert 
> counter rolls over, you just rebuild the entire data structure to compact 
> the insertion locations.

This doesn't meet the requirements. In particular, the ordering
is fixed to 'append at end' which is not enough. 

Consider rewriting a sequence of labelled assembler instructions..
(which is effectively what I'm doing).

-- 
John Skaller, mailto:sk...@us...
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net

Re: [Ocaml-lib-devel] Re: new dllist (yet again)

[skaller <sk...@us...>]

On Sat, 2004-08-28 at 07:07, Nicolas Cannasse wrote:

> "Could someone resume shortly the advantages of using a mutable double
> linked
> list against other existing ocaml data structures ? ( I guess it has to be
> mutable since immutable dllist sounds efficientless)."
> 
> Brian said :
> 
> "O(1) removal of an element with a known location as opposed to O(log N)."
> 
> That means exactly O(1) removal when we have an enumeration pointer. That's
> exactly the same complexity as a list using a filter on first matched
> element isn't it ? So I don't yet see the advantages.

I did add some other things in reply to your query which you
haven't quoted.

Dlists have the following properties:

(1) bidirectional iteration
(2) keys stable under all mutations
(3) keys are zero cost
(4) keys are generated by the data structure to support
any user defined ordering.

No other data structure I know of has these properties.
Maps and hashtbls are keyed and stable, but the keys
are not zero cost and they have to be supplied by the user.

A common trick is to use floating point numbers, since
they emulate real numbers which support user defined ordering
-- you can always insert between k1 and k2 by using 
the key (k1 + k2) / 2 which is in between. Of course that 
doesn't actually work with floats :)

As to using lazy functional techniques -- well, if you do enough
mutations you end up stacking up a lot of filters and folds
and things and the whole list goes thru all of them each
element -- the mutation is O(1) and once off. Furthermore
you can't use a normal filter to do a deletion since 
the only way to identify a particular node is to match
on physical node address -- a traditional filter, map,
or fold does not present that information to the client
function. Furthermore an 'Enum' style representation
could never do that anyhow, since it relies on being
able to change the sequencing infrastructure.

Enums are forward iterators over the *values* in the list
but dlist nodes are actually pairs where the first element
is the node address (machine synthesised unique key where
the client insertion defines the key ordering dynamically), 
and Enums don't support that. Or reverse iteration.

That is -- dlinked lists have quite unique and useful
properties. Of course, they aren't functional -- but then
neither are Hashtbls  :)

-- 
John Skaller, mailto:sk...@us...
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net

Re: [Ocaml-lib-devel] Re: Re: new dllist (yet again)

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

On Fri, 27 Aug 2004, Richard Jones wrote:

> FWIW I'm also not convinced by dllist.

In defense of dllist, we currently don't have a way to do an ordered
lookup table- either imperitively (hashtable + dllist) or functionally.  
I don't think we need to support the combined data structure, but I think
we need to support the individual data structures.

My preference would actually be to do both- provide the necessary 
substrate for both the functional and imperitive versions.

The best functional solution I can come up with to do it functionally is a 
double map solution- a ('key, int * 'data) map to do key lookups, and an
(int, 'key * 'data) map to do insertion order lookups.  When the insert 
counter rolls over, you just rebuild the entire data structure to compact 
the insertion locations.

As a side note, I'm grokking Okasaki's paper on random access lists.  
Note that it only gives O(1) access to elements near one or the other end
of the list, and updates (inserts and deletes) and the rest of the finds
still take O(log N).

One huge advantage of using my data structure- inserting a funcarr of 
length M anywhere into a funcarr of length N should only take O(log 
(M+N)).

-- 
"Usenet is like a herd of performing elephants with diarrhea -- massive,
difficult to redirect, awe-inspiring, entertaining, and a source of
mind-boggling amounts of excrement when you least expect it."
                                - Gene Spafford 
Brian