Re: [Caml-list] Functor implementation

[Xavier Leroy <xavier.leroy@inria.fr>]

> Hi all, I was curious as to how ocaml implements functors and
> finding no help with google, I thought I could ask on the
> list.

Basically, a structure is compiled like a record, and a functor like a
function.

> After giving it a little thought I was thinking they might be
> implemented as follows:
> [...]
> How far off is Ocaml's way and is the performance comparable?

It's pretty close, and the performance is comparable.
Here is pseudocode that is closest to the actual compiled code:

 type 'a orderedtype = {
     compare: 'a -> 'a -> comparison
 }

 type 'a setmodule = {
     empty: 'a tree;
     insert: 'a tree -> 'a -> 'a tree;
     member: 'a tree -> 'a -> bool;
 }

 let make compare =

   let node l v r = Node(l, v, r) in
   let single v = Node(Empty, v, Empty) in

   let rec insert t a =
       match t with
           Empty -> single a
         | Node(l, v, r) -> match (compare.compare a v) with
               LT -> node (insert l a) v r
             | EQ -> t
             | GT -> node l v (insert r a) in

  (* other struct members similar *)

  {
     empty = Empty;
     insert = insert;
     member = member
  }

  let mymodule =
    make { compare = fun x y -> ... }


Now, let me warn you about the following code:

> let compare x y =
    let cmp = x - y in if cmp > 0 then GT else if cmp < 0 then LT else EQ

which doesn't work if x and y are sufficiently far apart
(e.g. x = max_int and y = min_int).

- Xavier Leroy

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners