A short history of frames

[Nathan Hawkins]

On Sat, 27 Apr 1996, Eric W. Biederman wrote:

> Long ago in programming land there was a language called Fortran.  Now
> Fortran had this marvelous new concept, you could have functions!  In
> those days when Fortran on punch cards was high level programming
> nothing was spared for efficiency, not even recursion.  That is
> loading a variable off of a stack was more inefficient then a
> statically allocated variable, so all vairables were statically
> allocated.  To allow variables that were specific to a function
> certain areas (frames) were set aside to allow for the local variables
> of a function.  In these frames also were set aside places for the
> arguments to the function, and it's return address.  Exactly where
> return values were stored I don't know but they were highly restricted
> anyway.  In all functions the location of frames was statically know.  

This part is ancient....

> In later languages when machines got better at indirect addressing and
> people were more concerned with functionality, frames were allocated
> upon a stack, to allow for recursion.  Recently since frames upon
> stacks has become such a defacto part of life many optimizations have
> been introduced to attempt to keep frames, especially their arguments
> in registers.
> 
> So while C and other languages allocate their frames upon a stack, it
> is just a convinience.  They just as well could dynamically allocate
> them from a heap, and use malloc and free.  In fact some variants of
> lisp actually do use the heap to allow for expressions that can return
> multiple times, only the garbage collector knows when it won't happen
> again.  

This is reasonable for C, for the obvious reason that C is constrained to 
frames which are of a known size and shape at compile time. (In fact, I 
rather suspect that this will start coming into use for compiling C on 
RISC chips, if it hasn't already.)

> For a garbage collector having a structure with all the variables of a
> function is very attractive.  It can then tag that structure as it
> would any other object, with garbage collected information.  But this
> needs to only be way out at the structure level, instead of having to
> tag every cell of memory as to weather or not it's a pointer.  There
> is at least one specialized collector for a stack/heap for lisp like
> languages that simply collects the stack/heap and not the general
> heap, is quite fast, and allows multiple `threads' upon the same it.

Why is it easier to handle a stack made of structure than a stack made of 
pointers and integers? The difference is only in breaking the pointers 
and integers into groups. You still have to consider the differences.

> The difficulty with integrating all of this into forth is that long
> ago forth took a different approach to memory management.  It
> implemented a global data stack & a global return stack, and words
> that implement them.  In forth there is no telling how much of the
> data stack a given word will consume.  It might just consume the whole
> data stack, and then return to the caller.  Or perhaps it might
> consume upon a rare occasion consume a word from the return stack it
> didn't push and then return to lala land.  Now much of this is good in
> that you can address completely manipulate the system.  The bad is
> that you can easily manipulate things wrong.

This is an important part of what I like about Forth. Forth's very lack 
of stack frames is one of it's greatest strengths, IMHO. Sure, you can 
mess up, but that's true of all good languages. ;-) I wouldn't want to 
work in an idiot-proofed language, since I would probably be prevented 
from doing most of the things I want to do.

> One last argument to dispell having a function like printf in C is not
> a very good argument in C because only the programmer can properly
> construct calls to printf!  In the few languages where you can
> actually construct function calls for printf at least it is quite
> difficult.  So my question is in a language where the heap is as fast
> as the stack, what kind of routines would benefit from variable
> arguments and variable return values?

Re: constructing calls to printf. Have you forgotten the varargs package? 
Granted, it's ugly, but that's to be expected.

We haven't established that the heap is as fast as the stack, and I doubt 
that this would be so. As for routines which would benefit from variable 
arguments and return values, in Forth it's fairly common to have 
conditional evaluation of parameters, using and returning a differing set 
of parameters accordingly. This is something which can very advantagous 
in certain places, and I certainly like it better than the constraints of 
the Algol descendents. (Only one return value! 8-)

*utsl*