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=0.0 required=5.0 tests=none 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 8A2F6BC0A for ; Thu, 5 Apr 2007 04:49:49 +0200 (CEST) Received: from ipmail02.adl2.internode.on.net (ipmail02.adl2.internode.on.net [203.16.214.141]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id l352nkKu024820 for ; Thu, 5 Apr 2007 04:49:48 +0200 X-IronPort-AV: E=Sophos;i="4.14,373,1170595800"; d="scan'208";a="106539371" Received: from ppp36-111.lns2.syd6.internode.on.net (HELO [192.168.1.201]) ([59.167.36.111]) by ipmail02.adl2.internode.on.net with ESMTP; 05 Apr 2007 12:19:44 +0930 Subject: Re: [Caml-list] Generators/iterators and lazy evaluation? From: skaller 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: Thu, 05 Apr 2007 12:49:39 +1000 Message-Id: <1175741379.6481.24.camel@rosella.wigram> Mime-Version: 1.0 X-Mailer: Evolution 2.8.1 Content-Transfer-Encoding: 7bit X-Miltered: at discorde with ID 461463CA.004 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; ocaml:01 val:01 mutable:01 ocaml:01 inverts:01 translated:01 notation:01 mutable:01 ptype:01 stack:01 stack:01 pointers:01 pointer:01 pointer:01 model:01 On Thu, 2007-04-05 at 07:16 +1000, Erik de Castro Lopo wrote: > One ocaml solution to this is an class/object: > > class pow2gen = > object > val mutable current = 0 > > method next () = > current <- > if current == 0 then 1 > else current * 2 ; > current > end Yep, and one solution would be for an Ocaml programmer to modify Felix so it can generate Ocaml instead of C++. Felix mechanically translates threaded code into event driven code, that is, it control inverts procedures so that I/O and calls become returns which remember their return point. The general structure of a translated procedure ( in Ocaml notation ): mutable pc : int mutable parent: ptype method resume() = match pc with | 1 -> ... | 2 -> ... .. | 6 -> ... pc <- 7; new thing (self) (* call thing *) | 7 -> ... let tmp = parent in parent <- NULL; tmp (* return *) | 8 -> ... pc <- 9; self (* yield *) which is used by while(tr != NULL) tr <- tr#resume() I call this procedural continuation passing, Reynolds calls it the method of resumptions. You will note the object here is a stack frame on the heap, and they're linked together into a spaghetti stack by parent pointers. To make this work for functions you add a pointer saying where to put the result, and translate the function to a procedure accepting the additional pointer. This requires unravelling applications to SSA (single assignment) form so an application: x := f a is modelled by f (x,a) There are more details, the above is only a sketch: you can have a look at the precise model used by Felix (which is written in Ocaml), noting Felix generators are simply functions translated to procedures and stored in variables so when they're resume()d they just keep going (whereas ordinary procedures invoked via variables are clones of a prototype to ensure they start in a fresh state). The thing to note is that this is a two step model: A. Translate Python to control inverted Ocaml code B. Compile and execute the generate Ocaml code and hence produces high performance native code. The problem is that Python is dynamically typed .. so most of the performance will be lost doing type dispatches. -- John Skaller Felix, successor to C++: http://felix.sf.net