Browse thread
RE: [Caml-list] Turning off type-checking
[
Home
]
[ Index:
by date
|
by threads
]
[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: | 2002-05-14 (07:10) |
From: | Francois Pottier <francois.pottier@i...> |
Subject: | Re: [Caml-list] Turning off type-checking |
> 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