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 DAA23437; Tue, 17 Jun 2003 03:00:10 +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 DAA23357 for ; Tue, 17 Jun 2003 03:00:09 +0200 (MET DST) Received: from exchfe1.cs.cornell.edu (exchfe1.cs.cornell.edu [128.84.97.27]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id h5H108H19845 for ; Tue, 17 Jun 2003 03:00:08 +0200 (MET DST) Received: from EXCHVS2.cs.cornell.edu ([128.84.97.24]) by exchfe1.cs.cornell.edu with Microsoft SMTPSVC(5.0.2195.5329); Mon, 16 Jun 2003 20:59:36 -0400 content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: quoted-printable X-MimeOLE: Produced By Microsoft Exchange V6.0.6375.0 Subject: RE: [Caml-list] Type safe affectation ? Date: Mon, 16 Jun 2003 20:59:36 -0400 Message-ID: Thread-Topic: [Caml-list] Type safe affectation ? Thread-Index: AcMzqIWkkZOET89USV2SGtWNbQlX2QAwmtfA From: "Gregory Morrisett" To: "Jacques Garrigue" , Cc: X-OriginalArrivalTime: 17 Jun 2003 00:59:36.0445 (UTC) FILETIME=[B8E1B2D0:01C3346B] X-Spam: no; 0.00; morrisett:01 cornell:01 caml-list:01 high-level:01 tail-call:01 perry:99 cheng:99 implemented:01 model:01 subtyping:01 flags:01 type-safe:01 -greg:01 compiler:01 implicit:02 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk >The problem is that holes at the type level are a difficult feature to >offer: they require linear types in the compiler. As an=20 >optimization, it is a rather high-level one, and maybe not so=20 >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. =20 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=20 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.) =20 -Greg ------------------- 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