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,SPF_FAIL autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by yquem.inria.fr (Postfix) with ESMTP id 090FEBBCA for ; Wed, 27 Feb 2008 14:29:56 +0100 (CET) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgAAAOL0xEfVpUAUmWdsb2JhbACQZwEBAQEBBgQGCQgWnFg X-IronPort-AV: E=Sophos;i="4.25,413,1199660400"; d="scan'208";a="23105548" Received: from mail.gmx.net ([213.165.64.20]) by mail4-smtp-sop.national.inria.fr with SMTP; 27 Feb 2008 14:29:55 +0100 Received: (qmail invoked by alias); 27 Feb 2008 13:29:53 -0000 Received: from dialin-145-254-247-017.pools.arcor-ip.net (EHLO dialin-145-254-247-017.pools.arcor-ip.net) [145.254.247.17] by mail.gmx.net (mp006) with SMTP; 27 Feb 2008 14:29:53 +0100 X-Authenticated: #11134691 X-Provags-ID: V01U2FsdGVkX19nU41LpKBnk+FZ83Sl/R28LpbeKQs9+4T8lzNrcy JavPT3PByIWygS Received: from dirk by feanor.private-host.de with local (masqmail 0.2.20) id 1JUKzo-2JK-00 for ; Wed, 27 Feb 2008 13:02:48 +0100 Date: Wed, 27 Feb 2008 13:02:48 +0100 To: caml-list@yquem.inria.fr Subject: Re: [Caml-list] Unexpected restriction in "let rec" expressions Message-ID: <20080227120248.GA8000@feanor> References: <6f9f8f4a0802260424o5bce2fd9i89fbfa38bb239a6a@mail.gmail.com> <47C524F3.9030005@fmf.uni-lj.si> <6f9f8f4a0802270143o68c58cbfh2ea059cda5c0a744@mail.gmail.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <6f9f8f4a0802270143o68c58cbfh2ea059cda5c0a744@mail.gmail.com> User-Agent: Mutt/1.5.6+20040523i From: Dirk Thierbach X-Y-GMX-Trusted: 0 X-Spam: no; 0.00; 0100,:01 haskell:01 explicitely:01 fixpoint:01 fixpoint:01 26,:98 wrote:01 partial:01 rec:01 caml-list:01 computation:01 semantic:02 lazy:02 argument:02 argument:02 On Wed, Feb 27, 2008 at 10:43:18AM +0100, Loup Vaillant wrote: > 2008/2/26, Nicolas Pouillard : > > A picture can helps... Fixed names to be consistent with loop :: ((a,c) -> (b,c)) -> a -> b loop f a = b where (b,c) = f (a,c) >> >> +---------+ >> a>-| |->b >> | x | >> c>-| |->c >> +---------+ >> >> +---------+ >> a>-| |->b >> | y | >> +->-| |->-+ >> | +---------+ | >> +--------c--------+ >> > I saw this image before, but despite of its clarity, it hasn't solved > my problem: the chicken and egg one. See, the looping "c" in y looks > like it has to be produced out of thin air. It's easier to think this in Haskell, because then one hasn't to deal with lazyness explicitely. Consider f (a,c) = (c, a : map (+a) c) That's a perfectly non-recursive function. Now, what happens when we apply "loop" to it? *Main> take 10 $ loop f 1 [1,2,3,4,5,6,7,8,9,10] *Main> take 10 $ loop f 2 [2,4,6,8,10,12,14,16,18,20] Ah, so it actually does produce values out of thin air :-) How did that happen? Well, inside f, we used the argument c before it was really defined, but in doing so, we added information *before* feeding it back through the loop. One can picture the "incomplete" list going round and round the loop, and with each step gaining more information (here for a = 1): ? 1,? 1,2,? 1,2,3,? and so on. Of course that's not what really happens during the computation -- there lazy evaluation takes care that the unkown part isn't actually evaluated before it has been defined. With strict evaluation, the complete argument is evaluated on function call, so this doesn't work. BTW, the "canonical" fixpoint operator, also called Y-combinator, fix : (a -> a) -> a which has already been mentioned can be thought of in a similar way. Does that explanation help? And a semantic explanation with domains (a special kind of partial orders) can make the "gain more information" idea concrete, and also make a bit more clear why it is called a "fixpoint". Google for those if you want to learn more. - Dirk