Re: [Caml-list] A shallow option type

[Jacques Garrigue <garrigue@math.nagoya-u.ac.jp>]

On 2012/05/07, at 0:34, Goswin von Brederlow wrote:

> Jacques Garrigue <garrigue@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