From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@sympa.inria.fr Delivered-To: caml-list@sympa.inria.fr Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by sympa.inria.fr (Postfix) with ESMTPS id B6C467F712 for ; Sat, 25 Jan 2014 21:59:58 +0100 (CET) Received-SPF: Neutral (mail2-smtp-roc.national.inria.fr: domain of simon.cruanes.2007@m4x.org does not assert whether or not 129.104.30.34 is permitted sender) identity=pra; client-ip=129.104.30.34; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="SRS0=rk4S=W7=m4x.org=simon.cruanes.2007@bounces.m4x.org"; x-sender="simon.cruanes.2007@m4x.org"; x-conformance=sidf_compatible; x-record-type="spf2.0" Received-SPF: Pass (mail2-smtp-roc.national.inria.fr: domain of SRS0=rk4S=W7=m4x.org=simon.cruanes.2007@bounces.m4x.org designates 129.104.30.34 as permitted sender) identity=mailfrom; client-ip=129.104.30.34; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="SRS0=rk4S=W7=m4x.org=simon.cruanes.2007@bounces.m4x.org"; x-sender="SRS0=rk4S=W7=m4x.org=simon.cruanes.2007@bounces.m4x.org"; x-conformance=sidf_compatible; x-record-type="spf2.0" Received-SPF: Pass (mail2-smtp-roc.national.inria.fr: domain of postmaster@mx1.polytechnique.org designates 129.104.30.34 as permitted sender) identity=helo; client-ip=129.104.30.34; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="SRS0=rk4S=W7=m4x.org=simon.cruanes.2007@bounces.m4x.org"; x-sender="postmaster@mx1.polytechnique.org"; x-conformance=sidf_compatible; x-record-type="v=spf1" X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AuIDAIQk5FKBaB4inGdsb2JhbABag0SDU7lKAwKBCRYOAQEBAQEIFAk8giUBAQEEIwQLAVYLBBQqAgIhNgYBEhuHVgMRBAmrdpcTDYVWEwSMd4ISgnqBSQSWO4FshkeGFohv X-IPAS-Result: AuIDAIQk5FKBaB4inGdsb2JhbABag0SDU7lKAwKBCRYOAQEBAQEIFAk8giUBAQEEIwQLAVYLBBQqAgIhNgYBEhuHVgMRBAmrdpcTDYVWEwSMd4ISgnqBSQSWO4FshkeGFohv X-IronPort-AV: E=Sophos;i="4.95,720,1384297200"; d="scan'208,217";a="54842112" Received: from mx1.polytechnique.org ([129.104.30.34]) by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/ADH-AES256-SHA; 25 Jan 2014 21:59:58 +0100 Received: from [192.168.0.13] (ip-96.net-81-220-126.rev.numericable.fr [81.220.126.96]) (using TLSv1 with cipher ECDHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by ssl.polytechnique.org (Postfix) with ESMTPSA id 478C1140C55C4; Sat, 25 Jan 2014 21:59:57 +0100 (CET) User-Agent: K-9 Mail for Android In-Reply-To: <52E41A3A.3020307@gmail.com> References: <52E404ED.80302@gmail.com> <52E41A3A.3020307@gmail.com> MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="----WZ034J3YSXI0PUD507DD1IQX23IIWI" Content-Transfer-Encoding: 8bit From: Simon Cruanes Date: Sat, 25 Jan 2014 21:59:54 +0100 To: Nicolas Braud-Santoni ,Nicolas Braud-Santoni ,caml-list@inria.fr Message-ID: <390ca919-b5e6-4f87-8587-da7218932e57@email.android.com> X-AV-Checked: ClamAV using ClamSMTP at svoboda.polytechnique.org (Sat Jan 25 21:59:57 2014 +0100 (CET)) X-Spam-Flag: No, tests=bogofilter, spamicity=0.000103, queueID=9F8FF140C55CF X-Org-Mail: simon.cruanes.2007@polytechnique.org Subject: Re: [Caml-list] ocaml{c,opt} choked ------WZ034J3YSXI0PUD507DD1IQX23IIWI Content-Transfer-Encoding: 8bit Content-Type: text/plain; charset=UTF-8 I'm not sure that it's the source of the issue, but is this exponential behaviour caused by the unification algorithm? Nicolas Braud-Santoni a écrit : >On 25/01/2014 19:39, Matej Kosik wrote: >> Hi, >> >> I am using ocaml 4.01.0. >> >> I have noticed the following strange behavior: >> [...] >> >> I would like to ask: is this is a known phenomenon? >> ------------------------------------------------------------------- >> The context: >> >> I have started to apply the advice given here: >> https://sympa.inria.fr/sympa/arc/caml-list/2013-11/msg00207.html >> That way I've got terms with which ocaml{c,opt} struggles. > >Hi, > >It is a well-known problem that type inference is exponential-type[0] >This worst-case behaviour is triggered when you have deeply nested -> >in >the types. > >For an example, consider : > >let f x y = y x x in >let g x = f (f x) in >let h x = g (g x) in >let h x = h (h x) in >let h x = h (h x) in >h;; (* This actually causes a stack overflow *) > > >Unfortunately, there isn't (as far as I know) a silver bullet. >Avoiding deep nesting of combinators mights be a solution, though. >I usually also helps with readability. > >Regards, >Nicolas > >[0] under ETH, probably, but I don't currently remember. -- Simon ------WZ034J3YSXI0PUD507DD1IQX23IIWI Content-Type: text/html; charset=utf-8 Content-Transfer-Encoding: 8bit I'm not sure that it's the source of the issue, but is this exponential behaviour caused by the unification algorithm?

Nicolas Braud-Santoni <nicolas.braudsantoni@gmail.com> a écrit :
On 25/01/2014 19:39, Matej Kosik wrote:
 Hi,

 I am using ocaml 4.01.0.

 I have noticed the following strange behavior:
 [...]

 I would like to ask: is this is a known phenomenon?

 The context:

 I have started to apply the advice given here:
 https://sympa.inria.fr/sympa/arc/caml-list/2013-11/msg00207.html
 That way I've got terms with which ocaml{c,opt} struggles.

Hi,

It is a well-known problem that type inference is exponential-type[0]
This worst-case behaviour is triggered when you have deeply nested -> in
the types.

For an example, consider :

let f x y = y x x in
let g x = f (f x) in
let h x = g (g x) in
let h x = h (h x) in
let h x = h (h x) in
h;; (* This actually causes a stack overflow *)


Unfortunately, there isn't (as far as I know) a silver bullet.
Avoiding deep nesting of combinators mights be a solution, though.
I usually also helps with readability.

Regards,
Nicolas

[0] under ETH, probably, but I don't currently remember.


--
Simon ------WZ034J3YSXI0PUD507DD1IQX23IIWI--