Nested functions - how many nesting levels are really needed?

I'm implementing a language that supports nested functions with closure semantics, i.e.

def func(x:int) returns (int):int
   return def nested(y:int) returns int 
          { x*y; }

Now, to simplify the closure implementation, I only allow one nesting level. Is this overly restrictive? What does other languages do?

I haven't come across a real-life use-case for multiple nesting levels.

Any opinions / counter examples would be greatly appreciated.


Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

For efficiency?

If you want to avoid closure chains, you can just not make that optimization and have every function close over every symbol it needs. Then supporting nesting is pretty trivial.

Concur: naive implementation

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.

Values shared across multiple closures

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

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

What am I missing?

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].

Missing the Purpose

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();
    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.

Still missing it

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]

Nesting Level Irrelevant

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.

Nesting Level Irrelevant was my point

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

I see.

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.

I would suggest that you are

I would suggest that you are being overly restrictive; taking a look at some O'Caml code implementing an interactive theorem prover, I can count several places where the nesting depth exceeds 2 (1 being a single function, 2 being a function nested in another, etc.) Maybe I should be more specific: I can find at least one case where the depth was 5, and more than 10 where the depth was 3 (this within about 2000 lines that I glanced through).

To be fair, it might not be great code according to some (though often the alternatives seemed worse), but it is real live code that someone wrote. So, there's one anecdote for you, and my vote is that you allow arbitrarily deep nesting (particularly if you allow for a "lambda-function" syntax; if you have a 'map' in a nested function, and the argument to the 'map' is a lambda function, that's 3 levels right there).

"particularly if you allow

particularly if you allow for a "lambda-function" syntax; if you have a 'map' in a nested function, and the argument to the 'map' is a lambda function, that's 3 levels right there

That nails it :)

Too restrictive

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.

In Haskell...

allSums xs ys zs = [...]

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

Good point!

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

Really needed? 0!

C and C++ languages which are quite widespread don't have nested functions.
Using those language, I was annoyed by many of their flaws but I've never really missed nested functions, because that's not something I'm used to..

C++ has it in disguise, in

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

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

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

Depth Limit vs. Cactus Stack

Since the 'depth' of a closure is pretty much a non-issue in pure languages, I assume you're using an impure functional language and you're essentially aiming to avoid maintaining deep cactus stacks when passing functions back down the stack.

Matt M's suggestion to maintain only the symbols you need is probably the best option.

You'll probably need to tweak the implementation such that unused stack frames will be garbage collected. For this to work, programmers should be prevented from directly manipulating state on the stack frames, and instead shift state management into referenced objects or actors, allowing the stack to be pure.

The simple translation from a language allowing mutation (set!) on any symbol (including those on the stack) would be to make every single item on the entire stack a reference. Once the stack is pure, the closure may readily copy just the entries corresponding to the necessary symbols off the stack, which will offer fine-grained garbage collection and avoid the cactus stack.

From there, you can optimize. For example, by distinguishing references from values, most of the references on the stack may readily be left as values... the cost being that you'll need to make explicit a 'create-reference' operation as well as either the 'dereference' operation or the 'do-not-dereference' operation.

All this may be implemented independently of effect typing or making all or part of the language 'pure'.

Admin note

I remind everyone that LtU is not the best place for detailed design discussions. Please see the policy document for suggestions of other venues, and related policies. Thanks.