From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id 42478BBBB for ; Sun, 22 Jan 2006 13:22:53 +0100 (CET) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id k0MCMq20029161 for ; Sun, 22 Jan 2006 13:22:52 +0100 Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id NAA28948 for ; Sun, 22 Jan 2006 13:22:51 +0100 (MET) Received: from haka.fmf.uni-lj.si (haka.fmf.uni-lj.si [193.2.67.18]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id k0MCMoGM031425 (version=TLSv1/SSLv3 cipher=AES256-SHA bits=256 verify=NO) for ; Sun, 22 Jan 2006 13:22:51 +0100 Received: from bsn-77-186-71.dsl.siol.net ([193.77.186.71] helo=[192.168.1.101]) by haka.fmf.uni-lj.si with esmtpa (Exim 4.50) id 1F0eF1-0000Ig-Hg; Sun, 22 Jan 2006 13:22:49 +0100 Message-ID: <43D37955.90408@andrej.com> Date: Sun, 22 Jan 2006 13:23:49 +0100 From: Andrej Bauer Reply-To: Andrej.Bauer@andrej.com User-Agent: Debian Thunderbird 1.0.7 (X11/20051017) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Caml list Cc: skaller References: <43C51C33.2000206@andrej.com> <1137031853.3681.138.camel@rosella> <43C661AF.2080404@andrej.com> <1137102848.3681.268.camel@rosella> <1137163342.3681.533.camel@rosella> <1137594157.8943.106.camel@rosella> <20060120004948.GA2490@coruscant.stwing.upenn.edu> <43D0B413.1060806@andrej.com> <20060120185911.GA22920@coruscant.stwing.upenn.edu> <1137790790.15137.39.camel@rosella> <43D27F18.9030102@andrej.com> <1137899816.885.45.camel@rosella> In-Reply-To: <1137899816.885.45.camel@rosella> Content-Type: text/plain; charset=ISO-8859-2 Content-Transfer-Encoding: 7bit X-SA-Exim-Connect-IP: 193.77.186.71 X-SA-Exim-Mail-From: Andrej.Bauer@andrej.com Subject: Re: [Caml-list] Coinductive semantics X-SA-Exim-Version: 4.2 (built Thu, 03 Mar 2005 10:44:12 +0100) X-SA-Exim-Scanned: Yes (on haka.fmf.uni-lj.si) X-Miltered: at concorde with ID 43D3791C.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at nez-perce with ID 43D3791A.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; andrej:01 andrej:01 caml-list:01 coinductive:01 semantics:01 arrays:01 arrays:01 notation:01 pairs:01 compilers:01 compiler:01 compiler:01 run-time:01 run-time:01 arbitrarily:01 X-Spam-Checker-Version: SpamAssassin 3.0.3 (2005-04-27) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.0.3 skaller wrote: > basically I don't know enough theory to turn the purely > algebraic finite array types -- fairly useless in practice -- > into variable length arrays required in practice. > [By variable I mean the length is an immutable dynamic type, > not that you can change the length of the array] If I understand you correctly, you have types [0], [1], [2], [3], ..., one for each natural number 0, 1, 2, ... (to avoid confusion I want to distinguish notationally between number n and type [n] here, even if Felix does not do it). Let me call [n] "the type of indices of arrays of length n". We may think of [n] as the set {0,1,2,...,n-1}. You know how to deal with the type [n]->t, which is an array of length n containing t's. Now you would like to "make n variable (dynamic)". This sounds like a dependent type to me, i.e, you want not just a bunch of types [0], [1], [2], ... but rather a _type constructor_ [-], which maps from int to types. You may define it in dependent type theory (I am going to use set-theretic notation so that I don't confuse everyone): [n] = {k : int | 0 <= k and k < n} In set theory, this is interpreted as follows: an index of an array of length n is an integer k. This integer must be between 0 and n. In type theory, this is interpreted as follows: an index of an array of length n is a _pair_ (k,p) where k is an integer and p is a proof of the fact k is between 0 and n. The type of arrays you're talking about is a dependent sum 't array = sum (n:int) [n]->'t An element of this type (according to type theory) consists of a pair (n,a) where n is an integer and a is a map [n]->'t, i.e., an array of length n. Elements of such an array are indexed by pairs (k,p). If everyone believed in type theory, compilers would be easy to write. Every time a programmer wanted to address an element of an array, he would provide not just the index k but also the proof p that k is a valid index. Compiler would just have to check that p is a valid proof (easy when p is a formal proof). But programmers don't want to do that. If we care about soundness and safety, we are left with two possibilities: either the compiler or the run-time environment must supply the missing proof p. For the run-time environment this is easy, because k and n are always instantiated to particular constants and we may simply check that 0<=k