From mboxrd@z Thu Jan 1 00:00:00 1970 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 q470TNL4010126 for ; Mon, 7 May 2012 02:29:23 +0200 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: Ap0EAIwWp0+FBoIF/2dsb2JhbABEs3WCDAEBBAEnEwYDATUBAQMLCzQSVwYTG4duBKcRhDeFHokCAQaQPGOIZo0ckEKCeA X-IronPort-AV: E=Sophos;i="4.75,540,1330902000"; d="scan'208";a="142767636" Received: from rabbit.math.nagoya-u.ac.jp (HELO mailhost.math.nagoya-u.ac.jp) ([133.6.130.5]) by mail4-smtp-sop.national.inria.fr with ESMTP; 07 May 2012 02:29:17 +0200 Received: from mailhost.math.nagoya-u.ac.jp (localhost [127.0.0.1]) by mailhost.math.nagoya-u.ac.jp (Postfix) with ESMTP id 11B116291; Mon, 7 May 2012 09:29:14 +0900 (JST) Received: from mailhost.math.nagoya-u.ac.jp (camel-172.math.nagoya-u.ac.jp [172.16.254.4]) by mailhost.math.nagoya-u.ac.jp (Postfix) with ESMTP id B8E7539A2; Mon, 7 May 2012 09:29:13 +0900 (JST) DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=math.nagoya-u.ac.jp; h= subject:mime-version:content-type:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; s=alpha; bh=7kOXOJe92nm1yiSS1O4hFD7N+Rs=; b=iAdMqYYv5tKZPhGIPHKtoFio4/uB mzEuzHpom/6ZpxdWMOEBmoKXDxC03VmVoRXe341BYmmSs7hWLi6tuuKDAT+0maGd bu2VTHVVMoXsBBvONq80qlzUIxaXN+R/oeMnCPbqAK/gq1J9C/O9EJQh8qVBQXDC j/z3FJk9S54/kPI= DomainKey-Signature: a=rsa-sha1; h=Received:Subject:Mime-Version:Content-Type:From:In-Reply-To:Date:Cc:Content-Transfer-Encoding:Message-Id:References:To:X-Mailer; b=ffGFvB1XkAHK79g+68AHnElNWbr8+hFrzsFynRDqPR4B2FMX8a36wu1okwpI5+Zs9OpMSedTXegBroJiGsV0l3K28/nJy3lG9AzfOQ9hIVLzmHVZ2ozjreF8eQpaN6crtWvxNtabqwApzsUtXbMv4aeYUN9myqc1iv20vaeBUu0=; c=nofws; d=math.nagoya-u.ac.jp; q=dns; s=alpha Received: from tet.garrigue.jp (58x158x128x157.ap58.ftth.ucom.ne.jp [58.158.128.157]) by mailhost.math.nagoya-u.ac.jp (Postfix) with ESMTPSA id A94533999; Mon, 7 May 2012 09:29:12 +0900 (JST) Mime-Version: 1.0 (Apple Message framework v1084) Content-Type: text/plain; charset=us-ascii From: Jacques Garrigue In-Reply-To: <87aa1lcohv.fsf@frosties.localnet> Date: Mon, 7 May 2012 09:29:11 +0900 Cc: caml-list@inria.fr Message-Id: <345FFB0F-E4E0-43C5-864E-625E7AAAF940@math.nagoya-u.ac.jp> References: <87r4uykb09.fsf@frosties.localnet> <415387F7-557D-40C7-8F9E-E8CDC5603E3C@math.nagoya-u.ac.jp> <87aa1lcohv.fsf@frosties.localnet> To: Goswin von Brederlow X-Mailer: Apple Mail (2.1084) Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by walapai.inria.fr id q470TNL4010126 Subject: Re: [Caml-list] A shallow option type On 2012/05/07, at 0:34, Goswin von Brederlow wrote: > Jacques Garrigue writes: > >> Hi Goswin, >> >> Actually I remember discussing this issue with Xavier Leroy a long time ago, >> and we ended up concluding that this could be done in a clean way by using >> a bit pattern not yet used for ocaml values. >> >> Our idea was that rather than put some restriction on the shallowness of >> types (which is very hard to implement), one should just allow arbitrary nesting >> of option types, and represent the sequence "Some (Some (... ( Some None) ...))" >> as an integer. >> I think I even tried an implementation, but we then concluded that there >> was not enough demand to put it in the compiler. > > The advantage of providing it by the compiler would be to allow pattern > matching. And also being compatible with the default option type, and proper marshaling support. It's really a cost vs. usefulness discussion. I see no good solution for marshaling. It would be nice to be able to add hooks to the marshaler for handling pointers outside of the value area... >> However there is nothing wrong with providing it as a library. >> The basic idea is that you have only two kinds of values in ocaml: >> integers, which have their lower bit to 1, and pointers, which must >> all be multiples of 4 (on 32-bit architectures). >> So the pattern (v % 4) == 2 is not used. > > Actualy isn't (v % 4) == 2 an exception? > > caml/callback.h: > #define Make_exception_result(v) ((v) | 2) > #define Is_exception_result(v) (((v) & 3) == 2) > #define Extract_exception(v) ((v) & ~3) > > So returning an Sopt.none in a callback would be taken as exception. :) Well-spotted. It seems that this use of the second bit was added after our discussion. But the fundamental idea is just to represent "Some (Some (... ( Some None) ...))" by a special collection of pointers, and this can be done in other ways, like allocating a region in the C heap, or using a non-allocatable region (you only need to now that these pointers will never be used). Here is a version using Bigarray to allocate such a protected region: 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 is_sopt : 'a t -> bool val depth : 'a t -> int end = struct type 'a t = int let area = Bigarray.(Array1.create int32 c_layout 1024) let none : int = Obj.obj (Obj.field (Obj.repr area) 1) let is_none x = (x = none) let is_sopt x = (x >= none) && (x < none + 2048) let some (x : 'a) : 'a t = let y : 'a t = Obj.magic x in if is_sopt y then if y = none + 2047 then invalid_arg "Sopt.some" else y + 2 else y let arg (x : 'a t) : 'a = if is_sopt x then if is_none x then invalid_arg "Sopt.arg" else Obj.magic (x-2) else Obj.magic x let depth x = if is_sopt x then ((x - none) lor 1) lsr 1 else -1 end > The implementation relies on specific aspect of the compiler to > construct those values. I would give it a 99% chance to fail with an > llvm backend for ocaml for example. Using C stubs that directly > manipulate the bits seems a better approach. > > For example nothing says x + 2 can't be implemented as > > value add(value x, value y) { > return (x & ~1) + y; > } > > as opposed to > > value add(value x, value y) { > return x + y - 1; > } Actually I'm confident that any backend using a data representation compatible with ocaml is going to implement addition the same way. There are two reasons: * most processors can add two registers and a small constant in one operation * there is no reason to depart from the already published approach But of course there is nothing wrong to writing those as C primitives if you are already writing stubs. You might just want to add the "noalloc" qualifier to make calling them more efficient. Jacques