From mboxrd@z Thu Jan  1 00:00:00 1970
Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id PAA21391; Wed, 23 Jul 2003 15:01:40 +0200 (MET DST)
X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f
Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id PAA07308 for <caml-list@pauillac.inria.fr>; Wed, 23 Jul 2003 15:01:37 +0200 (MET DST)
Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35])
	by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id h6ND1Wf15688;
	Wed, 23 Jul 2003 15:01:32 +0200 (MET DST)
Received: (from xleroy@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id PAA20862; Wed, 23 Jul 2003 15:01:32 +0200 (MET DST)
Date: Wed, 23 Jul 2003 15:01:32 +0200
From: Xavier Leroy <xavier.leroy@inria.fr>
To: Chris Clearwater <chris@sharkzone.com>
Cc: caml-list@inria.fr
Subject: Re: [Caml-list] Functor implementation
Message-ID: <20030723150132.A30456@pauillac.inria.fr>
References: <20030723115644.GA28291@pyramid.twistedmatrix.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
X-Mailer: Mutt 1.0i
In-Reply-To: <20030723115644.GA28291@pyramid.twistedmatrix.com>; from chris@sharkzone.com on Wed, Jul 23, 2003 at 06:56:44AM -0500
X-Loop: caml-list@inria.fr
X-Spam: no; 0.00; caml-list:01 functor:01 functors:01 implemented:01 ocaml's:01 pseudocode:01 orderedtype:01 struct:01 implements:01 bool:01 ocaml:01 int:01 rec:01 node:02 match:02 
Sender: owner-caml-list@pauillac.inria.fr
Precedence: bulk

> 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