English version
Accueil     À propos     Téléchargement     Ressources     Contactez-nous    

Ce site est rarement mis à jour. Pour les informations les plus récentes, rendez-vous sur le nouveau site OCaml à l'adresse ocaml.org.

Browse thread
RE: [Caml-list] Turning off type-checking
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ 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
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