From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <daniel.buenzli@erratique.ch>
X-Original-To: caml-list@sympa.inria.fr
Delivered-To: caml-list@sympa.inria.fr
Received: from mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82])
	by sympa.inria.fr (Postfix) with ESMTPS id C36917ED7A
	for <caml-list@sympa.inria.fr>; Sun, 26 Aug 2012 21:59:34 +0200 (CEST)
Received-SPF: None (mail1-smtp-roc.national.inria.fr: no sender
  authenticity information available from domain of
  daniel.buenzli@erratique.ch) identity=pra;
  client-ip=74.55.86.74;
  receiver=mail1-smtp-roc.national.inria.fr;
  envelope-from="daniel.buenzli@erratique.ch";
  x-sender="daniel.buenzli@erratique.ch";
  x-conformance=sidf_compatible
Received-SPF: None (mail1-smtp-roc.national.inria.fr: no sender
  authenticity information available from domain of
  daniel.buenzli@erratique.ch) identity=mailfrom;
  client-ip=74.55.86.74;
  receiver=mail1-smtp-roc.national.inria.fr;
  envelope-from="daniel.buenzli@erratique.ch";
  x-sender="daniel.buenzli@erratique.ch";
  x-conformance=sidf_compatible
Received-SPF: None (mail1-smtp-roc.national.inria.fr: no sender
  authenticity information available from domain of
  postmaster@smtp.webfaction.com) identity=helo;
  client-ip=74.55.86.74;
  receiver=mail1-smtp-roc.national.inria.fr;
  envelope-from="daniel.buenzli@erratique.ch";
  x-sender="postmaster@smtp.webfaction.com";
  x-conformance=sidf_compatible
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: AgcCAMJ/OlBKN1ZKm2dsb2JhbABFhgO1CgEBAQEBCAkUFCeCIAEBBAEjBFIFCwsaAiYCAkcQBhuHfwYEB6hYkhiBIYlnhX8yYAObHhONHg
X-IronPort-AV: E=Sophos;i="4.80,316,1344204000"; 
   d="scan'208";a="170858823"
Received: from mail6.webfaction.com (HELO smtp.webfaction.com) ([74.55.86.74])
  by mail1-smtp-roc.national.inria.fr with ESMTP; 26 Aug 2012 21:59:33 +0200
Received: from [192.168.0.103] (127-234.197-178.cust.bluewin.ch [178.197.234.127])
	by smtp.webfaction.com (Postfix) with ESMTP id B60C820FFEBC;
	Sun, 26 Aug 2012 14:59:30 -0500 (CDT)
Date: Sun, 26 Aug 2012 21:59:24 +0200
From: =?utf-8?Q?Daniel_B=C3=BCnzli?= <daniel.buenzli@erratique.ch>
To: oliver <oliver@first.in-berlin.de>
Cc: Gabriel Scherer <gabriel.scherer@gmail.com>, Hongbo Zhang
 <bobzhang1988@gmail.com>, Caml List <caml-list@inria.fr>
Message-ID: <AF136E3F79894EEE86D12D9E5CE13226@erratique.ch>
In-Reply-To: <20120826191020.GB1908@siouxsie>
References: <503A30A7.3030707@gmail.com>
 <CAPFanBFtypXBgv-vOZjPfk0hKeXnLJddkw0aKRNX6YV_3Uu2nA@mail.gmail.com>
 <20120826191020.GB1908@siouxsie>
X-Mailer: sparrow 1.6.3 (build 1172)
MIME-Version: 1.0
Content-Type: text/plain; charset="utf-8"
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline
Subject: Re: [Caml-list] How to profile compiler's performance

Le dimanche, 26 ao=C3=BBt 2012 =C3=A0 21:10, oliver a =C3=A9crit :
> Which are the sources of this behaviour?
Type inference can be exponential but is rarely so in practice.

> Is this documented somewhere?
A. J. Kfoury, J. Tiuryn, P. Urzyczyn. ML typability is Dexptime-complete. C=
AAP'90. 1990
http://dx.doi.org/10.1007/3-540-52590-4_50

Harry G. Mairson. Deciding ML typability is complete for deterministic expo=
nential time. POPL'90. 1990
http://dx.doi.org/10.1145/96709.96748

Example program, from Mairson, as found in Pierce's Types and Programming l=
anguages:

let f0 =3D fun x -> (x, x) in
let f1 =3D fun y -> f0 (f0 y) in
let f2 =3D fun y -> f1 (f1 y) in
let f3 =3D fun y -> f2 (f2 y) in
let f4 =3D fun y -> f3 (f3 y) in
let f5 =3D fun y -> f4 (f4 y) in
f5 (fun z -> z)
;;

(Start compilation and go make the coffee)

Best,

Daniel