On 2012/05/07, at 0:34, Goswin von Brederlow wrote:
> Jacques Garrigue <garri...@math.nagoya-u.ac.jp> 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
--
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
