Talk:Funarg problem

From Wikipedia, the free encyclopedia

Contents 1 Examples? Returning a function vs. returning a struct 2 Upwards vs. downwards funarg? 3 Nested functions in C 4 Typical implementation as heap-allocated closures 5 I do not understand

[edit] Examples? Returning a function vs. returning a struct

Examples? What makes the upwards funarg problem so much different from, let's say, returning structs in C? Or is the main problem that the environment's size may be variable, which interferes with conventional mechanisms to pass return values on the stack? Is it really necessary to allocate each closure as a heap object, or would it be possible to use a second stack, separate from the execution stack, just for returning closures? Ok, that's enough questions for now, I guess. Aragorn2 09:38, 29 Mar 2005 (UTC)

From my understanding, the funarg "problem" was pretty much solved forever with the invention of the closure. Once one understands that the important thing is to save a function's environment somehow and pair that up with a pointer to its code, and then execute subsequent calls to the function in that environment, there is no problem. Storing closures, including their environments, in the heap avoids most issues of size (so long as you don't get the environments from different closures mixed up!). Allocating closures on a stack would only work if they were used in a last-in, first-out fashion; since there's no particular rhyme or reason to which closures will outlive which others, it generally makes the most sense to store them in the heap. Cjoev 19:10, 29 Mar 2005 (UTC)

So is it the core of the problem that a function may return a closure, but the size of the closure (in bytes) isn't known beforehand, while the caller has to set a size limit for return values passed up the stack (and/or registers)? This means that if the caller allocated 1000 bytes, the closure may require 1100 bytes, and if the caller allocates 10000 bytes, the closure may require 11000... Obviously, putting closures on the heap and returning only fixed-size pointers to them solves this problem since the allocation can be performed by the called function at a point in time where the closure's size is already known.

If this is the case, the funarg problem could be applied to all instances where the size of a return value is not known beforehand. Maybe it's just a complicated way of saying that stack machines aren't turing-complete. ;-) Aragorn2 16:38, 23 Apr 2005 (UTC)

No. First of all, it is possible to get all the expressiveness of a Turing machine without any functions or stack at all. (If you want to do without a heap, you have to use really really big integers to represent the Turing machine's unbounded storage, but it works in theory and Turing machines are a theoretical construction anyway.) Second and more importantly, the sizes of closures are not the core of the problem. The core of the problem, when people still thought it was a problem, was that people did not understand the very idea of a closure. Imagine that you had never heard of a closure and ask yourself how you would implement returning a function from a function. It's hard. You pretty much have to invent closures in order to do it. That's the funarg problem. Once you have the basic idea of closures, the fact that they may differ in size is a minor detail. Equate "funarg problem" with "unknown-size return value problem" as you propose misses the point, I think. Cjoev 14:55, 25 Apr 2005 (UTC)

First of all, it is possible to get all the expressiveness of a Turing machine without any functions or stack at all.

Of course, since Turing machines don't have functions or a stack... I'd be curious to know in what way this is supposed to have anything to do with what I said (that stack machines aren't turing-complete).

If you want to do without a heap, you have to use really really big integers to represent the Turing machine's unbounded storage

Stack machines do not permit an infinite alphabet. And please tell me where I stated that a heap was a necessary criterion for turing-completeness.

Second and more importantly, the sizes of closures are not the core of the problem. The core of the problem, when people still thought it was a problem, was that people did not understand the very idea of a closure. Imagine that you had never heard of a closure and ask yourself how you would implement returning a function from a function. It's hard. You pretty much have to invent closures in order to do it. That's the funarg problem. Once you have the basic idea of closures, the fact that they may differ in size is a minor detail. Equate "funarg problem" with "unknown-size return value problem" as you propose misses the point, I think.

That's an interesting approach, but the article says something entirely different (much closer to my interpretation), namely that people tried to implement closures (not come up with them), and that they couldn't figure out how to pass them up the stack. And obviously you took my turing-completeness remark way too serious. Aragorn2 19:59, 25 Apr 2005 (UTC)

Ok, fine, clearly when you said "complicated way of saying that stack machines aren't turing-complete" you meant a much higher level of complication than I thought. I now see that perhaps you may just have been saying that it is ridiculous to assume a stack is the only data structure you need for general programming. That I agree with. That said, however badly I may have expressed myself before, I don't think there is a precise correspondence between the difficulty of implementing functional arguments and the impossibility of solving certain problems with a stack machine. If you weren't claiming there was one then I am more than willing to drop this subject.

As for the funarg problem, I have done a small amount more research on the web and I now believe that I understand the precise definition of the problem better than I did before. The problem was first discovered when somebody wrote a Lisp program that passed a function as an argument and it did not do what he expected it to do. The reason was that Lisp implementors before that time did not realize it was necessary to bundle functions with environments. A new construct was added to the language to allow programmers to explicitly create such packages -- this construct went by the name FUNARG, and also lent that name to the problem it was solving. There was apparently some argument for a while about what the right way to implement FUNARGs would be. Eventually, language designers (and implementors) came to (mostly) agree that functions should always be packaged together with environments.

The thing that's hard about upwards funargs is not any issue of size; it's that a function that refers to a variable may outlive that variable's stack-allocated storage location. (This does not happen with downward funargs.) Imagine a function F that declares a local variable x and has a function G nested inside it. Suppose that G refers to the variable x that belongs to F. Normally x would live in F's stack frame. Now suppose that F returns G as its result; when F returns, its stack frame is deallocated, including the location that holds x. If G is subsequently called, the variable x that it needs will be nowhere to be found. Since this particular difficulty does not arise if all funargs are "downward", the upwards problem is considered harder.

So there are a couple of things about the article that need to be fixed. One is that it needs to tell the story I just told (right now, it basically tells no story at all). Another is that, as you said quite a while ago, it needs to be illustrated with an example, like a more concrete version of what I just wrote. Finally, it needs to cite some external references rather than just being made up by people like me.

Cjoev 04:15, 26 Apr 2005 (UTC)

[edit] Upwards vs. downwards funarg?

I don't understand the difference between upwards and downwards funarg 202.163.215.11 06:41, 16 June 2006 (UTC)

[edit] Nested functions in C

This article is a little incorrect. C can have nested functions and they are available in GCC's dialect. From what I have read (I have no need for nested functions :) they go out of scope when the parent function ends (just like variables) thereby solving the problem. -- 127.*.*.1 14:02, 23 August 2006 (UTC)

[edit] Typical implementation as heap-allocated closures

This is usually accomplished by representing function values as heap-allocated closures, as previously described.

Could that statement be backed with sources? I find it strange at first, knowing that one of the first papers of one of the first implementations of Scheme, namely "RABBIT: A Compiler for SCHEME", Steele's Master Thesis, says the following:

A fair amount of analysis is devoted to determining whether environments may be stack-allocated or must be heap- allocated.

—The preceding unsigned comment was added by Nowhere man (talk • contribs) 02:24, 1 February 2007 (UTC).

[edit] I do not understand

I do not see why it should be any more complex than returning a pointer to a function.

If a ynamic language like Ocaml or Lisp can define function on the fly, all that is needed is a way to reference those functions... Obviously that is already done.

Moreover, the whole idea of Lisp was to implement lambda expressions as a computational model, therefore Funargs were invented even before Lisp was invented (even before computers were invented).

—The preceding unsigned comment was added by 201.239.221.235 (talk • contribs) 12:27, 14 August 2007 (UTC).

Not quite. You're right that the funarg problem has now been solved; but it's actually much more complex than just returning a pointer to the function, and it wasn't solved until well after the initial versions of Lisp. —Ruakh_TALK 14:49, 14 August 2007 (UTC)