Re: [Caml-list] "Nasty" functions and memory usage

[Alex Baretta <alex@baretta.com>]

Hendrik Tews wrote:
> 
>    let f0 = function x,y -> x,y;;
>    let f1 = function x,y -> f1(f0 x, f0 y);;
>    let ...
>    let f5 = function x,y -> f5(f4 x, f4 y);;
> 
> Can you post the correct program? For this I get
> 
>     #   let f1 = function x,y -> f1(f0 x, f0 y);;
> 
>     Characters 26-28:
>     Unbound value f1
> 
> And if I insert let rec's f5 is typechecked in less than a
> second.
> 

That's right. I screwed up. 

let f0 = function x -> x,x;;
let f1 = function x,y -> f0 ( f0 x, f0 y);;
let f2 = function x,y -> f1 ( f1 x, f1 y);;
let f3 = function x,y -> f2 ( f2 x, f2 y);;
let f4 = function x,y -> f3 ( f3 x, f3 y);;
let f5 = function x,y -> f4 ( f4 x, f4 y);;

f0 doubles the size of the type of its argument. f1 doubles twice
the size (*4) of the type of its arguents. f2 multiplies by 4
twice (*16) the size of the type of its argument. f3 multiplies by
16 twice the size of the type of its argument (*256). f4
multiplies its arguments type size by 65536. f5 by 65536**2, which
is 4294967296, or 2**(2**5)). Basically, one sees immediately that
fn has space complexity = k*2**(2**n). A nice double exponential.
Find me a computer capable of f7, now... (3.4*10**38 times the
size of the argument)

Now, my question is, how come the memory usage of the Ocaml (3.00)
front end does not grow with time as it attempts to compute the
type of, say, f6?

Alex
-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr