06 Procedures

Named block of code. When the name is called, the body is executed.

Types of Procedures¶

Procedure Definition¶

• Procedure Name
• Code body
• Formal Parameters
• Return type

function square(x:integer):integer
begin
    square := x*x
end

int square(int x)
{
  return x*x;
}

Note¶

C does not allows procedure bodies to be nested, so uses control links only. So calling a procedure means that procedure will be

• Within same procedure (or)
• Outside all procedures

Procedure Calls¶

procedure_name(parameters)

Procedure Activation¶

Execution of procedure body

Layout of activation is known at run-time

Frame is put on the stack and storage within is accessed relative to the frame pointer.

The values of variables in an activation are accessed as

• Frame Pointer + Displacement (or offset)
• Displacement is calculated at run-time

Benefits of Procedures¶

• Procedure Abstraction
• Hides implementation details
• Program Legibility
• Better maintainence
• Better modularity
• Code re-usability (user-defined and from libraries)

Parameter Passing Methods¶

Scope¶

Scope of Variable¶

Part of program where use of variable refers to its declaration

Visibility rules for names in a PL; names could denote procedures, types, constants, variables

Macros¶

• Procedure body is substituted at every point of call
• Actual parameters are substituted for the formals Different from call by value/reference

Dynamic scoping

#define pi 3.14

Every occurance of pi is replace with \(3.14\) by the compiler.

#define product(x, y) x*y

Every call of product(x, y) is replaced with x*y

Runtime Memory Model¶

Layout of executable file

Procedure Activations¶

I didn't understand this

Activation Record¶

Activation records on stack are called as stack frame

Sections¶

Special Registers¶

Variables¶

Storage is allocated at compile time

Languages without recursive procedure treat all variables as static.

Example for Static variable declaration in C

static int count = 0;
int count = 0; // variables declared outside main() are static by default

Activation Tree¶

Tree representing procedure activations of program

For eg: Trees for merge sort, quicksort in DSA

Garbage Collection¶

Technique to reclaim storage that is no longer needed

Recursion¶

Also called as multiple activation

Recursive procedure is one that can be activated by its own body.

// Traditional
factorial(n) {
    if (n == 0)
    return 1;

  return n * factorial(n - 1);
}

// Tailed
factorial1(n, accumulator)
{
  if (n == 0)
    return accumulator;

  return factorial1(n - 1, n * accumulator);
}

factorial(n)
{
  return factorial1(n, 1);
}

Converting a tailed-recursion logic into an equivalent control-flow logic is called as Tail-recursion elimination. This can be done using goto

Comments