Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question
2  
Any variables that are closed-over should be protected from garbage collection, and any variables that are not closed over should be eligible for garbage collection. It follows that any mechanism that can reliably track whether or not a variable is closed over can also reliably reclaim the memory that variable occupies. –  Robert Harvey Mar 9 '13 at 0:04
3  
@btilly: Refcounting is just one of many different implementation strategies for a garbage collector. It doesn't really matter how the GC is implemented for the purpose of this question. –  Jörg W Mittag Mar 9 '13 at 1:13
3  
@btilly: What does "true" garbage collection mean? Refcounting is just another way of implementing GC. Tracing is more popular, probably because of the difficulties of collecting cycles with refcounting. (Usually, you end up with a separate tracing GC anyway, so why bother implementing two GCs if you can get by with one.) But there are other ways of dealing with cycles. 1) Just forbid them. 2) Just ignore them. (If you're doing an implementation for quick one-off scripts, why not?) 3) Try to explicitly detect them. (It turns out that having the refcount available can speed that up.) –  Jörg W Mittag Mar 9 '13 at 2:52
1  
It depends on why do you want closures in the first place. If you want to implement, say, a full lambda calculus semantics, you definitely need GC, period. There is no other way around. If you want something which distantly resembles closures, but does not follow the exact semantics of such (like in C++, Delphi, whatever) - do whatever you want, use region analysis, use fully manual memory management. –  SK-logic Mar 10 '13 at 10:58
2  
@Mason Wheeler: Closures are just values, in general it is not possible to predict how they will be moved around at runtime. In this sense, they are nothing special, the same would be valid for a string, a list, and so on. –  Giorgio Mar 10 '13 at 17:43
show 24 more comments

4 Answers 4

up vote 12 down vote accepted

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.

share|improve this answer
1  
Very interesting link and reference to the Rust language. Thanks. +1. –  Giorgio Mar 9 '13 at 23:10
1  
I thought a lot before accepting an answer because I find Mason's answer to be also very informative. I have chosen this one because it is both informative and it cites a lesser known language with an original approach to closures. –  Giorgio Mar 21 '13 at 17:28
    
Thanks for that. I am very enthusiastic about this young language, and I am happy to share my interest. I didn't know wether safe closures were possible without GC, before I heard about Rust. –  barjak Mar 25 '13 at 20:11
add comment

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.

share|improve this answer
1  
Ah, so it is only possible to capture local variable, not the arguments! This seems a reasonable and clever trade-off! +1 –  Giorgio Mar 9 '13 at 0:28
1  
@Giorgio: It can capture arguments, just not ones that are var parameters. –  Mason Wheeler Mar 9 '13 at 0:31
1  
I haven't used Delphi since the time it was called Turbo Pascal, but this approach to closures seems coherent with Pascal's design principles. –  Giorgio Mar 9 '13 at 0:38
1  
You also lose the ability to have 2 closures who communicate through shared private state. You won't encounter that in the basic use cases, but it limits your ability to do complex stuff. Still great example of what is possible! –  btilly Mar 9 '13 at 1:01
2  
@btilly: Actually, if you put 2 closures inside the same enclosing function, that's perfectly legal. They end up sharing the same functor object, and if they modify the same state as each other, changes in one will be reflected in the other. –  Mason Wheeler Mar 9 '13 at 1:03
show 7 more comments

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.

share|improve this answer
4  
"Garbage collection is not needed for closures.": The question is whether it is needed so that the language can enforce safe closures. I know that I can write safe closures in C++ but the language does not enforce them. For closures that extend the lifetime of captured variables, see the edit to my question. –  Giorgio Mar 9 '13 at 10:40
1  
I suppose the question could be reworded into: for safe closures. –  Matthieu M. Mar 9 '13 at 14:39
1  
The title contains the term "safe closures", do you think I could formulate it in a better way? –  Giorgio Mar 9 '13 at 15:46
1  
Can you please correct the second paragraph? In SML, closures do extend the lifetime of data that is referenced by captured variables. Also, it is true that you cannot assign variables (change their binding) but you do have mutable data (through ref's). So, OK, one can debate whether the implementation of closures is related to garbage collection or not, but the above statements should be corrected. –  Giorgio Mar 9 '13 at 23:15
1  
@Giorgio: How about now? Also, in what sense do you find my statement that closures do not need to extend the lifetime of a captured variable incorrect? When you talk about mutable data, you are talking about reference types (refs, arrays, etc) that point to a structure. But the value is the reference itself, not the thing it points to. If you have var a = ref 1 and you make a copy var b = a, and you use b, does that mean you are still using a?No. You have access to the same structure pointed to by a?Yes. That is just how these types work in SML and have nothing to do with closures –  user102008 Mar 10 '13 at 10:33
show 5 more comments

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):

  1. Extend the lifetime of closed over variables (like a GC does, for example)
  2. 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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.