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 JAA08969; Tue, 14 May 2002 09:10:55 +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 JAA08965 for ; Tue, 14 May 2002 09:10:54 +0200 (MET DST) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id g4E7Arn20053 for ; Tue, 14 May 2002 09:10:53 +0200 (MET DST) Received: (from fpottier@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id JAA08961 for caml-list@inria.fr; Tue, 14 May 2002 09:10:53 +0200 (MET DST) Date: Tue, 14 May 2002 09:10:53 +0200 From: Francois Pottier To: caml-list@inria.fr Subject: Re: [Caml-list] Turning off type-checking Message-ID: <20020514091053.A8883@pauillac.inria.fr> Reply-To: Francois.Pottier@inria.fr References: <706871B20764CD449DB0E8E3D81C4D4301EE6D43@opus.cs.cornell.edu> Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit X-Mailer: Mutt 1.0i In-Reply-To: <706871B20764CD449DB0E8E3D81C4D4301EE6D43@opus.cs.cornell.edu>; from jgm@CS.Cornell.EDU on Mon, May 13, 2002 at 11:10:23PM -0400 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk > Well, type-checking ML involves more than term unification -- the > worst case complexity is something truly horrible (EXP-time). > Having said this, for most programs, the worst-case complexity > rarely, if ever arises in "natural" code. (I've not run into > it...) The worst-case complexity is obtained by nesting `let' bindings on the left side, i.e. let x1 = let x2 = let x3 = ... Do you generate such code, Markus? > So, I'd actually be surprised if there was any significant speedup > obtained by eliminating the type-inference from the compilation > path. O'Caml's type inference algorithm is sub-optimal for at least one reason: it performs the occurs check at every unification step, instead of delaying it until the current `let' binding is exited. This causes it to have (theoretical) quadratic complexity, instead of linear, in the case where `let' bindings aren't left-nested. However, in practice, this has never turned out to be a problem. Markus, do the sub-expressions in your programs have huge types? -- François Pottier Francois.Pottier@inria.fr http://pauillac.inria.fr/~fpottier/ ------------------- 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