Lambda the Ultimate

There is a simple, naive implementation for closures that provides a good way to "get going". Whenever you see that something is captured, "heapify" it by copying it into the heap, and then do all accesses through the pointer. Once this is done, it becomes very easy to deal with values that are shared across multiple closures, and that is the main complication in deep closures. No closure chaining is necessary in this implementation.

Later you can go do a proper escape analysis a la Hannan and optimize this, but get your language design right first.

Watch out for by-reference parameters if you have them. Those create, umm, "interesting" complications if you don't do region typing.

Deeper nesting tends to show in provers a lot. It is one of the principal means of abstraction.

Once this is done, it becomes very easy to deal with values that are shared across multiple closures, and that is the main complication in deep closures.

You can have shared values with consecutive (not nested) closures, can't you? Is that not as complicating for some reason?

John meant shared state across closures, at least from context. The trick is supporting shared state across closures without maintaining full cactus stacks, an implementation for which John is describing above (and basically the same thing I described below).

def foo:
    x = 0
    def bar:
        x = 1
    def baz:
        x += 1
    return (bar, baz)

This has shared state. I'm trying to understand the complication that arises going from once nested closures to the more general case. It looks to me like you need a "cactus stack" as soon as you can return a single nested function with state on the stack [just as much as you do in cases with deeper nesting].

Perhaps you need to follow your original suggestion to its logical conclusion: if you wish to close over ONLY those symbols that are necessary, you'll need to solve the problem of garbage-collecting 'y' in the following code:

def foo:
    x = 0
    y = CallWithSideEffects();
    DoSomething(y);
    def bar:
        x = 1
    def baz:
        x += 1
    return (bar, baz)

The 'cactus stack' approach keeps 'y' around indefinitely, for as long as bar and baz are around. That is an issue worth resolving.

The OP is essentially asking: "how many stack frames do I really need to keep around?". I inferred (abductively) that the most likely reason behind the OP question is the desire to trim down on memory requirements when dealing with the upfunarg problem. In particular, avoiding the 'cactus stack' is a major win. I suspect that John came to the same conclusion.

What we've been describing is an implementation approach to simultaneously meet the goals of sharing state and avoid the cactus stack.

Your suggestion is the right way to go, but it does entail something in terms of implementation. For example, 'x' needs to be 'heapified' (as John put it) so that it can be updated and collected independently of the stack frame. The simple implementation would be to 'heapify' everything, then allow an optimizer to go around and selectively unheapify things that don't need to be heapified.

It's worth noting that all this is a non-issue in a 'pure' functional language since closures have no state.

I understand all of that. AFAICT each of your points applies to situations with once nested functions as well as it applies to deeper nesting. You didn't even include deeper nesting in your example, so I don't think you're addressing my question.

[Also, I added an edit to my previous post to clarify its meaning - maybe that was a source of confusion]

The nesting level is irrelevant if one closes over exactly the symbols one needs... so my points should apply regardless of nesting level.

Your suggestion is to 'close over the symbols one needs'. Perhaps I misread your intention as 'close over ONLY the symbols one needs'. If one closes over only symbols that are actually used in the closure, one can collect the rest of the stack out from under the first class functions. There is no need for cactus stacks, and all closures become 'shallow'. Closures effectively carry around a micro-stack containing exactly and only the references and values they require, skipping entries like 'y' in the above example. (The cost? Well, one must perform a small extra allocation to create the closure rather than simply reusing a pointer to already-allocated stack frames.)

We're obviously talking past one another here. I'll ask a couple questions to help clarify:

• Did you read John's title "Concur: naive implementation" as calling your implementation naive? (It seems clear to me that "concur" means he agrees with your statement, and "naive implementation" describes the OP.)
• Do you believe your initial suggestion applies differently to once nested functions vs. any other sort? (I don't believe it does.)
• Do you believe your suggestion requires cactus stacks of potentially indeterminate length? Because what Shapiro is suggesting is an approach to implement your suggestion without this problem.

I think you understood my original suggestion. My follow-up to shap was regarding a single sentence in his reply, in which he referred to complications of "deep closures." Given the context of the OP, I interpreted that phrase to mean functions nested more than once. I thus asked for clarification as to what complicates the "deep closure" case that doesn't already complicate the "once nested closure" case.

Answers to your questions: 1) No 2) No 3) No

Deep closures aren't "more complicated" with the approach you and Shapiro described, but certainly are "more complicated" than once nested closures when following the OP approach.

Capturing one stack frame is simplistic - attempts to demolish essential complexity, violates the Einstein principle (as simple as possible but no simpler) - and so everything else naturally seems "more complicated"... or at least it looks more complicated until you start pushing extra arguments into nested methods, explicitly heapify stuff that was once in an earlier stack frame just so it can be captured in a closure you use later, etc.

My guess is this is not the style of code that you have in mind, but the following is quite typical in Haskell (well, structurally typical, maybe not literally):

  allSums xs ys zs = 
    xs >>= \x ->
    ys >>= \y ->
    zs >>= \z ->
    return (x + y + z)

Haskell's do-notation translates into precisely that kind of nested function chain, so it's natural for them to get fairly deep.

In any case, I think it's too restrictive. If you'll allow closures at all, allow nesting.

allSums xs ys zs = [...]

You had a triply nested function at line 1. :)

Although I'm definitely sure that's not what the OP had in mind... ;)

C++ has it in disguise, in the form of operator() [apply]. There is currently discussion about adding some form of non-escaping lambda form as well.

Well, it is a bit more than 'discussion' as lambdas are in the current draft standard (which has been recently declared feature complete).

BTW, C++0x lambdas can certainly escape, as long as you are careful to close *by value* over automatic variables (which is the default):

  std::function<void()>
  get_printer(int i) {
      return [] { std::cout << i << "\n"; };
  }
  ...
  get_printer(10)(); // prints 10