From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <oleg@okmij.org>
X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr
X-Spam-Level: *
X-Spam-Status: No, score=1.6 required=5.0 tests=AWL,NO_REAL_NAME,SPF_FAIL 
	autolearn=disabled version=3.1.3
X-Original-To: caml-list@yquem.inria.fr
Delivered-To: caml-list@yquem.inria.fr
Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78])
	by yquem.inria.fr (Postfix) with ESMTP id 10960BB83
	for <caml-list@yquem.inria.fr>; Thu,  7 Sep 2006 11:52:16 +0200 (CEST)
Received: from selenite.metnet.navy.mil (selenite.metnet.navy.mil [192.16.167.32])
	by nez-perce.inria.fr (8.13.6/8.13.6) with ESMTP id k879q9Ef013168
	(version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=FAIL)
	for <caml-list@inria.fr>; Thu, 7 Sep 2006 11:52:15 +0200
Received: (qmail 3368 invoked by uid 107); 7 Sep 2006 09:52:06 -0000
Received: from vwmetnet.metnet.navy.mil (192.16.167.21)
  by selenite.metnet.navy.mil with SMTP; 7 Sep 2006 09:52:06 -0000
Received: from Adric.metnet.fnmoc.navy.mil ([10.100.105.102])
 by vwmetnet.metnet.navy.mil (NAVGW 2.5.2.9) with SMTP id M2006090710051009985
 ; Thu, 07 Sep 2006 10:05:10 GMT
Received: by Adric.metnet.fnmoc.navy.mil (Postfix, from userid 760)
	id 5EA15ABF9; Thu,  7 Sep 2006 02:48:51 -0700 (PDT)
To: jonathan.roewen@gmail.com
Cc: caml-list@inria.fr
In-reply-to: <ad8cfe7e0609052215y52c613b6r6208e43644421bc1@mail.gmail.com>
Subject: Re: [Caml-list] Eliminating array bounds check
Reply-To: oleg@pobox.com
Errors-To: oleg@okmij.org
From: oleg@pobox.com
Message-Id: <20060907094851.5EA15ABF9@Adric.metnet.fnmoc.navy.mil>
Date: Thu,  7 Sep 2006 02:48:51 -0700 (PDT)
X-Miltered: at nez-perce with ID 44FFEBC9.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)!
X-Spam: no; 0.00; oleg:01 val:01 val:01 ocaml:01 functors:01 functor:01 sml:01 crary:01 ocaml:01 sig:01 struct:01 foo:01 sig:01 struct:01 foo:01 


> > val test = let local structure A = Kernel(val a = ...)
> >               open A in ... end in ...
> >
>
> I don't understand what the 'generative' part means, but are modules
> defined inside a let binding equivalent to the above?

In OCaml, functors behave like pure functions: an application of a
functor to identical arguments yields structures with compatible
types. Not so in SML (with strong sealing):

	http://www.cs.cmu.edu/~crary/papers/2003/thoms/thoms.pdf
Please see Figs 6 and 7 in that paper.

Here's a sample demonstration:

In Ocaml:

module type S = sig type tt end;;
module SI : S = struct type tt = unit end;;

module Foo (X : S) : sig type t val v : t end
= struct type t = int let v = 1 end;;

let module M = struct
  module M1 = Foo(SI)
  let x = M1.v
  module M2 = Foo(SI)
  let y = M2.v
  let res = x == y
end in M.res
;;


In SML (poly/ML):

signature S = sig type tt end;
structure SI : S = struct type tt = unit end;

functor Foo (X : S) :> sig type t val v : t end
= struct type t = int val v = 1 end;

(* A function that takes two arguments of the same type *)
fun cmp (x:'t) (y:'t) = true;

local structure M1 = Foo(SI)  val x = M1.v 
      structure M2 = Foo(SI)  val y = M2.v 
in val t = cmp x  y end;

# Error:
Can't unify M1.t with M2.t (Different type constructors) Found near cmp(x)(y)


In retrospect, for bsearch application, either functor would have
sufficed. However, a generative functor seems cleaner (and, in a
higher-ranked emulation) more easily formalizable.