Abstract data structure type

Learning
8

I like this style because of the encapsulation, the OOP style, the ability to design algorithms working with any stack implementation. However, I never saw something like this anywhere and I wonder why.

If you’re going to do OO, you might as well use OCaml’s built-in support:

type 'a stack = < (* abstract imperative stack *)
  empty : bool;
  push : 'a -> unit;
  pop : 'a
>

let stack_of_array t = (* t is the array that will contain stack elements *)
  let n = ref 0 in
  object (_ : _ stack)
    method empty = (!n = 0)
    method push e =
      if !n >= Array.length t 
      then failwith "Full stack"
      else (t.(!n) <- e; incr n)
    method pop =
      if !n = 0
      then failwith "Empty stack"
      else (decr n; t.(!n))
  end

let () = (* example *)
  let s = stack_of_array (Array.make 100 0) in
  s#push 4;
  Printf.printf "> %d\n" s#pop

That avoids duplicating the vtable for every stack (you could also make n a mutable field instead of allocating a separate ref cell for it).

The main advantage of using modules is that it’s easier to see what the program does. In the OO style (yours or mine), every time you see a stack being used you have to work out all the places it could have come from to know what code will be called. In the functor style, the implementation is usually chosen once, statically, at the top of the file, not once per stack. So I think it’s better to avoid objects whenever you don’t need that flexibility.

3 Likes