On 2012/05/08, at 2:08, Goswin von Brederlow <goswin-...@web.de> wrote:
> Jacques Garrigue <garri...@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 -- Caml-list mailing list. Subscription management and archives: https://sympa-roc.inria.fr/wws/info/caml-list Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs