Array interface question

Array interface question

[Brian Rogoff]

Hi,
	Why is there no creation function which does not take a default
value for filling the array? When building abstractions like dynamic
arrays or (SRC Modula-3 style) Sequences on top of Arrays I'm forced to 
provide a fill value even though the abstraction really doesn't call for 
one. Is this a simple omission, or is there some compelling reason for 
leaving this out?

-- Brian
 

Re: Array interface question

[Pierre Weis]

> 	Why is there no creation function which does not take a default
> value for filling the array?
[...]
> 
> -- Brian

This is due to the coexistance in Caml of polymorphism and mutable
values. The system would be unsafe if we were able to allocate
polymorphic mutable values (those mutable values could be filled
afterwards with values of unrelated types, and hence would break the
homogeneous sequence nature of arrays, and then may be read back with
types unrelated to their proper types).

Hope this helps,

Pierre Weis

INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://cristal.inria.fr/~weis/

Re: Array interface question

[Brian Rogoff]

On Fri, 22 Jan 1999, Pierre Weis wrote:
> > 	Why is there no creation function which does not take a default
> > value for filling the array?
> [...]
> > 
> > -- Brian
> 
> This is due to the coexistance in Caml of polymorphism and mutable
> values. The system would be unsafe if we were able to allocate
> polymorphic mutable values (those mutable values could be filled
> afterwards with values of unrelated types, and hence would break the
> homogeneous sequence nature of arrays, and then may be read back with
> types unrelated to their proper types).

Thanks, I should have known that was it.

Given this, I'd like to request a Sequence abstraction like the one in 
SRC Modula-3, which permits addition and removal at either end, and random
access, in expected constant time, for inclusion in the stdlib. I have 
several times had need of such an ADT (usually I only need to add at one
end and have random access), most recently in a BDD library I'm writing.
Any suggestions on how to write Sequence elegantly (and safely of course ;-)
in OCaml as it stands?

Probably having a default value for dynamic arrays is not so bad...

-- Brian

Re: Array interface question

[Anton Moscal]

On Fri, 22 Jan 1999, Pierre Weis wrote:

> > 	Why is there no creation function which does not take a default
> > value for filling the array?
> [...]
> > 
> > -- Brian
> 
> This is due to the coexistance in Caml of polymorphism and mutable
> values. The system would be unsafe if we were able to allocate
> polymorphic mutable values (those mutable values could be filled
> afterwards with values of unrelated types, and hence would break the
> homogeneous sequence nature of arrays, and then may be read back with
> types unrelated to their proper types).

Other reason for immediate arrays initialization is garbage collection, I
think.

Anton

Re: Array interface question

[David Monniaux]

On Fri, 22 Jan 1999, Pierre Weis wrote:

> > 	Why is there no creation function which does not take a default
> > value for filling the array?

Perhaps the solution is to have an improved implementation of the 'a
option type, where a NULL pointer would mean "None" and anything else
would be the element of type 'a.

Is there anything wrong with this approach? [except that it could break
some interfaced C code that relies on NULL pointers in "private" types..]

Regards,
D. Monniaux

Re: Array interface question

[Jerome Vouillon]

On Sat, Jan 23, 1999 at 11:57:28AM +0100, David Monniaux wrote:
> On Fri, 22 Jan 1999, Pierre Weis wrote:
> 
> > > 	Why is there no creation function which does not take a default
> > > value for filling the array?
> 
> Perhaps the solution is to have an improved implementation of the 'a
> option type, where a NULL pointer would mean "None" and anything else
> would be the element of type 'a.
> 
> Is there anything wrong with this approach? [except that it could break
> some interfaced C code that relies on NULL pointers in "private" types..]

The problem is that you need to be able to differentiate None from
Some None, Some (Some None), ...

-- Jerome

Re: Array interface question

[Pierre Weis]

> > Perhaps the solution is to have an improved implementation of the 'a
> > option type, where a NULL pointer would mean "None" and anything else
> > would be the element of type 'a.
> > 
> > Is there anything wrong with this approach? [except that it could break
> > some interfaced C code that relies on NULL pointers in "private" types..]
> 
> The problem is that you need to be able to differentiate None from
> Some None, Some (Some None), ...
> 
> -- Jerome

Exactly, even if nobody thinks to write this kind of strange
expressions, the option datatype is powerful enough to represent
arithmetic.

On the other hand, the problem of NULL pointers is easy to solve: we
just need a unique object to represent None, and this object has not
to be NULL, and in fact it cannot be 0, if we want to differentiate
None and Some 0 (Some being supposedly omitted). (An Atom in terms
of the Caml memory manager would perfect for this purpose).

The Some (Some ...) problem could be solve if option where not only a
datatype but ... an option of record field names (or even constructor
names), analoguous to the mutable annotation for record fields. You
could write

type person = { option name : string; option age : int};;

This way the None values can be introduced by the compiler when
building a value of type person, for each optional field with no
associated value. The Some constructors would be ommitted from the
representation as desired. At pattern matching you may write None as a
valid pattern for an optional field, and write the normal expected
pattern otherwise (no need to write a Some constructor). In addition,
you could set once an optional field with some value, the compiler
checking that this field is indeed None before setting the new value.

This is absolutely similar to the mutable annotation that was
introduced to avoid the systematic insertion of reference cells in
records, hence leading to mutable values without extra indirections
(and more intuitive typings in my mind). The introduction of the
notion of ``option'' at the langage level would lead to the same
advantages: more compact representation of values, more natural
handling of the notion, especially for construction of values, pattern
matching, and typing.

Pierre Weis

INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://cristal.inria.fr/~weis/

Re: Array interface question

[Brian Rogoff]

On Sun, 24 Jan 1999, Pierre Weis wrote:

> The Some (Some ...) problem could be solve if option where not only a
> datatype but ... an option of record field names (or even constructor
> names), analoguous to the mutable annotation for record fields. You
> could write
> 
> type person = { option name : string; option age : int};;
> 
> This way the None values can be introduced by the compiler when
> building a value of type person, for each optional field with no
> associated value. The Some constructors would be ommitted from the
> representation as desired. At pattern matching you may write None as a
> valid pattern for an optional field, and write the normal expected
> pattern otherwise (no need to write a Some constructor). In addition,
> you could set once an optional field with some value, the compiler
> checking that this field is indeed None before setting the new value.

This is an interesting idea, but I fear that for my particular problem
this is not helpful. For example, lets say I want to represent a Sequence
abstraction as an array of arrays, where the top level array grows by
doubling when an addition forces a resizing, and the data blocks are
of fixed size. Currently, I represent the indirection array as a 
"'a array option Dynarray.t", and all of my access functions contain a 
pattern match to extract the data array. Its this needless wrapping and 
unwrapping  (forced since I don't want to have "fill" elements in the
interface) of the array elements that I don't like, though I don't know
of any better option.  

-- Brian (yes, the pun is intentional)

Size of arrays

[Juan Jose Garcia Ripoll]

Hi

I've noticed that OCaml imposes a very small upper limit in the size of
arrays: 8Mb or so, I think. Can this limit be modified somehow?

[Please do not answer that I'm not choosing the right data structure
because I work in numerical analysis and here we need large vectors of
at least floating point type -- complex would also be nice, though]

Regards
	Juanjo

Re: Size of arrays

[Pierre Weis]

> I've noticed that OCaml imposes a very small upper limit in the size of
> arrays: 8Mb or so, I think. Can this limit be modified somehow?
[...]

No there is no way to modify this limit: it is wired into the data
structures representation algorithm. However, this limit is machine
dependant, and very high on a 64bits machine
(18014398509481983).

Anyway, it is not difficult to design an ADT that gives you large
arrays on a 32 bits machine:

(* Module Bvect of big vectors (length up-to max_int).
   Access and assigment 2 times slowlier than regular arrays.
   Iteration is as efficient as Array.iter.  *)
(* bvect.mli *)
type 'a bvect;;
val make : int -> 'a -> 'a bvect;;
val length : 'a bvect -> int;;
val item : 'a bvect -> int -> 'a;;
val assign : 'a bvect -> int -> 'a -> unit;;
....

(* bvect.ml *)
type 'a bvect = 'a array * 'a array;;

let make len init =
 if len <= Sys.max_array_length then (Array.make len init, [| |])
 else (Array.make Sys.max_array_length init,
       Array.make (len - Sys.max_array_length) init);;

let length (v1, v2) = Array.length v1 + Array.length v2;;

let item (v1, v2) i =
 if i < Sys.max_array_length then v1.(i)
 else v2.(i - Sys.max_array_length);;

let assign (v1, v2) i item =
 if i < Sys.max_array_length then v1.(i) <- item
 else v2.(i - Sys.max_array_length) <- item;;

let iter f (v1, v2) = Array.iter f v1; Array.iter f v2;;

(* Omitted, sub_vect, map_vect, ..., as in module Array. *)

Hope this helps,

Pierre Weis

INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://cristal.inria.fr/~weis/