From mboxrd@z Thu Jan 1 00:00:00 1970 X-Sympa-To: caml-list@inria.fr Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id q4807Ge9025181 for ; Tue, 8 May 2012 02:07:16 +0200 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AnECAEVjqE/RVda2imdsb2JhbAA7CaJrikSEVQKBGwgiAQEBCgkNBxIGI4IMAQEBAwESAhMZARsdAQMBCwYFRiMRAQUBHAYTGweHXQEDBgWcOgkDjCSCc4UVChknDRVCiHYBBQuLBIFDhDYEiGKbfj2EG4FHBQ X-IronPort-AV: E=Sophos;i="4.75,546,1330902000"; d="scan'208";a="142883933" Received: from mail-ob0-f182.google.com ([209.85.214.182]) by mail4-smtp-sop.national.inria.fr with ESMTP/TLS/RC4-SHA; 08 May 2012 02:07:11 +0200 Received: by obcni5 with SMTP id ni5so15356483obc.27 for ; Mon, 07 May 2012 17:07:09 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=references:from:in-reply-to:mime-version:date:message-id:subject:to :cc:content-type; bh=mRv69mD/eECnRc0whKIuj2Jo+rgXv004PEL7znNvsQg=; b=uxLOzBdAtiseDqsELfU6yNWhbU4igmwlhqrMdIwoeFfrpIvqejyy70Iti4pzzEiE1v ze2ttIESvu/sC/bfDFgNzUBxPi/k4ZbDiHvINhrE1YHziuTYUqTea3t286CEosJMKmL3 qIrkWmleyxXW0igtXZRjKFPfQNNn3k58OfS9V1myhgnBn0w9VXN/RP3QmLfrlCmVAq8p Njyz8hk7KwrvN7Au6bbvgYh1feuqmh5vWboZeei+fv6WJTWT5qgk9EnQW/RlcKjZ4xU+ BmABWoUx6O6In4Kr1Ix3g23Md1vjt0ubpgnW4HJrLEDchpzw6sVXI7S7Nzb42uAFRzI8 /9ig== Received: by 10.182.117.98 with SMTP id kd2mr24664778obb.4.1336435629782; Mon, 07 May 2012 17:07:09 -0700 (PDT) References: <87r4uykb09.fsf@frosties.localnet> <415387F7-557D-40C7-8F9E-E8CDC5603E3C@math.nagoya-u.ac.jp> <87aa1lcohv.fsf@frosties.localnet> <4A169BB4-3316-437A-9E73-FABEAEDB9D2F@math.nagoya-u.ac.jp> <87397bly1w.fsf@frosties.localnet> From: Jacques Garrigue In-Reply-To: <87397bly1w.fsf@frosties.localnet> Mime-Version: 1.0 (1.0) Date: Tue, 8 May 2012 09:07:13 +0900 Message-ID: <6468522386138480403@unknownmsgid> To: Goswin von Brederlow Cc: OCaML List Mailing Content-Type: text/plain; charset=ISO-8859-1 X-Validation-by: jacques.garrigue@gmail.com Subject: Re: [Caml-list] A shallow option type On 2012/05/08, at 2:08, Goswin von Brederlow wrote: > Jacques Garrigue 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