Re: [Caml-list] A shallow option type

[Jacques Garrigue <jacques.garrigue@gmail.com>]

On 2012/05/08, at 2:08, Goswin von Brederlow <goswin-v-b@web.de> wrote:

> 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)

Marshaling.
Without the distinctive tag, there is no way to know that a value you receive
was a special one.
Without the marshaling requirement there are indeed many solutions.
Also I should be honest, and point that my solution does interfere with some
values of tag sopt_tag. Namely, applying Sopt.some to the block
(sopt_tag, last) is going to fail whereas it might be representing a perfectly
safe value. But this looks like a very exceptional condition.
If you don't need marshaling, you can use your stronger criterion to avoid
any interference. Using a special tag still allows a faster test.

Jacques