6
\$\begingroup\$

One of the annoying things about OCaml arrays is that every cell has to be initialized when the array is first created.

I'm trying to implement an array in OCaml that distinguishes size (the current number of elements in the array) from capacity (the maximum size that the array can grow to).

At any given point in the array's lifetime, the "inhabited cells" must form a prefix of the array itself. In other words, you can't do something like:

1 2 UNINITIALIZED 3 4 UNINITIALIZED

The array also clears cell immediately once they've been popped so the application doesn't leak memory / hold references to stuff that "used to be in the array" but isn't anymore.

The array uses the last element as the size. The reason for this is three-fold: 1) creating an array only requires one call to Array.make 2) you don't need to do any arithmetic on the indices to access the elements in the underlying array and 3) it only requires chasing one pointer, not two, to get to the elements.

This code uses Obj.magic, but I try to confine it to places where it can be easily audited.

I'm not using Sys.opaque_identity from the Sys Module anywhere because I'm not actually using uninitialized memory anywhere ... I'm just using Obj.magic to subvert the type system and let me store integers in strategic places. I am curious what work is needed to flambda-proof this code though.

Anyway, here's the interface file uninit.mli:

type 'a t

val make : int -> 'a t

val size : 'a t -> int

val cap : 'a t -> int

val get_exn : 'a t -> int -> 'a

val get_opt : 'a t -> int -> 'a option

val set_exn : 'a t -> int -> 'a -> unit

val append_exn : 'a t -> 'a -> unit

val pop_exn : 'a t -> 'a

And the source file uninit.ml:

type 'a t = 'a array

(* set every value to the integer 0, regardless of the
 * type of the array.
 * note that the last zero is special, it is the current size
 * of the array. *)
let make : int -> 'a t =
    fun cap -> Array.make (cap + 1) (Obj.magic 0)

let cap : 'a . 'a t -> int =
    fun arr -> (-1) + Array.length arr

(* get the index of the size. This is the same as the capacity *)
let size_idx : 'a t -> int = cap

let size : 'a . 'a t -> int =
    fun arr -> (Obj.magic arr.(size_idx arr))

(* NOTE: incr_size is not checked and not safe *)
let incr_size : 'a . 'a t -> unit =
    fun arr ->
        let new_size : int = 1 + Obj.magic arr.(size_idx arr) in
        arr.(size_idx arr) <- (Obj.magic new_size)

(* NOTE: decr_size is not checked and not safe *)
let decr_size : 'a . 'a t -> unit =
    fun arr ->
        let new_size : int = -1 + Obj.magic arr.(size_idx arr) in
        arr.(size_idx arr) <- (Obj.magic new_size)

let get_exn : 'a . 'a t -> int -> 'a =
    fun arr idx ->
        if idx < size arr then arr.(idx) else raise (Invalid_argument "out of bounds")

let get_opt : 'a . 'a t -> int -> 'a option =
    fun arr idx ->
        if idx < size arr then Some arr.(idx) else None

let set_exn : 'a . 'a t -> int -> 'a -> unit =
    fun arr idx v ->
        if idx < size arr then arr.(idx) <- v else raise (Invalid_argument "out of bounds")

let append_exn : 'a . 'a t -> 'a -> unit =
    fun arr v ->
        let s = size arr in
        let c = cap arr in
        if s = c then
            failwith "cannot extend array! size = capacity"
        else
            (* put the new item one after the last item, increment
             * the size by 1 *)
            (arr.(s) <- v; incr_size arr)

let pop_exn : 'a . 'a t -> 'a =
    fun arr ->
        let s = size arr in
        if size arr = 0 then
            failwith "cannot pop from empty array"
        else
            let item = arr.(-1 + s) in
            (* shrink the array, re-zero the discarded element *)
            (decr_size arr; arr.(-1 + s) <- (Obj.magic 0); item)
\$\endgroup\$
  • \$\begingroup\$ Have you looked at weak arrays? This seems to provide a solution to your initial complaint (initializing every element.) Plus, you don't have to worry about Obj.magic issues. caml.inria.fr/pub/docs/manual-ocaml/libref/Weak.html \$\endgroup\$ – RichN May 31 '18 at 19:30
  • \$\begingroup\$ @RichN unfortunately, weak references do not keep their items alive, so the semantics is really different from an ordinary array. \$\endgroup\$ – Gregory Nisbet Jun 1 '18 at 16:11
  • \$\begingroup\$ You're right. I missed that one important detail. \$\endgroup\$ – RichN Jun 1 '18 at 18:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.