ocaml-lib-devel — Developer's mailing list

Re: [Ocaml-lib-devel] Advancements

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

On Tue, 25 Mar 2003, Nicolas Cannasse wrote:

> > > I'm currently still working on the List implementation... okay ,
> > > some words about it : I'm currently at Kyoto, and having everyday at
> lunch
> > > some ocaml-talks with Jacques Garrigue, and when I told him about this
> > > setcdr trick, is first reaction was that it would be nice but perhaps
> there
> > > is some GC issues since that can create pointers from the major to the
> minor
> > > heap, and then causing speed overhead.
> >
> > I'm only using setcdr on list elements I just recently allocated, which
> > makes it signifigantly less likely that I would be adding a pointer from
> > the major to the minor heap.  Possible, but not likely.
> 
> Actually, it depends !
> For example the map function is calling an user function, that can do lots
> of things, resulting a minor heap collection, and then back to ExtList.map
> your root has been moved to major heap. But Damien Doligez conclusion was
> that it will only occur once at a time, since next GC will put everything in
> the major heap, so the cost is very low.
> 

Even with append it's possible.  I have to allocate the next node in the 
list before calling setcdr (obviously).  Allocating the next node could 
cause a collection (minor heap being full) moving the previous node into 
the major heap.  Then, when I call setcdr, I'm still setting a pointer 
from the major heap to point to the minor heap.  So this is a problem that 
needs to be handled correctly no matter what.

On the other hand, it doesn't have to be the most efficient- because for 
every time we write a pointer into the major heap, we also have to do a 
garbage collection.  In your example, the map with a complex function, the 
cost of the function itself becomes a major cost.  These costs will 
overwhealm the cost of setting the pointer itself.

Some back of the envelope calculations.  Assume the minor heap is 16K 
words (64K bytes).  And we allocate 1 word every 6 instructions (about 
average for ML programs).  This means we do a GC every 96K instructions on 
average.  Even if setting a pointer from a major to a minor heap is 1K 
instructions, this is still less than 1% of the execution cost (not 
counting the cost of the garbage collection itself).

Which is, effectively, the conclusion you came to.

Brian

Re: [Ocaml-lib-devel] Advancements

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

> > I'm currently still working on the List implementation... okay ,
> > some words about it : I'm currently at Kyoto, and having everyday at
lunch
> > some ocaml-talks with Jacques Garrigue, and when I told him about this
> > setcdr trick, is first reaction was that it would be nice but perhaps
there
> > is some GC issues since that can create pointers from the major to the
minor
> > heap, and then causing speed overhead.
>
> I'm only using setcdr on list elements I just recently allocated, which
> makes it signifigantly less likely that I would be adding a pointer from
> the major to the minor heap.  Possible, but not likely.

Actually, it depends !
For example the map function is calling an user function, that can do lots
of things, resulting a minor heap collection, and then back to ExtList.map
your root has been moved to major heap. But Damien Doligez conclusion was
that it will only occur once at a time, since next GC will put everything in
the major heap, so the cost is very low.

Nicolas Cannasse

Re: [Ocaml-lib-devel] Module Structure

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

> > This still does let one use all of ExtLib with a simple
> >   open ExtLib
> >
> > I think that
> >
> >     module ExtLib = struct
> >       module List = ExtList
> >       ...
> >     end
> >
> > will solve this problem.
>
> Perhaps, but I wonder then if you're doing
> open ExtLib
> are you linking with all the modules ExtList, ExtHashtbl, ExtString...
even
> if you're not using them ?

I have checked the following.
When you're doing "open ExtLib" it will really link all the modules declared
in extLib.ml, even if later the application does not use them. We have then
three choices :
- use my module structure proposal, that will cause the users which are
using ExtLib as an extension to link all the overidden modules
- use Manos Renieris one, that will cause the users which are using ExtLib
as an StdLib replacement to link all the overidden modules
- find another prefix keyword ( for exemple Std ) so there is no more ExtLib
module, but it can be use :

As a replacement of the List standard module :
        --- test.ml ---
        open StdList
        List.map f l
        --- stdList.mli ---
        module List : sig <...> end

As a extended library of functions :
        --- test.ml ---
        ExtList.map f l
        -- extList.ml ----
        include StdList.List

Nicolas Cannasse

Re: [Ocaml-lib-devel] Sets, ordered and unordered

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

On Mon, 24 Mar 2003, Nicolas Cannasse wrote:

> > Actually, what I'd like to see is the stdlib Set to give up pretending to
> > maybe be unordered, and declare itself ordered.  And to implement a true
> > unordered set built on hash tables (sometimes, checking for membership in
> > O(1) instead of O(log n) is usefull).  With both modules inheriting from a
> > common Set module.
> [..]
> 
> This starts a good thread about relationship of datastructures, and functor
> usage.
> Actually we can say that a data structure can be defined by :
> - its add/remove/find complexities
> - its order properties ( no-order, order on keys, order on items )
> - the way you're using it ( mainly : with or without keys )
> 
> I'm not realy sure if we should simply follow the current ocaml library
> style, or build a whole new architecture, but perhaps that was already your
> question, Brian :)
> 

That was precisely my question.  And no, I don't have an answer to it 
either :-).

Brian

Re: [Ocaml-lib-devel] Advancements

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

On Mon, 24 Mar 2003, Nicolas Cannasse wrote:

> > - bitset is being rewritten into bitarray, with the new features suggested
> > by the change in name.  The goal is to produce something you could write
> > elliptic curve cryptosystems in at least semi-efficiently.
> 
> Nice !

Status report on this: I spent the weekend writting and rewritting and 
rerewritting the damned rotate functions.  Everything else looks like it's 
about ready to go.  I'm going to take another swing at the rotates 
tonight, and see if I can kick my brain into working.

> 
> > - I have the beginings of what I'm currently calling an XString library,
> > which stores a string as an unbalanced tree of of substrings.  The big
> > advantage here is that concats are O(1), and then converting the XString
> > to a normal string is O(n).  In-place modification won't be supported.
> > This will be usefull in constructing strings by concating substrings
> > efficiently.  Sort of like Java's StringBuffer.
> 
> Very good also, but what then does not call it StringBuffer ?
> The name came by itself, so... :)

I may.

> 
> > - A resizable array module- rather like Java's Vector or Python's List.
> 
> Yes we realy need this Vector one

As a side note, I do way too much numerical programming to like the term
'vector' to denote extensible arrays.  This annoys me no end in Java.  
I'm likely to call this library 'xarray' or something instead.

> 
> > Life has been rather hectic of late for me- sorry I haven't been more
> > timely on this.  But this weekend is looking dull, so I should be able to
> > spend some serious coding time.
> 
> Yes, I would like to apologize for my previous post, and after some
> thinking, I think now we're walking the good way, and we have no need to
> hurry more. 

It's OK.

> I'm currently still working on the List implementation... okay ,
> some words about it : I'm currently at Kyoto, and having everyday at lunch
> some ocaml-talks with Jacques Garrigue, and when I told him about this
> setcdr trick, is first reaction was that it would be nice but perhaps there
> is some GC issues since that can create pointers from the major to the minor
> heap, and then causing speed overhead. 

I'm only using setcdr on list elements I just recently allocated, which 
makes it signifigantly less likely that I would be adding a pointer from 
the major to the minor heap.  Possible, but not likely.

Brian

[Ocaml-lib-devel] CVS

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

Hi !
I put the first version of the ExtLib on the Sourceforge CVS ( as
extlist-dev )
It compiles as a CMA but miss a lot of implementations / documentation.
You can right now access it anonymously, but only the registered developpers
of the ocaml-lib SF project can commit. Since I don't have any administrator
rights right know, I don't think I can add new developpers, but I will ask
Amit.
Comments are welcomed.

Nicolas Cannasse

Re: [Ocaml-lib-devel] mutable cyclic list

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

On Mon, Mar 24, 2003 at 05:27:45PM +0900, Nicolas Cannasse wrote:
> > If there is any interest in this module, I can clean it up, document and
> > so on. Now I'm dropping it here just for comments.
> 
> Thanks, this is a nice library, but I'm not really sure that the average
> Ocaml user are really needing an circular list ( I actually never have used
> theses since my first caml days ) , but of course I would be more convinced
> if somehow bring up some samples of common usage of them.

I needed (well, will need :-) it for some algorithm for control flow
graph processing. Simply algorithm relays on it. And there was a post
on caml-list recently asking about data structure allowing fast adding
of elements, lists of elements, removal of specific elements, and with
tail recursive fold functions. Somebody suggested priority queue (that
have more features, but better to much then to less), that will do all
of this in O(log n). My circular list will do all of this in O(1).

-- 
: Michal Moskal ::::: malekith/at/pld-linux.org :  GCS {C,UL}++++$ a? !tv
: PLD Linux ::::::: Wroclaw University, CS Dept :  {E-,w}-- {b++,e}>+++ h

Re: [Ocaml-lib-devel] mutable cyclic list

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

> If there is any interest in this module, I can clean it up, document and
> so on. Now I'm dropping it here just for comments.

Thanks, this is a nice library, but I'm not really sure that the average
Ocaml user are really needing an circular list ( I actually never have used
theses since my first caml days ) , but of course I would be more convinced
if somehow bring up some samples of common usage of them.

Nicolas Cannasse

Re: [Ocaml-lib-devel] Sets, ordered and unordered

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

> Actually, what I'd like to see is the stdlib Set to give up pretending to
> maybe be unordered, and declare itself ordered.  And to implement a true
> unordered set built on hash tables (sometimes, checking for membership in
> O(1) instead of O(log n) is usefull).  With both modules inheriting from a
> common Set module.
[..]

This starts a good thread about relationship of datastructures, and functor
usage.
Actually we can say that a data structure can be defined by :
- its add/remove/find complexities
- its order properties ( no-order, order on keys, order on items )
- the way you're using it ( mainly : with or without keys )

I'm not realy sure if we should simply follow the current ocaml library
style, or build a whole new architecture, but perhaps that was already your
question, Brian :)

Nicolas Cannasse

Re: [Ocaml-lib-devel] Advancements

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

> - bitset is being rewritten into bitarray, with the new features suggested
> by the change in name.  The goal is to produce something you could write
> elliptic curve cryptosystems in at least semi-efficiently.

Nice !

> - I have the beginings of what I'm currently calling an XString library,
> which stores a string as an unbalanced tree of of substrings.  The big
> advantage here is that concats are O(1), and then converting the XString
> to a normal string is O(n).  In-place modification won't be supported.
> This will be usefull in constructing strings by concating substrings
> efficiently.  Sort of like Java's StringBuffer.

Very good also, but what then does not call it StringBuffer ?
The name came by itself, so... :)

> - A resizable array module- rather like Java's Vector or Python's List.

Yes we realy need this Vector one

> Life has been rather hectic of late for me- sorry I haven't been more
> timely on this.  But this weekend is looking dull, so I should be able to
> spend some serious coding time.

Yes, I would like to apologize for my previous post, and after some
thinking, I think now we're walking the good way, and we have no need to
hurry more. I'm currently still working on the List implementation... okay ,
some words about it : I'm currently at Kyoto, and having everyday at lunch
some ocaml-talks with Jacques Garrigue, and when I told him about this
setcdr trick, is first reaction was that it would be nice but perhaps there
is some GC issues since that can create pointers from the major to the minor
heap, and then causing speed overhead. Right now I'm aiming at tricking the
compiler with mutable structures , with the goal to have at least the
ExtList.map speed be as good as the ExtList.map one.
Even if I don't manage to do it, I will move the non-tails functions
List.map , List.fold_right, etc. into a "Fast" ExtList sub-module ( I'll
test for speed only for native code version under Windows OCaml/VC++, since
when you compile to bytecode you not care so much about speed, and since I
don't have access to other platforms right now - I'll post here the test
samples and results to know about other platforms speeds )

> Longer term, libraries I'd like (and that I think would be usefull) would
> include:
>
> - A BLAS-like library.  Although I need to think about this design some-
> OOLALA has shown me that BLAS itself is probably not the best overall
> library design.
>
> - A regular expressions library- although I think this might already be
> out there.
>
> - An elliptic curve crypto systems library.

Except the reg expr library ( and the new Regexp is the third one after the
Str module and PCRE ) I can't tell theses could be massively used enough to
be included in the ExtLib :)
Keep going on !

Nicolas Cannasse

Re: [Ocaml-lib-devel] Module Structure

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

> This still does let one use all of ExtLib with a simple
>   open ExtLib
>
> I think that
>
>     module ExtLib = struct
>       module List = ExtList
>       ...
>     end
>
> will solve this problem.

Perhaps, but I wonder then if you're doing
open ExtLib
are you linking with all the modules ExtList, ExtHashtbl, ExtString... even
if you're not using them ?

Nicolas Cannasse

Re: [Ocaml-lib-devel] Module Structure

[Manos R. <er...@cs...>]

This still does let one use all of ExtLib with a simple 
  open ExtLib

I think that 

    module ExtLib = struct
      module List = ExtList
      ...
    end

will solve this problem.

-- Manos

On Mon, Mar 17, 2003 at 05:23:57PM +0900, Nicolas Cannasse wrote:
> Hi list,
> 
> I have been thinking for some time on the module structure for ExtLib
> issues, and I think I found a quite reasonable comprise.
> Ok, first of all, we we talk there only about modules which are extending
> the StdLib ones, other "new" modules doesn't cause any problems.
> But for the Stdlib one - let's take the example of ExtList - there is some
> problems :
> 
> - some people would like to use ExtList as a replacement of List
> 
> For this first category of people, we can do the following :
> 
> -- file extList.mli ---
> module List : sig ... end
> --- eof ---
> 
> Like this theses people will only have to add an extra "open ExtList" in the
> beginning of their files and then they can use the List standard functions
> as well as the List extended ones within the same short and readable
> namespace : List.
> 
> But !
> - this we're modifying the specification of some functions, people with
> existing running code would like to use only ExtList as an additionnal
> library of functions, without overriding the current Stdlib ones.
> 
> Here's the answer :
> --- file extLib.mli ---
> module ExtList = ExtList.List
> --- eof ---
> 
> So they only have to do an "open ExtLib" and then they can use extended
> functions under the ExtList namespace.
> 
> Nicolas Cannasse
> 

[Ocaml-lib-devel] Sets, ordered and unordered

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

Actually, what I'd like to see is the stdlib Set to give up pretending to 
maybe be unordered, and declare itself ordered.  And to implement a true 
unordered set built on hash tables (sometimes, checking for membership in 
O(1) instead of O(log n) is usefull).  With both modules inheriting from a 
common Set module.

Which opens up a whole new can of worms.  To what extent do we want to go
down this path?  At the end, we have a whole family of datastructures,
with all the obvious relationships, both derived from (an array is a form
of a list) and built on top of (a hash table can be build on top of an
array or a tree).  And most of the implementations.  Hash tables on top of
expandable arrays, hash tables on top of trees, etc.

Done correctly, it could be an incredible advantage to defining new
algorithms and data structures.  It's be easy to "Ok, this new data
structure builds on top of a balanced tree- so I just use the standard
balanced tree and build ontop of it...".  Rather like BLAS is used for the
introduction of numerical libraries.  Plus you would never get caught
going "Gee, I wish they had built X ontop of Y instead of Z".

The cost for this generalicity is, of course, performance.  And memory.  
Take one example- my implementation of priority search queues.  I have
tree information (children references, key), balancing
information (color), tournament information (domination), and priority 
queue information (element references, from which I get priority) all in 
the same structure.  In the 'degenerate' case of the ADT library, they 
would be in four different structures, referencing each other in some sort 
of list.  

Also, dependencies would be fun in a bad way- to use the equivilent to
PSQueue, you'd need to pull in at least four different modules (tree,
balancedTree, tournament, psqueue) if not more (set, priority queue,
queue, etc).  This basically forces you to the monolithic library 
approach.

Brian

Re: [Ocaml-lib-devel] Another library for me to implement

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

On Thu, 20 Mar 2003, Michal Moskal wrote:

> On Thu, Mar 20, 2003 at 11:30:08AM -0600, Brian Hurt wrote:
> > 
> > Ordered set.
> > 
> > Basically, a general balanced tree.  Insert, delete, search all O(log n), 
> > access nth element O(log n), convert to sorted list O(n).  
> 
> Like Set.Make?

No.  By definition, the Set in the standard library is *unordered*.  Take 
a look at the definition of iter, fold, etc.- the order that elements are 
presented are not defined.

Although it is implemented as an ordered set, and the current definition
wouldn't allow, for example, a hash table implementation (without some
deep trickery).  I'm not sure if we gain anything by pretending that it is
an unordered set.

Hmm.  And there's no way that I'm seeing to access the nth element cheaply 
(O(log n)).  elements gives you a sorted list of elements- you could then 
call nth on this.  A size function would also be nice.

Brian

Re: [Ocaml-lib-devel] Advancements (long-winded)

[William D. N. <wne...@cs...>]

On Thu, 20 Mar 2003, Brian Hurt wrote:

> Blowfish I'm less interested in.  I'm a fan of Twofish myself- especially
> given some of the weaknesses discovered in AES/Rijndael recently...

I share your feelings on Blowfish, but it's still popular and I have an
OCaml interfaced version lying around that I could pretty much copy and
paste into cryptokit.  it  has all sorts of hooks in there for peeking at
and mussing with the internal state, but I might just leave those in for
folks who want to have some fun...

BTW:  Which Rijndael weaknesses are you referring to?  Not the Filiol
mistake (let's be charitable and call it a mistake)?  Or are you referring
to the Courtois & Pieprzyk XSL work?  Or something else?

> I'd like an easy, reasonably fast, library to find primitive polys in
> GF(2^n) for some n.

Hmmm...I'll have to look at that.  I haven't needed it yet (hence its
non-existance in my code), but I could see needing it in the future.  I'm
just not sure if that kind of stuff should really go in a crypto library
though.  It would probably be better to have a number theory/algeba
library that is used by the crypto library instead.

> Is there a Yarrow-based PRNG?

No.  I don't usually care about having a strong source of randomness,
since most of what I do is testing, but I agree that a strong PRNG should
be included in any publicly released version, so I suppose I could add
yarrow (I'd have to look at the code and see when I can fit it into my
schedule, though).

William D. Neumann

---

"Well I could be a genius, if I just put my mind to it.
And I...I could do anything, if only I could get 'round to it.
Oh we were brought up on the space-race, now they expect you to clean toilets.
When you've seen how big the world is, how can you make do with this?
If you want me, I'll be sleeping in - sleeping in throughout these glory days."

	-- Jarvis Cocker

Re: [Ocaml-lib-devel] Another library for me to implement

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

On Thu, Mar 20, 2003 at 11:30:08AM -0600, Brian Hurt wrote:
> 
> Ordered set.
> 
> Basically, a general balanced tree.  Insert, delete, search all O(log n), 
> access nth element O(log n), convert to sorted list O(n).  

Like Set.Make?

-- 
: Michal Moskal ::::: malekith/at/pld-linux.org :  GCS {C,UL}++++$ a? !tv
: PLD Linux ::::::: Wroclaw University, CS Dept :  {E-,w}-- {b++,e}>+++ h

Re: [Ocaml-lib-devel] New Library 1: XList

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

On Thu, 20 Mar 2003, fva wrote:

> Uh? You mean to put both in or you're just asking advice as to what we 
> think about it?
> 
> - If the former... I'd say one of them would never get used (probably) 
> fold_right' because it is somewhat alien to the rest of the interfacing 
> conventions.

I meant to put both in.  fold_right' was just to spike the guns of any 
performance argument.  Of the two, I perfer the reversing version- I'll 
take correctness over performance any day of the week.

Brian

Re: [Ocaml-lib-devel] Advancements (long-winded)

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

On Thu, 20 Mar 2003, William D. Neumann wrote:

> On Thu, 20 Mar 2003, Brian Hurt wrote:
> 
> > - bitset is being rewritten into bitarray, with the new features suggested
> > by the change in name.  The goal is to produce something you could write
> > elliptic curve cryptosystems in at least semi-efficiently.
> 
> Umm...when you say EC cryptosystems, I assume you're just talking about a
> package that's good for doing generic work over GF(2^n), right?  That'd be
> pretty handy to have around...

Yes.  That is precisely what I meant.  EC crypto is just the hardest, most 
complicated, most performance important GF computations I know of.

> 
> - Repackage some stuff to create a byte-array type with easy conversion
>   between 8bits/byte (for working with internally) 4bits/byte (for working
>   with in a readible format), and appropriate manipulation routines
>   (shifts, rotates, boolean functions, etc.).  I need to put more thought
>   into this, I've just been tossing things together in an ad-hoc fashion
>   when I need something for work -- perhaps your bitarrays would be all
>   that I'm really looking for.

Hmm.  Should add a function to return bits n..n+k with k <= Sys.word_size 
as a combined in.  And set and invert as well.

> - Add other ciphers like Blowfish, RC5, and some of the AES and NESSIE
>   applicants.  I'd like to add SEAL, but I'm not sure what IBM's stance is
>   on its licensing is.

Blowfish I'm less interested in.  I'm a fan of Twofish myself- especially 
given some of the weaknesses discovered in AES/Rijndael recently...

> - Add some more number theory tools (so far all I have is CRT-enabled
>   modular exponentiation used in the RSA module).

I'd like an easy, reasonably fast, library to find primitive polys in 
GF(2^n) for some n.

> * Added two new PRNGs (the crappy GMP default PRNG -- good for testing --
>   and a stronger, slower PRNG described by Peter Guttman)

Is there a Yarrow-based PRNG?

Brian

Re: [Ocaml-lib-devel] Advancements (long-winded)

[William D. N. <wne...@cs...>]

On Thu, 20 Mar 2003, Brian Hurt wrote:

> - bitset is being rewritten into bitarray, with the new features suggested
> by the change in name.  The goal is to produce something you could write
> elliptic curve cryptosystems in at least semi-efficiently.

Umm...when you say EC cryptosystems, I assume you're just talking about a
package that's good for doing generic work over GF(2^n), right?  That'd be
pretty handy to have around...

> - An elliptic curve crypto systems library.

Well, I've got my modifications to Xavier's cryptokit library that I could
contribute (I'd want to clear it with Xavier first though).  I haven't
done too much to it yet, the changes I've made are listed at the end of
this mail.

Anyway, I've been wanting to add an EC module to this library along with a
number of other changes and additions, such as:

- Repackage some stuff to create a byte-array type with easy conversion
  between 8bits/byte (for working with internally) 4bits/byte (for working
  with in a readible format), and appropriate manipulation routines
  (shifts, rotates, boolean functions, etc.).  I need to put more thought
  into this, I've just been tossing things together in an ad-hoc fashion
  when I need something for work -- perhaps your bitarrays would be all
  that I'm really looking for.
- Fix arcfour so it can take a full 2048 bit key (I think Xavier misread
  the specs and limited it to 128 bits).
- Add a generic Fiestel cipher construction.
- Add other ciphers like Blowfish, RC5, and some of the AES and NESSIE
  applicants.  I'd like to add SEAL, but I'm not sure what IBM's stance is
  on its licensing is.
- Add a construction that allows for easy creation of Luby-Rackoff
  ciphers.
- Add some qth root versions of PK ciphers.
- Add some more number theory tools (so far all I have is CRT-enabled
  modular exponentiation used in the RSA module).
- Add some secret sharing tools.
- Figure out why the included implementation of SHA-1 runs so freakin'
  slow on the PPC G4 processor...
- Perhaps add factoring and DL computation routines, but I'm not sure this
  belongs here...
- Oh yeah...and fix my screwed up Ocamldoc documentation.

If you can think of anything else that should be added (or if you want to
help with the development of this let me know.

---

My changes to cryptokit (v1.0) so far:
* Replaced the bigint part of the library with much faster calls to
  GMP using mlgmp (so I suppose I might need to talk to David Monniaux as
  well -- I forget what the license situations are).
* Changed the RSA module so that it now has two keytypes, public and
  private, and uses those key types appropriately (note: this breaks
  compatability with the original cryptokit.  Obviously.)
* Added DSA signatures (with the fix for Bleichenbacher's potential
  attack)
* Added SHA-256, SHA-384, and SHA-512 (currently only compiles with
  compilers that support the 64-bit long long type, e.g. gcc)
* Added Markus Jakobsson style hash chains.
* Added two new PRNGs (the crappy GMP default PRNG -- good for testing --
  and a stronger, slower PRNG described by Peter Guttman)
* Added some random number routines for generating a specific number of
  bits, rather than bytes, and returning the number either as a string or
  as a GMP MP Integer.
* Added a number of random prime generation routines (probabilistic
  primes, strong primes, proveable primes, and DSA primes)
* Added the cipherX construction that allows you to build DESX style
  extensions out of any block cipher.

William D. Neumann

---

"Well I could be a genius, if I just put my mind to it.
And I...I could do anything, if only I could get 'round to it.
Oh we were brought up on the space-race, now they expect you to clean toilets.
When you've seen how big the world is, how can you make do with this?
If you want me, I'll be sleeping in - sleeping in throughout these glory days."

	-- Jarvis Cocker

[Ocaml-lib-devel] Another library for me to implement

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

Ordered set.

Basically, a general balanced tree.  Insert, delete, search all O(log n), 
access nth element O(log n), convert to sorted list O(n).  

Brian

[Ocaml-lib-devel] [Caml-list] Announce: Regexp/OCaml syntax extension (fwd)

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

Opps.  Too late :-)

Brian

---------- Forwarded message ----------
Date: 21 Mar 2003 01:50:36 +0900
From: Yutaka OIWA <oi...@yl...>
To: cam...@in...
Subject: [Caml-list] Announce: Regexp/OCaml syntax extension

Hello subscribers:

I release a camlp4-macro package called Regexp/OCaml.

I believe Objective Caml is a powerful tool not only for writing an
interpreter and compiler but also for writing casual "script"
applications which were in a territory of Perl, Python and
Ruby. However, string decomposition is one of OCaml's weak points when
compared to those scripting languages: the interfaces of both Str
module and Pcre module are very primitive and cumbersome if they are
heavily used.  Regexp/OCaml solves this point by providing syntax
support for regular expression matching.

Regexp/OCaml provides convenient syntax sugar for regular expression
match against strings using PCRE/OCaml library. The features of this
macro package are the following:

    * Convenient syntax: similar to standard match-with expressions
    * Binding matching substrings to variables: no more $1, $2, ...
    * Automagical easy-to-use type-coercion: no flood of int_of_string etc.
    * Support for optional-patterns: gives string option type etc.
    * Default values for optional-patterns 

For example, parsing an entry for some log file becomes as easy as follows:

  try
    while true do
      let line = input_line ic in
        Regexp.match line with
          "^\((\d\d):(\d\d):(\d\d)\)\[(.*?)\] (.*)$" 
           as hour : int, min: int, sec : int, name, line ->
             let time = hour * 3600 + min * 60 + sec in
             ...
        | "^# (.*)$" as meta_info ->
             ...
        | _ -> ()
    done
  with End_of_file -> ()

This short code parses both line in format like
  "(00:34:32) [foobar] something" and "# some meta info"
and binds appropriate data into variables which can be used inside "...".
Compare the code above with an equivalent without using syntax extension.

Regexp/OCaml is downloadable from the web location
http://www.yl.is.s.u-tokyo.ac.jp/~oiwa/caml/ .

In addition to the main macro called pa_regexp_match, the package also
contains two tiny macros:

 1) pa_pragma changes an option for loaded camlp4 macros inside source code.
 2) pa_once provides "once" construct which evaluates any expression
    only once per execution (pa_regexp_match uses this internally).

Any comments will be greatly appreciated.

-- 
Yutaka Oiwa              Yonezawa Lab., Dept. of Computer Science,
      Graduate School of Information Sci. & Tech., Univ. of Tokyo.
      <oi...@yl...>, <yu...@oi...>
PGP fingerprint = C9 8D 5C B8 86 ED D8 07  EA 59 34 D8 F4 65 53 61

-------------------
To unsubscribe, mail cam...@in... Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Ocaml-lib-devel] Advancements

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

Oh, and I have more to contribute.  Basic status of my work at this point:

- bitset is being rewritten into bitarray, with the new features suggested 
by the change in name.  The goal is to produce something you could write 
elliptic curve cryptosystems in at least semi-efficiently.

- I have the beginings of what I'm currently calling an XString library,
which stores a string as an unbalanced tree of of substrings.  The big
advantage here is that concats are O(1), and then converting the XString
to a normal string is O(n).  In-place modification won't be supported.  
This will be usefull in constructing strings by concating substrings 
efficiently.  Sort of like Java's StringBuffer.

- A resizable array module- rather like Java's Vector or Python's List.

Life has been rather hectic of late for me- sorry I haven't been more 
timely on this.  But this weekend is looking dull, so I should be able to 
spend some serious coding time.

Longer term, libraries I'd like (and that I think would be usefull) would 
include:

- A BLAS-like library.  Although I need to think about this design some- 
OOLALA has shown me that BLAS itself is probably not the best overall 
library design.

- A regular expressions library- although I think this might already be 
out there.

- An elliptic curve crypto systems library.

Brian


On Thu, 20 Mar 2003, Nicolas Cannasse wrote:

> Hi,
> 
> I'm quite disapointed about the current silence on this list... After a
> short period of time where everyone really wanted to contribute, there seems
> to be no more will to do so (excepted Brian modules post), but perhaps most
> of people there only wanted to give advices about how to name such module
> and not really develop and implement the ExtLib :))
> For people who are still interested, I'll keep on gathering modules, and
> since we have a 3-days WeekEnd here in Japan starting tomorrow, I'll try to
> come on monday with a first ExtLib version implementing all suggestions
> being made, so we can put it on some CVS.
> 
> Nicolas Cannasse
> 
> 
> 
> -------------------------------------------------------
> This SF.net email is sponsored by: Tablet PC.  
> Does your code think in ink? You could win a Tablet PC. 
> Get a free Tablet PC hat just for playing. What are you waiting for? 
> http://ads.sourceforge.net/cgi-bin/redirect.pl?micr5043en
> _______________________________________________
> ocaml-lib-devel mailing list
> oca...@li...
> https://lists.sourceforge.net/lists/listinfo/ocaml-lib-devel
> 

Re: [Ocaml-lib-devel] New Library 1: XList

[fva <fv...@ts...>]

Brian Hurt wrote:

>On Mon, 17 Mar 2003, fva wrote:
>
>  
>
>> Rather than using ExtList which gives the impression of an extension of 
>>the signature (maybe there is, I haven't looked into the code, really) 
>>    
>>
>
>The only extension to the list signature I made was that I added a
>fold_right'.  The only way I could think of to implement fold_right in a
>tail-recursive manner was to first reverse the list, and then traverse it.  
>My experiments with append show that reversing the list is about 30%
>slower than simply doing a non-tail recursion.  So I provided two
>functions- fold_right which reverse the list (works correctly for all
>lists, slower), and fold_right' which does non-tail-recursion (faster,
>doesn't work for all lists).
>
Uh? You mean to put both in or you're just asking advice as to what we 
think about it?

- If the former... I'd say one of them would never get used (probably) 
fold_right' because it is somewhat alien to the rest of the interfacing 
conventions.

- If the latter... I'd say keep the one that you think works best 
(perhaps the less easily programmable, so that people who are 
dissatisfied with the behaviour can code their own and use it instead). 
I think you should have the freedom to supply any of them: you're the 
contributing author.

Regards,

       Fran

Re: [Ocaml-lib-devel] Module Structure

[fva <fv...@ts...>]

Nicolas Cannasse wrote:

>Hi list,
>
>I have been thinking for some time on the module structure for ExtLib
>issues, and I think I found a quite reasonable comprise.
>Ok, first of all, we we talk there only about modules which are extending
>the StdLib ones, other "new" modules doesn't cause any problems.
>But for the Stdlib one - let's take the example of ExtList - there is some
>problems :
>
>- some people would like to use ExtList as a replacement of List
>
>For this first category of people, we can do the following :
>
>-- file extList.mli ---
>module List : sig ... end
>--- eof ---
>
>Like this theses people will only have to add an extra "open ExtList" in the
>beginning of their files and then they can use the List standard functions
>as well as the List extended ones within the same short and readable
>namespace : List.
>
>But !
>- this we're modifying the specification of some functions, people with
>existing running code would like to use only ExtList as an additionnal
>library of functions, without overriding the current Stdlib ones.
>
>Here's the answer :
>--- file extLib.mli ---
>module ExtList = ExtList.List
>--- eof ---
>
>So they only have to do an "open ExtLib" and then they can use extended
>functions under the ExtList namespace.
>
>Nicolas Cannasse
>
How was that going...?

Vote +1 for this proposal...

Regards,

       Fran

[Ocaml-lib-devel] mutable cyclic list

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

Hi,

If there is any interest in this module, I can clean it up, document and
so on. Now I'm dropping it here just for comments.

-- 
: Michal Moskal ::::: malekith/at/pld-linux.org :  GCS {C,UL}++++$ a? !tv
: PLD Linux ::::::: Wroclaw University, CS Dept :  {E-,w}-- {b++,e}>+++ h