Re: [Caml-list] A shallow option type

[Goswin von Brederlow <goswin-v-b@web.de>]

Jacques Garrigue <garrigue@math.nagoya-u.ac.jp> writes:

> Sorry for all these mails.
> Looks like I don't think well when I'm sleepy...
>
> Anyway, I think that at last I have a reasonable (much simpler) solution.
> This still uses sopt_tag (i.e. lazy_tag-1), but this time the argument is
> the number of "some" constructors, so there is no extra cost for marshaling.
> The only values on which Sopt.some is not the identity are those with a
> single argument, which is additionally represented by an integer between 0 and last.
> Moreover, even if for some reason you build such a value using a real sum
> type, you still have Sopt.arg (Sopt.some v) = v, the only change being a loss
> of sharing (which is anyway not guaranteed by the ocaml specification).
>
> Jacques
>
> module Sopt : sig
>  type +'a t
>  val none : 'a t
>  val some : 'a -> 'a t
>  val is_none : 'a t -> bool
>  val arg  : 'a t -> 'a
>  val depth : 'a t -> int
> end = struct
>  type 'a t = Obj.t
>  let sopt_tag = Obj.lazy_tag - 1
>  let none = Obj.new_block sopt_tag 1
>  let last = 255
>  let area = Array.create (last+1) none
>  let () =
>    Obj.set_field none 0 (Obj.repr 0);
>    for i = 1 to last do
>      let stub = Obj.new_block sopt_tag 1 in
>      Obj.set_field stub 0 (Obj.repr i);
>      area.(i) <- stub
>    done
>  let is_none x = (x = none)
>  let is_sopt x =
>    Obj.is_block x && Obj.tag x = sopt_tag && Obj.size x = 1 &&
>    let i = Obj.obj (Obj.field x 0) in i >= 0 && i <= last
>  let depth x =
>    let x = Obj.repr x in
>    if is_sopt x then Obj.obj (Obj.field x 0) else -1
>  let some (x : 'a) : 'a t =
>    let i = depth x in
>    if i < 0 then Obj.magic x else
>    if i = last then invalid_arg "Sopt.some" else Obj.obj area.(i+1)
>  let arg (x : 'a t) : 'a =
>    let i = depth x in
>    if i < 0 then Obj.magic x else
>    if i = 0 then invalid_arg "Sopt.arg" else Obj.obj area.(i-1)
> end

What exactly is the point of specially tagged blocks? All you need is a
bunch of pointers to values to encode the depth. You can use the value
pointed at to encode the index the pointer is at and physical equality
to ensure it actualy is one of your pointers:

let area = Array.init (last+1) (fun i -> ref i)

let is_sopt x =
  let r = Obj.repr x in
  Obj.is_block r && Obj.size x = 1 && Obj.is_int (Obj.field r 0) &&
  let i = Obj.obj (Obj.field r 0) in
  i >= 0 && i <= last && Obj.obj r == area.(i)

# is_sopt 1;;
- : bool = false
# is_sopt area.(5);;
- : bool = true
# is_sopt (ref 5);;
- : bool = false

MfG
        Goswin