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 NAA02245; Tue, 17 Jun 2003 13:10:19 +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 NAA32306 for ; Tue, 17 Jun 2003 13:10:18 +0200 (MET DST) Received: from post.bourget.univ-savoie.fr (post.bourget.univ-savoie.fr [193.48.120.73]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id h5HBAHH26391 for ; Tue, 17 Jun 2003 13:10:17 +0200 (MET DST) Received: from univ-savoie.fr (d85.lama.univ-savoie.fr [193.48.123.85]) by post.bourget.univ-savoie.fr (8.12.3/jtpda-5.4) with ESMTP id h5HBABNp021096 ; Tue, 17 Jun 2003 13:10:11 +0200 Message-ID: <3EEEF722.3030208@univ-savoie.fr> Date: Tue, 17 Jun 2003 13:10:26 +0200 From: Christophe Raffalli User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.1) Gecko/20020826 X-Accept-Language: en-us, en MIME-Version: 1.0 CC: Jacques Garrigue , brian.hurt@qlogic.com, caml-list@inria.fr Subject: Re: [Caml-list] Type safe affectation ? References: X-Enigmail-Version: 0.65.2.0 X-Enigmail-Supports: pgp-inline, pgp-mime Content-Type: multipart/signed; micalg=pgp-sha1; protocol="application/pgp-signature"; boundary="------------enig052C4B0484F46BE51913C500" X-Spam: no; 0.00; raffalli:01 univ-savoie:01 caml-list:01 openpgp:01 2440:01 3156:01 morrisett:01 high-level:01 tail-call:01 perry:99 cheng:99 implemented:01 model:01 subtyping:01 flags:01 X-Attachments: type="application/pgp-signature" Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk This is an OpenPGP/MIME signed message (RFC 2440 and 3156) --------------enig052C4B0484F46BE51913C500 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 8bit Gregory Morrisett wrote: >>The problem is that holes at the type level are a difficult feature to >>offer: they require linear types in the compiler. As an >>optimization, it is a rather high-level one, and maybe not so >>easy to know when it will apply. > > > Perhaps, but it's easy for a compiler to offer support > for "tail-allocation" (i.e., a tail-call except for a > constructor application) which is what you need for > a tail-recursive append or map. Perry Cheng implemented it in > the TIL compiler in about a week if memory serves and > it was a tremendous improvement in performance without > any magic. > > Yasuhiko Minamide wrote a paper on how to model this > well (I think it appeared in ICFP). The approach used > in our Typed Assembly Language paper is yet another > approach based on a simple subtyping trick with initialization > flags. It didn't require linear types at all and > instead of implicit subtyping, you could accomplish > the same thing with an explicit (type-safe) up-cast. > > So, all in all, it's quite possible to have the compiler > implement this optimization for the common case of > tail-allocation, and if you think it's more generally > applicable, then you could move to something like TAL's > initialization flags (though I would prefer the former > option.) Does this also solve the construction of structure with loop ? (the other case were affectation is needed ? I say that because it is a similar problem and can be seen as a failuer of the compiler to type some expressions like this (the compiler says : This kind of expression is not allowed as right-hand side of `let rec' for add_Greater and add_Less module Var = struct type t = var let compare = (-) end module MapVar = Map.Make(Var) type env = value MapVar.t and value = | Def of closure | Less of closure | Greater of closure and closure = typ * env let add_Greater v t e = let rec va = Greater(t, e') and e' = MapVar.add v va e in e' let add_Less v t e = let rec va = Greater(t, e') and e' = MapVar.add v va e in e' The same fonction is easy to write with affectation ... so it should be possible to compile it ? -- Christophe Raffalli Université de Savoie Batiment Le Chablais, bureau 21 73376 Le Bourget-du-Lac Cedex tél: (33) 4 79 75 81 03 fax: (33) 4 79 75 87 42 mail: Christophe.Raffalli@univ-savoie.fr www: http://www.lama.univ-savoie.fr/~RAFFALLI --------------------------------------------- IMPORTANT: this mail is signed using PGP/MIME At least Enigmail/Mozilla, mutt or evolution can check this signature --------------------------------------------- --------------enig052C4B0484F46BE51913C500 Content-Type: application/pgp-signature -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.0.7 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQE+7vciSQDyWB/+xBwRAl65AJ9E/QwJgVNnsVO6GEA6j7flmAT0FACgwF6f IRe8oj8xZzsd+pYElXjd3IU= =KnaS -----END PGP SIGNATURE----- --------------enig052C4B0484F46BE51913C500-- ------------------- 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