* Array interface question @ 1999-01-22 19:10 Brian Rogoff 1999-01-22 19:21 ` Pierre Weis 0 siblings, 1 reply; 10+ messages in thread From: Brian Rogoff @ 1999-01-22 19:10 UTC (permalink / raw) To: caml-list 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: Array interface question 1999-01-22 19:10 Array interface question Brian Rogoff @ 1999-01-22 19:21 ` Pierre Weis 1999-01-22 20:05 ` Brian Rogoff ` (3 more replies) 0 siblings, 4 replies; 10+ messages in thread From: Pierre Weis @ 1999-01-22 19:21 UTC (permalink / raw) To: Brian Rogoff; +Cc: caml-list > 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/ ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: Array interface question 1999-01-22 19:21 ` Pierre Weis @ 1999-01-22 20:05 ` Brian Rogoff 1999-01-23 10:47 ` Anton Moscal ` (2 subsequent siblings) 3 siblings, 0 replies; 10+ messages in thread From: Brian Rogoff @ 1999-01-22 20:05 UTC (permalink / raw) To: caml-list 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: Array interface question 1999-01-22 19:21 ` Pierre Weis 1999-01-22 20:05 ` Brian Rogoff @ 1999-01-23 10:47 ` Anton Moscal 1999-01-23 10:57 ` David Monniaux 1999-01-23 14:00 ` Size of arrays Juan Jose Garcia Ripoll 3 siblings, 0 replies; 10+ messages in thread From: Anton Moscal @ 1999-01-23 10:47 UTC (permalink / raw) To: Pierre Weis; +Cc: Brian Rogoff, caml-list 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: Array interface question 1999-01-22 19:21 ` Pierre Weis 1999-01-22 20:05 ` Brian Rogoff 1999-01-23 10:47 ` Anton Moscal @ 1999-01-23 10:57 ` David Monniaux 1999-01-24 15:44 ` Jerome Vouillon 1999-01-23 14:00 ` Size of arrays Juan Jose Garcia Ripoll 3 siblings, 1 reply; 10+ messages in thread From: David Monniaux @ 1999-01-23 10:57 UTC (permalink / raw) To: Liste CAML 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: Array interface question 1999-01-23 10:57 ` David Monniaux @ 1999-01-24 15:44 ` Jerome Vouillon 1999-01-24 21:36 ` Pierre Weis 0 siblings, 1 reply; 10+ messages in thread From: Jerome Vouillon @ 1999-01-24 15:44 UTC (permalink / raw) To: David Monniaux, Liste CAML 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: Array interface question 1999-01-24 15:44 ` Jerome Vouillon @ 1999-01-24 21:36 ` Pierre Weis 1999-01-28 19:57 ` Brian Rogoff 0 siblings, 1 reply; 10+ messages in thread From: Pierre Weis @ 1999-01-24 21:36 UTC (permalink / raw) To: Jerome Vouillon; +Cc: caml-list > > 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/ ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: Array interface question 1999-01-24 21:36 ` Pierre Weis @ 1999-01-28 19:57 ` Brian Rogoff 0 siblings, 0 replies; 10+ messages in thread From: Brian Rogoff @ 1999-01-28 19:57 UTC (permalink / raw) To: caml-list 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) ^ permalink raw reply [flat|nested] 10+ messages in thread
* Size of arrays 1999-01-22 19:21 ` Pierre Weis ` (2 preceding siblings ...) 1999-01-23 10:57 ` David Monniaux @ 1999-01-23 14:00 ` Juan Jose Garcia Ripoll 1999-01-24 22:31 ` Pierre Weis 3 siblings, 1 reply; 10+ messages in thread From: Juan Jose Garcia Ripoll @ 1999-01-23 14:00 UTC (permalink / raw) To: caml-list 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: Size of arrays 1999-01-23 14:00 ` Size of arrays Juan Jose Garcia Ripoll @ 1999-01-24 22:31 ` Pierre Weis 0 siblings, 0 replies; 10+ messages in thread From: Pierre Weis @ 1999-01-24 22:31 UTC (permalink / raw) To: Juan Jose Garcia Ripoll; +Cc: caml-list > 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/ ^ permalink raw reply [flat|nested] 10+ messages in thread
end of thread, other threads:[~1999-01-28 20:01 UTC | newest] Thread overview: 10+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 1999-01-22 19:10 Array interface question Brian Rogoff 1999-01-22 19:21 ` Pierre Weis 1999-01-22 20:05 ` Brian Rogoff 1999-01-23 10:47 ` Anton Moscal 1999-01-23 10:57 ` David Monniaux 1999-01-24 15:44 ` Jerome Vouillon 1999-01-24 21:36 ` Pierre Weis 1999-01-28 19:57 ` Brian Rogoff 1999-01-23 14:00 ` Size of arrays Juan Jose Garcia Ripoll 1999-01-24 22:31 ` Pierre Weis
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).