Compile-Time Decisions

Run-Time Information

Unit Activation

Activation Records

Language Issues

Static Storage Allocation

Activation Records for Languages that Support Recursion

Activation Records for Languages that Support Block Structure

Activation Records Whose Size Is Known at Unit Activation

Activation Records with Dynamically Varying Size

Activation Records for Concurrent Units

Storage Allocation for Lisp-like Languages

Storage Allocation for Arrays

There are languages that contain constructs whose values vary in size, not just as a unit is invoked, as in the previous section, but during the unit's execution. C (and other language) pointers, flexible arrays (whose bounds change during execution), strings in languages such as Snobol, and lists in Lisp are a few examples. These all require on demand storage allcoation, and such variables are called dynamic variables.

Example 5 shows the problems encountered with such constructs.

EXAMPLE 5 Dynamic variables

 PROGRAM Main
   GLOBAL a,b
   DYNAMIC p4
   PROCEDURE P (PARAMETER x)
     LOCAL p1,p2
   BEGIN {P}
     NEW (p4)
     Call P(p2) ***
   END {P}
 BEGIN {Main}
   Call P(a)
 END {Main}
 

In Example 5, notice that p4 is declared in Main, but not used until procedure p. Suppose that the program is executing at the point where the asterisks are shown, using the stack of activation record structure as in the previous examples. Where should space for p4's value be allocated?

P's activation record is on top of the stack. If space for p4 is allocated in P, then when P finishes, this value will go away (incorrectly). Allocation space for p4 in main is possible since the static link points to it, but it would require reshaping P's activation record, a messy solution since lots of other values (e.g., the dynamic links) would need to be adjusted.

The solution here is not to use a stack, but rather a data structure called a heap.

Heap

A heap is a block of storage within which pieces are allocated and freed in some relatively unstructured way.

Heap storage management is needed when a language allows the creation, destruction or extension of a data structure at arbitrary program points. It isimplemented by calls to the operating system to create or destory a certain amount of storage.