Stack-based hardware in the days of First Class Functions

Joe Gregorio

From Wikipedia, The Funarg Problem

Funarg is an abbreviation for "functional argument"; in computer science, the funarg problem relates to the difficulty of implementing functions as first-class objects in stack-based programming language implementations.

I've been thinking about this in the context of the Professionalization of Scripting Languages, does anyone know if any of the processor manufacturers are working on adding silicon support for activation records?

Well, if they think this problem is peculiar to stack-based programming-language implementations, they should consider the difficulty of non-stack-based programming-language implementations. What a strange thought. There were ALGOL 60 implementations, and of course PL/I in its odd way, that had to deal with the cactus problem. The Funarg problem is easier to solve than the coroutine and multiple-thread cross-communication problems. In a way, the creation of objects with garbage-collected lifecycles provides an implementation mechanism for closures too. The pain is that the caller has to be aware that a closure (method on a class instance) is being invoked, and it is usually difficult to pass an instance method around as if it were a function or procedure reference. The idea with closures is that the recipient of one (say, as a parameter) doesn't know they are any different than any other function-like thingy that can be invoked, applied to arguments, etc. Now that there are lambda-expressions in .NET, I suppose it would be useful to see if they get the closures right or even lead to properly-bound closures. Time to resuscitate Knuth's ManOrBoy compiler test and try it out with the various scripting-language funarg provisions. I would not pray for a silicon solution. The tendency of hardware guys who do this has been to yield instant designs that don't actually work and have to be worked around with software anyhow. I would treat that as a later optimization. The big thing is figuring out how to handle lexical binding from a closure into its environment.

Posted by orcmid on 2008-07-11

comments powered by Disqus