Announcement: automatically resizing arrays

Announcement: automatically resizing arrays

[Markus Mottl]

Hello,

as promised last week, I have just released my implementation of
automatically resizing contiguous memory (= arrays, strings, etc...).

Here a part of the README explaining the advantages of using it:

  * Fast constant-time access to indexed elements (e.g. in arrays and
    strings) is often a prerequisite for short execution times of
    programs.

    Still, operations like adding and/or removing elements to/from the
    end of such datastructures are often needed.  Unfortunately, having
    both properties at the same time sometimes requires reallocating
    this contiguous part of memory.

    This module does not eliminate this problem, but hides the process
    of reallocation from the user, i.e. it happens automatically.

    Thus, the user is liberated from this bug-attracting (e.g. index
    errors) task.

  * This library allows the user to parameterize allocation strategies at
    runtime. This is a very important feature, because it is impossible
    for any allocation algorithm to perform optimally without having
    knowledge about the user program.

    For example, the programmer might know that a consecutive series
    of operations will alternately add and remove large amounts of
    elements. In such a case it would be wise to keep a high reserve
    of available slots in the datastructure, because otherwise it will
    resize very often during this procedure which requires a significant
    amount of time.

    By raising a corresponding threshold in appropriate places at runtime,
    the programmer can fine-tune the behaviour of e.g. his buffers for
    optimal performance and set this parameter back later to save memory.

  * Because reallocation strategies themselves may be quite complicated,
    it was also a design goal to have the user supply his own ones
    (if required).

    By using functors the user can parameterize these datastructures
    with his own reallocation strategies, giving him even more control
    over how and when reallocations are triggered.

  * It is possible that the user wants to add support for additional
    low-level implementations that require reallocations (e.g. bit-strings
    have not yet been added to this distribution). Even in this case it
    is fairly easy to create new modules by using functors.

  * The library implements a large interface of functions, all of which
    are completely independent of the reallocation strategy and the
    low-level implementation.

    All the interfaces of the corresponding low-level implementations
    of datastructures (e.g. array, string) are fully supported and have
    been extended with further functionality. There is even a new buffer
    module which can be used in every context of the standard one.

  * OCaml makes a distinction between unboxed and boxed arrays. If
    the type of an array is "int" or "float", the representation will
    be unboxed in most cases.

    To benefit from these much faster representations there are
    specialized versions of automatically resizing arrays in the
    distribution.

The examples in the distribution are fairly short - the documentation
could surely be better (is there something like a perfect
documentation??). If you have questions, comments, etc., feel free to
contact me...

Best regards,
Markus Mottl

-- 
Markus Mottl, mottl@miss.wu-wien.ac.at, http://miss.wu-wien.ac.at/~mottl

Undefined labels

[skaller]

I am getting an undefined label error. 
I know why. I do not know how to fix the problem:

	(Unix.fstat argument).st_kind

Here, the function returns a structure, st_kind
is a label of that structure, but it is not known
in the calling module. Is there a syntax for this?
Using 'open Unix' is unacceptable.

-- 
John Skaller, mailto:skaller@maxtal.com.au
1/10 Toxteth Rd Glebe NSW 2037 Australia
homepage: http://www.maxtal.com.au/~skaller
downloads: http://www.triode.net.au/~skaller

Re: Undefined labels

[Jean-Christophe Filliatre]

> I am getting an undefined label error. 
> I know why. I do not know how to fix the problem:
> 
> 	(Unix.fstat argument).st_kind
> 
> Here, the function returns a structure, st_kind
> is a label of that structure, but it is not known
> in the calling module. Is there a syntax for this?
> Using 'open Unix' is unacceptable.

	(Unix.fstat argument).Unix.st_kind

Best regards,
-- 
Jean-Christophe FILLIATRE
  mailto:Jean-Christophe.Filliatre@lri.fr
  http://www.lri.fr/~filliatr

Undefined labels

[William Chesters]

skaller writes:
 > I am getting an undefined label error. 
 > I know why. I do not know how to fix the problem:
 > 
 > 	(Unix.fstat argument).st_kind

You want (Unix.fstat argument).Unix.st_kind

(Is this in the docs?  I found it once when looking at the camlp4 parser.)

This is definitely one of those cases where type inference doesn't
seem such a good idea ... it feels so like K&R C, sometimes having to
fall back on giving labels little prefixes ... I wonder if some kind
of inference would be possible, not going the whole way to the
tag-based system used for classes, but at least something that
maintains a set of hypotheses consistent with the labels used in
connection with a value, which could then be narrowed down
contextually.

Re: Undefined labels

[Christian RINDERKNECHT]

Hello,

> 	(Unix.fstat argument).st_kind
> 
> Here, the function returns a structure, st_kind
> is a label of that structure, but it is not known
> in the calling module. Is there a syntax for this?

Yes:

        (Unix.fstat argument).Unix.st_kind
                              ^^^^
because the compiler doesn't know in what module to look-up for label
[st_kind]. 


> Using 'open Unix' is unacceptable.

I also never use the "open" feature, but the consequence is, when using
nested records, I must qualify all the labels (as in your example),
and the code becomes unreadable.

I recently started using classes in order to avoid this practical
problem, since methods are in the scope of their object, not of the
module embedding their class.

But this doesn't work if the library you are using is not
object-oriented, of course:)

Best regards,

-- 

Christian

-----------------------------------------------------------------------
Christian Rinderknecht                     Phone +33 (0)1 60 76 44 43
Institut National des Télécommunications   Fax   +33 (0)1 60 76 47 11
Département Logiciels Réseaux (LOR)        WWW
9, Rue Charles Fourier, F-91011 Évry Cedex

Re: Undefined labels

[Jean-Francois Monin]

>         (Unix.fstat argument).Unix.st_kind
>                               ^^^^
> > Using 'open Unix' is unacceptable.
> 
> I also never use the "open" feature, but the consequence is, when using
> nested records, I must qualify all the labels (as in your example),
> and the code becomes unreadable.

Not so unreadable if you declare

module U=Unix

This can be local to a (group of) function(s), e.g.

let f,g =
   let module U = Unix in
   let f argument = (U.fstat argument).U.st_kind in
   let g = 5
   in f,g;;

  Jean-Francois

Re: Undefined labels

[skaller]

Thanks to everyone who answered this question for me.
[Quite a lot of replies!]

-- 
John Skaller, mailto:skaller@maxtal.com.au
1/10 Toxteth Rd Glebe NSW 2037 Australia
homepage: http://www.maxtal.com.au/~skaller
downloads: http://www.triode.net.au/~skaller

Re: Undefined labels

[Markus Mottl]

> I'm not familiar with the parser too much, but perhaps something like:
> 
> open (bleep, bloop, SubMod) Module;;

I think there is not really a big difference to:

  let bleep = Module.bleep
  let bloop = Module.bloop
  module SubMod = Module.SubMod

The typing effort is nearly neglectible, especially if you use a convenient
editor. It also may make things clearer. In fact, your proposal would be
ambiguous, because it is not clear whether "bleep" is a function or a type
(different name spaces!).

> There probably should also be a way to open all of the constructors of
> a type.

Now this would not be so bad an idea, because often such types may have
quite many constructors and in general you need all of them at once.

Unfortunately, e.g.

  module M = struct type t = A | B end

  type u = M.t

will not do this for you.

What problems could arise if the semantics of "type" were changed to allow
"importing" constructors like this? - It looks pretty harmless at first
sight and would fit to the style of abbreviations used above...

Regards,
Markus Mottl

-- 
Markus Mottl, mottl@miss.wu-wien.ac.at, http://miss.wu-wien.ac.at/~mottl

RE: Undefined labels

[Anton Moscal]

On Mon, 15 Nov 1999, Brian Rogoff wrote:

> > This is the standard example for why we need a local open in the language.
> > 
> > -Manuel
> 
> Let me second that motion. Coming from Ada, I always wondered why OCaml
> doesn't allow you to restrict the scope of open, instead of putting it 
> always at module level.

This construction can be easy simulated by `let module' construction:

let open M in E 
 =>
let module _TEMP = struct 
   open M;
   let __RES = E
end
in __RES

I implement this conversion for my own use by camlp4 as syntax extension
(with other local declarations: let type, let exception, etc.)

Anton

RE: Undefined labels

[David Brown]

Gerard Huet writes:
 > open is a facility that is convenient to the programmer because the code is
 > uncluttered with long explicit names, but it is of course a source of bugs.
 > The addition of a new binding in a module may change drastically the
 > semantics of modules which open it, in a way that stays unnoticed if types
 > match. 

One feature I like of Python and Erlang is a selective import.  It is
possible to specify only the items that you would like imported from a
module.  If you use the selective open, the open declaration itself
states which symbols come from that module.  Since the scope is
explicit, it makes it easy to tell where something is coming from.

I'm not familiar with the parser too much, but perhaps something like:

open (bleep, bloop, SubMod) Module;;

There probably should also be a way to open all of the constructors of
a type.

Dave Brown

RE: Undefined labels

[Gerard Huet]

At 16:30 15/11/99 -0800, Brian Rogoff wrote:
>On Fri, 12 Nov 1999, Manuel Fahndrich wrote:
>> 
>> This is the standard example for why we need a local open in the language.
>> 
>> -Manuel
>
>Let me second that motion. Coming from Ada, I always wondered why OCaml
>doesn't allow you to restrict the scope of open, instead of putting it 
>always at module level.
>
>-- Brian
>

open is a facility that is convenient to the programmer because the code is
uncluttered with long explicit names, but it is of course a source of bugs.
The addition of a new binding in a module may change drastically the
semantics of modules which open it, in a way that stays unnoticed if types
match. 
Things would get worse with a local open. This reminds me of the old days
of Pascal, with the dreadful "with" construction which opened an implicit
scope (the field names of the corresponding record declaration) at this
point in the code. This made the scope structure dependent of the type
analysis in a global way, and thus broke an essential phase distinction for
the compiler. This was the source of unending headaches. For instance, it
was a cause of unnecessary complications in terminal recursion removal,
since the names of the formal parameters of procedures could be hidden at
the point of call by an intermediate with. 

GH

RE: Undefined labels

[Brian Rogoff]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: TEXT/PLAIN; charset=X-UNKNOWN, Size: 1861 bytes --]

On Fri, 12 Nov 1999, Manuel Fahndrich wrote:
>
> This is the standard example for why we need a local open in the language.
>
> -Manuel

Let me second that motion. Coming from Ada, I always wondered why OCaml
doesn't allow you to restrict the scope of open, instead of putting it
always at module level.

-- Brian

>
>
> -----Original Message-----
> From: Christian RINDERKNECHT [mailto:rinderkn@hugo.int-evry.fr]
> Sent: Friday, November 12, 1999 8:48 AM
> To: caml-redistribution@pauillac.inria.fr
> Cc: caml-list@inria.fr
> Subject: Re: Undefined labels
>
>
> Hello,
>
> > 	(Unix.fstat argument).st_kind
> >
> > Here, the function returns a structure, st_kind
> > is a label of that structure, but it is not known
> > in the calling module. Is there a syntax for this?
>
> Yes:
>
>         (Unix.fstat argument).Unix.st_kind
>                               ^^^^
> because the compiler doesn't know in what module to look-up for label
> [st_kind].
>
>
> > Using 'open Unix' is unacceptable.
>
> I also never use the "open" feature, but the consequence is, when using
> nested records, I must qualify all the labels (as in your example),
> and the code becomes unreadable.
>
> I recently started using classes in order to avoid this practical
> problem, since methods are in the scope of their object, not of the
> module embedding their class.
>
> But this doesn't work if the library you are using is not
> object-oriented, of course:)
>
> Best regards,
>
> --
>
> Christian
>
> -----------------------------------------------------------------------
> Christian Rinderknecht                     Phone +33 (0)1 60 76 44 43
> Institut National des Télécommunications   Fax   +33 (0)1 60 76 47 11
> Département Logiciels Réseaux (LOR)        WWW
> 9, Rue Charles Fourier, F-91011 Évry Cedex
>

RE: Undefined labels

[Manuel Fahndrich]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 1484 bytes --]


This is the standard example for why we need a local open in the language.

-Manuel


-----Original Message-----
From: Christian RINDERKNECHT [mailto:rinderkn@hugo.int-evry.fr]
Sent: Friday, November 12, 1999 8:48 AM
To: caml-redistribution@pauillac.inria.fr
Cc: caml-list@inria.fr
Subject: Re: Undefined labels


Hello,

> 	(Unix.fstat argument).st_kind
> 
> Here, the function returns a structure, st_kind
> is a label of that structure, but it is not known
> in the calling module. Is there a syntax for this?

Yes:

        (Unix.fstat argument).Unix.st_kind
                              ^^^^
because the compiler doesn't know in what module to look-up for label
[st_kind]. 


> Using 'open Unix' is unacceptable.

I also never use the "open" feature, but the consequence is, when using
nested records, I must qualify all the labels (as in your example),
and the code becomes unreadable.

I recently started using classes in order to avoid this practical
problem, since methods are in the scope of their object, not of the
module embedding their class.

But this doesn't work if the library you are using is not
object-oriented, of course:)

Best regards,

-- 

Christian

-----------------------------------------------------------------------
Christian Rinderknecht                     Phone +33 (0)1 60 76 44 43
Institut National des Télécommunications   Fax   +33 (0)1 60 76 47 11
Département Logiciels Réseaux (LOR)        WWW
9, Rue Charles Fourier, F-91011 Évry Cedex