From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: * X-Spam-Status: No, score=1.0 required=5.0 tests=AWL,DNS_FROM_RFC_POST autolearn=disabled version=3.1.3 Received: from discorde.inria.fr (discorde.inria.fr [192.93.2.38]) by yquem.inria.fr (Postfix) with ESMTP id 0FDDABC6B for ; Thu, 5 Apr 2007 00:55:35 +0200 (CEST) Received: from rwcrmhc11.comcast.net (rwcrmhc11.comcast.net [216.148.227.151]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id l34MtXfb018221 for ; Thu, 5 Apr 2007 00:55:34 +0200 Received: from 192.168.1.101 (c-66-41-169-138.hsd1.mn.comcast.net[66.41.169.138]) by comcast.net (rwcrmhc11) with SMTP id <20070404225521m11005ge5ee>; Wed, 4 Apr 2007 22:55:32 +0000 Subject: Re: [Caml-list] Generators/iterators and lazy evaluation? From: Bill Wood To: Erik de Castro Lopo Cc: caml-list@yquem.inria.fr In-Reply-To: <20070405071652.bcb9be46.mle+ocaml@mega-nerd.com> References: <46140EB5.50700@inria.fr> <20070405071652.bcb9be46.mle+ocaml@mega-nerd.com> Content-Type: text/plain Date: Wed, 04 Apr 2007 17:55:20 -0500 Message-Id: <1175727321.21360.9.camel@localhost> Mime-Version: 1.0 X-Mailer: Evolution 2.0.1-1mdk Content-Transfer-Encoding: 7bit X-Miltered: at discorde with ID 46142CE5.002 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; frisch:01 iterator:01 runtime:01 threads:01 computations:01 stack:01 python's:01 python's:01 complained:01 allocating:01 high-level:01 rewrote:01 iterator:01 statically:01 allocating:01 On Thu, 2007-04-05 at 07:16 +1000, Erik de Castro Lopo wrote: > Alain Frisch wrote: > > > I think you cannot implement this notion of iterator without some kind > > of control flow operator (at runtime) or some code rearrangement (at > > compile time). The point is that you must mainting several active > > "threads" of computations, including their own stack. > > Alain, I think you may have misunderstood Python's yeild operator. > Typically the original poster's pow2 generators would be used like: > > for p = pow2 (10): > print p > > but I really don't see how laziness Python's generators actually > provide any benefit for this problem over the more obvious Python > solution to this which is: > > for i = range (10): > p = 2 ^ i > print p > I think the motivation was to treat the memory issues with the "range" function, which is most often used to implement "for" loops (range(N) returns the list [0, ..., N-1]). People complained about a control structure allocating memory linear in the depth of the loop, so "xrange" was created; it generates the items of the list one at a time rather than all at once. Further releases of Python generalized to iterators and generators. It does make a difference too. Somebody wrote a Sieve of Eratosthenes using Python's high-level list operators; it blew up on fairly small arguments. I wrote a straight-forward Sieve using indexing into a static array, with reasonable time performance. I then rewrote it using an iterator and got analogous time performance (roughly a factor of 2 penalty), without statically allocating the entire sieve first.