From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id QAA15678; Mon, 19 Mar 2001 16:27:12 +0100 (MET) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id QAA16271 for ; Mon, 19 Mar 2001 16:27:12 +0100 (MET) Received: from localhost.localdomain (s057.dhcp212-109.cybercable.fr [212.198.109.57]) by nez-perce.inria.fr (8.11.1/8.10.0) with ESMTP id f2JFRBP21758 for ; Mon, 19 Mar 2001 16:27:11 +0100 (MET) Received: from baretta.com (IDENT:alex@localhost.localdomain [127.0.0.1]) by localhost.localdomain (8.9.3/8.9.3) with ESMTP id QAA00855 for ; Mon, 19 Mar 2001 16:25:45 +0100 Message-ID: <3AB624F9.5B6C6680@baretta.com> Date: Mon, 19 Mar 2001 16:25:45 +0100 From: Alex Baretta X-Mailer: Mozilla 4.72 [en] (X11; U; Linux 2.2.14-5.0 i586) X-Accept-Language: it, en MIME-Version: 1.0 To: "caml-list@inria.fr" Subject: Re: [Caml-list] "Nasty" functions and memory usage References: <3AB2BF73.75CD2B03@baretta.com> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk 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