ocaml-lib-devel — Developer's mailing list

Re: [Ocaml-lib-devel] Dllist

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

On Sat, 2005-05-28 at 13:44 +0200, Christophe TROESTLER wrote:
> On Sat, 28 May 2005, John Skaller <sk...@us...> wrote:
> > 
> > The library supplies the maximally efficient and simplest
> > representation by Occam's Razor, and that cannot be empty.
> 
> So it all boils down to efficiency. 

Well my view is that a *base* library provides simple
efficient things -- it is oriented to the computer NOT the user.

>From these basic libraries, more abstract and more 'user friendly'
interfaces can be implemented.

>  (Hereafter, Dllist' refers to this
> library and Dllist to Extlib one.  The Benchmark module is used.)

That's kind of confusing .. :)

What you have is the same node structure, but have added a 'head'
element.

The problem with doing that is that you can't so easily
chop bits of the list up, or splice bits of a list together.

For example, consider two lists A and B, and you join them
to create a list C. What happens to A and B?

With the current implementation as I understand it,
there isn't an issue, A, B, and C are now all the one list.

With your implementation the operation is impossible.
Joining A to B is a destructive operation: A and B don't
exist aftwards. Sorry I am not explaining this well.

-- 
John Skaller, skaller at users.sf.net
PO Box 401 Glebe, NSW 2037, Australia Ph:61-2-96600850 
Download Felix here: http://felix.sf.net

Re: [Ocaml-lib-devel] Dllist

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

On Fri, 27 May 2005, Christophe TROESTLER wrote:

> On Thu, 26 May 2005, Brian Hurt <bh...@sp...> wrote:
>>
>> On Wed, 25 May 2005, Christophe TROESTLER wrote:
>>
>>> Hi,
>>>
>>> Is there a good reason (aside from implementation easiness) not to
>>> allow Dllist to be empty?  IMHO, empty lists are very useful and it is
>>> rather an hindrance that Dllists cannot be.
>>
>> My original implementation did allow for empty lists, but it got
>> overridden.
>
> Where?  The CVS version does not seem to allow it.  As an example,
> consider:
>
> # let l = create 1 in
>    demote l;
>    length l;;
> - : int = 1
>
> (hum).   How do you create an empty list?

If I recall correctly, the original implementation of dllist I submitted 
way back when worked like this:

type 'a node_t = {
     data: 'a;
     mutable next: 'a node_t;
     mutable prev: 'a node_t;
};;

type 'a t = {
     mutable head: 'a node_t option;
     mutable tail: 'a node_t option;
};;

let empty () = { head = None; tail = None };;

let prepend x lst =
     let rec newnode = { data = x; next = newnode; prev = newnode } in
     match lst.head with
         | Some(node) ->
              newnode.next <- node;
              node.prev <- newnode;
              lst.head <- Some(newnode)
         | None ->
             let opt = Some(newnode) in
             lst.tail <- opt;
             lst.head <- opt
;;

Which allows for the obvious empty list representation.  It got overrulled 
in an attempt to save a couple of clock of cycles and maybe a few bytes. 
Having fought this battle before, at length, and lost, I just said "yeah, 
sure, whatever".

Brian

Re: [Ocaml-lib-devel] Dllist

[Christophe T. <chr...@us...>]

On Sat, 28 May 2005, John Skaller <sk...@us...> wrote:
> 
> The library supplies the maximally efficient and simplest
> representation by Occam's Razor, and that cannot be empty.

So it all boils down to efficiency.  Of course the problem -- as we
experience with the shootout -- is that it is not so easy to measure
(because we are talking of the big-O constant, not about asymptotic
complexity).  So instead of discussing, I propose to experiment!
Attached is an updated version of the interface together with an
implementation (hopefully without mistakes :).  According to my little
experiments, it is not so bad.  (Hereafter, Dllist' refers to this
library and Dllist to Extlib one.  The Benchmark module is used.)

Example 1: inserting 10000 elements using Dllist'.append and
---------- Dllist.add (they don't exactly do the same thing but
           Dllist.add doesn't need the "list" to be handled through a
           reference):

Throughputs for Dllist' running 4 times for at least 4 CPU seconds:
   Dllist':  7 WALL ( 6.25 usr +  0.31 sys =  6.56 CPU) @ 185.98/s (n=1220)
             7 WALL ( 6.25 usr +  0.29 sys =  6.54 CPU) @ 186.54/s (n=1220)
             7 WALL ( 5.62 usr +  0.30 sys =  5.92 CPU) @ 206.08/s (n=1220)
             4 WALL ( 3.92 usr +  0.22 sys =  4.14 CPU) @ 294.69/s (n=1220)
Throughputs for Extlib running 4 times for at least 4 CPU seconds:
    Extlib:  5 WALL ( 4.02 usr +  0.19 sys =  4.21 CPU) @ 187.41/s (n=789)
             4 WALL ( 4.01 usr +  0.21 sys =  4.22 CPU) @ 186.97/s (n=789)
             4 WALL ( 4.00 usr +  0.20 sys =  4.20 CPU) @ 187.86/s (n=789)
             5 WALL ( 4.02 usr +  0.18 sys =  4.20 CPU) @ 187.86/s (n=789)
         Rate      Extlib Dllist'
 Extlib 188+- 0/s      --  [-14%]
Dllist' 218+-43/s   [16%]      --

(The results are between brackets because the variability in the
measures does not confirm that the rates are significantly different.
The experiment should be repeated more times.  A full_major garbage
collection was done between the two tests.)


Example 2: Inserting 10000 elements and removing them with
---------- Dllist'.remove_last and Dllist.remove (again same canva
           applies):

Throughputs for Dllist' running 4 times for at least 4 CPU seconds:
   Dllist':  8 WALL ( 7.29 usr +  0.25 sys =  7.54 CPU) @ 295.36/s (n=2227)
             6 WALL ( 5.72 usr +  0.21 sys =  5.93 CPU) @ 375.55/s (n=2227)
             5 WALL ( 4.85 usr +  0.16 sys =  5.01 CPU) @ 444.51/s (n=2227)
             5 WALL ( 3.97 usr +  0.15 sys =  4.12 CPU) @ 540.53/s (n=2227)
Throughputs for Extlib running 4 times for at least 4 CPU seconds:
    Extlib:  5 WALL ( 4.03 usr +  0.19 sys =  4.22 CPU) @ 152.84/s (n=645)
             4 WALL ( 3.98 usr +  0.15 sys =  4.13 CPU) @ 156.17/s (n=645)
             5 WALL ( 3.96 usr +  0.17 sys =  4.13 CPU) @ 156.17/s (n=645)
             4 WALL ( 3.95 usr +  0.17 sys =  4.12 CPU) @ 156.55/s (n=645)
         Rate      Extlib Dllist'
 Extlib 155+- 1/s      --    -62%
Dllist' 414+-86/s    166%      --

You will probably not agree with the above results -- and maybe I made
mistakes in my hastiness -- but the code is there to discuss upon.

Cheers,
ChriS

Re: [Ocaml-lib-devel] Tips on integrating ocaml-lib with the ocaml stdlib?

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

> > That's interesting idea, could you give more informations about the goal
of
> > your project ?
>
> To write a robust, type-safe OS.
>
> > Actually you just need to declare in IO.ml the C externals to caml
channels
> > functions and hide them in the mli so they can't be used directly. Have
a
> > look at pervasives.ml and .mli sources to see how ocaml is doing.
>
> I'd prefer to get rid of the channels completely (as well as
> printf/fprintf, use of file descriptors, probably other things too),
> to avoid writing a lot of libc stub code.
>

Then you need to write  :

external open_file : string -> bin:bool -> IO.input = "camlos_open_file"

for example, and generate an input from this on the C side.
That's quite tricky because You'll have to :
a) know about IO.input structure on the C side ( order of record fields )
b) create closures in C using caml API : not very easy.
You should really consider the approach of having  file_channel primitives
in IO.ml for internal usage only.

Nicolas

Re: [Ocaml-lib-devel] Tips on integrating ocaml-lib with the ocaml stdlib?

[Jonathan R. <jon...@gm...>]

> That's interesting idea, could you give more informations about the goal =
of
> your project ?

To write a robust, type-safe OS.

> Actually you just need to declare in IO.ml the C externals to caml channe=
ls
> functions and hide them in the mli so they can't be used directly. Have a
> look at pervasives.ml and .mli sources to see how ocaml is doing.

I'd prefer to get rid of the channels completely (as well as
printf/fprintf, use of file descriptors, probably other things too),
to avoid writing a lot of libc stub code.

Jonathan

Re: [Ocaml-lib-devel] Tips on integrating ocaml-lib with the ocaml stdlib?

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

>  Hi,
>
> I'm doing an OS project, and I want to make a custom ocaml environment
> where the ExtLib modules are integrated to be part of the OCaml
> standard library.
>
> I plan on going so far as to remove pervasives.out_channel/in_channel,
> among other things, and using the IO module exclusively.
>
> If anyone could provide some helpful suggestions on how best to go
> about this, it would be greatly appreciated.
>
> Jonathan

That's interesting idea, could you give more informations about the goal of
your project ?

Actually you just need to declare in IO.ml the C externals to caml channels
functions and hide them in the mli so they can't be used directly. Have a
look at pervasives.ml and .mli sources to see how ocaml is doing.

Nicolas

Re: [Ocaml-lib-devel] IO module & scanf

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

> Hi,
>
> I see you have a printf function in IO that works on the output type,
> but for symmetry, why is there no scanf for the input type?
>
> Jonathan

At first, it was not asked before, so that's the reason it's not in IO.
A reason I can see now not to add it is that will link the whole Scanf
module ( 32 Ko ) just for this function as soon as you use IO.

You can simply use the following :

let io_scanf ch = Scanf.bscanf (Scanf.Scanbuf.from_function (fun() ->
IO.read ch))

Nicolas

[Ocaml-lib-devel] Tips on integrating ocaml-lib with the ocaml stdlib?

[Jonathan R. <jon...@gm...>]

Hi,

I'm doing an OS project, and I want to make a custom ocaml environment
where the ExtLib modules are integrated to be part of the OCaml
standard library.

I plan on going so far as to remove pervasives.out_channel/in_channel,
among other things, and using the IO module exclusively.

If anyone could provide some helpful suggestions on how best to go
about this, it would be greatly appreciated.

Jonathan

[Ocaml-lib-devel] IO module & scanf

[Jonathan R. <jon...@gm...>]

Hi,

I see you have a printf function in IO that works on the output type,
but for symmetry, why is there no scanf for the input type?

Jonathan

Re: [Ocaml-lib-devel] Dllist

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

On Fri, 2005-05-27 at 16:23 +0200, Christophe TROESTLER wrote:
> On Fri, 27 May 2005, John Skaller wrote:

> Can you explain a bit more your point?  

In C notation slists are made of 

struct slist { T data; slist *next; };

and dlists are made of

struct  { T data; dlist * next; dlist *prev; };

neither can represent an empty list in Ocaml.

The library supplies the maximally efficient
and simplest representation by Occam's Razor,
and that cannot be empty. It isn't a bug, but
a consequence of the mathematics.

Really, what is represented is a doubly linked
list node (not a doubly linked list).

-- 
John Skaller, skaller at users.sf.net
PO Box 401 Glebe, NSW 2037, Australia Ph:61-2-96600850 
Download Felix here: http://felix.sf.net

Re: [Ocaml-lib-devel] Dllist

[Christophe T. <Chr...@um...>]

On Fri, 27 May 2005, John Skaller wrote:
> 
> On Fri, 2005-05-27 at 12:06 +0200, Christophe TROESTLER wrote:
> > On Thu, 26 May 2005, Brian Hurt <bh...@sp...> wrote:
> > > 
> > > On Wed, 25 May 2005, Christophe TROESTLER wrote:
> > > 
> > > > Is there a good reason (aside from implementation easiness)
> > > > not to allow Dllist to be empty?  IMHO, empty lists are very
> > > > useful and it is rather an hindrance that Dllists cannot be.
> > > 
> > > My original implementation did allow for empty lists, but it got 
> > > overridden.
> > 
> > Where?  The CVS version does not seem to allow it.  
> 
> Originally, the dlists had 'header' objects.

No sure what you mean precisely by that.

> I think I'm responsible for arguing that this is too complex, the
> lists should be made from a single simple data structure.

Can you explain a bit more your point?  IMO, when one designs a
library for wide use, one should take care about simplicity of the
interface, usability and (if relevant) performance.  If that means a
bit more of coding, that's not a big deal.  Here the usability is at
stake: I think a [mutable,...] list that cannot be empty is not nearly
as useful as one that can.

> As such, an empty list cannot be represented: use dlist opt
> if you want possibly empty dlists.

And redefine every single function of the module to cope with that!
That defeats the purpose of using the library doesn't it.

ChriS

Re: [Ocaml-lib-devel] Dllist

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

On Fri, 2005-05-27 at 12:06 +0200, Christophe TROESTLER wrote:
> On Thu, 26 May 2005, Brian Hurt <bh...@sp...> wrote:
> > 
> > On Wed, 25 May 2005, Christophe TROESTLER wrote:
> > 
> > > Hi,
> > >
> > > Is there a good reason (aside from implementation easiness) not to
> > > allow Dllist to be empty?  IMHO, empty lists are very useful and it is
> > > rather an hindrance that Dllists cannot be.
> > 
> > My original implementation did allow for empty lists, but it got 
> > overridden.
> 
> Where?  The CVS version does not seem to allow it.  

Originally, the dlists had 'header' objects. I think I'm
responsible for arguing that this is too complex,
the lists should be made from a single simple data structure.

As such, an empty list cannot be represented: use dlist opt
if you want possibly empty dlists.

-- 
John Skaller, skaller at users.sf.net
PO Box 401 Glebe, NSW 2037, Australia Ph:61-2-96600850 
Download Felix here: http://felix.sf.net

Re: [Ocaml-lib-devel] Dllist

[Christophe T. <chr...@us...>]

On Thu, 26 May 2005, Brian Hurt <bh...@sp...> wrote:
> 
> On Wed, 25 May 2005, Christophe TROESTLER wrote:
> 
> > Hi,
> >
> > Is there a good reason (aside from implementation easiness) not to
> > allow Dllist to be empty?  IMHO, empty lists are very useful and it is
> > rather an hindrance that Dllists cannot be.
> 
> My original implementation did allow for empty lists, but it got 
> overridden.

Where?  The CVS version does not seem to allow it.  As an example,
consider:

# let l = create 1 in
    demote l;
    length l;;
- : int = 1

(hum).   How do you create an empty list?

ChriS

Re: [Ocaml-lib-devel] Dllist

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

On Wed, 25 May 2005, Christophe TROESTLER wrote:

> Hi,
>
> Is there a good reason (aside from implementation easiness) not to
> allow Dllist to be empty?  IMHO, empty lists are very useful and it is
> rather an hindrance that Dllists cannot be.

My original implementation did allow for empty lists, but it got 
overridden.

Brian

Re: [Ocaml-lib-devel] Dllist

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

> Hi,
> 
> Is there a good reason (aside from implementation easiness) not to
> allow Dllist to be empty?  IMHO, empty lists are very useful and it is
> rather an hindrance that Dllists cannot be.
> 
> To have an idea of what I have in mind, see the attached interface.
> Comments are welcome.
> 
> Regards,
> ChriS

I can't tell exactly since I neither wrote or use Dlllist.
Could the Dlllist authors comment on this proposal ?

Nicolas

[Ocaml-lib-devel] Dllist

[Christophe T. <chr...@us...>]

Hi,

Is there a good reason (aside from implementation easiness) not to
allow Dllist to be empty?  IMHO, empty lists are very useful and it is
rather an hindrance that Dllists cannot be.

To have an idea of what I have in mind, see the attached interface.
Comments are welcome.

Regards,
ChriS

--
P.S. Following the standard library, [create] should be used for
_uninitialized_ structures.  Here [make] is more standard.

Re: [Ocaml-lib-devel] More enum conversions?

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

> > > Currently enum conversion functions are only provided for the data
> > > structures included in ExtLib itself.  Might it be a good idea to add
> > > them for some or all of the remaining parts of the OCaml standard
library?
> >
> > There is enum for Lists, DynArrays, Strings and Hashtbls.
> > The only reason there is not for Array is because ExtLib doesn't have an
> > ExtArray module.
> > IMHO, it's not needed since it's most of the time more convenient to use
> > DynArrays instead of Arrays.
>
> The issue is interfacing to existing code and existing
> interfaces which may specify a standard ocaml array,
> so I'd agree with Peter I think.

It's ok for me to add  of_array and to_array to Enum module.

Nicolas

Re: [Ocaml-lib-devel] More enum conversions?

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

On Mon, 2005-05-23 at 20:23 +0900, Nicolas Cannasse wrote:
> > Currently enum conversion functions are only provided for the data
> > structures included in ExtLib itself.  Might it be a good idea to add
> > them for some or all of the remaining parts of the OCaml standard library?
> 
> There is enum for Lists, DynArrays, Strings and Hashtbls.
> The only reason there is not for Array is because ExtLib doesn't have an
> ExtArray module.
> IMHO, it's not needed since it's most of the time more convenient to use
> DynArrays instead of Arrays.

The issue is interfacing to existing code and existing 
interfaces which may specify a standard ocaml array,
so I'd agree with Peter I think.


-- 
John Skaller, skaller at users.sf.net
PO Box 401 Glebe, NSW 2037, Australia Ph:61-2-96600850 
Download Felix here: http://felix.sf.net

Re: [Ocaml-lib-devel] More enum conversions?

[Peter J. <pe...@jo...>]

Nicolas Cannasse wrote:
> There is enum for Lists, DynArrays, Strings and Hashtbls.
> The only reason there is not for Array is because ExtLib doesn't have an
> ExtArray module.
> IMHO, it's not needed since it's most of the time more convenient to use
> DynArrays instead of Arrays.

This is true if you are in a position to choose the data structures you
use.  However, there are many existing libraries that contain functions
returning ordinary arrays.  The OCaml standard library itself has some,
like Sys.readdir.  In such cases I usually find building an enum from
the array to be the most convenient way to process it.

Re: [Ocaml-lib-devel] More enum conversions?

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

> Currently enum conversion functions are only provided for the data
> structures included in ExtLib itself.  Might it be a good idea to add
> them for some or all of the remaining parts of the OCaml standard library?

There is enum for Lists, DynArrays, Strings and Hashtbls.
The only reason there is not for Array is because ExtLib doesn't have an
ExtArray module.
IMHO, it's not needed since it's most of the time more convenient to use
DynArrays instead of Arrays.

Nicolas

[Ocaml-lib-devel] More enum conversions?

[Peter J. <pe...@jo...>]

Currently enum conversion functions are only provided for the data
structures included in ExtLib itself.  Might it be a good idea to add
them for some or all of the remaining parts of the OCaml standard library?

In particular, I've often found myself wanting to convert from the
builtin array type, and there doesn't seem to be a function to handle
that yet.  So at the very least I'd propose adding something along the
lines of:

  val enum_of_array : 'a array -> 'a Enum.t
  val array_of_enum : 'a Enum.t -> 'a array

  let enum_of_array a = (* stolen from DynArray.enum *)
      let rec make start =
          let idxref = ref 0 in
          let next () =
              if !idxref >= Array.length a then
                  raise Enum.No_more_elements
              else
                  let retval = Array.unsafe_get a !idxref in
                  incr idxref;
                  retval
          and count () =
              if !idxref >= Array.length a then 0
              else Array.length a - !idxref
          and clone () =
              make !idxref
          in
          Enum.make ~next:next ~count:count ~clone:clone
      in
      make 0

  let array_of_enum e =
      match Enum.peek e with
      | None -> [||]
      | Some elt ->
          let a = Array.make (Enum.count e) elt in
          Enum.iteri (Array.unsafe_set a) e;
          a

Re: [Ocaml-lib-devel] IO Bits API

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

> On Thu, May 19, 2005 at 04:34:19PM +0900, Nicolas Cannasse wrote:
> > I also have a complete, small, and easy Png library, that can be used
> > together with Unzip module to read Png using only ExtLib. If there is
some
> > interest it could be added to ExtLib.
>
> A Png library sounds nice, but I'm not sure how appropriate it is for
> Extlib.  How does it compare to the functionality of camlimages?
>
> Rich.

It's maybe more easy to use than a framework such as camlimages, and is pure
Ocaml (it doesn't require additionnal decoding libraries).
Here's the mli for review. The full ML source is only 11Ko.

Nicolas

---

type grey_bits =
| GBits1
| GBits2
| GBits4
| GBits8
| GBits16

type grey_alpha_bits =
| GABits8
| GABits16

type true_bits =
| TBits8
| TBits16

type index_bits =
| IBits1
| IBits2
| IBits4
| IBits8

type alpha =
| NoAlpha
| HaveAlpha

type color =
| ClGreyScale of grey_bits
| ClGreyAlpha of grey_alpha_bits
| ClTrueColor of true_bits * alpha
| ClIndexed of index_bits

type header = {
  png_width : int;
  png_height : int;
  png_color : color;
  png_interlace : bool;
}

type chunk_id = string

type chunk =
| CEnd
| CHeader of header
| CData of string
| CPalette of string
| CUnknown of chunk_id * string

type png = chunk list

type error_msg =
| Invalid_header
| Invalid_file
| Truncated_file
| Invalid_CRC
| Invalid_colors
| Unsupported_colors
| Invalid_datasize
| Invalid_filter of int
| Invalid_array

exception Error of error_msg

val error_msg : error_msg -> string

val is_critical : chunk_id -> bool
val is_public : chunk_id -> bool
val is_reseverd : chunk_id -> bool
val is_safe_to_copy : chunk_id -> bool

val header : png -> header

val data : png -> string

val color_bits : color -> int

val parse : IO.input -> png

val write : 'a IO.output -> png -> unit

val filter : png -> string -> string

val make : width:int -> height:int -> pixel:(int -> int -> int32) ->
compress:(string -> string) -> png

Re: [Ocaml-lib-devel] IO Bits API

[Richard J. <ri...@an...>]

On Thu, May 19, 2005 at 04:34:19PM +0900, Nicolas Cannasse wrote:
> I also have a complete, small, and easy Png library, that can be used
> together with Unzip module to read Png using only ExtLib. If there is some
> interest it could be added to ExtLib.

A Png library sounds nice, but I'm not sure how appropriate it is for
Extlib.  How does it compare to the functionality of camlimages?

Rich.

-- 
Richard Jones, CTO Merjis Ltd.
Merjis - web marketing and technology - http://merjis.com
Team Notepad - intranets and extranets for business - http://team-notepad.com

[Ocaml-lib-devel] Base64 tables

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

Hi again,

I also just modified Base64 module in order to make the chars used for
encoding/decoding customizable.
Using optional parameters, this will not break existing code.

Nicolas

[Ocaml-lib-devel] IO Bits API

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

Hi list,

I just added to the IO module a "bits" API that enable you to read/write
bit-by-bit binary files. This complete well the already defined APIs for
reading and writing integers in low and bigendian mode. It's quite short but
difficult to write correctly (a lot of bit shifting , especially concering
the 31 bits limit of ocaml).

type bc_in
type bc_out
exception Bits_error

val input_bits : input -> bc_in
(** Read bits from an input *)

val output_bits : 'a output -> bc_out
(** Write bits to an output *)

val read_bits : bc_in -> int -> int
(** Read up to 31 bits, raise Bits_error if n < 0 or n > 31 *)

val write_bits : bc_out -> nbits:int -> int -> unit
(** Write up to 31 bits represented as a value, raise Bits_error if nbits <
0
or nbits > 31 or the value representation excess nbits. *)

val flush_bits : bc_out -> unit
(** Flush remaining unwritten bits, adding up to 7 bits which values 0. *)

val drop_bits : bc_in -> unit
(** Drop up to 7 buffered bits and restart to next input character. *)

I also added the following that can be useful some time when you don't want
to carry the polymorphic value of an IO.output for example :

external cast_output : 'a output -> unit output = "%identity"
(** You can safely transform any output to an unit output in a safe way
by using this function. *)

I also have a complete, small, and easy Png library, that can be used
together with Unzip module to read Png using only ExtLib. If there is some
interest it could be added to ExtLib.

Nicolas