Re: [Caml-list] Re: How important are circular lists/recursive objects?

[skaller <skaller@users.sourceforge.net>]

On Thu, 2007-10-04 at 19:48 +0200, Fabrice Marchant wrote:
> On Wed, 04 Apr 2007 15:28:18 +1000
> skaller <skaller@users.sourceforge.net> 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 <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net