Language Design – Is Garbage Collection Needed for Safe Closures?

closureslanguage-agnosticlanguage-design

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.

Best Answer

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.

Related Topic