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 NAA30079; Wed, 28 Apr 2004 13:24:55 +0200 (MET DST) 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 NAA30075 for ; Wed, 28 Apr 2004 13:24:54 +0200 (MET DST) Received: from smtp1.adl2.internode.on.net (smtp1.adl2.internode.on.net [203.16.214.181]) by nez-perce.inria.fr (8.12.10/8.12.10) with ESMTP id i3SBOpjq026788 for ; Wed, 28 Apr 2004 13:24:52 +0200 Received: from [192.168.1.200] (ppp119-113.lns1.syd2.internode.on.net [150.101.119.113]) by smtp1.adl2.internode.on.net (8.12.9/8.12.9) with ESMTP id i3SBOhZq094451; Wed, 28 Apr 2004 20:54:44 +0930 (CST) Subject: Re: [Caml-list] [ANN] The Missing Library From: skaller Reply-To: skaller@users.sourceforge.net To: Jon Harrop Cc: caml-list In-Reply-To: <200404281018.14913.jdh30@cam.ac.uk> References: <200404280613.19547.jdh30@cam.ac.uk> <1083141467.9537.845.camel@pelican.wigram> <200404281018.14913.jdh30@cam.ac.uk> Content-Type: text/plain Message-Id: <1083151482.9537.904.camel@pelican.wigram> Mime-Version: 1.0 X-Mailer: Ximian Evolution 1.2.2 (1.2.2-4) Date: 28 Apr 2004 21:24:43 +1000 Content-Transfer-Encoding: 7bit X-Miltered: at nez-perce by Joe's j-chkmail ("http://j-chkmail.ensmp.fr")! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; caml-list:01 sourceforge:01 2004:99 2004:99 iterator:01 exhibit:01 ignoring:01 iterator:01 generalised:01 arbitrarily:01 higher-order:01 endline:01 callback:01 callbacks:01 endline:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Wed, 2004-04-28 at 19:18, Jon Harrop wrote: > On Wednesday 28 April 2004 9:37 am, skaller wrote: > > On Wed, 2004-04-28 at 15:13, Jon Harrop wrote: > > > ... > > > more interesting connectivities than a bidirectional iterator can > > > represent and which do not exhibit a clear notion of "sub". > > > > That isn't true. Computers can only do things in sequence > > (well, ignoring fledgling parallelism). > [snip] > > I think you've taken the STL concept of an iterator and generalised it so much > that it now covers all computation. :-) All computation by sequential machines. > This notion of an "iterator" would have to be specialised to a specific > sequence-generating algorithm. That algorithm could be arbitrarily > complicated. Sounds like a higher-order function to me. What aspect of this > can ocaml not express/enforce? Control inversion. In Ocaml you can write: List.iter (fun x -> print_endline x) ["Hello"; "World"];; but this isn't an iterator solution because the client algorithm is a callback. Callbacks suck :) Using an iterator we write: while ( p != e) do print_endline (get p); incr p done; This is quite different because the client algorithm is *reading* the data, not being called with it. The List.iter style HOF is very limited in utility in a functional language: there is no state. In Ocaml you can add state of course. But it's a mess. The saving grace of the HOF is that for simple problems, the termination is assured, and, the statelessness of the callback is actually an important property for reasoning about semantics. The control inverted solution is clearly much better for complex problems because it allow the stack to maintain some state. to say another way: an iterator IS just a control inverted HOF, indeed, the (abstraction of) the List.iter HOF. A third view: all computation is an engineering combination of the List.iter kind of iteration and the 'iterators' kind of iteration. Something about 'bisimulation' and inductive and coinductive types and categorical duality principle is here but I don't know exactly what. -- John Skaller, mailto:skaller@users.sf.net voice: 061-2-9660-0850, snail: PO BOX 401 Glebe NSW 2037 Australia Checkout the Felix programming language http://felix.sf.net ------------------- To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners