[Caml-list] ocaml{c,opt} choked

[Caml-list] ocaml{c,opt} choked

[Matej Kosik]

Hi,

I am using ocaml 4.01.0.

I have noticed the following strange behavior:

When I try to compile this fragment:
(irrelevant parts of the original program were removed)

  let a b = b []
  let c _ _ d = d []
  let _ = a c "" c "" c "" c "" c "" c "" c "" c "" c "" c "" c ""
            c "" c "" c "" c "" c "" c "" c "" c "" c "" c "" c ""

it takes 11 seconds to complete.

This fragment.

  let a b = b []
  let c _ _ d = d []
  let _ = a c "" c "" c "" c "" c "" c "" c "" c "" c "" c "" c ""
            c "" c "" c "" c "" c "" c "" c "" c "" c "" c "" c ""
            c ""

compiles in 22 seconds.

This fragment:

  let a b = b []
  let c _ _ d = d []
  let _ = a c "" c "" c "" c "" c "" c "" c "" c "" c "" c "" c ""
            c "" c "" c "" c "" c "" c "" c "" c "" c "" c "" c ""
            c "" c ""

compiles in 44 seconds.

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.

Re: [Caml-list] ocaml{c,opt} choked

[Nicolas Braud-Santoni]

[-- Attachment #1: Type: text/plain, Size: 1085 bytes --]

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.


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

Re: [Caml-list] ocaml{c,opt} choked

[Simon Cruanes]

[-- Attachment #1: Type: text/plain, Size: 1281 bytes --]

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

[-- Attachment #2: Type: text/html, Size: 1849 bytes --]