Re: [Caml-list] Eliminating array bounds check

[oleg@pobox.com]

> > 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.