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=AWL autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by yquem.inria.fr (Postfix) with ESMTP id 136DDBC69 for ; Thu, 4 Oct 2007 22:39:50 +0200 (CEST) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgAAANDrBEfLENaMnmdsb2JhbACOOAEBAQEHBAYp X-IronPort-AV: E=Sophos;i="4.21,232,1188770400"; d="scan'208";a="2392989" Received: from ipmail01.adl2.internode.on.net ([203.16.214.140]) by mail2-smtp-roc.national.inria.fr with ESMTP; 04 Oct 2007 22:39:48 +0200 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgAAAHPpBEd5LHvc/2dsb2JhbAAM X-IronPort-AV: E=Sophos;i="4.21,232,1188743400"; d="scan'208";a="204348924" Received: from ppp121-44-123-220.lns10.syd6.internode.on.net (HELO [192.168.1.201]) ([121.44.123.220]) by ipmail01.adl2.internode.on.net with ESMTP; 05 Oct 2007 06:09:45 +0930 Subject: Re: [Caml-list] Re: How important are circular lists/recursive objects? From: skaller To: Fabrice Marchant Cc: caml-list@yquem.inria.fr In-Reply-To: <20071004194808.6d7e1136@localhost.localdomain> References: <1175664498.24614.5.camel@rosella.wigram> <20071004194808.6d7e1136@localhost.localdomain> Content-Type: text/plain Date: Fri, 05 Oct 2007 06:39:44 +1000 Message-Id: <1191530384.7078.102.camel@rosella.wigram> Mime-Version: 1.0 X-Mailer: Evolution 2.10.1 Content-Transfer-Encoding: 7bit X-Spam: no; 0.00; recursive:01 0200,:01 abstraction:01 abstraction:01 bindings:01 fpls:01 mutable:01 mutable:01 bindings:01 initialise:01 incorrectly:01 lambda:01 sourceforge:01 sourceforge:01 garbage:01 On Thu, 2007-10-04 at 19:48 +0200, Fabrice Marchant wrote: > On Wed, 04 Apr 2007 15:28:18 +1000 > skaller wrote: > > > You can also create cycles using functional abstraction > > Sorry, I completely missed this old exciting topic and posts. > > Please could you develop a bit to show how we can create cycles using functional abstraction ? > > In fact, my problem is I do not exactly see what means "functional abstraction". I mean lambda-abstraction in theory and closure in practice. > Do you speak about something like this ? > > type circular_list = Circular_list of (unit -> circular_list) > let rec cl = fun () -> Circular_list (fun () -> Circular_list cl) I think of something like: let f () = let rec g() = k () and k = g in k() where g refers to itself. Other than use of a function closure to create a box, let/in bindings cannot create cycles because non-functional values have to be constructed from existing already initialised values. So apart from functional closures, FPLs can't have cycles and thus strangely would ensure that ref counting would be enough, and you'd not need a garbage collector. Once you have mutable variables then you need a gc because it is easy to get cycles with mutable cells. So what is weird about functions? It is because you can create function closure with uninitialised slots for storing bindings, and initialise the slots later by executing it .. by which time you can put the address of the closure itself in one of those slots. So what is it that GUARANTEES that these uninitialised values in the stack from of the function are not incorrectly accessed? The answer is abstraction, in particular lambda (functional) abstraction. The local variables of a function cannot be accessed from outside the function, you have to execute it. So it is safe to create closures with uninitialised slots in them -- in fact, that's the only way! Note that stuff like: let rec x= (1,x) is not generally allowed: in functional terms it is ill-defined, and it certainly can't be implemented unless you box values which is implementation detail. Felix doesn't box tuples, so this would crash if Felix allowed it. -- John Skaller Felix, successor to C++: http://felix.sf.net