> 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