Is garbage collection needed for implementing safe closures?

I recently attended an online course on programming languages in which, among other concepts, closures were presented. I write down two examples inspired by this course to give some context before asking my question.

The first example is an SML function that produces a list of the numbers from 1 to x, where x is the parameter of the function:

fun countup_from1 (x: int) =
    let
        fun count (from: int) =
            if from = x
            then from :: []
            else from :: count (from + 1)
    in
        count 1
    end

In the SML REPL:

val countup_from1 = fn : int -> int list
- countup_from1 5;
val it = [1,2,3,4,5] : int list

The countup_from1 function uses the helper closure count that captures and uses the variable x from its context.

In the second example, when I invoke a function create_multiplier t, I get back a function (actually, a closure) that multiplies its argument by t:

fun create_multiplier t = fn x => x * t

In the SML REPL:

- fun create_multiplier t = fn x => x * t;
val create_multiplier = fn : int -> int -> int
- val m = create_multiplier 10;
val m = fn : int -> int
- m 4;
val it = 40 : int
- m 2;
val it = 20 : int

So variable m is bound to the closure returned by the function call and now I can use it at will.

Now, for the closure to work properly throughout its lifetime, we need to extend the lifetime of the captured variable t (in the example it is an integer but it could be a value of any type). As far as I know, in SML this is made possible by garbage collection: the closure keeps a reference to the captured value which is later disposed of by the garbage collector when
the closure is destroyed.

My question: in general, is garbage collection the only possible mechanism to
ensure that closures are safe (callable during their whole lifetime)?

Or what are other mechanisms that could ensure the validity of closures without garbage collection: Copy the captured values and store it inside the closure? Restrict the lifetime of the closure itself so that it cannot be invoked after its captured variables have expired?

What are the most popular approaches?

EDIT

I do not think the example above can be explained / implemented by copying the captured variable(s) into the closure. In general, the captured variables can
be of any type, e.g. they can be bound to a very large (immutable) list.
So, in the implementation it would be very inefficient to copy these
values.

For the sake of completeness, here is another example using references
(and side effects):

(* Returns a closure containing a counter that is initialized
   to 0 and is incremented by 1 each time the closure is invoked. *)
fun create_counter () =
    let
        (* Create a reference to an integer: allocate the integer
           and let the variable c point to it. *)
        val c = ref 0
    in
        fn () => (c := !c + 1; !c)
    end

(* Create a closure that contains c and increments the value
   referenced by it it each time it is called. *)
val m = create_counter ();

In the SML REPL:

val create_counter = fn : unit -> unit -> int
val m = fn : unit -> int
- m ();
val it = 1 : int
- m ();
val it = 2 : int
- m ();
val it = 3 : int

So, variables can also be captured by reference and are still alive after
the function call that created them (create_counter ()) has completed.

The Rust programming language is interesting on this aspect.

Rust is a system language, with an optional GC, and was designed with closures from the beginning.

As the other variables, rust closures come in various flavors. Stack closures, the most common ones, are for one-shot usage. They live on the stack and can reference anything. Owned closures take ownership of the captured variables. I think they live on the so called “exchange heap”, which is a global heap. Their lifespan depends on who owns them. Managed closures live on the task-local heap, and are tracked by the task’s GC. I’m not sure about their capturing limitations, though.

Unfortunately beginning with a GC make you a victim of the XY syndrom:

closures require than the variables they closed over live as long as the closure does (for safety reasons)
using the GC we can extend the lifetime of those variables long enough
XY syndrom: are there other mechanisms to extend the lifetime ?

Note, however, than the idea of extending the lifetime of a variable is not necessary for a closure; it’s just brought over by the GC; the original safety statement is just the closed over variables should live as long as the closure (and even that is shaky, we could say they should live until after the last invocation of the closure).

There are, essentially, two approaches that I can see (and they could potentially be combined):

Extend the lifetime of closed over variables (like a GC does, for example)
Restrict the lifetime of the closure

The latter is just a symmetrical approach. It’s not often used, but if, like Rust, you have a region-aware type system, then it’s certainly possible.

Garbage collection is not needed for safe closures, when capturing variables by value. One prominent example is C++. C++ has no standard garbage collection. Lambdas in C++11 are closures (they capture local variables from the surrounding scope). Each variable captured by a lambda can be specified to be captured by value or by reference. If it is captured by reference, then you can say that it is not safe. However, if a variable is captured by value, then it is safe, because the captured copy and the original variable are separate and have independent lifetimes.

In the SML example you gave, it is simple to explain: variables are captured by value. There is no need to “extend the lifetime” of any variable because you can just copy its value into the closure. This is possible because, in ML, variables cannot be assigned to. So there is no difference between one copy and many independent copies. Although SML has garbage collection, it is not related to the capturing of variables by closures.

Garbage collection is also not needed for safe closures when capturing variables by reference (kind of). One example is the Apple Blocks extension to the C, C++, Objective-C, and Objective-C++ languages. There is no standard garbage collection in C and C++. Blocks capture variables by value by default. However, if a local variable is declared with __block, then blocks capture them seemingly “by reference”, and they are safe — they can be used even after the scope that the block was defined in. What happens here is that __block variables are actually a special structure underneath, and when blocks are copied (blocks must be copied in order to use them outside the scope in the first place), they “move” the structure for the __block variable into the heap, and the block manages its memory, I believe through reference counting.

Garbage collection is not necessary in order to implement closures. In 2008, the Delphi language, which is not garbage collected, added an implementation of closures. It works like this:

The compiler creates a functor object under the hood that implements an Interface representing a closure. All closed-over local variables get changed from locals for the enclosing procedure to fields on the functor object. This ensures that the state is preserved for as long as the functor is.

The limitation to this system is that any parameter passed by reference to the enclosing function, as well as the function’s result value, cannot be captured by the functor because they are not locals whose scope is limited to that of the enclosing function.

The functor is referred to by the closure reference, using syntactic sugar to make it look to the developer like a function pointer instead of an Interface. It uses Delphi’s reference-counting system for interfaces to ensure that the functor object (and all the state it holds) remains “alive” as long as it needs to, and then it gets freed when the refcount drops to 0.

Filed under: softwareengineering - @ 16:48

Thẻ: closures, language-agnostic, language-design

Is garbage collection needed for implementing safe closures?

The first example is an SML function that produces a list of the numbers from 1 to x, where x is the parameter of the function:

fun countup_from1 (x: int) =
    let
        fun count (from: int) =
            if from = x
            then from :: []
            else from :: count (from + 1)
    in
        count 1
    end

In the SML REPL:

val countup_from1 = fn : int -> int list
- countup_from1 5;
val it = [1,2,3,4,5] : int list

The countup_from1 function uses the helper closure count that captures and uses the variable x from its context.

In the second example, when I invoke a function create_multiplier t, I get back a function (actually, a closure) that multiplies its argument by t:

fun create_multiplier t = fn x => x * t

In the SML REPL:

- fun create_multiplier t = fn x => x * t;
val create_multiplier = fn : int -> int -> int
- val m = create_multiplier 10;
val m = fn : int -> int
- m 4;
val it = 40 : int
- m 2;
val it = 20 : int

So variable m is bound to the closure returned by the function call and now I can use it at will.

My question: in general, is garbage collection the only possible mechanism to
ensure that closures are safe (callable during their whole lifetime)?

What are the most popular approaches?

EDIT

For the sake of completeness, here is another example using references
(and side effects):

(* Returns a closure containing a counter that is initialized
   to 0 and is incremented by 1 each time the closure is invoked. *)
fun create_counter () =
    let
        (* Create a reference to an integer: allocate the integer
           and let the variable c point to it. *)
        val c = ref 0
    in
        fn () => (c := !c + 1; !c)
    end

(* Create a closure that contains c and increments the value
   referenced by it it each time it is called. *)
val m = create_counter ();

In the SML REPL:

val create_counter = fn : unit -> unit -> int
val m = fn : unit -> int
- m ();
val it = 1 : int
- m ();
val it = 2 : int
- m ();
val it = 3 : int

So, variables can also be captured by reference and are still alive after
the function call that created them (create_counter ()) has completed.

The Rust programming language is interesting on this aspect.

Rust is a system language, with an optional GC, and was designed with closures from the beginning.

Unfortunately beginning with a GC make you a victim of the XY syndrom:

closures require than the variables they closed over live as long as the closure does (for safety reasons)
using the GC we can extend the lifetime of those variables long enough
XY syndrom: are there other mechanisms to extend the lifetime ?

There are, essentially, two approaches that I can see (and they could potentially be combined):

Extend the lifetime of closed over variables (like a GC does, for example)
Restrict the lifetime of the closure

The latter is just a symmetrical approach. It’s not often used, but if, like Rust, you have a region-aware type system, then it’s certainly possible.

Garbage collection is not necessary in order to implement closures. In 2008, the Delphi language, which is not garbage collected, added an implementation of closures. It works like this:

Filed under: softwareengineering - @ 16:48

Thẻ: closures, language-agnostic, language-design

Thiết kế website giá rẻ

Danh mục

Is garbage collection needed for implementing safe closures?

Is garbage collection needed for implementing safe closures?