From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <Alain.Frisch@inria.fr>
X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr
X-Spam-Level: 
X-Spam-Status: No, score=0.0 required=5.0 tests=none 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 835B6BB83
	for <caml-list@yquem.inria.fr>; Mon,  4 Sep 2006 09:42:06 +0200 (CEST)
Received: from smtp5-g19.free.fr (smtp5-g19.free.fr [212.27.42.35])
	by nez-perce.inria.fr (8.13.6/8.13.6) with ESMTP id k847g6NS003485
	for <caml-list@inria.fr>; Mon, 4 Sep 2006 09:42:06 +0200
Received: from [192.168.0.1] (rke75-3-82-229-183-156.fbx.proxad.net [82.229.183.156])
	by smtp5-g19.free.fr (Postfix) with ESMTP id D942427492;
	Mon,  4 Sep 2006 09:42:05 +0200 (CEST)
Message-ID: <44FBD8C8.6000307@inria.fr>
Date: Mon, 04 Sep 2006 09:42:00 +0200
From: Alain Frisch <Alain.Frisch@inria.fr>
User-Agent: Thunderbird 1.5.0.5 (X11/20060812)
MIME-Version: 1.0
To: oleg@pobox.com
Cc: caml-list@inria.fr
Subject: Re: [Caml-list] Eliminating array bounds check
References: <20060904010002.9A553AC00@Adric.metnet.fnmoc.navy.mil> <44FBD432.8030602@inria.fr>
In-Reply-To: <44FBD432.8030602@inria.fr>
X-Enigmail-Version: 0.94.0.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
X-Miltered: at nez-perce with ID 44FBD8CE.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)!
X-Spam: no; 0.00; frisch:01 frisch:01 functor:01 functor:01 invariants:01 sig:01 val:01 work-around:01 sig:01 val:01 struct:01 run-time:01 arrays:01 unnamed:98 assert:01 

Alain Frisch wrote:
> What about making GenT a functor and passing it unnamed structures as
> arguments? (Ok, you must then trust the client not to apply GenT with
> named structures.)

Actually, GenT should be a functor anyway, since the abstract types in
the resulting structure must encode invariants which depends on the
(length of the) array. Unfortunaly, you cannot make a polymorphic
functor such as:

  module GenT(A : sig val a : 'a array end) ...

As a work-around, you can take only the length of the array as an argument:

  module TrustedKernel(L: sig val len: int end) : sig
      type 'a barray
      type bindex
      val unbi : bindex -> int

      type bindexL
      type bindexH
      ...
  end = struct
      let brand a =
         assert(Array.length a = L.len);
         (a,0,L.len - 1)
  end

On the one hand, this adds one run-time check, but on the other hand it
makes the abstract index types depend only on the length (so the trusted
kernel could be used in algorithms which work with several arrays of the
same size simultaneously).


-- Alain