[Camllist] "Nasty" functions and memory usage
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:  20010319 (15:27) 
From:  Alex Baretta <alex@b...> 
Subject:  Re: [Camllist] "Nasty" functions and memory usage 
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 2628: > 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 camllistrequest@inria.fr. Archives: http://caml.inria.fr