Activation records and call stack in Compiler Design - Mini Project: Build & Apply

Understanding Activation Records and Call Stack

📖 Scenario: Imagine you are learning how a computer keeps track of function calls when running a program. Each time a function is called, the computer creates a special box to store information about that call. This box is called an activation record. All these boxes are stacked on top of each other in a structure called the call stack.In this project, you will build a simple representation of activation records and the call stack to understand how function calls are managed.

🎯 Goal: You will create a simple model of activation records as dictionaries and manage them in a list to simulate the call stack. This will help you see how information about function calls is stored and removed as functions start and finish.

📋 What You'll Learn

Create an activation record as a dictionary with specific keys and values.

Create a call stack as a list to hold activation records.

Add activation records to the call stack to simulate function calls.

Remove activation records from the call stack to simulate function returns.

💡 Why This Matters

🌍 Real World

Understanding activation records and the call stack helps in debugging programs and understanding how programming languages manage function calls internally.

💼 Career

This knowledge is important for software developers, compiler engineers, and anyone working with low-level programming or debugging complex software.

1

Create the first activation record

Create a dictionary called activation_record_main with these exact entries: 'function_name': 'main', 'return_address': 0, and 'local_variables': {'x': 10, 'y': 20}.

Compiler Design

# Create the activation_record_main dictionary with specified keys and values
# Your code here

Hint

Use curly braces {} to create a dictionary. Include the keys exactly as shown with their values.

2

Create the call stack list

Create a list called call_stack and add the activation_record_main dictionary as its first element.

Compiler Design

activation_record_main = {
    'function_name': 'main',
    'return_address': 0,
    'local_variables': {'x': 10, 'y': 20}
}
# Create the call_stack list and add activation_record_main
# Your code here

Hint

Create a list using square brackets [] and put activation_record_main inside it.

3

Add a new activation record for a function call

Create a dictionary called activation_record_func with these entries: 'function_name': 'compute', 'return_address': 5, and 'local_variables': {'a': 3, 'b': 4}. Then add activation_record_func to the end of the call_stack list.

Compiler Design

activation_record_main = {
    'function_name': 'main',
    'return_address': 0,
    'local_variables': {'x': 10, 'y': 20}
}

call_stack = [activation_record_main]
# Create activation_record_func dictionary and add it to call_stack
# Your code here

Hint

Create the dictionary like in step 1, then use the append() method to add it to the list.

4

Simulate function return by removing the top activation record

Remove the last activation record from the call_stack list to simulate returning from the compute function.

Compiler Design

activation_record_main = {
    'function_name': 'main',
    'return_address': 0,
    'local_variables': {'x': 10, 'y': 20}
}

call_stack = [activation_record_main]

activation_record_func = {
    'function_name': 'compute',
    'return_address': 5,
    'local_variables': {'a': 3, 'b': 4}
}

call_stack.append(activation_record_func)
# Remove the last activation record from call_stack
# Your code here

Hint

Use the pop() method on the list to remove the last item.

Practice

1. What is the main purpose of an activation record in a program's execution?

easy

A. To store information about a function call such as parameters and local variables

B. To manage the computer's memory allocation for the entire program

C. To compile the source code into machine code

D. To display output on the screen

Solution

1. Step 1: Understand what an activation record stores

   An activation record holds details about a specific function call, including parameters, local variables, and return address.

2. Step 2: Identify the main purpose

   This helps the program keep track of function calls and return correctly after execution.

3. Final Answer:

   To store information about a function call such as parameters and local variables -> Option A

4. Quick Check:

   Activation record = function call info [OK]

Hint: Activation record = function call details stored [OK]

Common Mistakes:

• Confusing activation record with overall memory management
• Thinking activation record compiles code
• Assuming activation record handles output display

2. Which of the following correctly describes the call stack's behavior during function calls?

easy

A. It executes functions in parallel without stacking

B. It removes the activation record before the function starts

C. It stores all activation records in a queue structure

D. It adds a new activation record on top when a function is called

Solution

1. Step 1: Recall how the call stack works

   The call stack adds (pushes) a new activation record on top each time a function is called.

2. Step 2: Confirm the correct description

   This stacking ensures the program knows which function is currently running and where to return after completion.

3. Final Answer:

   It adds a new activation record on top when a function is called -> Option D

4. Quick Check:

   Call stack pushes activation records [OK]

Hint: Call stack pushes new records on function call [OK]

Common Mistakes:

• Thinking activation records are removed before function starts
• Confusing stack with queue behavior
• Assuming functions run in parallel without stacking

3. Consider this sequence of function calls: main() calls funcA(), which calls funcB(). What is the order of activation records on the call stack just before funcB() finishes?

medium

A. funcB at bottom, funcA in middle, main on top

B. funcA at bottom, main in middle, funcB on top

C. main at bottom, funcA in middle, funcB on top

D. funcB at bottom, main in middle, funcA on top

Solution

1. Step 1: Understand call stack order

   The call stack adds activation records in order of calls: main first, then funcA, then funcB on top.

2. Step 2: Determine stack order before funcB finishes

   Since funcB is currently running, its record is on top, with funcA below it, and main at the bottom.

3. Final Answer:

   main at bottom, funcA in middle, funcB on top -> Option C

4. Quick Check:

   Call stack order = main, funcA, funcB [OK]

Hint: Last called function's record is on top [OK]

Common Mistakes:

• Reversing the order of activation records
• Confusing bottom and top of the stack
• Assuming parallel execution changes stack order

4. A programmer notices that after a function returns, the call stack still contains its activation record. What is the most likely cause?

medium

A. The function was never called

B. The activation record was not properly removed (popped) from the stack

C. The call stack is implemented as a queue

D. The program has no functions

Solution

1. Step 1: Understand normal call stack behavior on return

   When a function finishes, its activation record should be removed (popped) from the call stack.

2. Step 2: Identify cause of leftover activation record

   If the record remains, it means the stack pop operation did not happen correctly.

3. Final Answer:

   The activation record was not properly removed (popped) from the stack -> Option B

4. Quick Check:

   Activation record must be popped after return [OK]

Hint: Function return must pop activation record [OK]

Common Mistakes:

• Assuming function was never called
• Confusing stack with queue behavior
• Ignoring that program has functions

5. In a recursive function that calls itself 4 times before returning, how many activation records will be on the call stack at the deepest point of recursion?

hard

A. 5

B. 2

C. 1

D. 4

Solution

1. Step 1: Understand recursion and activation records

   Each recursive call adds a new activation record to the call stack.

2. Step 2: Count total activation records

   If the function calls itself 4 times, there are 4 new calls plus the original call, totaling 5 activation records on the stack.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   Recursive calls + original = 5 activation records [OK]

Hint: Count original call plus recursive calls [OK]

Common Mistakes:

• Counting only recursive calls, ignoring original
• Assuming recursion does not add activation records
• Confusing number of calls with return points