Stack, Heap and Frame Stack

The pseduo machine of the EDEN interpreter is a simple stack machine.

Stack

A stack holds the values used and computed during evaluation of an EDEN program.

When the machine calls a function, the parameters are pushed on the top of the stack. Actually, the parameters are merged to form a single list datum. If the function requires any local variable, the machine allocates space for their values. When the function returns, the allocated local variables and the arguments stored on the stack are poped; then the value is returned by pushing it onto the stack. See the figure below which shows the stack

• before a function is called,
• during a function call, the arguments having been pushed onto the stack, and
• after the function has returned, the arguments and local variables having been popped, and the answer pushed onto the stack.

Since the stack is a fixed size memory block, a deep function call may cause the ``stack overflow'' error.

Heap

To reduce the frequency of copying the contents of strings and lists, we add another data structure, called the heap, to hold the contents of temporary strings or lists during the string/list operations. The overhead for allocating/deallocating memory on the heap is less than that of malloc()/free().

The heap is a large memory block. Memory is allocated within this block. A pointer keeps track the top of heap similar to the stack pointer of the stack. The pseduo machine instruction, freeheap, releases all the memory allocated by previous computation. The heap is not affected by the return of the function call. Freeheap instructions are automatically inserted by the interpreter at the points that it thinks safe to free memory. However, if a computation involves long strings, lists or too deep function called, the machine may not have the chance to free the memory and thus causes the ``heap overflow'' error.

The user may have to modify their program to minimise the load of stack and heap to avoid memory overflow errors. For instance, an iterative function has less demand on stack and heap than its recursive equivalent.

Frame Stack

In returning from a function call, the machine has to stored the previous machine status, e.g. stack pointer, (pseduo machine) program counter, number of local variables (since local variables were put on the stack), etc. A frame stack holds these information.

When a function is called, the current machine status, a frame, is pushed on the frame stack. For example, if f1() calls f2(), the status of stack, heap and frame stack is shown below.

The frame stack keeps track of the stack and heap pointers. A freeheap instruction (generated by EDEN) causes the top-of-heap to return to the bottom pointed to by the top-most frame (e.g. f2). On the other hand, the stack pointer is lowered only if the function returns.

A frame is popped when a function returns and the machine status resumes to the previous state. Since the frame stack is implemented as a small stack, about 64 entries, the number of level of nested function call is 64 approx. This maximum limit is enough for general use, but if a function nested too deep, the machine will generate a ``nested too deep'' error.

Avoiding Memory Overflow

Since the EDEN interpreter passes list "by value", i.e. copies the entire list on heap, it is very eay to overflow the heap if you pass long lists as parameters of a recursive function. To get round this problem, you may consider the use of iterative loops instead of recursive functions, or you may pass the "pointer" of that list to the function, and let the function to copy that list to its local variable. For example, instead of:

func foo /* (list) */
{
        ...
        foo($1);
        ...
}

do:

func foo /* (list *) */
{
        auto list;
        list = *$1;     /* copy the list to local variable */
        ...
        list = ...;     /* do the calculation here */
        foo(&list); /* pass the pointer of that list */
        ...
}

Also not that the interpreter will try to free the heap space at the end of each statement. Therefore, it would be helpful space-wise to break a long expression into smaller expressions and use temperary variables to hold intermediate computation results. For instance:

a = expression;
foo(a);

uses less heap space than

foo(expression);

The machine uses malloc() to allocate space for strings and lists rather than claiming space from the heap. So the use of strings and lists would not normally causes memory overflow.