Log in / Register
Home arrow Computer Science arrow Data Structures and Algorithms with Python
< Prev   CONTENTS   Next >

3.3 The Run-Time Stack and the Heap

As we learned in the last section, the parameters and body of each function define a scope within a Python program. The parameters and variables defined within the local scope of a function must be stored someplace within the RAM of a computer. Python splits the RAM up into two parts called the Run-time Stack and the Heap.

The run-time stack is like a stack of trays in a cafeteria. Most cafeterias have a device that holds these trays. When the stack of trays gets short enough a spring below the trays pops the trays up so they are at a nice height. As more trays are added to the stack, the spring in this device compresses and the stack pushes down. A Stack in Computer Science is similar in many ways to this kind of device. The run-time stack is a stack of Activation Records. The Python interpreter pushes an activation record onto the run-time stack when a function is called. When a function returns the Python interpreter pops the corresponding activation record off the run-time stack.

Python stores the identifiers defined in the local scope in an activation record. When a function is called, a new scope becomes the local scope. At the same time a new activation record is pushed onto the run-time stack. This new activation record holds all the variables that are defined within the new local scope. When a function returns its corresponding activation record is popped from the run-time stack.

The Heap is the area of RAM where all objects are stored. When an object is created it resides in the heap. The run-time stack never contains objects. References to objects are stored within the run-time stack and those references point to objects in the heap.

Consider the program in Fig. 3.2. When the Python interpreter is executing lines 23 and 24 of the program, the run-time stack looks as it does in Fig. 3.3. There are three activation records on the run-time stack. The first activation record pushed onto the run-time stack was for the module. When the module first began executing, the Python interpreter went through the module from top to bottom and put any variable definitions in the module scope into the activation record for the module. In this program that consisted of the reference PI to the value 3.14159.

Then, at the end of the module the if statement called the main function. This caused the Python interpreter to push the activation record for the main function. The variables defined within the main function include historyOfPrompts, historyOfOutput, rString, r, and val. Each of these appear within the activation record for the main function.

As the main function began executing it called the getInput function. When that call occurred there was an activation record pushed for the function call. That activation record contained the prompt and x variables. This activation record does not appear in the figure because by the time we execute line 23 and 24 of the program the Python interpreter has already returned from the getInput function. When the interpreter returned from the function call the corresponding activation record was popped from the run-time stack.

Finally, the program calls the showOutput function on line 26 and execution of the function begins. An activation record for the showOutpout function call was pushed onto the run-time stack when showOutput was called. The references local to that scope, which includes just the val variable, were stored the activation record for this function call.

You can run this example program using Wing or some other IDE. The code for it appears in Sect. 20.2. When you use the Wing IDE to run this program you can stop the program at any point and examine the run-time stack. For instance, Fig. 3.4 shows Wing in the midst of running this program. A breakpoint has been set on line 24 to stop the program. The tab at the bottom of the Wing IDE window shows the Stack Data. This is the run-time stack.

Right below the Stack Data tab there is a combination box that currently displays showOutput():, line 24. This combo box lets you pick from the activation record that is currently being displayed. If you pick a different activation record, its contents will be displayed directly below it in the Wing IDE.

Fig. 3.3 The Run-time Stack and the Heap

One important note should be made here. Figure 3.4 shows historyOfOutput as a local variable in the showOutput function. This is not really the case, because the historyOfOutput reference is not defined within the local scope of the showOutput function. However, due to the way Python is implemented the reference for this variable shows up in the activation record for showOutput because it is being referenced from this scope. But, the reference to historyOfOutput in the activation record for showOutput and the reference called historyOfOutput in the main activation record point at the same object so no real harm is done. The important thing to note is that the Wing IDE is correct in showing the historyOfOutput variable as a local variable in this activation record since this is a reflection of Python's implementation and not due to a bug in Wing IDE 101.

Fig. 3.4 The Wing IDE Showing the Run-time Stack

Found a mistake? Please highlight the word and press Shift + Enter  
< Prev   CONTENTS   Next >
Business & Finance
Computer Science
Language & Literature
Political science